Kecerdasan Buatan Permainan Papan: Algoritma Minimax: 8 Langkah

2024 Pengarang: John Day | [email protected]. Diubah suai terakhir: 2024-01-30 11:09

Pernah terfikir bagaimana komputer yang anda mainkan di catur atau kotak-kotak dibuat? Lihatlah lebih jauh daripada Instructable ini kerana ia akan menunjukkan kepada anda bagaimana membuat kecerdasan buatan (AI) yang mudah tetapi berkesan menggunakan Algoritma Minimax! Dengan menggunakan Algoritma Minimax, AI membuat pergerakan yang dirancang dan difikirkan dengan baik (atau sekurang-kurangnya meniru proses pemikiran). Sekarang, saya boleh memberi anda kod untuk AI yang saya buat, tetapi itu tidak akan menyenangkan. Saya akan menerangkan logik di sebalik pilihan komputer.

Dalam Instructable ini, saya akan memandu anda melalui langkah-langkah bagaimana membuat AI untuk Othello (AKA Reversi) di python. Anda harus mempunyai pemahaman perantaraan tentang cara membuat kod di python sebelum menangani projek ini. Berikut adalah beberapa laman web yang bagus untuk dilihat untuk mempersiapkan anda untuk Instructable ini: w3schools atau learnpython. Pada akhir Instructable ini, anda harus mempunyai AI yang akan melakukan pergerakan yang dikira dan seharusnya dapat mengalahkan kebanyakan manusia.

Oleh kerana Instructable ini terutama berkaitan dengan cara membuat AI, saya tidak akan menerangkan bagaimana merancang permainan di python. Sebagai gantinya, saya akan memberikan kod untuk permainan di mana manusia dapat bermain melawan manusia lain dan mengubahnya sehingga anda dapat memainkan permainan di mana manusia bermain melawan AI.

Saya belajar bagaimana membuat AI ini melalui program musim panas di Columbia SHAPE. Saya bersenang-senang di sana jadi lihat di laman web mereka untuk melihat apakah anda berminat.

Sekarang kita tidak mendapat logistik, mari mulakan pengekodan!

(Saya meletakkan beberapa nota dalam gambar jadi pastikan untuk melihatnya)

Bekalan

Ini mudah:

1) Komputer dengan persekitaran python seperti Spyder atau IDLE

2) Muat turun fail untuk permainan Othello dari GitHub saya

3) Otak anda dengan kesabaran terpasang

Langkah 1: Muat turun Fail yang Diperlukan

Apabila anda masuk ke GitHub saya, anda akan melihat 5 fail. Muat turun semua 5 dan letakkan semuanya dalam folder yang sama. Sebelum kita menjalankan permainan, buka semua fail di persekitaran pengintip.

Inilah yang dilakukan oleh fail:

1) othello_gui.py fail ini membuat papan permainan untuk dimainkan oleh pemain (sama ada manusia atau komputer)

2) othello_game.py fail ini memainkan dua komputer antara satu sama lain tanpa papan permainan dan hanya menunjukkan skor dan kedudukan bergerak

3) ai_template.py di sinilah anda akan meletakkan semua kod anda untuk membuat AI anda

4) randy_ai.py ini adalah AI premade yang memilih pergerakannya secara rawak

5) othello_shared.py sekumpulan fungsi pra-dibuat yang boleh anda gunakan untuk membuat AI anda seperti memeriksa pergerakan, skor, atau keadaan papan yang tersedia

6) Tiga fail lain: Puma.py, erika_5.py, dan nathan.py, masing-masing dibuat oleh saya, Erika, dan Nathan dari program SHAPE, ini adalah tiga AI berbeza dengan kod unik

Langkah 2: Cara Membuka dan Memainkan Python Othello

Setelah anda membuka semua fail, di sudut kanan bawah skrin, ketik "run othello_gui.py" dan tekan enter di IPython Console. Atau di terminal Mac, ketik "python othello_gui.py" (setelah anda berada di folder yang betul). Kemudian papan akan muncul di skrin anda. Mod ini adalah mod manusia vs manusia. Cahaya menjadi kedua dan gelap pertama. Lihatlah video saya jika anda keliru. Di bahagian atas, terdapat skor setiap jubin warna. Untuk bermain, klik ruang bergerak yang sah untuk meletakkan jubin di sana dan kemudian berikan komputer kepada lawan anda yang akan melakukan perkara yang sama dan berulang.

