Backgammon

Osoba grająca czarnymi wykonuje ruchy w przeciwnym kierunku. O tym, kto rozpoczyna grę decyduje rzut jedną kostką, a dokładniej mówiąc ten kto wyrzuci większą liczbę oczek. Osoba, która wygrała ten mały pojedynek, następnie rzuca raz jeszcze obydwoma kostkami. Ruch można wykonać jednym pionem o liczbę oczek wynikającą z obydwu z nich, bądź też rozdzielając je na dwa piony i wykonanie nimi przemieszczenia zgodnie z ilością oczek. Pion może być ustawiony:
1. Na wolnym polu, nie zajętym przez żaden z pionów,
2. Na polu, które zajmują inny/e pion/y gracza, wykonującego ruch,
3. Na polu zajętym przez jeden pion przeciwnika (wtedy jego pion jest zbijany) i wędruje na bar. Pola, na które nie można postawić swojego piona, czyli mówiąc inaczej, które są zablokowane, stanowią te, na których znajdują się minimum dwa piony przeciwnika. A zatem jeśli pole jest zajmowane więcej niż przez 2 piony przeciwnika, wtedy nie można na nim postawić swojego piona.
- Jak się łatwo domyślić ustawianie pionów po dwa blisko siebie bardzo przeszkadza przeciwnikowi, stąd też występuje tendencja do stawiania bloków jak najszybciej jest to możliwe, lub też przygotowanie do nich.
- Gracz, który wyrzuci dublet, tj. dwie takie same ilości oczek na dwóch kostkach, ma prawo do wykonania czterokrotnie ruchu zgodnie ze wskazaniem pojedynczej kostki. To znaczy, wyrzucając dwie 6 można wykonać cztery ruchy po sześć. Gracz musi wykorzystać obydwie kostki do ruchu, chyba że jest zablokowany przez przeciwnika i nie może wykonać żadnego ruchu. Jeśli może wykorzystać tylko liczbę oczek z jednej kostki musi ją wykonać.
- Pion stojący samotnie nazywany jest blotką i narażony jest na zbicie. Do zbicia dochodzi wtedy, kiedy pion gracza staje na polu na którym znajduje się pojedynczy pion przeciwnika.
- Zbity pion umieszczany jest na poprzeczce.
- Przeciwnik chcąc wykonać swoje ruchy musi najpierw wprowadzić do gry pion zbity.
- Wprowadzenia dokonuje w bazie przeciwnika na podstawie rzutu kostkami, czyli dla gracza białymi pionami na pola od 19 do 24, a dla czarnych - od 1 do 6. Oczywiście, jeśli pola te są zajęte przez przeciwnika (tj. postawiony jest blok) na każdym z nich, to wtedy ruchu nie można wykonać i należy czekać na zwolnienie któregokolwiek.
- A zatem blokowanie pól w swojej bazie (im więcej tym trudniej przeciwnikowi wprowadzić zbite piony do gry przez przeciwnika) jest jednym z podrzędnych celów dla każdego graczy.
- Kiedy gracz ma wszystkie piony w swojej bazie, może rozpocząć ściąganie pionów z planszy.
- Ściąganie następuje zgodnie z ilością oczek wyrzucanych na kościach. Na przykład, wyrzucone 5 i 1 pozwala na ściągnięcie pionów z pola 20 i 24.
- Jeśli na danym polu nie stoi żaden pion należy wykonać w miarę możliwości ruch innym pionem o liczbie pól z kości.
- Jeśli liczba oczek jest większa, tj. wyrzucono m.in. 6, a na polu 19 nie stoi żaden pion, należy ściągnąć pion najdalej położony.
- Jeśli jakiś pion podczas ściągania został zbity przez przeciwnika, ściąganie można kontynuować dopiero po doprowadzeniu go do bazy.
- Jak wspomniano wcześniej, ten kto pierwszy ściągnie wszystkie swoje piony z planszy wygrywa grę.

W wielu grach, szczególnie w grach deterministycznych, główny algorytm służący do rozgrywek opiera się o algorytm MinMax. Min i Max są graczami. Przypuśćmy że zaczyna Max, sprawdza on wszystkie możliwe ruchy jakie może wykonać i wszystkie możliwe ruchy jakie może wykonać Min po każdym z jego ruchów. Algorytm może zasymulować wszystkie ruchy potrzebne do zakończenia gry lub do określonej głębokości, a następnie wybrać ten po którym możliwe ruchy przeciwnika będą najgorsze. To jak dany ruch zostanie oceniony zależy od funkcji oceniającej.

W porównaniu do innych gier, takich jak warcaby, w Backgammonie nie każdy prawidłowy ruch może być wykonany, ponieważ to czy można go wykonać zależy też od rzutu kostką i dlatego jest to gra niedeterministyczna. Stosując algorytm MinMax w tej grze podczas przeszukiwania rozwiązań, wraz z głębokością przeszukiwania prawdopodobieństwo osiągnięcia danego węzła maleje. W związku z tym wartość sprawdzania wprzód jest nikła i dlatego w algorytmach grających w grę Backgammon stosuje się algorytm MinMax z przeszukiwaniem na głębokość 2 co plus bardzo dobra funkcja oceny stanu gry daje bardzo wysoki poziom gry.

