Permainan Papan Kecerdasan Buatan: Algoritma Minimax: 8 Langkah

2024 Pengarang: John Day | [email protected]. Terakhir diubah: 2024-01-30 09:55

Pernah bertanya-tanya bagaimana komputer yang Anda mainkan dalam catur atau catur dibuat? Tidak terlihat lagi dari Instructable ini karena akan menunjukkan kepada Anda bagaimana membuat kecerdasan buatan (AI) yang sederhana namun efektif menggunakan Algoritma Minimax! Dengan menggunakan Algoritma Minimax, AI membuat gerakan yang direncanakan dan dipikirkan dengan baik (atau setidaknya meniru proses berpikir). Sekarang, saya hanya bisa memberi Anda kode untuk AI yang saya buat, tetapi itu tidak akan menyenangkan. Saya akan menjelaskan logika di balik pilihan komputer.

Dalam Instruksi ini, saya akan memandu Anda melalui langkah-langkah tentang cara membuat AI untuk Othello (AKA Reversi) dengan python. Anda harus memiliki pemahaman menengah tentang cara membuat kode dengan python sebelum menangani proyek ini. Berikut adalah beberapa situs web yang bagus untuk dilihat untuk mempersiapkan Anda mengikuti Instruksi ini: w3schools atau learnpython. Di akhir Instructable ini, Anda harus memiliki AI yang akan membuat gerakan yang diperhitungkan dan harus bisa mengalahkan sebagian besar manusia.

Karena Instructable ini terutama akan membahas cara membuat AI, saya tidak akan menjelaskan cara mendesain game dengan python. Sebagai gantinya, saya akan memberikan kode untuk game di mana manusia bisa bermain melawan manusia lain dan memodifikasinya sehingga Anda bisa memainkan game di mana manusia bermain melawan AI.

Saya belajar cara membuat AI ini melalui program musim panas di Columbia SHAPE. Saya bersenang-senang di sana, jadi lihatlah situs web mereka untuk melihat apakah Anda tertarik.

Sekarang setelah logistik selesai, mari mulai coding!

(Saya menaruh beberapa catatan di gambar jadi pastikan untuk melihatnya)

Perlengkapan

Ini mudah:

1) Komputer dengan lingkungan python seperti Spyder atau IDLE

2) Unduh file untuk game Othello dari GitHub saya

3) Otak Anda dengan kesabaran terpasang

Langkah 1: Unduh File yang Diperlukan

Saat Anda masuk ke GitHub saya, Anda akan melihat 5 file. Unduh semua 5 dan letakkan semuanya di folder yang sama. Sebelum kita menjalankan gamenya, buka semua file di lingkungan spyder.

Inilah yang dilakukan file:

1) othello_gui.py file ini membuat papan permainan untuk dimainkan para pemain (baik manusia atau komputer)

2) othello_game.py file ini memainkan dua komputer melawan satu sama lain tanpa gameboard dan hanya menampilkan skor dan posisi bergerak

3) ai_template.py ini adalah tempat Anda akan meletakkan semua kode Anda untuk membuat AI Anda

4) randy_ai.py ini adalah AI premade yang memilih gerakannya secara acak

5) othello_shared.py sekelompok fungsi pra-dibuat yang dapat Anda gunakan untuk membuat AI Anda seperti untuk memeriksa gerakan yang tersedia, skor, atau status papan

6) Tiga file lainnya: Puma.py, erika_5.py, dan nathan.py, dibuat oleh saya, Erika, dan Nathan masing-masing dari program SHAPE, ini adalah tiga AI berbeda dengan kode unik

Langkah 2: Cara Membuka dan Memainkan Python Othello

Setelah semua file terbuka, di sudut kanan bawah layar, ketik "run othello_gui.py" dan tekan enter di Konsol IPython. Atau di terminal Mac, ketik "python othello_gui.py" (setelah Anda berada di folder yang benar tentunya). Maka papan akan muncul di layar Anda. Mode ini adalah mode manusia vs manusia. Cahaya menjadi yang kedua dan gelap terlebih dahulu. Lihat video saya jika Anda bingung. iDi bagian atas, ada skor setiap ubin warna. Untuk bermain, klik ruang gerak yang valid untuk menempatkan ubin di sana dan kemudian berikan komputer kepada lawan Anda yang akan melakukan hal yang sama dan ulangi.

