Tic Tac Toe di Arduino Dengan AI (Algoritma Minimax): 3 Langkah

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

Dalam Instructable ini saya akan menunjukkan kepada Anda bagaimana membangun game Tic Tac Toe dengan AI menggunakan Arduino. Anda bisa bermain melawan Arduino atau menonton Arduino bermain melawan dirinya sendiri.

Saya menggunakan algoritma yang disebut "algoritma minimax", yang dapat digunakan tidak hanya untuk membangun AI untuk Tic Tac Toe, tetapi juga untuk berbagai permainan lain seperti Four in a Row, catur atau bahkan catur. Permainan seperti catur sangat kompleks dan membutuhkan versi algoritma yang jauh lebih halus. Untuk permainan Tic Tac Toe kami, kami dapat menggunakan versi algoritma yang paling sederhana, yang tetap saja cukup mengesankan. Faktanya, AI sangat bagus sehingga tidak mungkin untuk mengalahkan Arduino!

Permainan ini mudah dibangun. Anda hanya membutuhkan beberapa komponen dan sketsa yang sudah saya tulis. Saya juga menambahkan penjelasan algoritma yang lebih rinci, jika Anda ingin memahami cara kerjanya.

Langkah 1: Bangun dan Mainkan

Untuk membuat game Tic Tac Toe, Anda memerlukan komponen berikut:

• Arduino Uno
• 9 WS2812 RGB LED
• 9 tombol tekan
• beberapa kabel dan kabel jumper

Pasang komponen seperti yang ditunjukkan pada sketsa Fritzing. Kemudian unggah kode ke Arduino Anda.

Secara default, Arduino mengambil giliran pertama. Untuk membuat segalanya sedikit lebih menarik, langkah pertama dipilih secara acak. Setelah langkah pertama, Arduino menggunakan algoritma minimax untuk menentukan langkah terbaik. Anda memulai permainan baru dengan mengatur ulang Arduino.

Anda dapat menonton Arduino "berpikir" dengan membuka Serial Monitor. Untuk setiap langkah yang mungkin, algoritme menghitung peringkat yang menunjukkan apakah langkah ini akan menghasilkan kemenangan (nilai 10) atau kerugian (nilai -10) untuk Arduino atau seri (nilai 0).

Anda juga dapat melihat Arduino bermain melawan dirinya sendiri dengan menghapus komentar pada baris "#define DEMO_MODE" di awal sketsa. Jika Anda mengunggah sketsa yang dimodifikasi, Arduino membuat langkah pertama secara acak dan kemudian menggunakan algoritma minimax untuk menentukan langkah terbaik untuk setiap pemain di setiap giliran.

Perhatikan bahwa Anda tidak bisa menang melawan Arduino. Setiap pertandingan akan berakhir seri atau Anda kalah, jika Anda melakukan kesalahan. Ini karena algoritma selalu memilih langkah terbaik. Seperti yang Anda ketahui, permainan Tic Tac Toe akan selalu berakhir seri jika kedua pemain tidak melakukan kesalahan. Dalam mode demo, setiap pertandingan berakhir seri karena, seperti yang kita semua tahu, komputer tidak pernah membuat kesalahan;-)

Langkah 2: Algoritma Minimax

Algoritma terdiri dari dua komponen: fungsi evaluasi dan strategi pencarian. Fungsi evaluasi adalah fungsi yang memberikan nilai numerik ke posisi papan. Jika posisinya adalah posisi akhir (yaitu, posisi di mana pemain biru atau pemain merah telah menang atau di mana tidak ada pemain yang menang), fungsi evaluasinya sangat sederhana: Katakanlah Arduino bermain biru dan pemain manusia bermain merah. Jika posisinya adalah posisi pemenang untuk warna biru, fungsi memberikan nilai 10 ke posisi itu; jika itu adalah posisi pemenang untuk warna merah, fungsi memberikan nilai -10 ke posisi tersebut; dan jika posisinya seri, fungsi memberikan nilai 0.

Ketika giliran Arduino, ia ingin memilih langkah yang memaksimalkan nilai fungsi evaluasi, karena memaksimalkan nilai berarti lebih memilih menang daripada seri (10 lebih besar dari 0) dan lebih memilih seri daripada kalah (0 lebih besar dari -10). Dengan argumen analog, lawan ingin bermain sedemikian rupa sehingga dia meminimalkan nilai fungsi evaluasi.

