Algorytm grania w większe kółko i krzyżyk

Question

Myślę nad algorytmem który grałby w kółko i krzyżyk na planszy 6x7, gdzie aby wygrać trzeba mieć linię długości 4. Nie jest to takie proste jak mogłoby się wydawać bo złożoność sprawdzenia wszystkich możliwości brutem to (6*7)! gdyż w pierwszym ruchu są wszystkie opcje do wyboru, w drugim wszystkie -1 itd.

Zna ktoś jakiś optymalny algorytm, taki aby komputer robił najlepsze ruchy?

 

Jak narazie jedyne co mi przychodzi do głowy to ucinanie drzewa poszukiwań, ale to prawie nic nie da przy takich liczbach, myślałem też aby robić hash code każdej pozycji i zrobić spamiętywanie, aby w przypadku powtórzenia się takiej samej pozycji nie liczyć na nowo tego samego, ale to też nic nie da.

Comments

imo, to wystarczy że w danej chwili sprawdzisz wszystkie możliwości ruchów max 8 ruchów w przód. Możliwe, że nawet sprawdzenie 4 ruchów w przód by wystarczyło, ale pewien nie jestem.

---

Brzmi całkiem dobrze, ale pojawia się pewien problem

40^5 to już 102 mln i na więcej w praktyce czas działania nie pozwala.  Czyli 5 ruchów naprzemiennych do przodu. Problem pojawia się w tym, że np. po 5 ruchach nie widzi za dużo przegranych i wygranych i ma wiele ruchów do wyboru i np. wybierałoby jako pierwszy ruch zawsze lewy górny róg, bo czemu nie, przecież i tak po 5 ruchach nie przegra.

Może lepiej jakieś heurystyki używać?

Answer 1

Witam,

nie wiem czy o to Ci chodzi ale polecam zapoznać się z algorytmem minmax https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/.

który sprawdza się do pisania AI. Algorytm minimalizuje oraz maksymalizuje straty i na tej podstawie wybiera optymalny ruch.

Comments

Właściwie to używam czegoś podobnego, ale chyba nie zrozumiałeś w czym problem. Taki minmax sprawdza wszystkie możliwości i złożoność tego jest dramatyczna.

Btw. ciekawi mnie na jakiej podstawie miałaby być oceniana pozycja w grze? Wydaje mi się być tylko -1 0 lub 1 (przegrana, remis lub wygrana), z tego powodu skoro wyliczy że przy najlepszych ruchach każdy pierwszy ruch prowadzi do remisu to w jaki sposób powinien wybrać który najlepiej zagrać?

---

Nie wydaje mi się żeby użycie tego algorytmu było jakimś dużym obciążeniem. Algorytm minmax świetnie nadaje się do pisania AI prostych gier gdzie obliczeń jest więcej np. Szachy.

 

Co do skali to musisz sobie najlepiej sam ustalić skalę. Np. trzy pod rząd te same znaki zwraca Ci 10 a jak są cztery to 100

int evaluate(char b[3][3]) 
{ 
    // Checking for Rows for X or O victory. 
    for (int row = 0; row<3; row++) 
    { 
//dla 4 pod rzad 
        if (b[row][0]==b[row][1] && 
            b[row][1]==b[row][2] &&
            b[row][2]==b[row][3]
) 
        { 
            if (b[row][0]==player) 
                return +100; 
            else if (b[row][0]==opponent) 
                return -100; 
        } 
//dla 3 pod rzad 
        if (b[row][0]==b[row][1] && 
            b[row][1]==b[row][2]) 
        { 
            if (b[row][0]==player) 
                return +10; 
            else if (b[row][0]==opponent) 
                return -10; 
        } 
    } 
...

 

---

Dobry pomysł z tym dawaniem punktów za 3 takie same obok siebie, dodam to, ale to nadal za mało ;)

Co do obciążenia to jest to bardzo duże duże obciążenie. Komputer w jakimś rozsądnym czasie wykona operacje w pętli o długości około 10^7, a złożoność tego algorytmu jest w przybliżeniu wykładnicza do ilości pól. W kółko i krzyżyk 3x3 pola idzie to szybko bo jest to 9!, ale 4x4 to już 16! byś się za szybko tym algorytmem nawet z prostymi optymalizacjami nie doczekał wyniku. I wyobraź sobie teraz że ja chcę zrobić do 7x6