Sekiranya anda tidak tahu bermain Othello, baca peraturan ini dari laman web papan ultra:

Hitam selalu bergerak terlebih dahulu. Pergerakan dibuat dengan meletakkan cakera warna pemain di papan dalam kedudukan yang "melepasi" satu atau lebih cakera lawan. Cakera atau barisan cakera diungguli apabila dikelilingi di hujungnya dengan cakera dengan warna yang berlawanan. Cakera boleh melebihi jumlah cakera dalam satu atau lebih baris ke arah mana pun (mendatar, menegak, pepenjuru)…. (selesai membaca di laman web mereka)

Perbezaan antara permainan asal dan permainan python ini adalah apabila tidak ada gerakan yang sah untuk satu pemain permainan berakhir

Sekarang anda boleh bermain permainan dengan rakan, mari buat AI yang boleh anda mainkan.

Langkah 3: Algoritma Minimax: Menjana Senario

Sebelum membincangkan cara menulis ini dalam kod, mari kita teliti logik di belakangnya. Algoritma minimax adalah algoritma pembuatan keputusan, pengesanan belakang dan biasanya digunakan dalam permainan dua pemain, berdasarkan giliran. Matlamat AI ini adalah untuk mencari langkah terbaik seterusnya dan langkah terbaik berikut sehingga memenangi permainan.

Sekarang bagaimana algoritma akan menentukan pergerakan mana yang paling baik? Berhenti dan fikirkan bagaimana anda akan memilih langkah seterusnya. Sebilangan besar orang akan memilih langkah yang akan memberi mereka poin terbanyak, bukan? Atau jika mereka berfikir ke depan, mereka akan memilih langkah yang akan membuat situasi di mana mereka dapat memperoleh lebih banyak mata. Cara berfikir yang terakhir adalah cara berfikir Algoritma Minimax. Ia melihat ke depan untuk semua pengaturan papan masa depan dan membuat langkah yang akan membawa ke titik terbanyak.

Saya menyebutnya algoritma backtracking, kerana ia bermula dengan membuat dan menilai semua keadaan papan masa depan dengan nilai yang berkaitan. Ini bermaksud bahawa algoritma akan memainkan permainan sebanyak yang diperlukan (membuat gerakan untuk dirinya sendiri dan lawan) sehingga setiap senario permainan telah dimainkan. Untuk mengesan semua keadaan papan (senario), kita dapat melukis pokok (lihat dalam gambar). Pokok dalam gambar di atas adalah contoh mudah permainan Connect 4. Setiap konfigurasi papan dipanggil keadaan papan dan tempatnya di atas pokok disebut simpul. Semua nod di bahagian bawah pokok adalah keadaan papan terakhir setelah membuat semua pergerakan. Jelasnya beberapa keadaan papan lebih baik untuk satu pemain daripada yang lain. Jadi, sekarang kita harus membuat AI memilih keadaan papan yang ingin dicapai.

Langkah 4: Minimax: Menilai Konfigurasi Papan

Untuk memberi nilai kepada negara papan, kita harus mempelajari strategi permainan yang sedang kita mainkan: dalam hal ini, strategi Othello. Kerana permainan ini adalah pertempuran untuk membalik lawan dan cakera anda, kedudukan cakera terbaik adalah yang stabil dan tidak dapat dibalik. Sudut, misalnya, adalah tempat di mana cakera diletakkan tidak boleh diubah menjadi warna lain. Oleh itu, tempat itu akan sangat berharga. Kedudukan lain yang baik termasuk sisi papan yang membolehkan anda mengambil banyak batu. Terdapat lebih banyak strategi di laman web ini.

