Bagaimana cara mengimplementasikan AI untuk checker / draft?

Oh saya suka game-game ini!

Jadi hal pertama yang pertama, agar komputer dapat memainkan permainan, dibutuhkan:

sebuah struktur untuk dikerjakan
aturan mainnya
kondisi menang untuk bekerja menuju

Mari kita selesaikan ini satu per satu.

Struktur

Karena papan adalah kisi 8x8 (tetapi dapat dengan mudah skala), dan setiap ruang kisi mungkin hanya ada di satu dari lima negara, mari kita mendefinisikan negara-negara:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Masing-masing ENUM ingin:

[0, 1, 2, 3, 4]

Sekarang kita tahu apa ruang masing-masing kita perlu beberapa cara untuk mewakili semua ruang, atau papan jika Anda mau. Hampir setiap bahasa yang kuat akan mendukung array multi-dimensi (array di mana setiap elemen adalah array yang menyimpan data). Jadi, ambil slack-code berikut untuk mendefinisikan array kami:

BOARD_ARRAY = array(8, 8)

Ini akan memberi kita array 8 x 8 di mana kita dapat menyimpan integer (enum kita dari sebelumnya):

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

Sekarang Anda sudah dapat melihat bagaimana ini mulai terlihat seperti papan! Saya belum pernah memainkan varian yang disebutkan dalam video youtube tetapi tampaknya mulai dengan 2 baris potongan putih satu baris dari bawah, dan 2 baris potongan hitam satu baris dari atas. Yang artinya ketika kita memulai game, array kita akan terlihat seperti ini:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(Ingat 2 mewakili 'BLACK_PIECE' dan 1 mewakili 'WHITE_PIECE')

Jadi sekarang komputer memiliki struktur untuk dikerjakan. Langkah 1 selesai!

Aturan

Mari kita bayangkan Anda memiliki papan yang sebenarnya dipasang di depan Anda, bermain melawan pemain utama. Jika Anda mencoba memindahkan salah satu bagiannya, tangan Anda akan ditampar. Jika Anda mencoba untuk memindahkan bagian dengan cara yang tidak bisa Anda lakukan, tangan Anda akan ditampar. Jika Anda mencoba menipu dengan baik ... Anda mendapatkan idenya. Tetapi masalahnya adalah, komputer tidak. Jadi tugas kita adalah memberikan aturan ketat untuk bermain di dalamnya.

Kita perlu menciptakan cara untuk memeriksa apakah langkah yang diberikan adalah 'sah'. Yang berarti pertama-tama kita perlu beberapa cara untuk mewakili suatu 'langkah'. Salah satu caranya adalah dengan menggunakan posisi array; Misalnya untuk memindahkan bagian dari [0, 0] ke [0, 1], kita dapat membuat fungsi yang akan memperbarui papan yang diberikan langkah itu. Jadi kembali kendur:

MY_MOVE = array( [0, 0], [0, 1] )

Di atas mewakili satu bagian, bergerak satu ruang ke bawah dari sudut atas papan (dengan asumsi 0, 0 adalah sudut kiri atas). Anda juga dapat memperhatikan bahwa saya memilih untuk menggunakan array multidimensi untuk perpindahan. Ini karena potongan-potongan secara teoritis dapat bergerak banyak kali dalam satu putaran (untuk 'melompat' potongan lainnya). Jadi mari kita berpura-pura pada 0, 1 ada bagian lawan, yang berarti kita akan mendarat di 0, 2:

MY_MOVE = array( [0, 0], [0, 2] )

Cukup sederhana, eh. Program harus memahami bahwa jika kita melewatkan ruang kita melompat bagian lain (atau itu langkah ilegal, dan harus membuang kesalahan). Sekarang mari kita lompati dua bagian:

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Ini memberi kita cara untuk menggambarkan langkah apa pun di papan tulis. Yay! Sekarang karena saya tidak sepenuhnya memahami aturan-aturan permainan yang dimaksud (walaupun saya telah memainkan sedikit permainan catur Kanada di zaman saya), legalitas gerakan yang tepat harus ditentukan oleh Anda. Aliran yang baik hingga titik ini akan terlihat seperti:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

Di atas mengasumsikan Anda dapat menelusuri setiap bagian untuk menemukan semua langkah hukum itu, kemudian diberi koleksi semua langkah hukum entah bagaimana memilih yang terbaik (strategi di sini). Langkah ini kemudian diterapkan ke papan, atau melempar kesalahan. Kemudian pemain berikutnya mengambil giliran mereka. Jadi kami memiliki AI yang tahu cara bermain! Kegembiraan! Bergerak.

Kemenangan

