Wrocław 18.06.2007

Metody i algorytmy sztucznej inteligencji

Prowadzący dr inż. Witold Paluszyński

Gra w tysiąca

Raport z wykonania dużego zadania

Politechnika Wrocławska, Wydział Elektroniki, ARS IV

 

Grzegorz Karczewski
Paweł Wierzba

1.     Prezentacja problemu

Celem projektu było stworzenie algorytmu do gry w tysiąca oraz zaimplementowanie go. Problem jest o tyle ciekawy, że nie spotkaliśmy się z programem do gry w tą popularną polską grę wykorzystującą elementy sztucznej inteligencji. Jedyne dostępne aplikacje, które możemy napotkać to internetowe rozgrywki w trybie on-line, umożliwiające jedynie grę z innymi użytkownikami.
Nasz program został stworzony w taki sposób, że gra odbywa się pomiędzy jednym „żywym” użytkownikiem, a dwoma graczami symulowanymi przez komputer.
Główną trudnością była złożoność zasad gry, w której można wyróżnić: licytacje, wydanie dwóch kart oraz samą rozgrywkę, co wymusiło zupełnie inne podejście (zastosowanie zupełnie różnych zestawów reguł i faktów) do każdego z etapów gry.

2.     Zasady gry

Gra jest typowo polską grą, spotyka się również odmianę rosyjską. Do gry jest używana tzw. mała talia czyli 24 karty od dziewiątki do asa. Możemy wyróżnić następujące etapy rozgrywki:

·        Rozdanie kart

·        Licytacja

·        Zebranie przez grającego „musika”, ustalenie poziomu gry

·        Gra czyli zbieranie lew

·        Podliczenie i zapisanie punktów

Rozdanie kart:

Pierwszego rozdającego wyznacza się przez losowanie lub w sposób umowny. Gracze w kolejnych rozgrywkach rozdają karty na zmianę. Każdy z graczy otrzymuje po siedem kart, reszta kart czyli trzy pozostają w zakrytym stosie.

Licytacja:

Licytację rozpoczyna gracz siedzący po lewej stronie rozdającego słowem "sto" – musi zalicytować sto punktów, niezależnie od tego co ma w kartach i czy ma jakiekolwiek szanse na ugranie 100 punktów. Kolejny gracz (po jego lewej stronie) może powiedzieć „sto dziesięć”, lub taką liczbę punktów, którą uważa, że może wziąć np. „sto czterdzieści”. Może również spasować słowem "pas". Następni gracze mogą również podbić licytację o kolejne 10 lub spasować. Jeśli ktoś raz spasował, nie bierze udziału w dalszej licytacji. Jeśli w pewnym momencie licytacji po zadeklarowaniu przez niego sumy punktów, wszyscy kolejni gracze, biorący jeszcze udział w licytacji, spasują, licytacja jest zakończona – gracz, który ostatni deklarował liczbę punktów, zostaje „grającym”.

Zebranie przez grającego Musika:

Wygrywający licytację podejmuje karty z talonu, pokazuje przeciwnikom i umieszcza je na ręku. Następnie dwie dowolne karty z ręki przekazuje - po jednej, zakryte - każdemu z przeciwników. W rozgrywce biorą udział wszystkie karty.

 

Gra:

Grę rozpoczyna osoba która wygrała licytację, wychodząc kartą z ręki. W rozgrywce istnieje obowiązek dorzucania do koloru i przebijania atutem w przypadku nieposiadania koloru wyjścia. Nie ma obowiązku przebijania starszą kartą. W momencie wyjścia można zgłaszać posiadanie meldunku (pary króla i damy w tym samym kolorze). Jeśli gracz posiada taką parę, może, gdy rozpoczyna lewę, położyć na stół damę lub króla z tego meldunku i powiedzieć: „melduję”  .Meldunek premiowany jest w sposób zależny od jego koloru:

meldunek kierowy 100pkt

meldunek karowy 80pkt

meldunek treflowy 60pkt

