Najlepsze techniki dla sztucznej inteligencji gry karcianej

Próbuję opracować sztuczną inteligencję do gry karcianej i trochę utkwiłem w technice / algorytmie, którego powinienem użyć. Oto kilka założeń dotyczących gry:

• Po rozdaniu kart graczom nie ma losowości. Mam tu na myśli to, że każdy gracz może wybrać, które karty zagrywa, ale nie następuje losowy proces, jak w przypadku rozdawania kart na początku gry.
• Istnieją ograniczenia dotyczące kart, które można zagrać, gdy karta została już zagrana.
• Gracz, który wygrywa lewę, gra najpierw. Np. Gracz 1 zagrywa kartę, Gracz 2 zagrywa kartę i wygrywa. Następnie Gracz 2 zagrywa kartę, a następnie Gracz 1 gra.

Znam wiele wskazówek / zasad (np. Jeśli wiem, że gracz ma karty A, B, C, powinienem zagrać w D), co pomaga mi wygrać w grze. Dlatego najpierw chciałem użyć sieci bayesowskiej do opisania tych zasad. Problem polega na tym, że nie znam żadnych prawdopodobieństw do przypisania, ale mógłbym obliczyć heurystykę na podstawie historii gier (przeciwko człowiekowi). Po drugie, bardzo prawdopodobne jest, że nie znam wszystkich zasad i że istnieją pewne ukryte reguły, które są potrzebne AI do znalezienia optymalnej gry.

Nie jestem pewien, czy byłby to dobry sposób na opracowanie sztucznej inteligencji dla takiej gry karcianej?

Zastanawiam się także, czy istnieją inne techniki, które najlepiej pasowałyby do problemu. Na przykład rzuciłem okiem na minimax (może z algorytmem przycinania), ale czy byłby dobrą opcją dla tego problemu? Nie jestem pewien, ponieważ najważniejsze gry są na początku gry, gdy występują najwyższe nieznane parametry (większość kart nie jest jeszcze zagrana).

Twój przykład brzmi podobnie do Bridge . Najlepsze systemy gry brydżowej wykorzystują metody Monte Carlo do wybierania ruchów. Na wysokim poziomie:

• Określ prawdopodobieństwo, że każda karta będzie w danym rozdaniu. Wiesz z pewnością, które karty masz na ręce i które karty zostały zagrane. Określ prawdopodobieństwo wszystkich innych kart na podstawie kart, które zostały zagrane i ewentualnie oferty gracza, jeśli dotyczy to licytacji. Na początek możesz użyć naiwnego i równego prawdopodobieństwa, że ​​karta jest w ręce jakiegoś gracza.
• Teraz przejrzyj jak najwięcej „wirtualnych” gier. Symuluj grę z ręki, a następnie określ reakcje przeciwników, korzystając z zasad gry i swoich prawdopodobieństw. Dla każdej gry wirtualnej użyj swoich prawdopodobieństw, aby przypisać karty do gracza, a następnie szybko symuluj grę. Załóż, że każdy gracz będzie grał najlepiej jak potrafił. Znasz wszystkie karty w wirtualnej grze, dzięki czemu każdy gracz może grać idealnie.
• Kiedy masz solidną próbkę (lub zabraknie Ci czasu), wybierz legalny ruch, który najczęściej daje Ci najlepszy wynik.

Gdy już coś zaczniesz działać, możesz dodać wiele rodzajów wzbogaconych strategii. Na przykład, zmieniaj swoje prawdopodobieństwa w oparciu o historyczne gry gracza, zmieniaj prawdopodobieństwo w zależności od stylu gracza (pasywny, ostrożny, agresywny), a nawet weź pod uwagę wpływ konkretnych graczy grających razem.

Edytuj według komentarza LaurentG:

Ostatecznie możesz zrzucić ideę idealnej gry dla wszystkich graczy i zastąpić coś bardziej realistycznego. Pod względem koncepcyjnym oddziel prawdopodobieństwo karty znajdującej się w czyjejś ręce (rozkład karty) od prawdopodobieństwa, że ​​gracz zagra daną kartę prawną podczas rozdania (wybór karty).

