chess_engine_using_python

Mesin Catur Menggunakan Python

Repositori ini berisi implementasi mesin catur menggunakan Minimax , pemangkasan Alpha-Beta dan algoritma pencarian Quiescence . Notebook Jupyter di dalam Docker Container digunakan untuk pengkodean. Semua Notebook Jupyter juga tersedia dalam bentuk docker image.

Lihat makalah proyek untuk melihat analisis terperinci.

Modul Eksternal Digunakan

• Catur Python

Cara menjalankannya menggunakan buruh pelabuhan

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

Algoritma Mesin Catur

Minimal

Teori

Inti dari Catur bermain Catur di minmax. Minmax biasanya mengasosiasikan bidak Hitam dengan MAX, dan bidak putih dengan MIN, dan selalu mengevaluasi dari sudut pandang putih.

Algoritma Minmax merupakan algoritma Adversarial Search dalam teori Game. Ini menggunakan pohon permainan dan mencakup dua pemain MIN dan MAX. Kedua pemain mencoba membatalkan tindakan pemain lain. Max mencoba memaksimalkan hasil sedangkan MIN mencoba meminimalkan hasil. Kedua pemain bermain bergantian dengan asumsi keduanya bermain maksimal. Permainan optimal berarti kedua pemain bermain sesuai aturan, yaitu MIN meminimalkan hasil dan MAX memaksimalkan hasil.

Algoritma minmax menggunakan pendekatan Depth First Search untuk mencari hasilnya. Selain itu, ini juga menggunakan penelusuran mundur dan rekursi. Algoritma akan melintasi hingga simpul terminal dan kemudian akan mundur sambil membandingkan semua nilai anak. Ini akan memilih nilai minimum atau maksimum, berdasarkan giliran siapa. Ini kemudian akan menyebarkan nilainya kembali ke induknya. Ia menggunakan fungsi evaluasi statis untuk menentukan nilai di setiap node daun. Ini memanfaatkan Zero-Sum Game.

Pelaksanaan

Mesin Catur menggunakan Minmax

Kompleksitas Waktu

Minmax menggunakan Depth First Search (DFS) pada Game Tree, maka kompleksitas waktu dari algoritma minmax adalah O(b**m) , dimana b adalah faktor percabangan dari game-tree, dan m adalah kedalaman maksimum dari pohon tersebut.

Kompleksitas Ruang

Kompleksitas ruang pada algoritma minmax juga mirip dengan DFS yaitu O(bm) , dimana b adalah faktor percabangan pohon permainan, dan m adalah kedalaman maksimum pohon.

Kelengkapan

Algoritma Minmax Selesai. Ia pasti akan menemukan solusi, jika ada, di pohon pencarian terbatas.

Optimalitas

Algoritma minmax optimal jika kedua lawan bermain maksimal.

---

Pemangkasan Alfa-Beta

Teori

Algoritma minmax dapat dioptimalkan dengan memangkas beberapa cabang. Cabang yang dipangkas adalah cabang yang tidak mempengaruhi hasil. Ini akan meningkatkan kompleksitas waktu. Versi minmax ini dikenal sebagai minmax dengan pemangkasan alfa-beta. Ini juga disebut sebagai algoritma alfa-beta.
Pada Alpha-Beta Pruning terdapat dua nilai yaitu Alpha dan Beta. Berikut adalah beberapa hal yang perlu dipertimbangkan tentang alfa dan beta:

Beberapa poin tentang Alfa(α)

• Alpha adalah nilai tertinggi yang ditemukan di sepanjang jalur MAX.
• Nilai awal alpha adalah negatif tak terhingga karena nilai alpha akan terus bertambah atau tetap sama setiap kali bergerak. Jika kita memilih nilai selain tak terhingga negatif, maka skenario mungkin terjadi di mana semua nilai alfa mungkin lebih kecil dari nilai yang dipilih. Jadi, kita harus memilih nilai serendah mungkin, yaitu negatif tak terhingga.
• Alpha hanya diperbarui oleh pemain MAX.

Beberapa poin tentang Beta(β)