Sekarang kita dapat memberikan nilai pada kedudukan untuk setiap papan negara papan. Apabila kedudukan diduduki oleh bahagian AI, maka anda memberikan sejumlah titik bergantung pada kedudukannya. Sebagai contoh, keadaan papan di mana bahagian AI berada di sudut, anda boleh memberikan bonus 50 mata, tetapi jika berada di tempat yang tidak baik, potongan itu mungkin mempunyai nilai 0. Setelah mengambil kira semua nilai kedudukan, anda menetapkan nilai dewan. Sebagai contoh, jika AI mempunyai bahagian di sudut keadaan papan boleh mendapat skor 50 sementara keadaan papan lain dengan bahagian AI di tengahnya mempunyai skor 10.

Terdapat banyak cara untuk melakukan ini, dan saya mempunyai tiga heuristik yang berbeza untuk menilai kepingan papan. Saya mendorong anda untuk membuat jenis heuristik anda sendiri. Saya memuat naik tiga AI yang berbeza ke github saya oleh tiga pembuat yang berbeza, dengan tiga heuristik yang berbeza: Puma.py, erika5.py, nathanh.py.

Langkah 5: Algoritma Minimax: Memilih Langkah Terbaik

Sekarang lebih baik jika AI dapat memilih semua langkah untuk menuju ke keadaan papan dengan skor tertinggi. Tetapi ingat bahawa AI juga memilih pergerakan untuk lawan ketika menghasilkan semua keadaan papan dan jika lawan pintar, ia tidak akan membenarkan AI mencapai skor papan tertinggi. Sebaliknya, lawan yang cerdas akan bergerak untuk membuat AI pergi ke keadaan papan paling rendah. Dalam algoritma, kami memanggil kedua pemain sebagai pemain yang memaksimumkan dan pemain yang meminimumkan. AI akan menjadi pemain yang memaksimumkan kerana ingin mendapatkan mata terbanyak untuk dirinya sendiri. Lawan akan menjadi pemain yang meminimumkan kerana lawan berusaha untuk membuat pergerakan di mana AI mendapat mata paling sedikit.

Setelah semua keadaan papan dihasilkan dan nilai diberikan kepada papan, algoritma mula membandingkan keadaan papan. Dalam gambar, saya membuat pokok untuk mewakili bagaimana algoritma akan memilih pergerakannya. Setiap perpecahan di cabang adalah gerakan yang berbeza yang boleh dimainkan oleh lawan. Di sebelah kiri baris nod, saya menulis sama ada pemain memaksimumkan atau meminimumkan berlaku. Baris bawah adalah semua keadaan papan dengan nilainya. Di dalam setiap node itu adalah nombor dan itulah skor yang kami berikan kepada setiap papan: semakin tinggi, semakin baik untuk AI.

Definisi: nod induk - nod yang menghasilkan atau membuat nod di bawahnya; asal node anak - nod yang berasal dari nod ibu bapa yang sama

Node kosong mewakili pergerakan yang akan dibuat oleh AI untuk mencapai keadaan papan terbaik. Ia dimulakan dengan membandingkan anak-anak dari simpul paling kiri: 10, -3, 5. Oleh kerana pemain yang memaksimumkan akan melakukan pergerakan, ia akan memilih gerakan yang akan memberikan poin terbanyak: 10. Oleh itu, kami kemudian memilih dan menyimpannya bergerak dengan skor papan dan tuliskan di nod induk. Sekarang 10 berada di nod induk, kini giliran pemain yang meminimumkan. Walau bagaimanapun, node yang akan kita bandingkan 10 adalah kosong, jadi kita harus menilai simpul itu terlebih dahulu sebelum pemain yang meminimumkan dapat memilih. Oleh itu, kita kembali ke giliran pemain yang memaksimumkan dan membandingkan anak-anak dari nod yang berdekatan: 8, -2. Memaksimumkan akan memilih 8 dan kami menuliskannya di simpul induk kosong. Sekarang setelah algoritma selesai mengisi tempat kosong untuk anak-anak nod di atasnya, pemain yang meminimumkan dapat membandingkan anak-anak itu - 10 dan 8 dan memilih 8. Algoritma kemudian mengulangi proses ini sehingga seluruh pokok diisi. Pada akhir contoh ini, kita mempunyai skor 8. Itulah keadaan papan tertinggi yang dapat dimainkan oleh AI dengan anggapan lawan bermain dengan optimum. Oleh itu, AI akan memilih langkah pertama yang menuju ke 8 keadaan papan, dan jika lawan bermain dengan optimum, AI harus memainkan semua gerakan untuk sampai ke keadaan papan 8. (Ikuti nota pada gambar saya)

