Keacakan dalam permainan mesin

Jika saya mendapatkan dua mesin untuk bermain melawan satu sama lain dengan warna yang sama, akankah hasil game yang sama setiap saat? Jika tidak, dari mana asal keacakan mesin itu? (Mengabaikan buku pembuka, di mana jika aku tidak salah buku itu dapat memberitahu mesin untuk memilih antara dua gerakan secara acak karena mereka sama-sama bagus.)

Saya berasumsi bahwa ada keacakan karena dalam pertandingan Alphazero vs Stockfish, kami tidak mendapatkan permainan yang sama terjadi berkali-kali berturut-turut. Namun saya tidak mengerti mengapa. Agaknya satu-satunya cara untuk melakukan ini adalah untuk mendapatkan mesin untuk memainkan gerakan di bawah standar beberapa waktu, yang terdengar seperti seppuku.

Mengenai pertandingan AlphaZero vs Stockfish, pertanyaan ini sudah dibahas di sini oleh SmallChess .

Selain AlphaZero (yang menggunakan rutinitas Monte Carlo ^{1 khusus} dalam eksplorasi garis permainan), yang dibuat menjadi non-deterministik oleh konstruksi, untuk mesin catur berbasis heuristik biasa, seperti Stockfish dan lainnya (meskipun ada yang lain mesin yang memiliki rutinitas berbasis MC, AFAIK Rybka digunakan untuk memiliki fitur tersebut), sumber keacakan umumnya hanya konsekuensi dari aspek teknis dalam implementasi, dan bukan keacakan yang disengaja secara algoritmik dalam pengambilan keputusan mesin. Secara abstrak, satu alasan untuk itu adalah kenyataan bahwa mesin tidak berjalan secara murni berurutan (menjalankan satu tugas demi satu). Sebagai gantinya, untuk membuat mesin lebih efisien, mereka melakukan pencarian paralel di berbagai cabang pohon gerakan yang mungkin. Mereka melakukannya melalui apa yang disebut multi-threading (atau -proses tetapi itu agak berbeda). Jadi banyak utas CPU secara bersamaanmenjalankan operasi untuk mencari pohon (dan menyimpan evaluasi posisi yang dikunjungi), jadi bayangkan setiap utas diberi subtree. Masalah dengan implementasi semacam ini adalah bahwa keseluruhan pelaksanaan utas menjadi sangat tergantung pada semua jenis kondisi (waktu tunggu, RAM swap, ...), jadi pada akhirnya variasi utama dapat dipilih tanpa mengizinkan semua lainnya. utas untuk menyelesaikan pencarian mereka.

Ini memang sering terjadi karena mesin diatur untuk membuat keputusan di bawah jumlah waktu tertentu, sehingga manajemen waktu mengubah perilaku. Anda juga dapat mengembalikan pernyataan ini dengan mengatakan: mengetahui algoritme dan menerapkan rutinitas threading deterministik tidak cukup untuk memprediksi keadaan program dengan andal setelah waktu t. Tentu saja jika seseorang selalu mengizinkan semua utas untuk menyelesaikan pencarian mereka, dan belum ada masalah konkurensi selama eksekusi tersebut (misalnya utas yang mencoba mengakses cache tertentu yang tidak dapat diakses), maka perilaku tersebut akan sepenuhnya dapat direproduksi mengingat yang lainnya sama ² .

^{1 : Bersamaan dengan kenyataan bahwa melalui pelatihan tambahan (misalnya bermain sendiri) jaringan sarafnya terus berkembang (parameter yang disesuaikan kembali), atau jika Anda mau fungsi evaluasinya tidak memiliki definisi yang konstan dan tetap (tidak seperti mesin berbasis heuristik) ).}

^{2 : Bahkan saat itu, seperti yang Anda katakan, pada tingkat pembukaan, dengan buku pembuka, kadang-kadang ada keputusan acak yang disengaja yang dibuat oleh mesin untuk memilih variasi mana. Demikian pula, di luar fase pembukaan, mungkin ada saat-saat di mana beberapa variasi mendekati evaluasi yang sama (dalam resolusi yang dipilih untuk Eval), kemudian berdasarkan pada desain, mungkin akhirnya memilih satu secara acak. Terakhir, pada level pengaturan mesin Anda harus berhati-hati juga, misalnya kedalaman pencarian dan waktu perenungan yang dipilih untuk setiap mesin (dan apakah mereka dapat menghitung lebih lanjut selama waktu perenungan satu sama lain).}

Terima kasih kepada @Phonon yang meliput jawaban saya sebelumnya secara terperinci. Saya ingin menambahkan satu poin lagi: kontrol waktu .

Satu-satunya kontrol waktu deterministik adalah dengan jumlah node , tetapi ini tidak biasa. Kontrol waktu yang lebih umum - jumlah detik atau waktu permainan yang tetap umumnya tidak deterministik.

Mari kita coba sebuah contoh. Jalankan stockfish di terminal Anda. Tipe:

pergi bergerak 20.000

Perintah ini menginstruksikan mesin untuk bergerak setelah 20 detik. Hasil saya:

info depth 23 seldepth 32 multipv 1 score cp 6 upperbound nodes 24325860 nps 1216171 hashfull 999 tbhits 0 time 20002 pv g1f3 d7d5
bestmove g1f3 ponder d7d5

Langkahnya adalah 1.Nf3. Selanjutnya, saya membunuh Stockfish saya, memulai yang baru. Lagi, 20 detik. Saya mendapatkan:

info depth 23 seldepth 32 multipv 1 score cp 20 nodes 26185280 nps 1309067 hashfull 999 tbhits 0 time 20003 pv d2d4
bestmove d2d4 ponder g8f6

1.d4! Posisi yang sama, keduanya mencari 20 detik!

Apakah kamu lihat? Keduanya 20 detik untuk pindah, tetapi karena fluktuasi dalam sistem operasi Linux menjalankan kedua saya memiliki pencarian yang lebih dalam (26185280> 24325860).

Harap perhatikan percobaan kecil ini bahkan tidak multithreaded (jumlah utas = 1). Multithreading akan membuat segalanya menjadi lebih non-deterministik.

Stockfish diberikan satu menit per langkah dalam pertandingan Google AlphaZero. Jumlah utas adalah 64. Keputusan Stockfish dalam pertandingan tidak mungkin menjadi deterministik.