Tic Tac Toe di Arduino With AI (Minimax Algorithm): 3 Langkah

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

Dalam Instructable ini saya akan menunjukkan kepada anda bagaimana membina permainan Tic Tac Toe dengan AI menggunakan Arduino. Anda boleh bermain menentang Arduino atau menonton Arduino bermain dengan sendirinya.

Saya menggunakan algoritma yang disebut "algoritma minimax", yang dapat digunakan bukan hanya untuk membangun AI untuk Tic Tac Toe, tetapi juga untuk pelbagai permainan lain seperti Four in a Row, catur atau bahkan catur. Permainan seperti catur sangat kompleks dan memerlukan versi algoritma yang jauh lebih halus. Untuk permainan Tic Tac Toe kami, kami dapat menggunakan versi algoritma termudah, yang tetap mengagumkan. Sebenarnya, AI sangat baik sehingga mustahil untuk mengalahkan Arduino!

Permainan ini senang dibina. Anda hanya memerlukan beberapa komponen dan lakaran yang telah saya tulis. Saya juga menambah penjelasan algoritma yang lebih terperinci, jika anda ingin memahami bagaimana ia berfungsi.

Langkah 1: Bangun dan Main

Untuk membina permainan Tic Tac Toe, anda memerlukan komponen berikut:

• Arduino Uno
• 9 LED WS2812 RGB
• 9 butang tekan
• beberapa kabel wayar dan pelompat

Kabelkan komponen seperti yang ditunjukkan dalam lakaran Fritzing. Kemudian muat naik kod ke Arduino anda.

Secara lalai, Arduino mengambil giliran pertama. Untuk menjadikan sesuatu menjadi lebih menarik, langkah pertama dipilih secara rawak. Selepas langkah pertama, Arduino menggunakan algoritma minimax untuk menentukan langkah terbaik. Anda memulakan permainan baru dengan menetapkan semula Arduino.

Anda boleh menonton "berfikir" Arduino dengan membuka Serial Monitor. Untuk setiap kemungkinan pergerakan, algoritma menghitung penilaian yang menunjukkan sama ada pergerakan ini akan membawa kepada kemenangan (nilai 10) atau kerugian (nilai -10) untuk Arduino atau seri (nilai 0).

Anda juga dapat menyaksikan Arduino bermain dengan sendirinya dengan melepaskan baris "#define DEMO_MODE" di awal lakaran. Sekiranya anda memuat naik lakaran yang diubah, Arduino membuat pergerakan pertama secara rawak dan kemudian menggunakan algoritma minimax untuk menentukan pergerakan terbaik bagi setiap pemain dalam setiap giliran.

Perhatikan bahawa anda tidak boleh menang melawan Arduino. Setiap permainan akan berakhir seri atau anda kalah, jika anda melakukan kesalahan. Ini kerana algoritma selalu memilih langkah terbaik. Seperti yang anda ketahui, permainan Tic Tac Toe akan selalu berakhir seri jika kedua-dua pemain tidak melakukan kesalahan. Dalam mod demo, setiap permainan berakhir seri kerana, seperti yang kita semua tahu, komputer tidak pernah melakukan kesalahan;-)

Langkah 2: Algoritma Minimax

Algoritma terdiri daripada dua komponen: fungsi penilaian dan strategi pencarian. Fungsi penilaian adalah fungsi yang memberikan nilai berangka ke kedudukan papan. Sekiranya kedudukan adalah kedudukan terakhir (iaitu, kedudukan di mana pemain biru atau pemain merah telah menang atau di mana tidak ada pemain yang menang), fungsi penilaiannya sangat mudah: Katakanlah Arduino bermain biru dan pemain manusia bermain merah. Sekiranya kedudukan itu adalah posisi menang untuk warna biru, fungsi memberikan nilai 10 ke kedudukan itu; jika kedudukan menang merah, fungsi memberikan nilai -10 ke kedudukan; dan jika kedudukannya adalah seri, fungsi memberikan nilai 0.

Apabila tiba giliran Arduino, ia ingin memilih langkah yang memaksimumkan nilai fungsi penilaian, kerana memaksimumkan nilai itu bermaksud bahawa ia lebih suka menang atas keputusan seri (10 lebih besar daripada 0) dan membuat keputusan seri kerana kalah (0 lebih besar daripada -10). Dengan argumen yang serupa, lawan ingin bermain sedemikian rupa sehingga dia meminimumkan nilai fungsi penilaian.

