Jika diberi kekuatan pemrosesan yang tak terbatas, apakah ada algoritma yang bisa bermain catur dengan sempurna?

Apakah ada algoritma seperti itu di mana, jika diberi kekuatan pemrosesan yang tak terbatas, komputer dapat bermain catur dengan sempurna sehingga tidak akan pernah kalah?

Jika demikian, di mana saya dapat menemukan kode semu untuknya?

Apakah ada algoritma? Iya nih. Menurut Teorema Zermelo , ada tiga kemungkinan untuk permainan dua pemain dengan informasi lengkap deterministik sempurna terbatas seperti catur: apakah pemain pertama memiliki strategi kemenangan, atau pemain kedua memiliki strategi kemenangan, atau salah satu pemain dapat memaksakan hasil seri. Kami belum (belum) tahu untuk catur mana. (Sebaliknya, Dam, telah diselesaikan : salah satu pemain dapat memaksakan hasil seri.)

Secara konseptual, algoritma ini cukup sederhana: membangun pohon permainan yang lengkap , menganalisis node daun (posisi akhir permainan), dan membuat gerakan awal yang menang, mengundurkan diri, atau menawarkan undian.

Masalahnya terletak pada perinciannya: ada sekitar 10 ⁴³ posisi yang mungkin, dan jumlah gerakan yang bahkan lebih besar (sebagian besar posisi dapat dicapai dalam lebih dari satu arah). Anda benar-benar membutuhkan komputer Anda yang sangat kuat untuk mengambil keuntungan dari ini, karena komputer yang dapat memanfaatkan algoritma ini tidak dapat masuk ke dalam alam semesta yang diketahui, atau tidak akan menyelesaikan perhitungan sampai beberapa saat setelah alam semesta berakhir.

Lihat https://en.wikipedia.org/wiki/Endgame_tablebase .

Dengan kekuatan komputer yang tak terbatas, orang dapat membangun meja seperti itu untuk posisi awal dan menyelesaikan catur .

Dalam praktiknya, hanya posisi dengan hingga tujuh "laki-laki" (bidak dan bidak, menghitung raja) telah diselesaikan menggunakan superkomputer saat ini, jadi kami sangat jauh dari menyelesaikan catur. Kompleksitas masalah meningkat secara eksponensial dengan jumlah kepingan.

Jika Anda benar-benar memiliki kekuatan pemrosesan yang tak terbatas , algoritma seperti itu sebenarnya sepele untuk ditulis. Karena catur memiliki sejumlah kemungkinan keadaan yang terbatas , secara teori Anda bisa mengulanginya semua sampai Anda menemukan jalur permainan yang sempurna. Akan sangat tidak efisien, tetapi jika Anda memiliki kekuatan pemrosesan yang tak terbatas , itu tidak masalah.

Untuk langsung menjawab pertanyaan: ya ada algoritma seperti itu. Ini disebut minimax. (Tablase endgame dihasilkan dengan menggunakan algoritme ini (mundur!), Tetapi hanya algoritma minimax sederhana lama yang Anda butuhkan). Algoritma ini dapat memainkan game dua pemain zero sum dengan sempurna. Temukan pseudocode di sini:

https://en.wikipedia.org/wiki/Minimax

perhatikan bahwa varian dari algoritma ini digunakan oleh program catur komputer modern.

Tidak hanya ada algoritma untuk bermain catur sempurna, ada kemungkinan untuk menulis sebuah program pendek yang akan (diberikan sumber daya tak terbatas) memainkan setiap permainan dua pemain dengan durasi terbatas yang terbatas dengan pengetahuan deterministik yang sempurna .

Mesin game bahkan tidak perlu tahu aturan main yang dimainkannya. Yang dibutuhkan hanyalah representasi buram dari "kondisi permainan" dan fungsi yang (a) memberikan status permainan apa pun, memberikan daftar status hukum berikutnya, dan (b) memberikan status permainan, memutuskan apakah itu merupakan kemenangan bagi pemain 1 , kemenangan untuk pemain 2, seri, atau itu bukan status akhir.

Dengan adanya fungsi-fungsi tersebut, algoritma rekursif sederhana "memecahkan" permainan.

Fakta ini telah disinggung dalam jawaban sebelumnya oleh program catur (minimax) dan oleh Akumulasi (yang menyediakan versi program dengan python).

Saya menulis program semacam itu lebih dari 20 tahun yang lalu. Saya mengujinya dengan memainkan noughts-and-crosses (tic-tac-toe jika Anda orang Amerika). Cukup yakin itu memainkan permainan yang sempurna.

Tentu saja ini akan jatuh dengan cepat pada komputer apa pun yang bisa Anda bayangkan untuk game yang serius. Karena bersifat rekursif, ia secara efektif membangun seluruh pohon permainan di tumpukan, sehingga Anda akan mendapatkan "tumpukan tumpah" (permainan kata yang sangat dimaksudkan) sebelum Anda mendekati menganalisis 10 ^ 123 keadaan catur yang dirujuk dalam jawaban lain. Tetapi menyenangkan mengetahui bahwa pada prinsipnya program kecil ini akan melakukan pekerjaan.