Untuk posisi non-final, algoritma menghitung nilai fungsi evaluasi dengan strategi pencarian rekursif. Mulai dari posisi saat ini, secara bergantian mensimulasikan semua gerakan yang dapat dilakukan oleh pemain biru dan pemain merah. Ini dapat divisualisasikan sebagai pohon, seperti pada diagram. Ketika tiba di posisi akhir, ia mulai melangkah mundur, membawa nilai fungsi evaluasi dari tingkat rekursi yang lebih rendah ke tingkat rekursi yang lebih tinggi. Ini menetapkan maksimum (jika dalam langkah rekursi yang sesuai giliran pemain biru) atau minimum (jika dalam langkah rekursi yang sesuai giliran pemain merah) dari nilai-nilai fungsi evaluasi dari tingkat rekursi yang lebih rendah ke posisi di tingkat rekursi yang lebih tinggi. Terakhir, ketika algoritma telah selesai melangkah mundur dan telah sampai pada posisi saat ini lagi, dibutuhkan langkah itu (atau salah satu gerakan) yang memiliki nilai fungsi evaluasi maksimum.

Ini mungkin terdengar agak abstrak, tetapi sebenarnya tidak terlalu sulit. Pertimbangkan posisi yang ditunjukkan di bagian atas diagram. Pada langkah rekursi pertama, ada tiga gerakan berbeda yang bisa dilakukan biru. Biru mencoba memaksimalkan nilai fungsi evaluasi. Untuk setiap gerakan yang bisa dilakukan biru, ada dua gerakan yang bisa dilakukan merah. Merah mencoba meminimalkan nilai fungsi evaluasi. Pertimbangkan langkah di mana biru bermain di sudut kanan atas. Jika merah bermain di kotak tengah, merah menang (-10). Sebaliknya, jika merah bermain di kotak tengah bawah, biru akan menang di langkah berikutnya (10). Jadi, jika biru bermain di pojok kanan atas, merah akan bermain di kotak tengah, karena itu meminimalkan nilai fungsi evaluasi. Analoginya, jika biru bermain di kotak tengah bawah, merah akan kembali bermain di kotak tengah karena itu meminimalkan fungsi evaluasi. Sebaliknya, jika biru bermain di kotak tengah, tidak peduli langkah mana yang diambil merah, biru akan selalu menang (10). Karena biru ingin memaksimalkan fungsi evaluasi, ia akan bermain di kotak tengah, karena posisi itu menghasilkan nilai fungsi evaluasi yang lebih besar (10) daripada dua gerakan lainnya (-10).

Langkah 3: Pemecahan Masalah dan Langkah Selanjutnya

Jika Anda menekan tombol dan LED yang berbeda dari yang sesuai dengan tombol menyala, Anda mungkin memiliki kabel pada pin A0-A2 atau 4-6 yang tercampur, atau Anda menghubungkan LED dengan urutan yang salah.

Perhatikan juga bahwa algoritme tidak selalu memilih langkah yang akan membuat Arduino menang secepat mungkin. Sebenarnya, saya menghabiskan beberapa waktu untuk men-debug algoritma karena Arduino tidak memilih langkah yang akan menjadi langkah yang menang. Butuh beberapa waktu sampai saya menyadari bahwa itu malah memilih langkah yang menjamin bahwa itu akan memenangkan satu langkah nanti. Jika Anda mau, Anda dapat mencoba memodifikasi algoritme sehingga selalu lebih memilih langkah yang menang daripada kemenangan berikutnya.

Perpanjangan yang mungkin dari proyek ini adalah menggunakan algoritme untuk membangun AI untuk 4x4 atau bahkan 5x5 Tic Tac Toe. Namun, perhatikan bahwa jumlah posisi yang perlu diperiksa algoritme tumbuh sangat cepat. Anda perlu menemukan cara untuk membuat fungsi evaluasi lebih cerdas dengan menetapkan nilai ke posisi yang belum final, berdasarkan kemungkinan posisi itu baik atau buruk bagi pemain yang bersangkutan. Anda mungkin juga mencoba membuat pencarian lebih cerdas dengan menghentikan rekursi lebih awal jika suatu gerakan ternyata kurang layak untuk dieksplorasi lebih lanjut daripada gerakan alternatif.

Arduino mungkin bukan platform terbaik untuk ekstensi semacam itu karena memorinya yang terbatas. Rekursi memungkinkan tumpukan tumbuh selama eksekusi program, dan jika tumpukan tumbuh terlalu banyak, dapat merusak memori program, menyebabkan crash atau perilaku tidak menentu. Saya memilih Arduino untuk proyek ini terutama karena saya ingin melihat apakah itu bisa dilakukan dan untuk tujuan pendidikan, bukan karena itu pilihan terbaik untuk masalah semacam ini.