Permainan sederhana itu luar biasa, karena menang ditentukan oleh keadaan yang sangat sederhana. Bukankah tidak ada potongan putih di papan tulis? Yah saya kira Anda sudah menang! Ini diimplementasikan pada langkah 2 ketika kita memilih langkah terbaik untuk membawa kita lebih dekat ke kondisi menang.

Untuk membuat AI yang sangat cerdas, Anda bisa menyimpan basis data yang menyimpan setiap papan yang mungkin sebagai keadaan, dengan setiap gerakan yang mungkin dari setiap keadaan yang mungkin, untuk menemukan rantai menuju kemenangan.

Anda juga dapat membuat strategi, seperti: jika ada bagian yang AKAN dilompati, simpan bagian itu atau jika bagian tersebut mampu melompat lebih dari satu bagian lainnya lakukan lompatan itu.

Itu seharusnya memberi Anda titik lompatan yang baik, itu hanya satu metode kemungkinan yang tidak terbatas secara harfiah. Anda secara teoritis bisa membuat robot raksasa untuk menggambar dengan krayon kemudian melakukan analisis spektral pada gambar untuk memilih gerakan ... tetapi itu tidak akan bekerja dengan sangat baik, atau cepat. Cara ini telah berhasil di masa lalu, dan bekerja dengan baik (: Harapan itu membantu!

Beberapa Kata Pada Implementasi

Checker adalah apa yang disebut sebagai permainan 'terpecahkan', karena kita dapat menghitung setiap gerakan tanpa diketahui. Tapi itu pukulan total! Jadi tidak ada cara untuk melakukan semuanya secara manual ... jika hanya ada beberapa ... oh benar kami programmer. pompa tinju

SQL adalah alat yang luar biasa untuk menyimpan semua gerakan yang tampaknya tak ada habisnya ini. Bagi mereka yang tidak memiliki pengalaman dengan SQL, mySQL adalah server SQL sumber terbuka gratis (cukup mudah digunakan). SQL digunakan untuk mengelola basis data, seperti spreadsheet tentang steroid. Ia juga mampu menyimpan data dalam jumlah besar dan bekerja sangat cepat.

Jadi bagaimana kita bisa menggunakan ini? Karena kita tahu bahwa jika papan dalam keadaan yang tepat (masing-masing bagian dalam posisi tertentu) kita dapat menghitung semua gerakan yang tersedia, dan menyimpannya. Sebagai contoh:

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

Jadi, ketika komputer perlu bergerak, ia hanya melihat keadaan papan (disimpan sebagai kunci utama) dalam database, dan dapat memilih langkah terbaik (harus tidak terkalahkan) atau salah satu langkah lain untuk membuat lebih ramah AI.

Hebat sekarang mari kita membangun database ini. Pertama, kita perlu menghitung setiap status dewan. Yang bisa dilakukan dengan lingkaran besar yang tidak menyenangkan, jika seseorang ingin meluangkan waktu dan menyelesaikannya, itu akan luar biasa. Lihatlah array sebagai satu angka besar, lalu hitung ke atas, kecuali di base 5 (0, 1, 2, 3, 4), dan syarat bahwa setiap pemain hanya boleh memiliki 16 buah.

Pada titik ini kita harus menyimpan semua status papan dan dapat menghitung semua gerakan yang mungkin.

Setelah semua gerakan yang mungkin dihitung muncul bagian yang menyenangkan dari merintis jalan gerakan terbaik yang mungkin. Di sinilah pengetahuan saya mulai gagal, dan hal-hal seperti Minimax atau A * mulai ikut bermain. Maaf saya tidak bisa membantu lebih dari itu: /

Adrian Seeley
sumber

Anda melakukan banyak upaya ke pos itu yang mengagumkan. Namun Anda tidak menjawab pertanyaan tentang bagaimana menerapkan AI. Jika Anda dapat menguraikan sedikit tentang itu (atau memberikan tautan yang sesuai) jawaban Anda akan pantas mendapatkan beberapa upvotes :)

bummzack

Rumit dengan cara apa? (Saya akan lebih dari bahagia juga) Hanya ingin memastikan saya berada di halaman yang sama. Menerapkannya ke dalam model MVC, atau? dalam konteks apa? Baik dengan konsep, tidak begitu baik dengan kata-kata untuk mereka.

Adrian Seeley

Apa yang saya maksudkan adalah sesuatu yang sejalan dengan apa yang diposting CiscoIPPhone ... bagaimana sebenarnya mengimplementasikan AI sehingga itu benar-benar bermain melawan Anda :)

bummzack

+1 untuk upaya Anda. Iya nih. Saya akan sangat tertarik untuk memiliki logika AI yang sebenarnya juga terutama dari sudut pandang implementasi.

Legenda

Ahh, gotchya, saya akan menulis itu sekarang, satu-satunya cara saya melakukannya, adalah dengan database SQL ... jadi kita akan melihat bagaimana ini ternyata ...