Bagaimana mesin meningkat sejak Deep Blue?

17

Mesin catur komputer menjadi lebih baik sejak Deep Blue mengalahkan Kasparov pada tahun 1997.

Apakah algoritme menjadi lebih baik, atau apakah peningkatan sebagian besar karena algoritma yang sama berjalan lebih cepat berkat perangkat keras yang lebih cepat, dll?

Jika yang pertama, apakah perbaikan algoritmik ini bersifat publik?

Dan jika demikian, apa perbaikannya? Di mana saya bisa membaca tentang mereka?

engines programming computer-chess chess-algorithms MaxB
sumber
Jawaban saya yang sederhana: chess.stackexchange.com/questions/19575/is-deep-blue-outdated
SmallChess
Bagaimana? Secara dramatis.
Evargalo

Jawaban:

8

Mungkin Anda bisa melihat TalkChess , sebuah forum yang didedikasikan untuk catur komputer. Saya menemukan utas baru-baru ini yang mungkin menarik bagi Anda: Kemajuan dalam 30 tahun dengan empat interval 7-8 tahun

Beberapa pertandingan antara (mantan) mesin top dimainkan pada perangkat keras yang sama . Tes ini menunjukkan bahwa dalam beberapa tahun terakhir (2002-2017), keuntungan utamanya adalah peningkatan perangkat lunak. Dalam tes tersebut, Stockfish (2017) mencetak 94/100 yang mengesankan melawan RobboLito (2009), sementara RobboLito, pada gilirannya, menghancurkan Shredder (2002) dengan 92/100.

Komentar penting: karena komputasi paralel tidak diterapkan pada mesin yang lebih tua, pengujian dilakukan pada satu inti. Akibatnya, perolehan perangkat keras oleh mesin paralel tidak diukur. Di sisi lain, Anda dapat berargumen bahwa komputasi paralel juga merupakan keuntungan perangkat lunak: tidak mudah untuk merancang dan mengimplementasikan paralelisasi yang efisien dan berskala baik untuk algoritma pencarian.

Mesin Stockfish adalah open source, sehingga peningkatan algoritmik bersifat publik. Banyak dokumentasi dapat ditemukan di https://chessprogramming.wikispaces.com

Maxwell86
sumber
Ini menjawab pernyataannya. Coba jawab pertanyaan itu lain kali.
Fred Knight
1
Yah, saya yakin saya memang menjawab pertanyaan: keuntungan terutama dibuat oleh peningkatan algoritma. Selanjutnya, saya menunjukkan data yang mendukung klaim ini (lihat tautan) dan menunjukkan kemungkinan kekurangan (tidak ada paralelisasi yang diukur).
Maxwell86
3

Saya tidak dapat berbicara untuk algoritma yang digunakan untuk Deep Blue, tetapi saya akan mencoba dan menjelaskan peningkatan dalam pemrograman catur. Kecepatan adalah peningkatan terbesar. Deep Blue menggunakan komputer khusus multi-prosesor, jadi perbandingan tidak benar-benar mungkin.

https://chessprogramming.wikispaces.com/ adalah sumber yang bagus, tetapi sulit dinavigasi.

Ada 3 fungsi utama yang di-tweak untuk meningkatkan mesin catur yaitu fungsi evaluasi, pemindahan bergerak, dan pencarian.

Evaluasi adalah yang paling sulit untuk diprogram, karena ada banyak pengecualian pada aturan. Dengan ruang hard drive yang semakin murah, fungsi eval memungkinkan lebih banyak pengecualian untuk dievaluasi.

Generasi yang bergerak, bersamaan dengan membuat dan tidak bergerak, menghabiskan banyak memori karena harus berkali-kali dibentuk sebelumnya. Fungsi generasi yang paling umum adalah kotak surat, bitboard, 0x88, 8x8, papan yang diperluas (10x10, 10x12), dan array / tabel pemindahan yang telah ditentukan (* Saya menggunakan tabel pemindahan yang diindeks). Pendapat saat ini adalah bahwa bitboard lebih cepat, dan menggunakan bitboards ajaib mempercepatnya hingga 30%. Robert Hyatt, profesor dan pencipta mesin catur cratfy, mengklaim tidak ada peningkatan kecepatan yang signifikan.

Fungsi pencarian awal adalah fungsi min-max primitif. Pada dasarnya Anda mencoba memaksimalkan skor sisi untuk bergerak dan meminimalkan skor lawan. Alpha-Beta adalah peningkatan pertama. Mereka mengurangi jumlah gerakan yang dicari oleh tabel transposisi, nilai cut-off, jendela aspirasi, dan heuristik sejarah. Ini adalah pencarian mendalam-pertama. Ada juga pencarian pendalaman iteratif internal yang mencoba untuk mencari langkah "terbaik" (s) yang terdalam berharap bahwa pencarian gerakan lain akan terbukti sia-sia.