meldunek pikowy 40pkt

Za zameldowanie meldunku gracz otrzymuje tyle punktów, ile wynosi wartość meldunku. Po zameldowaniu dowolnego meldunku wszystkie karty w jego kolorze stają się atu, to znaczy, że w lewie przebijają wszystkie pozostałe karty z innych kolorów np. w lewie 9 pik – as pik – walet karo (atu) wygrywa walet.

Podliczanie i zapisanie punktów

Poszczególne figury maja następujące wartości:

9 – 0pkt.

J – 2pkt.

Q – 3pkt.

K – 4pkt.

10 – 10pkt.

A – 11pkt.

Jeśli rozgrywający zdobył zadeklarowaną lub większą ilość punktów, to tę zadeklarowaną liczbę mu się zapisuje. Jeśli ich nie zdobył odpisuje mu się zadeklarowaną liczbę punktów jako minusowe. Przeciwnikowi rozgrywającego zapisuje się ilość punktów faktycznie

przez niego zdobytą w lewach i zgłoszonych meldunkach. Po przekroczeniu przez któregoś z graczy 800 punktów następne punkty dodaje mu się tylko w przypadku wygrania przez niego licytacji i ugrania zadeklarowanej liczby punktów.

 

3.    Implementacja i metoda.

 

Program został zaimplementowany w języku C#, użyliśmy do tego środowiska Microsoft Visual Studio 2005. Język C# jest językiem obiektowym, toteż większość działań opartych jest na metodach klasy głównej. Jako że możliwości rozgrywki jest bardzo dużo, a w naturze, gra opiera się na regułach zagrywek, oraz regułach postępowania, dlatego do rozwiązania problemu zastosowaliśmy algorytm własny oparty o system regułowy. Stan wiedzy każdego gracza, jest reprezentowany przez strukturę danych „daneDlaGracza”, w której odpowiednie pola odpowiadają różnym faktom, zbieranym w czasie przebiegu rozgrywki.

Jako strukturę przechowującą dane na temat posiadanych kart zastosowaliśmy obiekt DataSet, którego poszczególne tabele odpowiadają posiadanym przez graczy kartom.

Etapy rozgrywki i przykłady zastosowania reguł:

Rozdanie: Każdy z graczy otrzymuje losowo wybrane 7 kart, 3 karty trafiają na stół jako „musik”.

 

Licytacja na przykładzie jednego z symulowanych graczy:

W czasie przeszukiwania zestawu kart gracza, wyławiane są pewne ułożenia kart, które stwarzają możliwość uzyskania jak najwyższego wyniku. Rozpoznawane są m.in. ułożenia typu: meldunki(zapamiętywana jest ich ilość oraz kolor), ułożenia typu As-singiel, as+10+meldunek, as+10, as+ meldunek oraz inne. Na podstawie tych faktów dokonywana jest ich interpretacja, w wyniku której zwracana jest maksymalna stawka jaką dany gracz może wylicytować.

Gracz który wygrał licytacje, otrzymuje 3 karty z tzw. „musika”. Aby liczba kart każdego z graczy była równa, gracz rozgrywający( ten który wygrał licytacje) daje każdemu z rywali po jednej karcie. Wbrew pozorom problem jest złożony. Łatwo wybrać karty, których nie potrzebujemy, ze zestawu kart gdzie występują karty ewidentnie niepotrzebne(pojedynczo występujące karty jednego koloru o niskich wartościach), lub większość kart ma małą wartość(2-3 karty o niskiej wartości tego samego koloru). Problemem jest stworzenie reguł które zadecydują które karty wybrać z zestawu kart, w którym wszystkie karty dają pewność wygranej( wzięcia lew).

 Karty do oddania wybierana są również na podstawie faktów, które mówią o występowaniu konkretnych ułożeń figur i kolorów. W pierwszej kolejności wydawane są karty, które występują jako zestaw 2-3 kart tego samego koloru , następnie pojedynczo występujące karty ze względu na kolor. Później występuje jeszcze szereg innych reguł,  gdzie w ostateczności, jeżeli żadna reguła się nie wykona, wybierane są karty o najniższej figurze.