Untuk kedudukan bukan akhir, algoritma mengira nilai fungsi penilaian dengan strategi carian rekursif. Bermula dari kedudukan sekarang, secara bergantian mensimulasikan semua pergerakan yang dapat dilakukan oleh pemain biru dan pemain merah. Ini dapat dilihat sebagai pokok, seperti dalam rajah. Apabila tiba di posisi akhir, ia mulai mundur, membawa nilai fungsi penilaian dari tahap rekursi yang lebih rendah ke tahap rekursi yang lebih tinggi. Ia memberikan nilai maksimum (jika dalam langkah rekursi yang sesuai adalah giliran pemain biru) atau minimum (jika dalam langkah rekursi yang sesuai itu adalah giliran pemain merah) nilai fungsi penilaian dari tahap rekursi bawah ke posisi di tahap rekursi yang lebih tinggi. Akhirnya, apabila algoritma selesai melangkah mundur dan kembali ke kedudukan semasa, ia mengambil langkah (atau salah satu pergerakan) yang mempunyai nilai fungsi penilaian maksimum.

Ini mungkin terdengar agak abstrak, tetapi sebenarnya tidak begitu sukar. Pertimbangkan kedudukan yang ditunjukkan di bahagian atas rajah. Pada langkah rekursi pertama, terdapat tiga gerakan biru yang boleh dilakukan. Biru cuba memaksimumkan nilai fungsi penilaian. Untuk setiap pergerakan yang boleh dilakukan biru, ada dua pergerakan yang boleh dilakukan oleh warna merah. Red cuba meminimumkan nilai fungsi penilaian. Pertimbangkan pergerakan di mana biru bermain di sudut kanan atas. Sekiranya merah bermain di kotak tengah, merah telah menang (-10). Sekiranya, sebaliknya, warna merah bermain di kotak bawah tengah, biru akan menang pada langkah seterusnya (10). Jadi, jika warna biru bermain di sudut kanan atas, warna merah akan bermain di kotak tengah, kerana ini meminimumkan nilai fungsi penilaian. Secara analognya, jika warna biru bermain di kotak tengah tengah, warna merah akan kembali bermain di kotak tengah kerana ini meminimumkan fungsi penilaian. Sekiranya, sebaliknya, biru bermain di kotak tengah, tidak kira pergerakan merah yang diambil, biru akan selalu menang (10). Oleh kerana biru ingin memaksimumkan fungsi penilaian, ia akan dimainkan di kotak tengah, kerana kedudukan itu menghasilkan nilai fungsi penilaian yang lebih besar (10) daripada dua gerakan lain (-10).

Langkah 3: Penyelesaian Masalah dan Langkah Lanjut

Sekiranya anda menekan butang dan LED yang berbeza daripada yang sesuai dengan butang menyala, anda mungkin mempunyai kabel pada pin A0-A2 atau 4-6 bercampur, atau anda menyambungkan LED dengan urutan yang salah.

Perhatikan juga bahawa algoritma tidak semestinya selalu memilih langkah yang akan membolehkan Arduino menang secepat mungkin. Sebenarnya, saya meluangkan masa untuk men-debug algoritma kerana Arduino tidak memilih langkah yang akan menjadi langkah yang berjaya. Saya mengambil masa sehingga saya menyedari bahawa ia telah memilih langkah yang menjamin bahawa ia akan memenangi satu gerakan kemudian. Sekiranya anda mahu, anda boleh mengubah suai algoritma agar selalu memilih langkah menang daripada kemenangan kemudian.

Kemungkinan pengembangan projek ini adalah menggunakan algoritma untuk membina AI untuk 4x4 atau bahkan 5x5 Tic Tac Toe. Walau bagaimanapun, perhatikan bahawa bilangan kedudukan yang perlu dikaji oleh algoritma berkembang dengan sangat cepat. Anda perlu mencari cara untuk menjadikan penilaian berfungsi lebih cerdas dengan menetapkan nilai pada kedudukan yang tidak muktamad, berdasarkan kemungkinan kedudukan itu baik atau buruk bagi pemain yang dimaksudkan. Anda mungkin juga berusaha menjadikan carian lebih cerdas dengan menghentikan pengulangan lebih awal jika langkah itu ternyata kurang layak untuk diterokai lebih jauh daripada gerakan alternatif.

Arduino mungkin bukan platform terbaik untuk sambungan seperti itu kerana ingatannya terhad. Pengulangan membolehkan timbunan tumbuh semasa pelaksanaan program, dan jika timbunan tumbuh terlalu banyak, ia dapat merosakkan memori program, yang menyebabkan kerosakan atau tingkah laku yang tidak menentu. Saya memilih Arduino untuk projek ini terutamanya kerana saya ingin melihat apakah ia dapat dilakukan dan untuk tujuan pendidikan, bukan kerana ini adalah pilihan terbaik untuk masalah seperti ini.