Napisany przeze mnie algorytm grający w backgammona działa w następujący sposób:
Po rozpoczęciu kolejki wirtualnego gracza, zostają wylosowane dwie liczby z przedziału 1-6, które traktowane są jako dwa rzuty kośćmi. Następnie algorytm wyszukuje wszystkie możliwe i prawidłowe, ze względu na zasady gry, kombinacje dwóch lub czterech ruchów. Każdy z tych ruchów zostaje oceniony przez dwie niezależne funkcje oceniające. Pierwsza z nich wykonuję kolejno wszystkie możliwe ruchy wirtualnego gracza i po wykonaniu każdego z nich wyszukuje wszystkie możliwe ruchy przeciwnika a następnie ocenia każdy z nich. Po wykonaniu tej operacji do każdego możliwego ruchu wirtualnego gracza, program ma przypisaną ocenę najlepszego możliwego ruchu przeciwnika, który będzie mógł zostać wykonany jeżeli wirtualny gracz wykona dany ruch. Druga ocena jaka jest przypisywana, jest to ocena danego ruchu wirtualnego gracza.

Funkcja oceniająca

Funkcje oceniające są napisane przeze mnie od podstaw. Funkcja oceniająca to najważniejszy element gry odpowiadający za ruchy wirtualnego gracza. We wszystkich opracowaniach dotyczących algorytmów grających w tą grę, jakie udało mi się znaleźć, znajdują się tylko wzmianki, że wybór ruchów zależy od funkcji oceniającej, natomiast nigdzie nie ma opisanych funkcji a nawet nie ma przykładów oceny jakiś przykładowych pojedynczych ruchów. Wyboru parametrów, które przedstawione są poniżeń dokonałem na podstawie przemyśleń a następnie modyfikowałem je sprawdzając zmiany strategi gry algorytmu. Końcowe wartości parametrów w porównaniu z wartościami pierwotnymi w bardzo znaczącym stopniu poprawiły poziom gry algorytmu.

Ruchy poszczególnych graczy są oceniane według tabelek w następujący sposób:

przykład 1: Jeżeli gracz wykona ruch, który zakończy się w strefie 2 a na polu na którym zatrzyma się pionek znajduje sie jeden pionek, który należy do niego i przy takim ruchu zostanie osłonięty przed zbiciem, ocena w tym przypadku wynosi 170 pkt.

przykład 2: Jeżeli gracz wykona ruch, który zakończy się w strefie 4 i nie jest to ruch bijący ani osłaniający to ruch ten zostanie oceniony na 10 lub 100 pkt. w zależności od tego czy pionek przed wykonaniem ruchu znajdował sie w strefie 4 (10 pkt) czy w którejś z pozostałych (100 pkt).

Jeżeli więcej niż 10 pionków przeciwnika znajduje się w strefie bazowej, punkty za zbicie pionka są podwajane. Analogicznie oceniane są ruchy przeciwnika. Jedyną różnica w ocenie jest inna tabela, według której przydziela się punkty a spowodowane jest to tym, że przeciwnik porusza się swoimi pionkami w odwrotną stronę niż gracz wirtualny.

Opis programu

Program został napisany w środowisku Borland Builder6 i można go uruchomić jedynie pod Window. Program w całości został napisany przeze mnie i nie wykorzystuje w nim żadnych gotowych elementów.
Poniższy obrazek przedstawia widok gry po uruchomieniu programu. Liczby znajdujące sie na pionkach mówią nam o liczbie pionków znajdujących się na danym polu. Po włączeniu gry automatycznie zaczyna gracz czerwony, czyli użytkownik. Jeżeli chcemy, aby grę zaczął wirtualny gracz należy wcisnąć przycisk "brak ruchu". Przycisk ten należy również nacisnąć w momencie gdy nie wykonaliśmy jeszcze wszystkich naszych ruchów a nie mamy możliwości ich wykonania ponieważ wszystkie pola na które możemy stanąć są zablokowane przez przeciwnika.

Materiały wykorzystane przy pisaniu projektu

Sztuczna inteligencja i systemy doradcze - www.mimuw.edu.pl/~awojna/SID/wyklady/gry.pdf
http://grecja.home.pl/tavli.htm
http://www.gnu.org/software/gnubg/ - na stronie tej znajduje się bardzo dużo linków do innych stron o tematyce Backgammona.

Nie podaje większej ilości linków ponieważ na większość ciekawych stron związanych z backgemmonem można dostać sie ze strony [3]. Jeżeli chodzi o inne strony polsko języczne to w większości przypadków zawierają one jedynie opisy zasad gry. Jeżeli jest już opisany algorytm gry, to jest on opisany bardzo słabo i pobierznie, a na podstawie takiego opisu nie da się napisać algorytmu.

Strefa:	1(baza)	2	3	4
osłona pionka	200	170	150	100
zbicie pionka	50	150	200	200
ruch	100	100	100	10 lub 100

Strefa:	1	2	3	4 (baza)
osłona pionka	100	150	170	200
zbicie pionka	200	200	150	50
ruch	100	100	100	100