Rozgrywka:

Rozgrywkę rozpoczyna gracz, który wygrał licytacje i rozdał karty. Występują dwie strategie gry: jeżeli gracz jest rozgrywającym,  to na początku zbiera wszystkie lewy na których zdobycie ma całkowitą pewność. Drugim celem jest zameldowanie posiadanych meldunków. A następne zbierane są lewy, które da się zdobyć. Drugą strategią jest „przeszkadzanie”, czyli w pierwszym możliwym momencie przebicie rozgrywającego, następnie zebranie jak największej ilości lew i ewentualnie zameldowanie własnego meldunku( ustalenie własnego atu). Gra kończy się w momencie, gdy gracze zrzucą wszystkie karty, poczym następuje podliczenie zdobytych przez nich punktów.

4. Dyskusja działania oraz wyników testów.

Głównym celem, który staraliśmy się osiągnąć było stworzenie systemu, który przede wszystkim nie popełniał by rażących błędów. Ten cel udało się osiągnąć, ponieważ w większości rozgrywek system zachowuje się zgodnie z oczekiwaniami jakimi kieruje się przeciętny gracz. Wnioski takie opieramy na testach przeprowadzonych we własnym zakresie oraz wśród 6 innych osób potrafiących grać w tysiąca. Komputer uzyskuje skuteczność w granicach 60% - 70% w momencie gdy wygrywa licytacje. Ciekawe jest to, że znacznie lepiej sprawdza się strategia "przeszkadzania", gdzie w 80 % (z 30 prób) wirtualny gracz wykorzystuje możliwości przeszkodzenia oraz stosuje odpowiednie strategie. Dużym problemem była konfrontacją wyników z innym programem ponieważ takowego nie znaleźliśmy.

Interfejs:

Przebieg licytacji:

Gracz 2: 110

Gracz 3: pass

Gracz 1: pass

Licytację wygrał gracz1.

Przebieg gry:

1: k A

1: k J

1: k 9

3: k K  - meldunek gracza 2

3: c 9

3: k 10

2: p 9

2: p A

2: p Q – meldunek gracza 3

2: c Q

2: c K

2: c J

2: t J

2: p 10

2: p J

1: t A

1: t Q

1: t 9

3: k Q

3: t 10

3: p K

2: t K

2: c A

2: c 10

Komunikat końcowy:

Jedynym z mankamentów jest wysokość licytacji, gdzie gracze nie stosują ryzyka, natomiast w czasie rozgrywki, tylko w specyficznych przypadkach zdarzają się ruchy niepożądane.

5. Wnioski

System do gry w tysiąca okazał się trudnym i złożonym problemem.  Oprócz trudności z implementacją wszystkich zasad gry, poważnym problemem jest stworzenie wystarczającej ilości reguł, oraz zebranie potrzebnych faktów do rozgrywania bezbłędnych rozgrywek. Na potrzeby projektu niektóre z reguł gry zostały ograniczone bądź pominięte, dotyczy to jednak tylko zasad, które nie wpływają znacząco na decyzje jakie trzeba podejmować w trakcie pojedynczej rozgrywki. W tego typu problemach systemy regałowe oparte na systemach takich jak np. CLIPS mogły by się dobrze sprawdzić z uwagi na łatwość wprowadzania nowych reguł. Niemniej jednak nasz system spełnia większość z postawionych przed nim problemów i na tym etapie rozwoju daje użytkownikowi satysfakcję z gry, dodatkowo jest dobrą bazą do dalszego rozwijania i ulepszania algorytmu.

6. Bibliografia

Lech Pijanowski - Przewodnik Gier  - szczegółowy opis gry

www.codeguru.pl

www.kurnik.pl 

www.pagat.com - podstawowe strategie w grach karcianych, baza linków do innych stron o podobnej tematyce.