Autor Wątek: halma, obiektowo c++, gra z komp  (Przeczytany 3069 razy)

Offline pozyt

  • Użytkownik

# Listopad 11, 2010, 22:39:53
Witam,
mam do napisania modyfikację gry halma (koniki polne).
Lekko zmodyfikowana, plansza 10x10, pionków po 15, można skakać przez swoje piony.
http://pl.wikipedia.org/wiki/Halma
Grę dla 2 graczy mam już napisaną. Muszę napisać jeszcze sztuczną inteligencję dla komputera.
Wybór najlepszego ruchu dla komputera, na podstawie oceny mam zrobioną (sprawdzam każdy możliwy ruch, oceniam go i wybieram najlepszy).

Niestety mam problem z tym, aby komputer umiejscowił pion po drugiej stronie planszy (żeby po prostu wygrał).

Zastanawiam się na zmianą całego systemu poruszania, albo dodaniem "tego czegoś" tak aby dążył do ustawienia końcowego.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xirdus

  • Redaktor

# Listopad 11, 2010, 22:45:34
No więc, jakie masz pytanie? Jeśli "Jak zrobić, by komputer wygrywał?", to przy ocenie ruchu zrób tak, by liczyła się odległość pionów od końcowej pozycji.

Offline pozyt

  • Użytkownik

# Listopad 12, 2010, 00:15:56
Czytasz w myślach. Jeśli jeszcze ktoś ma jakiś pomysł to proszę o podzielenie się

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 12, 2010, 00:30:59
Temat algorytmów sztucznej inteligencji w grach logicznych jest już mocno oklepany, więc najprostszym sposobem jest poszukanie opisów gotowych algorytmów.

W tym przypadku polecałbym się zapoznać z:
- algorytmem min-max z alfa-beta obcięciem (algorytm dobry taktycznie, głównie jeżeli jest mało możliwych ruchów)
- metoda Monte-Carlo (dobry strategicznie, często słaby taktycznie)

To z odległościami, o czym piszesz, to tzw. funkcja oceniająca - od tego nie uciekniesz, bo większość algorytmów wymaga jakiejś metody oceny sytuacji na planszy. W tym przypadku prostą oceną sytuacji gracza A może być suma odległości pionków gracza A od końcowej pozycji, od której odejmuje się podobnie policzoną sumę odległości pionków gracza B od jego końcowej pozycji.

Offline pozyt

  • Użytkownik

# Listopad 12, 2010, 01:38:47
Dzięki. Znam te algorytmy. Pozostaje mi napisać dobry sposób oceniania odległości. Trzeba będzie nad tym pomyśleć

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 12, 2010, 03:19:51
Dzięki. Znam te algorytmy. Pozostaje mi napisać dobry sposób oceniania odległości. Trzeba będzie nad tym pomyśleć
Najprostsze: suma X i Y wszystkich pionków (zakładając, że gracze grają po skosie (0,0)-(w,h)). :)

Offline pozyt

  • Użytkownik

# Listopad 12, 2010, 11:27:44
Dobry pomysł. Dokładnie to zrobię tak, że w przypadku pierwszego gracza to będzie X+Y, a w przypadku drugiego gracza 10-X,10-Y, i suma wszystkich pozycji dla gracza, tam gdzie pionek się znajduje.

Offline pozyt

  • Użytkownik

# Listopad 12, 2010, 13:06:22
Napisałem, ale będę musiał coś zmodyfikować, gdyż dochodzę do takiej sytuacji http://img221.imageshack.us/img221/5294/plansza.jpg i program wysypuje się. Brak możliwego ruchu z punktu widzenia algorytmu (niebieskimi pionkami steruje komputer) jest normalny, bo ruch tym pionkiem z dołu do góry to suma zmniejszy się.

No, ale w sumie kolejne ruchy będą prowadziły do zwiększenia sumy i zwycięstwa, trzeba przepatrzeć kod jeszcze raz.
« Ostatnia zmiana: Listopad 12, 2010, 13:23:04 wysłana przez pozyt »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 12, 2010, 13:39:31
Dobry pomysł. Dokładnie to zrobię tak, że w przypadku pierwszego gracza to będzie X+Y, a w przypadku drugiego gracza 10-X,10-Y, i suma wszystkich pozycji dla gracza, tam gdzie pionek się znajduje.
To nie przejdzie. Funkcja oceniająca planszę powinna być jedna i wspólna dla obu graczy, a jedyną różnicą jest to, że jeden gracz maksymalizuje, a drugi minimalizuje wynik (przez to jeżeli będziesz analizował dłuższe sekwencje ruchów, AI będzie się starało za bardzo nie ułatwiać życia przeciwnikowi).