Jika Anda tidak tahu cara bermain Othello, baca aturan ini dari situs web ultraboard:

Hitam selalu bergerak lebih dulu. Sebuah langkah dilakukan dengan menempatkan disk warna pemain di papan dalam posisi yang "mengungguli" satu atau lebih dari disk lawan. Sebuah piringan atau deretan piringan dipinggirkan ketika ujung-ujungnya dikelilingi oleh piringan-piringan dengan warna yang berlawanan. Sebuah disk dapat mengungguli sejumlah disk dalam satu atau lebih baris ke segala arah (horizontal, vertikal, diagonal)…. (selesai membaca di situs web mereka)

Perbedaan antara game asli dan game python ini adalah ketika tidak ada gerakan valid yang tersisa untuk satu pemain, game berakhir

Sekarang Anda dapat memainkan game dengan teman, mari buat AI yang dapat Anda mainkan.

Langkah 3: Algoritma Minimax: Menghasilkan Skenario

Sebelum berbicara tentang cara menulis ini dalam kode, mari kita bahas logika di baliknya. Algoritme minimax adalah algoritme pengambilan keputusan, pelacakan mundur, dan biasanya digunakan dalam permainan dua pemain, berbasis giliran. Tujuan dari AI ini adalah untuk menemukan langkah terbaik berikutnya dan gerakan terbaik berikut hingga memenangkan permainan.

Sekarang bagaimana algoritma menentukan langkah mana yang terbaik? Berhentilah dan pikirkan bagaimana Anda akan memilih langkah selanjutnya. Kebanyakan orang akan memilih langkah yang akan memberi mereka poin terbanyak, bukan? Atau jika mereka berpikir ke depan, mereka akan memilih langkah yang akan membuat situasi di mana mereka bisa mendapatkan lebih banyak poin. Cara berpikir yang terakhir adalah cara bagaimana Algoritma Minimax berpikir. Itu melihat ke depan untuk semua pengaturan papan di masa depan dan membuat langkah yang akan menghasilkan poin terbanyak.

Saya menyebut ini sebagai algoritma lacak balik, karena ini dimulai dengan membuat dan mengevaluasi semua status papan masa depan dengan nilai terkaitnya terlebih dahulu. Ini berarti bahwa algoritme akan memainkan game sebanyak yang diperlukan (membuat gerakan untuk dirinya sendiri dan lawan) hingga setiap skenario game telah dimainkan. Untuk melacak semua status papan (skenario), kita dapat menggambar pohon (lihat di gambar). Pohon pada gambar di atas adalah contoh sederhana dari permainan Connect 4. Setiap konfigurasi papan disebut status papan dan tempatnya di pohon disebut simpul. Semua simpul di bagian bawah pohon adalah status papan terakhir setelah melakukan semua gerakan. Jelas beberapa status papan lebih baik untuk satu pemain daripada yang lain. Jadi, sekarang kita harus membuat AI memilih status papan mana yang ingin dicapai.

Langkah 4: Minimax: Mengevaluasi Konfigurasi Papan

Untuk memberi nilai pada status papan, kita harus mempelajari strategi permainan yang kita mainkan: dalam hal ini, strategi Othello. Karena permainan ini adalah pertempuran membalik cakram lawan dan Anda, posisi cakram terbaik adalah yang stabil dan tidak dapat dibalik. Pojok, misalnya, adalah tempat di mana ketika disk diletakkan tidak dapat diubah ke warna lain. Dengan demikian, tempat itu akan sangat berharga. Posisi bagus lainnya termasuk sisi papan yang memungkinkan Anda mengambil banyak batu. Ada lebih banyak strategi di situs web ini.

