Ini adalah cerita tentang bagaimana saya mencoba untuk memenangkan permainan catur dengan saudara saya. Hanya satu permainan sialan. Apa yang istimewa darinya? Apakah saya pandai catur? Tidak semuanya. Apakah saya belajar sesuatu saat bermain? Juga tidak. Mungkin ini cerita tentang sebuah perjalanan demi sebuah perjalanan, bukan sebuah tujuan? Tidak juga. Apakah saya bahkan menikmatinya? Tidak yakin.
Ini adalah cerita tentang upaya saya untuk menjadi orisinal di salah satu game yang paling banyak dipelajari di dunia, menggunakan pengalaman pengembangan perangkat lunak yang mungkin tidak diperlukan.
Terlepas dari kebodohan mutlak saya dalam catur dan ketidakbergunaan artikel ini bagi mereka yang ingin meningkatkan permainan mereka, saya masih berpikir bahwa berbagi cara orisinal untuk menerapkan prinsip-prinsip rekayasa pada suatu masalah masih layak dilakukan. Apakah saya sukses? Anda akan belajar tentang ini di akhir.
Mengapa saya bahkan terlibat dengan catur
Selama pandemi 2020, saudara saya, seperti banyak orang lain, menjadi kecanduan catur online. Setelah bermain selama beberapa bulan, ia mulai berbicara dengan penuh inspirasi tentang permainan ini dan menantang anggota keluarga lainnya. Ayah kami menjawab panggilan itu (walaupun dia mengalami kegagalan digital), tetapi saya tidak menyerah. Salah satu faktor pembatasnya adalah keengganan saya untuk mendalami hobi yang berpotensi menghabiskan banyak waktu. Saya cukup tahu tentang game ini untuk menyadari bahwa menjadi pemain menengah sekalipun membutuhkan waktu ratusan bahkan ribuan jam untuk memainkannya. Meski saya akui sekaligus saya juga tidak terinspirasi dengan ide kalah dari kakak saya yang saat itu sudah memainkan lebih dari seratus pertandingan. saya bukan satu.
Namun suatu hari saya menyerah pada tantangannya. Tak perlu dikatakan, kehilangan itu menghancurkan. Saya tahu aturan dan dasar-dasar permainan, sejak saya bermain sedikit sebagai seorang anak, tetapi ini sama sekali tidak dapat dibandingkan dengan keterampilan saudara saya. Kemudian, melihat analisis permainan di chess.com , saya melihat bahwa lag taktis saya hanya bertambah, bergerak demi langkah, hingga mencapai tanda +9 (yang sama dengan kehilangan benteng, uskup dan pion melawan ketidakhadiran kerugian musuh). Pada saat itu, setelah kehilangan semua harapan, saya menyerah. Situasi serupa terulang untuk beberapa pertandingan lagi, ketika saya menyadari bahwa sesuatu perlu dilakukan tentang hal ini.
Keputusan pertama saya adalah untuk mempelajari lebih dalam permainan.
Percobaan pertama: belajar
Upaya pertama saya untuk meningkatkan kualitas permainan sudah jelas: buka Reddit dan YouTube untuk mendapatkan rekomendasi dari siswa lain. Di sela-sela pelajaran dari GM Naroditsky , membaca dan memecahkan masalah di Lichess, saya juga memainkan beberapa game dengan lawan acak di Internet. Terlepas dari semua ini, peringkat saya tetap rendah (1300 - 1400 Cepat di Lichess).
Setelah beberapa pertandingan lagi melawan saudara laki-laki saya, saya sadar bahwa saya tidak memiliki peluang untuk menang. Saya terus mengikuti semua metode pengembangan yang sama (bermain, mempelajari teknik, dan menonton video), tetapi mencurahkan lebih sedikit waktu untuk ini daripada saudara saya. Saat itu, dia sudah bermain ratusan game sebulan, sementara saya tidak lebih dari 10. Pada tingkat ini, kesenjangan saya semakin besar.
Saat itulah saya menyadari nuansa yang sangat penting: saya tidak terlalu tertarik dengan permainan itu sendiri, dan, pada kenyataannya, saya tidak ingin meningkatkannya. Tujuan utama saya hanya untuk mengalahkan satu orang - saudara saya.
Percobaan kedua: mempelajari musuh
Sebuah permainan catur umumnya dibagi menjadi tiga fase: pembukaan , permainan tengah dan permainan akhir . Setelah mempelajari beberapa pola dasar kawin, biasanya "mudah" untuk beralih dari keuntungan besar ke kemenangan di tahap akhir permainan, jadi mendapatkan keuntungan itu adalah pertanyaan pertama bagi saya.
Pada tahap middlegame, keuntungan biasanya dicapai dengan menerapkan strategi jangka panjang dan menerapkan taktik . Strategi dapat ditingkatkan dengan membaca dan mempelajari prinsip-prinsip permainan (saya suka itu), dan taktik dikembangkan hanya melalui pemecahan masalah(yang saya sangat benci). Oleh karena itu, saya mengerti bahwa dalam keterampilan taktis saya pasti akan tertinggal, mengingat saudara saya memecahkan sekitar 20 masalah seperti itu di chess.com setiap hari. Bagi saya, ini adalah batas yang tidak dapat dicapai. Dengan demikian, hanya ada satu kesempatan tersisa: untuk mendapatkan keuntungan pada tahap pembukaan.
Teori di balik fase pembukaan sangat besar. Pada saat yang sama, itu membutuhkan menghafal urutan panjang dan variasi gerakan, serta kemungkinan jawaban dari lawan. Pemula tidak perlu banyak menghafal, tetapi beberapa keakraban dengan bukaan yang paling umum bisa sangat bermanfaat (atau begitulah yang saya katakan).
Kemudian saya memutuskan untuk melihat beberapa permainan acak saudara saya dan mencoba memahami celah yang dia gunakan. Saya juga belajar tentang debut Lichess "Partai Italia" dan Pertahanan Sisilia , mencoba mengingat prinsip dasar mereka. Selain itu, saya menonton banyak video YouTube.
Jelas, saudara saya telah melakukan semua ini sebelum saya (dan lebih baik), jadi tentu saja saya kalah lagi. Belum lagi fakta bahwa menghafal gerakan pembukaan yang tidak berarti (setidaknya bagi saya) hanya membosankan dan melelahkan. Semua ini tidak memberi saya kesenangan dengan cara apa pun. Masalah lain adalah ketika lawan saya mulai menyimpang dari gerakan yang ditentukan dalam buku, saya sama sekali tidak tahu bagaimana harus bereaksi, karena saya tidak mengerti posisi yang muncul.
Sudah waktunya untuk mundur dan berpikir lagi. Kemudian saya menyadari bahwa saya sebenarnya berusaha untuk tidak mengalahkan saudara saya, tetapi untuk meningkatkan permainan saya melawan lawan yang memainkan pembukaan yang sama dengan sempurna. Bisakah saya bertindak lebih terarah? Mungkinkah justru telah mempersiapkan diri secara khusus terhadap kelemahan saudaranya? Jelas, pendekatan ini hanya akan berhasil melawannya, tetapi itu cukup konsisten dengan tujuan saya.
Percobaan ketiga: pemrograman
Sekarang tugas saya telah mengambil bentuk yang berbeda: untuk menemukan posisi di pintu keluar dari pembukaan, yang kemungkinan besar akan dicapai oleh saudara saya (selanjutnya PlayerX), sementara berada pada posisi yang kurang menguntungkan. Harap dicatat bahwa tidak ada dari kami yang ahli dalam permainan, dan bahwa pemain level kami tidak bermain dengan sangat hati-hati.
Satu-satunya cara untuk melawan pemain yang baik adalah dengan mengikuti gerakan di buku dengan tepat, karena dengan begitu Anda setidaknya tahu bahwa lawan Anda tidak akan melakukan gerakan apa pun, mendapatkan keuntungan. Namun, situasinya berubah ketika Anda bermain melawan pemain level klub. Anda dapat mengambil risiko (yaitu, untuk sementara menemukan diri Anda dalam posisi yang kurang menguntungkan) jika Anda tahu bahwa musuh tidak mungkin dapat bereaksi dengan benar terhadap hal ini, dan karena itu akan menemukan diri Anda dalam posisi yang sulit.
Saya juga memiliki daftar lebih dari 500 game yang dimainkan saudara saya di chess.com. Dan karena saya seorang programmer, itu menjadi pendekatan alami bagi saya untuk memecahkan masalah ini dengan cara rekayasa.
Saya mulai mengunduh game yang dia mainkan menggunakan API chess.com dan membaginya menjadi game putih dan hitam. Kemudian saya fokus pada permainan di mana saudara laki-laki saya bermain untuk kulit hitam, karena saya merasa bahwa saya memiliki peluang yang lebih baik untuk mengarahkan permainan ke arah yang saya inginkan ketika bermain untuk kulit putih.
import json
import requests
def get_month_games(player, yyyy_mm):
url = 'https://api.chess.com/pub/player/{}/games/{}'
r = requests.get(url.format(player, yyyy_mm))
if not r.ok:
raise Exception('get_month_games failed')
games = json.loads(r.content)
# Format: {games: [{url, pgn}, ...]}
return games['games']
# ...
import chess.pgn
import io
import json
with open('games.json') as f:
data = json.load(f)
games = []
for game in data:
pgn = io.StringIO(game)
games.append(chess.pgn.read_game(pgn))
black_games = [g for g in games if g.headers["Black"] == "playerx"]
Kemudian saya merumuskan tugas sebagai berikut: βMengingat semua posisi yang telah dilihat PlayerX, mana di antara mereka yang kemungkinan besar paling tidak menguntungkan baginya di akhir pembukaan?
Kali ini, tugas didefinisikan dengan jelas, dan pekerjaan dimulai di bidang yang saya kenal. Saya memutuskan untuk melakukan analisis dengan Python, yaitu di notebook Jupyter , karena saya tidak memiliki tujuan untuk membuat alat yang dapat digunakan kembali, dan saya hanya perlu mempelajari data yang tersedia untuk menemukan satu solusi.
Ternyata Python sudah memiliki perpustakaan yang sangat baik untuk bekerja dengan catur: python-chess (pembuatan gerakan, evaluasi dan visualisasi) dan python stockfish(pengikatan untuk mengevaluasi posisi catur menggunakan mesin catur Stockfish yang terkenal).
Saya mengonversi masalah menjadi grafik dengan cara ini: simpul adalah posisi catur tertentu (dijelaskan dalam notasi FEN ). Sebuah edge menghubungkan dua node, sedangkan posisi target dapat dicapai dari node awal dengan gerakan yang dapat diterima. Semua permainan memiliki satu dan simpul awal yang sama: posisi awal.
Kemudian saya membuat grafik dari semua game yang dimainkan oleh PlayerX sebagai Hitam, selain itu menandai setiap tepi dengan berapa kali gerakan yang sesuai dilakukan.
class GamesGraph():
def __init__(self):
self.graph = igraph.Graph(directed=True)
def add_move(self, start_fen, end_fen, uci):
vs = self._ensure_vertex(start_fen)
vt = self._ensure_vertex(end_fen)
try:
e = self.graph.es.find(_source=vs.index, _target=vt.index)
e["count"] += 1
except:
e = self.graph.add_edge(vs, vt)
e["uci"] = uci
e["count"] = 1
@property
def start_node(self):
return self.graph.vs.find(chess.STARTING_FEN)
def _ensure_vertex(self, fen):
try:
return self.graph.vs.find(fen)
except:
v = self.graph.add_vertex(name=fen)
v["fen"] = fen
v["turn"] = chess.Board(fen).turn
return v
Akibatnya, kami mendapatkan grafik berarah berbobot (bukan pohon, karena posisi dapat diperoleh dengan urutan gerakan yang berbeda) seperti ini (sintetis, karena yang asli tidak cocok di sini):
Di sini posisi awal ditunjukkan dengan simpul persegi, warna menunjukkan apakah itu putih atau hitam untuk bergerak di posisi ini.
Saya juga ingin mendapatkan penilaian dari setiap posisi dalam hal keuntungan putih, yang saya gunakan untuk Stockfish. Mengingat bahwa proses mengevaluasi ribuan posisi membutuhkan waktu, saya memutuskan untuk menjalankannya secara terpisah dan membuat objek JSON yang memetakan setiap posisi FEN unik ke estimasi Stockfish-nya.
from stockfish import Stockfish
stock = Stockfish(parameters={"Threads": 8})
stock.set_depth(20)
stock.set_skill_level(20)
def eval_pos(fen):
stock.set_fen_position(fen)
return stock.get_evaluation()
# fens - FEN .
for fen, node in graph.fens.items():
node.eva = eval_pos(fen)
Evaluasi keuntungan dikembalikan dalam centipoint atau sebagai βskakmat dalam gerakan Xβ, di mana angka positif berarti keuntungan untuk putih, dan keuntungan negatif untuk hitam:
{"type":"cp", "value":12} # 12 .
{"type":"mate", "value":-3} # .
100 centipoints berarti keunggulan lawan satu pion, dan 300 berarti satu bidak kecil seperti uskup. Namun, perlu dicatat bahwa Stockfish memberikan nilai pada bidaknya tergantung pada posisinya, yang berarti sangat mungkin untuk mendapatkan keuntungan 1000 centipoint bahkan dengan jumlah bidak yang sama di papan.
Saya perlu memetakan skor ini menjadi sesuatu yang lebih nyaman untuk diproses, misalnya, angka antara 0 dan 1. Untuk ini, saya memutuskan begitu saja bahwa keunggulan 300+ akan ditampilkan di 1.0, dan lag 300+ di 0. Selain itu, setiap pasangan dalam X bergerak (bahkan jika X adalah 20) akan menjadi 1 atau 0.
# [-1;1]
def rating(ev, fen):
val = ev["value"]
if ev["type"] == "cp":
# -300, +300. .
val = max(-300, min(300, val))
return val / 300.0
# X : max .
if val > 0: return 1.0
if val < 0: return -1.0
# , ?
b = chess.Board(fen)
return 1.0 if b.turn == chess.WHITE else -1.0
# [0;1], 0 - min, 1 - max .
def rating_black(ev, fen):
return -rating(ev, fen) * 0.5 + 0.5
Sekarang semua informasi tidak pada tempatnya, dan saya harus menemukan simpul grafik (yaitu posisi), di mana Hitam berada dalam posisi kalah, serta urutan gerakan yang paling cocok untuk mencapainya. Itu perlu untuk menimbang tulang rusuk sedemikian rupa sehingga menjadi mungkin untuk dengan mudah menghitung kemungkinan mencapai posisi tertentu. Saya beralasan seperti ini:
- Di setiap posisi, Anda dapat memperkirakan probabilitas melakukan gerakan tertentu dengan membagi jumlah operan di sepanjang tepi yang sesuai dengan jumlah total gerakan yang dilakukan dari posisi itu.
- Setiap tepi sekarang akan memiliki bobot antara 0 dan 1, di mana nilai yang lebih tinggi mencerminkan kemungkinan yang lebih tinggi untuk melintasinya dari posisi itu.
- Maka probabilitas melewati jalur tertentu akan menjadi produk dari probabilitas semua sisi yang dilalui.
Untuk menyelesaikan masalah dengan menggunakan algoritma graf standar, perlu dilakukan transformasi bobot tepi sehingga:
- Mereka mewakili jarak, bukan probabilitas (yaitu, semakin besar jarak, semakin rendah kemungkinan memilih jalur).
- Jarak antara dua simpul adalah jumlah bobot sisi yang dilalui (berlawanan dengan produk probabilitas).
Sebenarnya, ini jauh lebih mudah dilakukan daripada menjelaskan. Rumusnya sangat sederhana:
distance(e) = -log(prob(e))
Dalam Python, itu akan terlihat seperti ini:
def compute_edges_weight(vertex):
all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
for edge in vertex.out_edges():
prob = edge["count"] / all_count
edge["prob"] = prob
edge["weight"] = -math.log(prob)
Mengambil logaritma dari probabilitas memilih tepi akan memberikan angka negatif, karena probabilitasnya adalah antara 0 dan 1. Tidak perlu khawatir tentang kasus ketika probabilitasnya nol (sebagai akibatnya logaritma akan memberikan minus tak terhingga), karena setiap tepi grafik telah dilalui setidaknya sekali ... Semakin rendah probabilitasnya, semakin negatif logaritmanya, yang berarti membalikkan tandanya akan memberikan apa yang kita butuhkan, karena:
- Jumlah logaritma adalah logaritma dari produk argumen mereka
log(a) + log(b) = log(a*b)
. - Semakin besar hasilnya, semakin rendah kemungkinan yang menentukannya.
Berbekal ide ini, Anda dapat menghitung jalur terpendek antara node awal dan semua node lainnya menggunakan algoritma Dijkstra . Hasilnya adalah pemetaan antara setiap node dan jalur terpendek ke posisi awal, yang mewakili urutan gerakan yang paling mungkin mengarah ke sana.
Pada titik ini, saya secara sewenang-wenang memilih nilai minimum keuntungan dan mengurutkan jalur berdasarkan probabilitas. Beberapa jalur pertama mewakili peluang terbesar bagi saya untuk keluar dari debut dengan keunggulan dibandingkan PlayerX.
Perbaikan
Apa yang saya temukan? Di antara posisi yang diberikan oleh algoritma ini adalah sebagai berikut (Langkah White):
Seperti yang Anda lihat, Black berada dalam posisi yang sangat canggung (+8.9 menurut Stockfish) karena g6, langkah terakhir Black, adalah sebuah kesalahan. White melanjutkan, mengambil pion dari e5 dan benteng. Pada titik ini, permainan untuk Hitam hampir berakhir, karena dia harus menyelamatkan ksatria, pion di h7, dan uskup. Hasil lain dari algoritme adalah ini (Langkah White):
Di sini kita melihat skakmat dalam satu gerakan ( skakmat anak-anak ).
Masalahnya adalah PlayerX melakukan kesalahan ini hanya beberapa kali di game pertamanya dan tidak mengulanginya lagi. Serangan ratu awal biasanya hanya dilakukan oleh pemain yang tidak berpengalaman dan hanya efektif terhadap pemain dengan level yang sama. Setelah meninggalkan kategori pemula, PlayerX tidak melakukan kesalahan ini untuk waktu yang lama, karena lawan yang lebih kompeten tidak melakukannya. Saya tahu bahwa pembukaan seperti itu tidak akan berhasil, karena PlayerX tahu cara bertahan melawannya.
Masalah lain terkait dengan urutan gerakan, yang hanya terjadi sekali, tetapi dari posisi yang khas. Probabilitas posisi akhir mereka ternyata sama dengan probabilitas posisi tipikal terakhir, karena setiap tepi memiliki probabilitas 1,0 (mengingat tidak ada kemungkinan lain yang dimainkan). Pada contoh di bawah, Anda dapat mengikuti tepi 7 dan 6 (posisi paling umum pada langkah kedua), dan kemudian salah satu tepi dengan 1s. Selanjutnya, semua gerakan berikutnya hanya akan dimainkan sekali (karena posisi ini hanya terbentuk dalam satu pertandingan), akibatnya setiap gerakan akan memiliki probabilitas 1,0.
Dan inilah probabilitasnya:
Skema seperti itu tidak dapat dipercaya, karena tidak mungkin urutan gerakan yang sama dimainkan dengan jelas. Untuk kesimpulan seperti itu, kami tidak memiliki cukup permainan di mana permainan akan berlangsung dari posisi ini.
Kutipan terkenal ( B. Brewster ?): "Dalam teori tidak ada perbedaan antara teori dan praktik, tetapi dalam praktiknya ada" ternyata benar dalam kasus ini, jadi saya membutuhkan beberapa penyempurnaan dan penelitian independen untuk menemukan hipotesis yang lebih sukses posisi.
Saya memperbaiki masalah kedua dengan menetapkan batas atas pada probabilitas tepi sehingga urutan gerakan panjang yang dimainkan hanya sekali secara bertahap akan kehilangan probabilitasnya.
def compute_edges_weight(vertex, prob_ceiling=0.9):
all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
for edge in vertex.out_edges():
# ... (default 90%).
prob = min(edge["count"] / all_count, prob_ceiling)
edge["prob"] = prob
edge["weight"] = -math.log(prob)
Untuk masalah pertama, saya hanya menyaring asumsi buruk secara manual. Akibatnya, saya hanya memiliki beberapa posisi yang tersisa untuk dikerjakan.
Alasan untuk modifikasi lainnya adalah karena saya tidak ingin probabilitas pergerakan White mempengaruhi kemungkinan memilih jalur, karena saya bermain untuk White dan dapat memutuskan sendiri jalur mana yang akan diambil. Untuk alasan ini, saya mengatur semua probabilitas gerakan White ke 1,0 (berat nol), menghasilkan grafik seperti ini:
Persiapan
Dalam proses belajar, saya memilih posisi sebagai berikut:
Menurut Lichess, ini adalah Alekhine Defense (serangan dua bidak). Di posisi ini, Hitam hanya memiliki satu langkah yang berhasil (Nb6), setelah itu ia masih tetap dalam posisi yang kurang menguntungkan (+0,6 menurut Stockfish). Namun, dari posisi ini PlayerX sering memainkan Nf4, yang sangat disayangkan baginya (+2.3). Saya mendirikan studio di Lichess dan mulai melihat beberapa variasi (gerakan dan gerakan bagus yang dimainkan oleh PlayerX).
Pada akhirnya, saya mendapatkan pohon kemungkinan, yang saya coba ingat dan pahami. Misalnya, saya perlu mencari tahu apa yang mengancam langkah seperti d5, mengapa Nf4 tidak berhasil, dan menyiapkan jawaban yang optimal untuk semua.
Saya tidak melakukan ini lama, karena saya cepat bosan, dan sebenarnya saya hanya siap sebagian.
Permainan yang menentukan
Semuanya terjadi seolah-olah saya sedang melihat ke masa depan: PlayerX dan saya berada di posisi pertahanan Alekhine. Menemukan dirinya dalam situasi yang tidak nyaman, dia merindukan ksatrianya pada langkah kelima. Ternyata bahkan pemain yang jauh lebih berpengalaman daripada Anda mulai membuat kesalahan satu demi satu ketika mereka menemukan diri mereka dalam kondisi kalah. Sangat mudah untuk bermain dengan jelas ketika Anda menang, tetapi bisakah Anda tetap tenang dalam situasi yang berlawanan? Pada langkah 10, saya sudah memimpin dengan keunggulan +7.1, yang membuatnya sulit untuk kalah, tetapi itu juga akhir dari skema yang saya kerjakan. Lihatlah betapa sempitnya Hitam sekarang, dan bagaimana bidak saya bertujuan untuk menyerang raja:
Sejak saat itu, saya mulai membuat kesalahan di sana-sini, tetapi pada saat yang sama saya berhasil mempertahankan beberapa keunggulan hingga langkah ke 27:
Sayangnya, waktu saya sangat terbatas (kami memainkan game 10 menit yang dipercepat), jadi saya harus berjalan cepat. Pada akhirnya, saya membuat kesalahan fatal pada 32 dan 33 langkah, dan setelah satu lagi saya menerima skakmat dari lawan saya yang tidak terkalahkan: /
Inilah keseluruhan pertandingan (dengan kesalahan kotor dan sebagainya):
Pratinjau batch langsung: lichess.org/2qKKl2MI
kesimpulan
Apa yang telah saya pelajari dari semua ini? Beberapa hal, yang sebagian besar tampak jelas dalam retrospeksi:
- Mempersiapkan lawan tertentu dapat memberi Anda keuntungan pembukaan yang signifikan.
- Pemain pemula sering melewatkan kesempatan untuk memanfaatkan gerakan lawan yang meragukan. Dalam hal ini, mudah untuk mendapatkan keuntungan dengan mengarahkan musuh ke posisi di mana hanya ada satu kudeta.
- . , . .
- , , . .
- , , .
Kode yang saya gunakan ada di repositori. Perhatikan bahwa saya belum memasukkan data di sana, dan kodenya sendiri cukup ceroboh. Meskipun demikian, semoga bermanfaat, terutama bagi yang masih berpikir untuk menguasai ilmu komputer. Lihat - sangat mungkin dengan bantuannya untuk memecahkan masalah dalam kehidupan nyata, jadi itu bukan hanya memindahkan bit bolak-balik.
Itu saja, teman-teman. Saya berharap suatu hari saya akan dapat mengalahkan saudara saya, tetapi untuk saat ini saya akan mencoba untuk mencapai ini ... dengan cara saya sendiri.