Cytuj
Napisałem, ale będę musiał coś zmodyfikować, gdyż dochodzę do takiej sytuacji http://img221.imageshack.us/img221/5294/plansza.jpg i program wysypuje się. Brak możliwego ruchu z punktu widzenia algorytmu (niebieskimi pionkami steruje komputer) jest normalny, bo ruch tym pionkiem z dołu do góry to suma zmniejszy się.
W takim razie trzeba to zrobić inaczej i dla każdego pionka liczyć odległość od najbliższego pola wolnego w strefie końcowej. To powinno pomóc ustawić ostatnie pionki. Do tego oczywiście funkcja oceniająca powinna zwracać bardzo dużą wartość na plusie lub minusie w przypadku stwierdzenia wygranej jednego z graczy.

Offline Liosan

  • Moderator

# Listopad 12, 2010, 14:11:24
AI powinno być w stanie stwierdzić, że istnieje ruch, mimo że jest dla niego niekorzystny. W czym problem?

Liosan

Offline pozyt

  • Użytkownik

# Listopad 12, 2010, 16:05:12
Poprawiłem trochę. AI stwierdza, że istnieje ruch, ale jak wartość obliczonego ruchu jest taka sama jak kilku innych to wybiera pierwszy..

Mam napisany kod. Dla każdego pionka szukam najlepszego ruchu i zapisuję go do tablicy, potem najlepsza możliwa odpowiedź drugiego gracza, i możliwe najlepszy ruch mój w tym przypadku. Z tego wybieram najlepszy ruch.

Żeby zastosować alfabeta mam problem jak to rozplanować, jak szukać kolejnych ruchów. Jeśli sprawdzam tylko ruchy swoje i odpowiedź przeciwnika to już mam 15*15 kombinacji, a potem dalej wiadomo. Próbowałem z rekurencją, ale zajechałem kompa.

Offline Liosan

  • Moderator

# Listopad 12, 2010, 16:11:00
Spróbuj najpierw mini-max na 3 poziomy w dół, a potem funkcję oceniającą; potem możesz doimplementować alfa-beta. Kroczek po kroczku :)

Liosan

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 12, 2010, 19:48:57
Jak jest problem ze zbyt dużą liczbą kombinacji i odpowiedzi, to można próbować przez Monte-Carlo.

W uproszczeniu:
- wykonujemy sekwencję kilku losowych ruchów graczy i oceniamy wynik,
- powtarzamy losowanie wielokrotnie (np. 10 000 razy) i uśredniamy wyniki oddzielnie dla każdego pierwszego posunięcia,
- wybieramy takie pierwsze posunięcie, które daje najwyższy uśredniony wynik w grach losowych

Pomimo swojej prostoty, ta metoda działa zaskakująco dobrze.

Offline pozyt

  • Użytkownik

# Listopad 16, 2010, 14:48:26
Udało mi się napisać funkcję która szuka wszystkich możliwych ruchów, potem przeciwnik wykonuje najlepszy możliwy ruch dla każdego ruchu i znów funkcja szuka wszystkich ruchów dla nas.

Mam problem z funkcją oceniającą. Jak ocenić który gracz jeszcze bliżej wygranej ? W przypadku gracza pierwszego suma x i y (czym wieksza tym lepiej) dobrze się sprawdza, ale jak ocenić drugiego gracza ?

Rozumiem, że trzeba jedną funkcją ocenić sytuację na planszy obu gracz jednocześnie i zwrócić wartość.

Offline Liosan

  • Moderator

# Listopad 16, 2010, 15:05:40
Halma to taka gra, że jeden idzie do prawego dolnego rogu a drugi do lewego górnego? To po prostu mierz odległość manhatańską do celu zamiast "suma x i y". W przypadku pierwszego gracza wyjdzie na to samo, w przypadku drugiego będzie wynik o analogicznym znaczeniu.

Jeśli chcesz ocenić jedną funkcją ocenić obu gracz, to od score gracza maksymalizującego odejmij score minimalizującego.

Liosan