Saya pikir bukan rahasia bagi siapa pun bahwa "Bodoh" (selanjutnya kata ini akan ditulis dengan huruf kecil dan tanpa tanda kutip) adalah permainan kartu paling populer di Rusia dan negara-negara bekas Uni Soviet (meskipun hampir tidak dikenal di luarnya). Terlepas dari namanya dan aturan yang cukup sederhana, memenangkannya masih lebih tergantung pada keterampilan pemain daripada pada distribusi kartu secara acak (dalam terminologi bahasa Inggris , masing-masing permainan disebut permainan keterampilan dan permainan kesempatan . Jadi - bodoh dalam lebih banyak permainan keterampilan ).
Tujuan artikel ini adalah untuk menulis AI sederhana untuk permainan. Kata "sederhana" berarti yang berikut:
- algoritma pengambilan keputusan yang intuitif (yaitu, sebagai akibatnya, tidak ada pembelajaran mesin di mana algoritma ini tersembunyi secara mendalam "di bawah tenda");
- kurangnya status (yaitu, algoritma hanya dipandu oleh data pada saat saat ini, dengan kata lain, tidak mengingat apa pun (misalnya, tidak "menghitung" kartu yang telah meninggalkan permainan).
(Sebenarnya, paragraf pertama tidak lagi memberikan hak kepada AI semacam itu untuk disebut kecerdasan buatan , tetapi hanya AI semu. Tetapi terminologi ini telah ditetapkan dalam pengembangan game, jadi kami tidak akan mengubahnya.)
Aturan permainan, saya pikir, diketahui semua orang, jadi saya tidak akan mengingatkan mereka lagi. Mereka yang ingin memeriksa, saya sarankan Anda untuk menghubungi Wikipedia , ada artikel yang cukup bagus tentang topik ini.
Jadi mari kita mulai. Jelas, pada orang bodoh, semakin tua kartunya, semakin baik untuk memilikinya di tangan Anda. Oleh karena itu, kami akan membangun algoritma pada penilaian klasik tentang kekuatan tangan dan membuat keputusan (misalnya, untuk melemparkan kartu tertentu) berdasarkan penilaian ini. Kami menetapkan nilai ke peta, misalnya, seperti ini:
- ace (A) - +600 poin,
- raja (K) - +500,
- wanita (Q) - +400,
- Jack (J) - +300,
- sepuluh (10) - +200,
- sembilan (9) - +100,
- delapan (8) - 0,
- tujuh (7) - -100,
- enam (6) - -200,
- lima (5) - -300,
- empat (4) - -400,
- tiga (3) - -500,
- dan akhirnya, deuce (2) - -600 poin.
(Kami menggunakan angka yang merupakan kelipatan dari 100 untuk menyingkirkan floating-point dalam perhitungan kami dan hanya menggunakan bilangan bulat. Untuk ini, kami memerlukan taksiran negatif, lihat di bawah dalam artikel ini.)
Kartu truf lebih berharga daripada kartu sederhana mana pun (bahkan kartu truf mengalahkan kartu as "biasa"), dan hierarki dalam kartu truf adalah sama, jadi untuk mengevaluasinya, cukup tambahkan 1.300 ke nilai "dasar" - kemudian, misalnya, truf deuce akan "berharga" -600 + 1300 = 700 poin (yaitu, hanya sedikit lebih dari kartu truf yang tidak memiliki akses).
Dalam kode (semua contoh kode dalam artikel akan berada di Kotlin), akan terlihat seperti ini (fungsi relativaCardValue() mengembalikan perkiraan yang sama, dan RANK_MULTIPLIER hanya koefisien yang sama dengan 100):
for (c in hand) { val r = c.rank val s = c.suit res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt() if (s === trumpSuit) res += 13 * RANK_MULTIPLIER
Sayangnya, bukan itu saja. Penting juga untuk mempertimbangkan aturan evaluasi berikut:
- itu menguntungkan untuk memiliki banyak kartu dengan nilai yang sama - tidak hanya karena mereka dapat "mengisi" lawan, tetapi juga dengan mudah mengusir serangan (terutama jika kartu bernilai tinggi). Sebagai contoh, pada akhir permainan, sebuah tangan (untuk kesederhanaan, kami mengasumsikan bahwa truf selanjutnya adalah rebana)
$$ menampilkan $$ \ pakaian klub 2 \ pakaian spadesuit 2 \ pakaian berlian Q \ pakaian jas Q \ pakaian klub Q \ pakaian spadesuit $ $$ menampilkan $$ hampir sempurna (tentu saja, jika lawan tidak pergi di bawah Anda dengan raja atau kartu As): Anda akan dikalahkan oleh para wanita, setelah itu menggantung saingan beri dia sepasang deuces.
tetapi banyak kartu dengan jenis yang sama (tentu saja, non-kartu truf), sebaliknya, memiliki kelemahan - kartu tersebut akan "saling mengganggu". Misalnya tangan$$ display $$ \ spadesuit 5 \ spadesuit J \ spadesuit A \ diamondsuit 6 \ diamondsuit 9 \ diamondsuit K $$ display $$ sangat disayangkan - bahkan jika lawan tidak "merobohkan" kartu truf Anda dengan gerakan pertama dan pergi dengan kartu suit puncak, maka semua kartu lain yang dibuang akan menjadi kartu lain, dan mereka harus memberikan kartu truf. Selain itu, ada kemungkinan besar bahwa demam lima akan tetap tidak diklaim - Anda memiliki semua kartu truf dengan martabat lebih tinggi dari lima, jadi dalam keadaan apa pun (kecuali, tentu saja, Anda awalnya masuk dengan kartu yang lebih muda) Anda tidak akan dapat menutupinya dengan kartu lain - sangat mungkin untuk mengambil tinggi Di sisi lain, kami mengganti jack sekop dengan sepuluh klub, dan truf enam dengan triple:
$$ display $$ \ spadesuit 5 \ klub gugus 10 \ spadesuit A \ diamondsuit 3 \ diamondsuit 9 \ diamondsuit K $$ display $$ Terlepas dari kenyataan bahwa kami mengganti kartu dengan yang lebih muda, kartu seperti itu jauh lebih baik - pertama, Anda tidak perlu memberikan kartu truf pada kartu (dan itu akan lebih mungkin menggunakan kartu as sekop), dan kedua, jika Anda mengalahkan kartu kemudian sebuah kartu dengan kartu truf tiga Anda, ada kemungkinan seseorang akan melemparkan Anda tiga sekop (karena biasanya tidak ada gunanya memegang kartu seperti itu), dan Anda akan "mendapatkan" dari kelima kartu tersebut.
Untuk menerapkan strategi ini, kami memodifikasi algoritme kami: Di sini kami mempertimbangkan jumlah kartu dari setiap kartu dan keuntungan ...
val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25) var res = 0 val countsByRank = IntArray(13) val countsBySuit = IntArray(4) for (c in hand) { val r = c.rank val s = c.suit res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt() if (s === trumpSuit) res += 13 * RANK_MULTIPLIER countsByRank[r.value - 1]++ countsBySuit[s.value]++ }
... di sini kami menambahkan bonus untuk mereka (panggilan Math.max diperlukan agar tidak menambah bonus negatif untuk kartu rendah - karena dalam hal ini juga bermanfaat) ...
for (i in 1..13) { res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt() }
... dan di sini, sebaliknya, kami setuju untuk setelan yang tidak seimbang dalam setelan (nilai UNBALANCED_HAND_PENALTY eksperimental diatur ke 200):
Akhirnya, kami memperhitungkan hal yang dangkal seperti jumlah kartu di tangan. Faktanya, memiliki 12 kartu bagus di awal permainan sangat baik (terutama karena tidak lebih dari 6 masih bisa melempar), tetapi di akhir permainan, ketika hanya ada lawan dengan 2 kartu di samping Anda, ini sama sekali tidak terjadi.
Kami merangkum - secara lengkap, fungsi evaluasi terlihat seperti ini:
private fun handValue(hand: ArrayList<Card>, trumpSuit: Suit, cardsRemaining: Int, playerHands: Array<Int>): Int { if (cardsRemaining == 0 && hand.size == 0) { return OUT_OF_PLAY } val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25)
Jadi, kami memiliki fungsi evaluasi siap. Pada bagian berikutnya, direncanakan untuk menggambarkan keputusan pengambilan tugas yang lebih menarik berdasarkan penilaian tersebut.
Terima kasih atas perhatian Anda!
PS Kode ini adalah bagian dari aplikasi yang dikembangkan oleh penulis di waktu luangnya. Ini tersedia di GitHub (rilis biner untuk Desktop dan Android, untuk yang terakhir aplikasi ini juga tersedia di F-Droid ).