Teknik terbaik untuk AI permainan kartu

Saya mencoba mengembangkan AI untuk permainan kartu dan saya agak terjebak tentang teknik / algoritma yang harus saya gunakan. Berikut adalah beberapa asumsi tentang permainan:

• Setelah kartu dibagikan kepada pemain, tidak ada keacakan. Maksud saya di sini bahwa setiap pemain dapat memilih kartu mana yang dia mainkan tetapi tidak ada proses acak yang terjadi ketika mendistribusikan kartu pada awal permainan.
• Ada batasan tentang kartu yang dapat dimainkan ketika kartu sudah dimainkan.
• Pemain yang memenangkan trik, bermain terlebih dahulu. Misalnya Player 1 memainkan kartu, Player 2 memainkan kartu dan menang. Kemudian Player 2 memainkan kartu dan kemudian Player 1 memainkan.

Saya tahu banyak petunjuk / aturan (misalnya jika saya tahu pemain memiliki kartu A, B, C maka saya harus bermain D) yang membantu saya untuk menang ke permainan. Jadi saya pertama-tama ingin menggunakan jaringan Bayesian untuk menjelaskan aturan-aturan itu. Masalahnya adalah bahwa saya tidak tahu probabilitas untuk ditugaskan, tetapi saya bisa menghitung heuristik menggunakan sejarah game yang dimainkan (melawan manusia). Masalah kedua, sangat mungkin saya tidak tahu semua aturan dan ada beberapa aturan implisit yang dibutuhkan oleh AI untuk menemukan permainan yang optimal.

Saya tidak yakin apakah ini akan menjadi cara yang baik untuk mengembangkan AI untuk permainan kartu seperti itu?

Saya juga bertanya-tanya apakah ada teknik lain yang paling cocok untuk masalah ini. Misalnya, saya telah melihat minimax (mungkin dengan algoritma pemangkasan), tetapi apakah akan menjadi pilihan yang baik untuk masalah ini? Saya tidak yakin karena permainan yang paling penting adalah di awal permainan ketika ada parameter tertinggi yang tidak diketahui (sebagian besar kartu belum dimainkan).

Contoh Anda terdengar mirip dengan Bridge . Sistem Bridge-playing terbaik menggunakan metode Monte Carlo untuk memilih gerakan. Pada level tinggi:

• Tentukan probabilitas masing-masing kartu berada di tangan yang diberikan. Anda tahu dengan pasti kartu mana yang ada di tangan Anda dan kartu mana yang telah dimainkan. Tentukan probabilitas semua kartu lain berdasarkan kartu yang telah dimainkan dan mungkin tawaran pemain jika ada penawaran yang terlibat. Untuk memulai, Anda bisa menggunakan probabilitas yang naif dan sama bahwa sebuah kartu ada di tangan beberapa pemain.
• Sekarang, jalankan sebanyak mungkin game "virtual" yang Anda bisa. Simulasikan memainkan kartu dari tangan Anda dan kemudian tentukan respons lawan Anda menggunakan aturan permainan dan probabilitas Anda. Untuk setiap game virtual, gunakan probabilitas Anda untuk menetapkan kartu ke pemain dan kemudian dengan cepat mensimulasikan game. Asumsikan setiap pemain akan bermain dengan kemampuan terbaiknya. Anda tahu semua kartu di permainan virtual Anda sehingga Anda dapat membuat setiap pemain bermain dengan sempurna.
• Ketika Anda memiliki pengambilan sampel yang solid (atau Anda kehabisan waktu), pilih langkah hukum yang paling sering memberi Anda hasil terbaik.

Setelah Anda mendapatkan sesuatu yang berfungsi, Anda dapat menambahkan semua jenis strategi yang diperkaya. Misalnya, variasikan probabilitas Anda berdasarkan permainan historis pemain, variasikan probabilitas berdasarkan gaya pemain (pasif, hati-hati, agresif), atau bahkan pertimbangkan efek dari pemain tertentu yang bermain bersama.

Edit per komentar LaurentG:

Pada akhirnya, Anda mungkin ingin menghapus gagasan permainan sempurna untuk semua pemain dan mengganti sesuatu yang lebih realistis. Secara konseptual, pisahkan probabilitas untuk suatu kartu berada di tangan seseorang (distribusi kartu) dari probabilitas seorang pemain memainkan kartu legal yang diberikan selama kartu (pemilihan kartu).