Wybór karty jest gotowy do nauki. Jeśli śledzisz grę w różnych grach, możesz dowiedzieć się, w jaki sposób dany gracz lub ogólnie gracze mają tendencję do gry na podstawie kart w ręce i kart, które zostały zagrane. Możesz nawet fantazjować i modelować ich założenia dotyczące ukrytych przed nimi kart.

Istnieją również możliwości uczenia się w zakresie dystrybucji kart. Przeszłe oferty gracza i wybór karty podczas rozdania mogą ujawnić „powiedzieć” o tym, co jest ukryte w jego ręce. Możesz użyć danych historycznych, aby dostosować prawdopodobieństwo podczas tworzenia każdej gry wirtualnej.

Przypadek ostatniego osobistego doświadczenia:

Sam pracuję nad grą karcianą (Bisca, portugalska gra dla dwóch graczy) i osiągam dobre wyniki, stosując metody Monte Carlo, szczególnie używając najnowszego algorytmu wyszukiwania drzewa Monte Carlo informacji (ISMCTS, opisanego przykładowy kod źródłowy w Pythonie na http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Gra dość dobrze, od czasu do czasu niepoprawny ruch, tylko ze znajomością zasad gry. Obecnie staram się go poprawić, aby móc go ulepszyć, ponieważ zgodnie z informacjami, które o nim przeczytałem (i jego „macierzystym” MCTS), można ulepszyć grę dzięki heurystyce ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) i wnioskowanie o karcie przeciwnika.

Myślę, że to zależy od zasad gry.

Oto, co rozumiem z twojego pytania:

• Gra rozgrywana jest w rundach, przy czym każdy gracz gra jedną kartę na rundę
• Gracz, który idzie pierwszy, może zagrać dowolną kartę
• Gracz, który zajmuje drugie miejsce, może zagrać tylko niektóre karty, w zależności od tego, co zagrano jako pierwsze
• Gracz, który wygra rundę, przechodzi jako pierwszy w następnej rundzie
• Wszystkie karty są rozdawane przed pierwszą rundą

Założenia:

• Mając pełną wiedzę o kartach innego gracza, gracz, który wybierze pierwszy, może zdecydować dla każdej ze swoich kart, czy karta wygra rundę, czy nie (pierwszy gracz może zagrać pewną kartę wygranej)
• Jeśli zarówno karty A, jak i B wygrywają, gdy zostaną rozegrane jako pierwsze w tej rundzie, rozegranie A w tej rundzie (i zwycięstwo), a następnie zagranie B w kolejnej rundzie oznacza, że ​​B również wygra (karty nie tracą wartości)
• Mając pełną wiedzę o kartach drugiego gracza, gracz zajmujący drugie miejsce może zdecydować, czy dana karta może wygrać tę rundę, ale przegra, jeśli zostanie rozegrany jako pierwszy w następnej rundzie (wybierz najgorszą zwycięską kartę)

Przykładowa gra, która spełnia następujące zasady:

Pierwszy gracz zagrywa kartę. Drugi gracz musi zagrać kartę z tego samego zestawu lub przegrać. Jeśli kolory pasują, wygrywa najwyższa karta.

Teraz o tej grze decyduje szczęście losowania i umiejętność zapamiętania kart, które zostały zagrane, aby poznać układ przeciwnika.
W tej sytuacji sprawiłbym, że AI tylko częściowo pamiętała, które karty zostały zagrane, tj. Losowo usunąłem z zapamiętanej listy pewien procent zagranych kart (mniejsza liczba = AI o wyższym stopniu trudności), ale nie tak ważne jak asy lub królowie. W ten sposób na przykład AI będzie wiedziała, że ​​bezpiecznie jest zagrać Królową Kier, ponieważ pamięta, że ​​przeciwnik nie ma Asa ani Króla, ale będzie musiał obliczyć prawdopodobieństwo, jeśli chce zagrać 10, ponieważ może nie pamiętać, czy walet wciąż jest w grze.
To naśladuje ludzką uwagę.

TL; DR
Ogranicz ilość wiedzy AI, aby jej decyzje nie były idealne, wystarczy.