Sekarang kita dapat menetapkan nilai ke posisi untuk setiap papan negara bagian. Ketika suatu posisi ditempati oleh bidak AI, maka Anda memberikan sejumlah poin tergantung pada posisinya. Misalnya, keadaan papan di mana bidak AI berada di pojok, Anda dapat memberikan bonus 50 poin, tetapi jika berada di tempat yang tidak menguntungkan, bidak tersebut mungkin bernilai 0. Setelah memperhitungkan semua nilai posisi, Anda menetapkan nilai papan negara. Misalnya, jika AI memiliki bidak di sudut, status papan dapat memiliki skor 50 sementara status papan lain dengan bidak AI di tengah memiliki skor 10.

Ada banyak cara untuk melakukan ini, dan saya memiliki tiga heuristik berbeda untuk mengevaluasi potongan papan. Saya mendorong Anda untuk membuat jenis heuristik Anda sendiri. Saya mengunggah tiga AI berbeda ke github saya oleh tiga pembuat berbeda, dengan tiga heuristik berbeda: Puma.py, erika5.py, nathanh.py.

Langkah 5: Algoritma Minimax: Memilih Langkah Terbaik

Nah alangkah baiknya jika AI bisa saja memilih semua jurus untuk sampai ke board state dengan skor tertinggi. Tapi ingat bahwa AI juga memilih gerakan untuk lawan ketika menghasilkan semua status papan dan jika lawannya pintar, itu tidak akan memungkinkan AI untuk mencapai skor papan tertinggi. Sebaliknya, lawan yang cerdas akan membuat langkah untuk membuat AI pergi ke status papan terendah. Dalam algoritme, kami menyebut dua pemain sebagai pemain yang memaksimalkan dan pemain yang meminimalkan. AI akan menjadi pemain yang memaksimalkan karena ingin mendapatkan poin terbanyak untuk dirinya sendiri. Lawan akan menjadi pemain yang meminimalkan karena lawan mencoba melakukan gerakan di mana AI mendapat poin paling sedikit.

Setelah semua status papan dihasilkan dan nilai telah ditetapkan ke papan, algoritme mulai membandingkan status papan. Dalam gambar, saya membuat pohon untuk mewakili bagaimana algoritma akan memilih gerakannya. Setiap perpecahan di cabang adalah gerakan berbeda yang bisa dimainkan AI atau lawan. Di sebelah kiri baris node, saya menulis apakah pemain memaksimalkan atau meminimalkan. Baris bawah adalah semua status papan dengan nilainya. Di dalam masing-masing simpul itu ada angka dan itu adalah skor yang kami tetapkan untuk masing-masing papan: semakin tinggi mereka, semakin baik untuk dimiliki AI.

Definisi: simpul induk - simpul yang menghasilkan atau membuat simpul di bawahnya; asal dari simpul anak - simpul yang berasal dari simpul induk yang sama

Node kosong mewakili gerakan mana yang akan dilakukan AI untuk mencapai status papan terbaik. Ini dimulai dengan membandingkan anak-anak dari simpul paling kiri: 10, -3, 5. Karena pemain yang memaksimalkan akan membuat langkah, ia akan memilih langkah yang akan memberikan poin paling banyak: 10. Jadi, kami kemudian memilih dan menyimpannya bergerak dengan skor papan dan tulis di simpul induk. Sekarang 10 ada di simpul induk, sekarang giliran pemain yang meminimalkan. Namun, node yang akan kita bandingkan 10 kosong, jadi kita harus mengevaluasi node tersebut terlebih dahulu sebelum pemain yang meminimalkan dapat memilih. Jadi kita kembali ke giliran pemain yang memaksimalkan dan membandingkan anak-anak dari simpul yang berdekatan: 8, -2. Memaksimalkan akan memilih 8 dan kami menulisnya di simpul induk yang kosong. Sekarang setelah algoritme selesai mengisi ruang kosong untuk anak-anak dari simpul di atasnya, pemain yang meminimalkan dapat membandingkan anak-anak tersebut - 10 dan 8 dan memilih 8. Algoritme kemudian mengulangi proses ini hingga seluruh pohon terisi. Di akhir contoh ini, kita mendapatkan skor 8. Itu adalah status papan tertinggi yang bisa dimainkan AI dengan asumsi lawan bermain secara optimal. Jadi AI akan memilih langkah pertama yang mengarah ke status papan 8, dan jika lawan bermain optimal, AI harus memainkan semua gerakan untuk sampai ke status papan 8. (Ikuti catatan pada gambar saya)