Pemilihan kartu sudah matang untuk dipelajari. Jika Anda melacak permainan di seluruh permainan, Anda dapat mempelajari bagaimana pemain tertentu, atau pemain pada umumnya, cenderung bermain berdasarkan kartu di tangan mereka dan kartu yang telah dimainkan. Anda bahkan bisa mendapatkan mewah dan model asumsi mereka tentang kartu yang disembunyikan dari mereka.

Ada juga peluang belajar untuk distribusi kartu. Tawaran masa lalu pemain dan pemilihan kartu selama tangan dapat mengungkapkan "kirim" tentang apa yang tersembunyi di tangan mereka. Anda bisa menggunakan data historis untuk menyesuaikan probabilitas saat membangun setiap game virtual.

Kasus pengalaman pribadi terbaru:

Saya sendiri telah mengerjakan permainan kartu (Bisca, permainan 2-pemain Portugis), dan saya mendapatkan hasil yang baik menggunakan metode Monte Carlo, khususnya menggunakan algoritme Informasi Set Monte Carlo Tree Search (ISMCTS, dijelaskan dengan contoh kode sumber dengan Python di http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Ini bermain dengan cukup baik, dengan gerakan yang salah saat itu, hanya dengan pengetahuan tentang aturan permainan. Saat ini saya mencoba untuk grok, untuk dapat meningkatkannya, sesuai dengan informasi yang saya baca tentang itu (dan MCTS "induknya") dimungkinkan untuk meningkatkan permainannya dengan heuristik ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) dan inferensi kartu lawan.

Saya pikir itu tergantung pada aturan mainnya.

Inilah yang saya mengerti dari pertanyaan Anda:

• Permainan ini dimainkan dalam putaran, dengan masing-masing pemain memainkan satu kartu per putaran
• Pemain yang masuk pertama dapat memainkan kartu apa pun yang dia inginkan
• Pemain yang berada di urutan kedua hanya dapat memainkan kartu tertentu, tergantung pada apa yang dimainkan terlebih dahulu
• Pemain yang memenangkan ronde pertama pergi ronde berikutnya
• Semua kartu didistribusikan sebelum babak pertama

Asumsi :

• Dengan pengetahuan penuh tentang kartu pemain lain, pemain yang pertama akan dapat memutuskan, untuk masing-masing kartu, apakah kartu akan memenangkan ronde atau tidak (pemain pertama dapat memainkan kartu win pasti)
• Jika kartu A dan B keduanya akan menang saat bermain pertama babak ini, bermain A putaran ini (dan menang) kemudian bermain B babak berikut berarti B akan menang juga (kartu tidak kehilangan nilai)
• Dengan pengetahuan penuh tentang kartu pemain lain, pemain yang berada di urutan kedua dapat memutuskan apakah sebuah kartu dapat memenangkan babak ini, tetapi akan kalah jika dimainkan pertama kali pada ronde berikut (pilih kartu yang paling buruk menang)

Contoh game yang mengikuti aturan ini:

Pemain pertama memainkan kartu. Pemain kedua harus memainkan kartu dari suite yang sama atau kalah. Jika suite cocok, kartu tertinggi akan menang.

Sekarang, permainan ini ditentukan oleh keberuntungan undian dan dengan dapat menghafal kartu apa yang telah dimainkan untuk mengetahui tangan lawan Anda.
Dalam situasi ini, saya akan membuat AI hanya sebagian mengingat kartu apa yang dimainkan, yaitu secara acak menghapus dari daftar yang diingat beberapa persentase dari kartu yang dimainkan (angka yang lebih rendah = AI dengan tingkat kesulitan yang lebih tinggi), tetapi tidak yang penting seperti Aces atau Kings. Dengan cara ini, misalnya, AI akan tahu bahwa bermain Queen of Hearts aman karena ia akan ingat lawan tidak memiliki Ace atau Raja, tetapi harus menghitung probabilitas jika ia ingin kemudian memainkan 10, karena dia mungkin tidak ingat apakah Jack masih bermain.
Ini meniru rentang perhatian manusia.

TL; DR
Batasi seberapa banyak AI tahu sehingga keputusannya tidak sempurna, cukup baik.