AI permainan – minimax dan pemangkasan alfa-beta pada tic-tac-toe

InformatikaData, AI, dan pembelajaran mesinUsia 17–18

Gunakan di kelas saya

Mainkan tic-tac-toe melawan AI yang menelusuri pohon permainan dengan minimax. Tampilan pohon menunjukkan setiap langkah yang dipertimbangkan AI, skor yang diberikan minimax, dan berapa banyak posisi di bawahnya; buka sebuah cabang untuk mengikuti pencarian ke bawah. Aktifkan pemangkasan alfa-beta untuk melihat cabang dipangkas tanpa mengubah langkah, bandingkan jumlah posisi yang ditelusuri, dan turunkan batas kedalaman agar AI bermain cukup lemah untuk dikalahkan.

Pelajaran: Kecerdasan buatan dalam permainan: pohon permainan, minimax, pencarian dengan batas kedalaman, fungsi evaluasi, dan pemangkasan alfa-beta

Yang ditunjukkan

Program permainan dapat melihat ke depan: ia mencoba setiap langkah, setiap balasan, dan seterusnya, sehingga terbentuk pohon permainan. Minimax memberi skor pada posisi akhir (menang, kalah, atau seri) lalu meneruskan skor itu ke atas pohon: pemain yang mendapat giliran memilih skor terbaik baginya, dengan anggapan lawan berbuat sama. Tic-tac-toe cukup kecil untuk ditelusuri sampai habis, sehingga AI dengan kedalaman penuh tidak pernah kalah. Permainan sungguhan tidak demikian, jadi program berhenti pada batas kedalaman dan memperkirakan nilai posisi. Pemangkasan alfa-beta melewati cabang yang tidak dapat mengubah pilihan, sehingga menghasilkan langkah yang sama dengan jauh lebih sedikit posisi yang ditelusuri.

Cara menggunakan

Ketuk sebuah kotak untuk melangkah; AI akan membalas. Pohon menampilkan pilihan AI beserta skornya: ketuk salah satunya untuk membuka cabangnya, lalu gunakan ▲ Naik atau ⤒ Puncak pohon untuk kembali. Centang Pemangkasan alfa-beta untuk membandingkan. Turunkan Batas kedalaman, atau pilih Skor pada batas kedalaman, untuk melemahkan AI. Telusuri posisi ini menampilkan pilihan Anda sendiri.

Parameter yang dapat diubah

  • Anda bermain X (pertama), O (kedua)
  • Batas kedalaman (langkah ke depan) 1–9
  • Skor pada batas kedalaman 0 (tak diketahui), Garis terbuka
  • Pemangkasan alfa-beta

Pertanyaan untuk dijelajahi

  1. Pada batas kedalaman 9, mengapa AI tidak pernah kalah, di kotak mana pun Anda mulai?
  2. Kotak mana yang dipangkas alfa-beta lebih dulu, dan mengapa kotak itu boleh dilewati?
  3. Di bawah batas kedalaman berapa Anda dapat mengalahkan AI, dan bagaimana caranya?