• Beta adalah nilai terendah yang ditemukan di sepanjang jalur MIN.
• Nilai awal beta adalah positif tak terhingga karena nilai beta akan terus berkurang atau tetap sama setiap kali bergerak. Jika kita memilih nilai selain tak terhingga positif, maka skenario mungkin terjadi di mana semua nilai beta mungkin lebih besar dari nilai yang dipilih. Jadi, kita harus memilih nilai maksimum yang mungkin, yaitu nilai tak terhingga positif.
• Nilai beta hanya diperbarui oleh MIN pemain.

Saat melakukan backtracking, hanya nilai simpul yang diteruskan ke induk, bukan nilai alfa dan beta.

Syarat pemangkasan alfa-beta:

 α >= β

Pindahkan Pemesanan

Efektivitas algoritma alfa-beta sangat bergantung pada urutan traversal. Ini memainkan peran penting dalam Kompleksitas Ruang dan Waktu.

Pemesanan Terburuk

Dalam beberapa kasus, tidak ada node atau subpohon yang dipangkas dari Game Tree. Dalam hal ini, langkah terbaik terjadi di subpohon kanan Game Tree. Hal ini akan mengakibatkan peningkatan Kompleksitas Waktu.

Pemesanan Ideal

Dalam hal ini, jumlah maksimum node dan subpohon dipangkas. Pergerakan terbaik terjadi di subpohon kiri. Ini akan mengurangi Kompleksitas Ruang dan Waktu.

Pelaksanaan

Mesin Catur menggunakan Pemangkasan Alfa-Beta

Kompleksitas Waktu

Algoritma Alpha Beta, juga menggunakan Depth First Search (DFS) pada Game Tree.

• Dalam kasus Urutan Terburuk: O(b^m)
• Dalam hal Pengurutan Ideal: O(b^m/2)

Kompleksitas Ruang

• Dalam hal Pemesanan Terburuk: O(bm)
• Dalam hal Pengurutan Ideal: O(b(m/2))

Kelengkapan

Algoritma Alpha-Beta Selesai. Ia pasti akan menemukan solusi, jika ada, di pohon pencarian terbatas.

Optimalitas

Algoritma Alpha-Beta optimal jika kedua lawan bermain maksimal.

---

Pencarian Keheningan

Pencarian Tenang adalah modifikasi selain pemangkasan alfa-beta dengan min-maks. Quietness artinya tenang. Pencarian ini hanya mengevaluasi gerakan diam saja. Dengan kata lain, setelah kedalaman tertentu, ia hanya menggunakan gerakan penangkapan untuk menghitung gerakan selanjutnya. Pencarian diam dapat menghindari efek cakrawala.
Efek cakrawala terjadi ketika kita hanya mencari pada kedalaman tertentu, namun bisa saja terjadi jika kita melihat satu tingkat lebih dalam, maka pergerakannya mungkin mendapat poin lebih sedikit. Pencarian diam hanya menggunakan gerakan menangkap untuk mencegah hal ini. Pencarian diam juga mengurangi faktor percabangan pada tingkat yang berbeda, sehingga menghasilkan algoritma yang cepat.

Kompleksitas Waktu

Algoritma Quiescence Search, juga menggunakan Depth First Search (DFS) pada Game Tree.

• Dalam kasus Urutan Terburuk: O(b^m)
• Dalam hal Pengurutan Ideal: O(b^m/2)

Kompleksitas Ruang

• Dalam hal Pemesanan Terburuk: O(bm)
• Dalam hal Pengurutan Ideal: O(b(m/2))

Kelengkapan

Algoritma Pencarian Diam Selesai. Ia pasti akan menemukan solusi, jika ada, di pohon pencarian terbatas.

Optimalitas

Algoritma Quiescence Search optimal jika kedua lawan bermain maksimal.

---

Pengambilan Kunci

• Node yang dieksplorasi per gerakan berkurang 10 kali lipat di Alpha Beta dibandingkan dengan Minmax.
• Waktu yang dibutuhkan untuk menemukan langkah terbaik juga berkurang 10 kali lipat di Alpha Beta dibandingkan dengan Minmax.
• Pencarian diam bekerja dengan baik pada kedalaman yang lebih tinggi.
• Pencarian diam adalah algoritma tercepat dari ketiganya.
• Pencarian diam mengevaluasi lebih sedikit node.
• Pencarian diam dapat mengakibatkan gerakan berulang-ulang, jika tidak ditangani dengan benar.