Jaringan saraf vs Algoritma genetika dalam game seperti Tic Tac Toe?

9

Saat ini saya sedang melakukan proyek yang tentang membuat AI untuk memainkan game Gomoku (Ini seperti tic tac toe, tetapi dimainkan di papan 15 * 15 dan membutuhkan 5 berturut-turut untuk menang). Saya telah berhasil mengimplementasikan AI tic tac toe sempurna menggunakan pembelajaran Q dan memiliki status permainan / tindakan disimpan dalam sebuah tabel, tetapi untuk papan 15 * 15 status permainan yang mungkin menjadi terlalu besar juga mengimplementasikan proyek ini.

Pertanyaan saya adalah, haruskah saya menggunakan jaringan saraf atau algoritma genetika untuk masalah ini? Dan lebih khusus lagi, bagaimana saya harus menerapkan ini?

Conway
sumber
2
Selamat datang di AI! Pertanyaan yang sangat bagus.
DukeZhou

Jawaban:

7

Untuk gomoku, tampaknya sedikit berlebihan untuk menggunakan jaringan saraf atau algoritma genetika karena keduanya membutuhkan waktu dan lebih sering daripada tidak, jangan menuruti keinginan Anda. Pohon permainan gomoku agak besar, tetapi Anda bisa mendapatkan AI yang layak dari minimax, pemangkasan pohon permainan, dan fungsi heuristik yang baik (yang mencakup penghitungan setengah dan penuh 2s, 3s, 4s, ... dll.) Dibandingkan dengan pemetaan keluar ruang penuh.

Jika Anda tidak terbiasa dengan pemangkasan alfa beta dan minimax lihat https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

Jika Anda benar-benar ingin menggunakan jaringan saraf atau algoritma genetika Anda bisa untuk pengalaman belajar. Mengenai jaringan saraf, salah satu cara untuk melakukannya adalah sebagai berikut:

  • Tetapkan fungsi heuristik yang menerima input status papan (urutan 0,1,2 untuk kosong, hitam, putih), dan menampilkan nilai 'baik' dari status papan. Jaringan saraf adalah fungsi heuristik kami.
  • Dengan anggapan bahwa gerakan dalam permainan ini optimal, latihlah perbedaan antara gerakan terbaik saat ini (berdasarkan parameter Anda saat ini) dan apa yang dikatakan oleh data Anda adalah yang terbaik. Inilah cara kami mendefinisikan fungsi kesalahan kami! Dengan demikian Anda meminimalkan perbedaan ini sehingga apa yang dikatakan jaringan saraf Anda adalah yang terkuat adalah idealnya yang dikatakan oleh data game Anda adalah yang terkuat (Optimasi fungsi kesalahan ini dapat dilakukan melalui backpropagation atau algoritma genetika).
  • Idealnya, pada titik ini Anda sekarang dapat menggunakan fungsi evaluasi berbasis jaringan saraf ('kuat') Anda untuk evaluasi pemindahan game Anda alih-alih heuristik hardcoded.

Tentu saja ini hanya satu cara, dan Anda harus mencari data gim terlebih dahulu.

Catatan tambahan, penerapan algoritma genetika dapat terjadi dalam beberapa cara, seperti optimasi parameter dalam jaringan saraf seperti yang disebutkan di atas atau pencarian pohon permainan jadi pastikan Anda jelas bagaimana Anda mendefinisikan pengaturan masalah dengan itu! Hal yang sama berlaku untuk cara-cara alternatif untuk menerapkan jaringan saraf.

Akhirnya, sangat membantu untuk mengetahui gomuku terpecahkan. Lihat /programming/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe untuk pemikiran dan ide orang lain.

sma
sumber
2
Poin bagus tentang gomoku sebagai game yang diselesaikan. Ini membuatnya mudah untuk memvalidasi kekuatan AI (yaitu apakah ia menyelesaikan permainan dan mengekspresikan permainan yang sempurna, atau apakah itu hanya bermain lebih optimal daripada lawan, seperti dalam kasus AlphaGo.)
DukeZhou