Saya tahu itu banyak. Sekiranya anda adalah salah satu jenis yang perlu meminta seseorang bercakap dengan anda untuk memahami sesuatu, berikut adalah beberapa video yang saya tonton untuk membantu saya memahami idea di sebalik ini: 1, 2, 3.

Langkah 6: Algoritma Minimax: Pseudocode

Setelah anda memahami logik di sebalik algoritma minimax, lihatlah pseudocode ini (fungsi yang universal untuk semua kod) dari wikipedia:

minimax fungsi (nod, kedalaman, memaksimumkanPlayer) adalah

jika kedalaman = 0 atau nod adalah nod terminal maka

mengembalikan nilai heuristik nod

jika memaksimumkanPlayer maka

nilai: = −∞

untuk setiap anak nod lakukan

nilai: = maks (nilai, minimax (anak, kedalaman - 1, SALAH))

nilai pulangan

lain (* meminimumkan pemain *)

nilai: = + ∞

untuk setiap anak nod lakukan

nilai: = min (nilai, minimax (anak, kedalaman - 1, BENAR))

nilai pulangan

Ini adalah fungsi rekursif, yang bermaksud bahawa ia memanggil dirinya berulang-ulang hingga mencapai titik berhenti. Pertama, fungsi mengambil tiga nilai, simpul, kedalaman, dan gilirannya. Nilai nod adalah tempat di mana anda mahu program mula mencari. Kedalamannya adalah sejauh mana anda mahu program dicari. Sebagai contoh, dalam contoh pokok saya ia mempunyai kedalaman 3, kerana ia mencari semua keadaan papan setelah 3 bergerak. Sudah tentu, kami ingin AI memeriksa setiap keadaan papan dan memilih kemenangan yang menang, tetapi dalam kebanyakan permainan di mana terdapat ribuan jika tidak berjuta-juta konfigurasi papan, komputer riba anda di rumah tidak akan dapat memproses semua konfigurasi tersebut. Oleh itu, kami mengehadkan kedalaman carian AI dan memilikinya ke keadaan papan terbaik.

Pseudocode ini menghasilkan semula proses yang saya jelaskan dalam dua langkah sebelumnya. Sekarang mari kita melangkah lebih jauh dan membetulkannya dalam kod python.

Langkah 7: Membuat AI Anda dengan Ai_template.py

Sebelum melihat kod Minimax AI saya, cobalah untuk membuat AI anda sendiri dengan fail ai_template.py dan kod pseudo yang kami bicarakan pada langkah terakhir. Terdapat dua fungsi dalam templat ai yang dipanggil: def minimax_min_node (papan, warna) dan def minimax_max_node (papan, warna). Daripada fungsi minimax memanggilnya secara berulang, kita mempunyai dua fungsi yang berbeza, yang saling memanggil. Untuk membuat heuristik untuk menilai keadaan papan, anda harus membuat fungsi anda sendiri. Terdapat fungsi premade dalam fail othello_shared.py yang boleh anda gunakan untuk membina AI anda.

Sebaik sahaja anda mempunyai AI anda, cuba gunakannya, randy_ai.py. Untuk menjalankan dua ais antara satu sama lain, ketik "python othello_gui.py (masukkan nama fail ai).py (masukkan nama fail).py" di terminal mac atau ketik "jalankan othello_gui.py (masukkan nama fail ai).py (masukkan nama fail).py "dan pastikan anda berada di direktori yang betul. Juga, lihat video saya untuk langkah yang tepat.

Langkah 8: Masa untuk Melawan AI

Sekarang dapatkan sebilangan besar rakan komputer anda dan buat mereka merancang AI mereka sendiri! Kemudian anda boleh membuat pertandingan dan meminta AI anda melakukannya. Mudah-mudahan, walaupun anda tidak dapat membina AI anda sendiri, anda dapat memahami bagaimana algoritma minimax berfungsi. Sekiranya anda mempunyai sebarang pertanyaan, sila hantarkan sebarang pertanyaan di komen di bawah.