CATATAN: Tabel indeks saya. GNUChess dan Jester keduanya menggunakan array indeks untuk menghasilkan gerakan mereka. Mereka menginisialisasi mesin dengan mengisi array dengan gerakan yang mungkin. Ambil enam bagian dan hitung langkah hukum yang tersedia dari setiap kotak. Jadi masing-masing bagian memiliki array [64] [8]. Saya mengambil ide ini dan mengompresnya menjadi dua indeks dan sebuah tabel. Tabel memegang nilai yang memberitahu jika 16 gerakan mungkin, satu indeks memegang offset gerakan, dan yang lainnya memegang topeng.

offset [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

mask [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Kemudian generasi gerakan geser semudah mencari keabsahan topeng itu di dalamnya diimbangi dengan tabel bergerak.

Fred Knight
sumber
7
Saya mencoba untuk tidak menjawab jawaban, tapi ini hanya .... Alpha-beta dan bitboards diciptakan LAMA sebelum Deep Blue. Saya juga cukup yakin bahwa board eval tidak mengakses HD di mesin waras (latensinya BESAR). Keempat, saya sangat skeptis bahwa ukuran RAM membuat perbedaan nyata dalam implementasi pencarian alpha-beta normal Anda.
MaxB
Bisakah Anda menambahkan beberapa hyperlink ke beberapa konsep yang Anda diskusikan? Sebagai seseorang yang tertarik pada konsep, tetapi tidak terbiasa dengan terminologi, sulit untuk diikuti karena saya tidak tahu apa itu bitboard atau mesin Catur Catur.
Thunderforge
Saya berpikir bahwa saya jelas bahwa saya tidak membandingkan dengan Deep Blue, tapi saya memberikan sejarah singkat. Hard drive yang saya maksud adalah program itu sendiri. Setiap kali konsep eval baru dimasukkan ke dalam mesin catur, lebih banyak kode, dan karena itu lebih banyak ruang HD diperlukan.
Fred Knight
@Thunderforge, satu tautan yang saya berikan menjelaskan setiap aspek yang Anda inginkan terkait dengan pemrograman catur, namun saya akui bahwa ini sulit dinavigasi. Saya belajar dengan membaca kode sumber orang lain, tetapi yang paling banyak dikomentari adalah mesin Crafty dari Dr. Hyatt. Saya memilih untuk tidak terlalu komprehensif karena keterbatasan ruang dan perbedaan antar platform dan kompiler. Jika, setelah membaca halaman catur wiki, Anda masih bingung, ajukan pertanyaan dan saya yakin banyak yang akan memberikan jawaban yang lebih baik.
Fred Knight
1
Every time that a new eval concept in included into a chess engine, more code, and therefore more HD space is required.Fungsi eval papan biasanya dirancang agar sesuai dengan cache CPU. Cache CPU << RAM << HD. Ukuran HD tidak ada bedanya.
MaxB
2

Apakah algoritme menjadi lebih baik?

Jelas, ya sedikit.

atau apakah peningkatan sebagian besar karena algoritma yang sama berjalan lebih cepat berkat perangkat keras dan lunak yang lebih cepat?

Minor nit: Jika algoritme menjadi lebih baik maka perangkat lunaknya menjadi lebih baik sehingga tidak ada "atau".

Hukum Moore memberi tahu kita bahwa kecepatan prosesor akan berlipat ganda kira-kira setiap 18 bulan. Itu berarti telah dua kali lipat sekitar 13 kali dalam 20 tahun. Itu membuat prosesor modern di suatu tempat di wilayah 8.000 kali lebih cepat. Jadi, jauh dan jauh peningkatan terbesar dalam performa mesin adalah karena perangkat keras yang lebih cepat.

Jika yang pertama, apakah perbaikan algoritmik ini bersifat publik?

Dan jika demikian, apa perbaikannya? Di mana saya bisa membaca tentang mereka?

Yah, itu bukan yang pertama, itu yang terakhir. Namun demikian, perbaikannya sebagian besar bersifat open source dan dapat dilihat secara bebas dengan mengunduh sumber untuk mesin seperti Stockfish . Mungkin juga layak memberikan tautan unduhan Stockfish umum karena tautan kode sumber tertentu kemungkinan akan kedaluwarsa ketika versi 9 keluar.

Menara Brian
sumber
2
That means it has doubled roughly 13 times in 20 years.Saya pikir Anda salah mengutip Hukum Moore. Ia tidak mengatakan apa-apa tentang kecepatan prosesor. Bahkan, itu belum dua kali lipat dalam beberapa saat.
MaxB
hardware and softwareSaya maksudkan perangkat lunak seperti dalam implementasi algoritma (ASM vs C ++), tetapi saya bisa melihat bagaimana itu membingungkan. Tetap.
MaxB
1
Hukum He Moore benar, kecuali bahwa dia memasukkan frasa "dalam dekade berikutnya." Ini akan terjadi pada tahun 1975, dan dia benar.
Fred Knight
-1 karena jawaban salah - pada perangkat keras yang sama, mesin saat ini masih menghancurkan mesin yang sebelumnya-top.
Allure
0

Ini semua tentang algoritma.

Mengambil seorang pemain catur manusia mengambil salah satu komputer paling kuat di dunia pada saat itu. Pendekatan komputasi brute force ini memungkinkan Deep Blue untuk melihat sekitar enam hingga delapan langkah ke depan. Dalam kontes yang berlangsung ketat, mesin akhirnya mengalahkan Kasparov dengan 3 1/2 game menjadi 2 1/2.

Enam tahun kemudian, Kasparov terlibat dalam kontes manusia versus mesin. Kali ini ia bermain melawan penerus Deep Blue, Deep Junior. Hasilnya adalah seri seri di tiga pertandingan semua. Perbedaan terbesar adalah bahwa Deep Junior menjalankan mesin dengan sekitar satu persen dari kekuatan komputasi Deep Blue. Algoritma permainan catur telah meningkat hingga mencapai hasil yang hampir sama dengan daya komputasi seratus kali lebih sedikit.

David Hambling
sumber
4
Selamat Datang di Catur! Anda menulis bagian utama dari jawaban Anda seolah-olah itu adalah kutipan; bisakah Anda memberikan sumber?
Glorfindel
0

Penafian: bukan ahli.

Algoritma menjadi lebih baik, dan mesin terbaik saat ini berjalan pada 1995 (ingat Deep Blue adalah 1999) perangkat keras akan dengan mudah mengalahkan Kasparov. Seperti yang saya pahami, ada dua aspek algoritma:

Cari . Jika misalnya saya membawa ratu Anda dengan ratu saya, lawan manusia akan secara otomatis melihat pertama kali merebut kembali. Namun untuk komputer, komputer akan mengevaluasi setiap kemungkinan respons terhadap QxQ. Hampir sepanjang waktu, ini adalah kekuatan pemrosesan yang terbuang. Algoritme pencarian yang bagus memotong semua "cabang" ini karena tidak relevan.

Algoritma pencarian standar adalah pemangkasan alpha-beta , dan digunakan di komputer catur paling awal. Saya tidak tahu apakah Deep Blue menggunakan pemangkasan alpha-beta, tetapi mesin modern tidak. Akibatnya pencarian mereka "tidak aman" - mereka dapat kehilangan, misalnya, bahwa beberapa langkah selain merebut kembali sang ratu akan memenangkan permainan. Namun, jarang hal ini terjadi, dan sebagai gantinya mereka mendorong kedalaman mereka sangat tinggi. ("Kedalaman" adalah istilah teknis untuk seberapa dalam mesin mencari, jadi mis. Mesin yang mencari ke kedalaman 30 kemungkinan akan mengalahkan satu yang hanya mencari ke kedalaman 20, semua hal lain dianggap sama).

Evaluasi . Ini adalah cabang lain dari kode mesin. Mengingat posisi tertentu, apakah lebih baik untuk putih, hitam, atau sama? Ini dapat melibatkan semua jenis fungsi, misalnya

  • Jika satu sisi memiliki bahan / ruang ekstra, berikan bonus untuk eval.
  • Jika putih memiliki ksatria tingkat lanjut yang didukung oleh pion, berikan putih bonus untuk eval.
  • Jika raja kulit hitam mengalami kebuntuan, berikan putih bonus untuk eval.
  • Jika putih memiliki benteng di peringkat 7, berikan putih bonus untuk eval.
  • Jika ini adalah endgame (dan ada algoritma untuk memutuskan apakah posisinya adalah endgame) dan kedua belah pihak memiliki uskup warna yang berlawanan, beri penalti untuk eval (yaitu mendorongnya ke arah 0,00).

Mesin saat ini mengevaluasi posisi jauh lebih baik daripada Deep Blue.

Mengenai apakah algoritmanya bersifat publik, Stockfish saat ini merupakan mesin terkuat di dunia dan bersifat open source. Anda dapat mengunduh kode sendiri dari Github .

Daya tarik
sumber