Aku tahu itu banyak. Jika Anda adalah salah satu dari tipe orang yang membutuhkan seseorang untuk berbicara dengan Anda untuk memahami sesuatu, berikut adalah beberapa video yang saya tonton untuk membantu saya memahami ide di balik ini: 1, 2, 3.

Langkah 6: Algoritma Minimax: Pseudocode

Setelah Anda memahami logika di balik algoritma minimax, lihat pseudocode ini (fungsi yang universal untuk semua kode) dari wikipedia:

fungsi minimax(node, depth, maximizingPlayer) adalah

jika kedalaman = 0 atau simpul adalah simpul terminal maka

mengembalikan nilai heuristik dari node

jika memaksimalkan Player maka

nilai:=

untuk setiap anak dari simpul do

nilai:= max(nilai, minimax(anak, kedalaman 1, FALSE))

mengembalikan nilai

lain (* meminimalkan pemain *)

nilai:= +∞

untuk setiap anak dari simpul do

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

mengembalikan nilai

Ini adalah fungsi rekursif, artinya ia memanggil dirinya sendiri berulang-ulang hingga mencapai titik berhenti. Pertama, fungsi mengambil tiga nilai, simpul, kedalaman, dan giliran siapa. Nilai node adalah tempat di mana Anda ingin program mulai mencari. Kedalaman adalah seberapa jauh Anda ingin program mencari. Misalnya, dalam contoh pohon saya memiliki kedalaman 3, karena mencari semua status papan setelah 3 gerakan. Tentu saja, kami ingin AI memeriksa setiap status papan dan memilih kemenangan yang menang, tetapi di sebagian besar game di mana terdapat ribuan atau bahkan jutaan konfigurasi papan, laptop Anda di rumah tidak akan dapat memproses semua konfigurasi tersebut. Jadi, kami membatasi kedalaman pencarian AI dan membuatnya mencapai status papan terbaik.

Pseudocode ini mereproduksi proses yang saya jelaskan di dua langkah sebelumnya. Sekarang mari kita selangkah lebih maju dan memperbaiki ini dalam kode python.

Langkah 7: Membuat AI Anda Dengan Ai_template.py

Sebelum melihat kode AI Minimax saya, coba buat AI Anda sendiri dengan file ai_template.py dan kode semu yang kita bicarakan di langkah terakhir. Ada dua fungsi dalam template ai yang disebut: def minimax_min_node(board, color) dan def minimax_max_node(board, color). Alih-alih memiliki fungsi minimax memanggil dirinya sendiri secara rekursif, kami memiliki dua fungsi berbeda, yang saling memanggil. Untuk membuat heuristik untuk mengevaluasi status papan, Anda harus membuat fungsi Anda sendiri. Ada fungsi premade di file othello_shared.py yang dapat Anda gunakan untuk membangun AI Anda.

Setelah Anda memiliki AI, coba jalankan melawannya, randy_ai.py. Untuk menjalankan dua ais satu sama lain, ketik "python othello_gui.py (masukkan nama file ai).py (masukkan nama file).py" di terminal mac atau ketik "run othello_gui.py (masukkan nama file ai).py (masukkan nama file).py" dan pastikan Anda berada di direktori yang benar. Juga, lihat video saya untuk langkah-langkah yang tepat.

Langkah 8: Saatnya Membuat AI Fight

Sekarang dapatkan banyak teman komputer Anda dan buat mereka mendesain AI mereka sendiri! Kemudian Anda dapat membuat kompetisi dan membuat AI Anda mengalahkannya. Semoga, meskipun Anda tidak dapat membuat AI sendiri, Anda dapat memahami cara kerja algoritme minimax. Jika Anda memiliki pertanyaan, jangan ragu untuk memposting pertanyaan apa pun di komentar di bawah.