Bagi saya ini juga mengatakan sesuatu yang menarik tentang AI: betapapun banyak "kecerdasan" yang Anda pikir diperlihatkan oleh Deep Blue, atau Go Zero, atau memang oleh manusia yang bermain Catur atau Pergi, ada perasaan di mana game-game ini sepele, tepatnya dapat dihitung optimal solusi. Tantangannya adalah bagaimana mendapatkan solusi yang baik meskipun tidak optimal dalam waktu yang wajar.

Saya akan mengabaikan kemungkinan pengundian atau urutan gerakan tanpa batas untuk kesederhanaan. Setelah algoritma dipahami, tidak terlalu sulit untuk memperluasnya ke kasus-kasus tersebut.

Pertama, beberapa definisi:

1. Setiap langkah yang memenangkan permainan untuk pemain yang melakukan langkah itu adalah langkah yang menang.

2. Setiap langkah yang kehilangan permainan bagi pemain yang melakukan langkah itu adalah langkah yang kalah.

3. Setiap gerakan yang meninggalkan pemain lain dengan setidaknya satu gerakan yang menang juga merupakan langkah yang kalah. (Karena lawan dapat mengambil langkah itu dan memaksakan kerugian.)

4. Setiap langkah yang membuat pemain lain hanya kehilangan langkah juga merupakan langkah yang menang. (Tidak peduli apa pun gerakan lawanmu, kamu akan menang.)

5. Strategi yang sempurna berarti selalu membuat langkah-langkah kemenangan jika ada yang tersisa dan mengundurkan diri ketika seseorang hanya kehilangan langkah yang tersisa.

Sekarang, sepele untuk menulis strategi yang sempurna. Cukup meledak semua urutan langkah yang mungkin dan identifikasi gerakan menang / kalah. Mengabaikan kebuntuan, ini pada akhirnya akan mengidentifikasi setiap gerakan sebagai langkah menang atau langkah kalah.

Sekarang, strateginya sepele. Lihatlah semua kemungkinan gerakan Anda. Jika ada gerakan kemenangan yang tersisa, ambil satu dan menang. Jika hanya kekalahan yang tersisa, mundur, karena lawan Anda dapat memaksa Anda untuk kalah.

Tidak sulit untuk menyesuaikan strategi untuk memasukkan kemungkinan jalan buntu.

Pembaruan : Untuk berjaga-jaga jika tidak jelas bagaimana hal ini mengidentifikasi setiap gerakan sebagai langkah menang atau kalah, pertimbangkan:

1. Setiap gerakan yang menghasilkan kemenangan adalah langkah yang menang.
2. Setiap langkah yang menghasilkan kerugian adalah langkah yang hilang.
3. Setiap gerakan yang menghasilkan lawan hanya memiliki gerakan menang atau kalah adalah langkah menang atau kalah.
4. Sebut njumlah gerakan dalam permainan catur terpanjang yang mungkin. (Kami mengabaikan urutan yang tidak terbatas untuk saat ini, meskipun memasukkannya tidak sulit.)
5. Tidak ada gerakan dengan ngerakan sebelumnya yang perlu kita pertimbangkan.
6. Setiap gerakan dengan n-1gerakan sebelumnya adalah gerakan menang atau kalah karena ngerakan mengakhiri permainan terpanjang.
7. Jadi setiap gerakan di kedalaman n-2hanya diikuti oleh gerakan menang atau kalah dan dengan demikian merupakan gerakan menang atau kalah.
8. Dan selanjutnya kembali ke langkah pertama.

Misalkan Anda memiliki tiga fungsi: win_state, get_player, dan next_states. Input untuk win_stateadalah keadaan permainan, dan outputnya -1 jika putih dalam skakmat, 0 jika imbang, 1 jika hitam dalam skakmat, dan Nonesebaliknya. Input untuk get_playeradalah kondisi permainan, dan outputnya -1 jika giliran hitam dan 1 jika giliran putih. Input untuk next_statesadalah daftar kemungkinan kondisi permainan berikutnya yang dapat dihasilkan dari langkah hukum. Maka fungsi berikut, ketika diberi status permainan dan pemain, harus memberi tahu Anda kondisi permainan yang harus dimenangkan pemain tersebut.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)

Gunakan tabel pencarian

Iya nih. Mudah. Anda bahkan tidak memerlukan kekuatan pemrosesan yang tak terbatas. Yang Anda butuhkan adalah tabel pencarian yang berisi, untuk setiap posisi papan yang memungkinkan, gerakan terbaik untuk bermain di posisi itu. Berikut adalah pseudo-code:

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

Tangkapan

Satu-satunya tangkapan adalah bahwa tabel pencarian ini harus sangat, sangat besar — ​​mungkin lebih besar dari galaksi Bima Sakti — dan akan membutuhkan waktu lama untuk membangunnya — mungkin lebih lama dari usia alam semesta saat ini, kecuali ada beberapa keteraturan yang belum ditemukan dalam catur yang membuatnya jauh lebih sederhana daripada yang bisa kita lihat sekarang. Tetapi jika Anda memiliki tabel pencarian ini, subrutin untuk memilih langkah sempurna setiap kali dapat diimplementasikan hanya dalam satu instruksi CPU.

Juga, mengingat pengetahuan kami tentang catur saat ini, tidak ada cara untuk memastikan bahwa permainan yang sempurna menjamin bahwa Anda tidak akan kalah. Misalnya, jika permainan yang sempurna menjamin kemenangan untuk Putih, maka Hitam akan kehilangan bahkan jika Hitam bermain dengan sempurna.