Wprowadzenie algorytmu minimax do gomoku

Stworzyłem grę gomoku z dwa razy większą planszą (30 na 30 pól). Aby wygrać trzeba ułożyć piątkę obok siebie.
Gra jak najbardziej działa. W tej chwili z komputerem da się wygrać, a moim celem jest stworzenie takiego, który będzie niepokonany, lub chociaż będzie trochę lepszym graczem.
Co mam?
Metodę oceniającą sytuację na planszy (dla każdego wolnego pola znajduje współczynnik opłacalności ruchu, później liczę minimum i maksimum i wybieram takie pole, którego maksimum jest największe dla znalezionego najmniejszego minimum).
Metodę sprawdzającą czy ktoś wygrał.
Stan gry przechowywany jest w tablicy dwuwymiarowej. Zajęte pola są oznaczone jako X oraz O.
Czego nie potrafię w tym momencie wprowadzić?
Algorytmu minimax lub alfa-beta.
Mój obecny program ocenia tylko obecny stan gry, nie wybiera ruchu w zależności od tego jakie kolejne ruchy on za sobą pociąga. Można powiedzieć, że nie umie przewidywać kolejnych ruchów.
Czytałem dużo o tym, rozumiem jak to działa, a jednak nie wiem jak to zrobić.

jak już piszesz alfa-beta/minimax to od razu zacznij myśleć nad jego optymalizacją (spamiętwyanie i obecięcia) - minimax ma złożoność wykładniczą, wpisz sobie w google alfa-beta obcięcia, alfa-beta prunning. Knuth ma bardzo fajna analizę algorytmów cięcia drzew.
Nie znam gomoku, ale w przypadku warcabów brutal wygląda tak że generujesz wszystkie możliwe ruchy, robisz snapshota planszy dla każdego ruchu i go wykonujesz. I tak rekurencyjnie jedziesz do zadanej głębokości rekurencji. Co do funkcji oceniającej - możliwe że wygodniej jest nie badać jeden ruch tylko całą sytuację planszy w danym kroku.
(zakładając że mamy średnio po 8 możliwych ruchów na turę, licząc 5 ruchów do prozdu mamy 8^5 wywołań rekurencji - stąd warto za wczasu myśleć o cięciu :) )

co do samego minimaxa - jedziesz rekurencyjnie w dół, i dopiero na samym dole wyliczasz punktację za pomocą swojej funkcji, potem jak wracasz z rekurencji to wybierasz ruchy których dzieci dawały maksxymalne/minimalne punkty - w zależności który gracz w danym wywołaniu.

Dzięki kolego, Twoja wypowiedź trochę mi pomogła. Tutaj mam pseudokod algorytmu.

funkcja minmax( węzeł, głębokość )
	jeżeli dany węzeł jest końcowy lub głębokość == 0
		zwróć funkcja_oceniająca( węzeł )

	jeżeli my mamy zagrać w węźle
		foo = -∞
		dla każdego potomka węzła
			foo = max( foo, minmax( potomek, głębokość-1 ) )
		zwróć foo
	przeciwnie
		foo = +∞
		dla każdego potomka węzła
			foo = min( foo, minmax( potomek, głębokość-1 ) )
		zwróć foo 

Analizowałem wielokrotnie takie kody. Ale mam jeszcze pytania. Powinienem wywoływać tą metodę gdy przychodzi pora na ruch komputera. Z jakimi wartościami? Głębokość to wiadomo, ale węzeł? Wartość "węzeł" wskazuje na ilość rozgałęzień w każdym ruchu?
zwróć funkcja_oceniająca( węzeł )
do funkcji oceniającej potrzebuję numer wiersza i kolumny pola, sam węzeł mi nic nie daje. Może mam generować ruchy na początku metody, tyle ruchów ile węzłów(za pomocą funkcji oceniającej wybierać kilka najkorzystniejszych ruchów), wtedy będą te zmienne.
dla każdego potomka węzła

		dla każdego potomka węzła
			foo = max( foo, minmax( potomek, głębokość-1 ) )

Czy tutaj potomkiem jest wygenerowany ruch z tablicy, czyli numer kolumny i wiersza?

Mam nadzieję, że gdzieś się mylę, bo jeśli nie to nie wiem dlaczego to mi nie wychodzi.

A, i zwracana wartość powinna też być tablicą z wartościami wiersza i kolumny.

skoro czesto ogladałeś kody minimaxa w necie to na pewno oglądałeś też drzewka. Wązłem tego drzewka jest plansza, bądź sytuacja na planszy. Gałęzią jest ruch.
Czyli łopatologicznie, jesteś w węźle (czyli na jakiejś planszy). Generujesz potencjalne ruchy i tworzysz snapsho i na nim wykonujesz ruch -tu masz ten snapshot, o którym pisałem wyżej - ten nowy snapshot jest argumentem funkcji. Oczywiście każde wywołanie funkcji musi zawierać kolor przeciwnika względem aktualnie grającego.
Funkcja oceniająca zwraca punkty, funkcja_oceniająca( węzeł ) - musi zwrócić punktację dla danej planszy. Tutaj musisz pomyśleć co ta funkcja ma zwracać tak aby w jednym incie mieć informację o punktach obu graczy. możesz np policzyć punktację białego i czarnego i z tego policzyć ile % stanowi gracz czarny. Jak liczysz ruch dla gracza czarnego to cały algorytm zwraca % czarnego itd żebyś tego nie pomylił bo będą głupie wyniki.

To co może być mało intuicyjne wartość zwracana przez mimixa - po pierwsze musisz miec punkty które sa liczone dopiero na samym dole, a potem tylko zwracane na przemian minimum/maximum, po drugi musisz mieć ruch które te punkty generuje - ale których tylko z pierwszego wywołania - bo ten ruch będzie wykonywał przeciwnik/komputer po wyliczeniu.

Początkowe wywołanie minimaxa to mimimax(aktualny_snapshot_planszy)
Pamiętaj aby w swojej fukncji nie pomyślić +/- Infinity z graczami.

PS. algorytm który podałeś będzie zwracał dobre wyniki i będziesz miał bardzo silnego gracza. W przypadku warcabów minimax daje niedzielnego gracza na poziomie 4-6 ruchów do przodu. Przy 7 -8 jest już trudno. ALE - dla gomoku 30x30 liczba ruchów jest tak wielka że chyba nie starczy Ci życia aby zobaczyć wynik liczenia 8 ruchów do przodu powyższym skrawkiem kodu :)
(jeżeli liczysz dla wszystkich możliwych ruchów )

Nie wiem, jak w przypadku gomoku, ale dla go lepiej działają algorytmy randomizowane (oparte na Monte Carlo, najlepiej z odcięciami i heurystykami). Problemem w przypadku mini-max i alfa-beta jest wielkość planszy (liczba możliwych ruchów). Alfa-beta działa dobrze dla małych plansz (jak w szachach).

public static int[] MINIMAX(String planszaB[][], int ruchy[][], int glebokosc, String gracz) {
		//Użyłem tablic, ponieważ muszę dostać wartość kolumny i wiersza dla najlepszego ruchu
		int foo[] = new int[3];
		int v[] = new int[3];
		if(glebokosc == 0)
			return ocena(gracz, planszaB);
		if(gracz.equals("O")) {
			v[2] = -1000;
			for(int i=0; i<4; i++) {
				String planszaC[][] = new String[30][30];
				planszaC = kopiuj(planszaB);
				move(ruchy[i][0], ruchy[i][1], planszaC);
				foo = MINIMAX(planszaC, generatorRuchow(gracz, planszaC), glebokosc-1, gracz);
				if(foo[2]>v[2]) v = foo;
			}
			gracz = "X";
		}
		if(gracz.equals("X")) {
			v[2] = 1000;
			for(int i=0; i<4; i++) {
				String planszaC[][] = new String[30][30];
				planszaC = kopiuj(planszaB);
				move(ruchy[i][0], ruchy[i][1], planszaC);
				foo = MINIMAX(planszaC, generatorRuchow(gracz, planszaC), glebokosc-1, gracz);
				if(foo[2]<v[2]) v = foo;
			}
			gracz = "O";
		}
		return v;
	}

Chyba jest to najbliższa wersja działającej. Aczkolwiek nie działa. Ale komputer nie rzuca pionków w przypadkowe miejsca, zawsze jest w pobliżu postawionego już pionka, czasami o jedno pole odstępu. Cały czas coś zmieniam. Nie rozumiem jak ten algorytm zwraca jeden z początkowych 4 ruchów. Starałem się odzwierciedlić znaleziony pseudokod. Miło będzie jakby ktoś spróbował przeanalizować to co napisałem.

public static int[] MINIMAX(String planszaB[][], int ruchy[][], int glebokosc, String gracz) {
		int foo[] = new int[3];
		int v[] = new int[3];
		if(glebokosc == 0)
			return ocena(gracz, planszaB);
		if(gracz.equals("X")){ gracz = "O"; v[2] = -1000;}
		else {gracz = "X";v[2]=1000;}
			for(int i=0; i<4; i++) {
				String planszaC[][] = new String[30][30];
				for(int k=0; k<30; k++) 
					for(int j=0; j<30; j++)
						planszaC[k][j] = "";
				planszaC = kopiuj(planszaB);
				move(ruchy[i][0], ruchy[i][1], planszaC);
				foo = MINIMAX(planszaC, generatorRuchow(gracz, planszaC), glebokosc-1, gracz);
				if(gracz.equals("X") && v[2]>foo[2]) v = foo;
				else if(gracz.equals("O") && v[2]<foo[2]) v = foo;
			}
		
		return v;
	}

To jest druga wersja, na podstawie troszeczkę inne pseudokodu. W tym przypadku komputer jeśli musi robi ruch broniący, ale wydaję mi się, że nie robi to analizując możliwe przyszłe ruchy tylko na podstawie sytuacji obecnej, ponieważ łatwo da się doprowadzić do 2 niekrytych trójek. W ruchach kiedy nie musi się bronić nie widać sensu w jego ruchach, ale są w pobliżu reszty ruchów (nie przylegają).
Ok. więcej nic nie wrzucam, bo wersji byłoby za dużo.

//
Zapewne linijka odpowiada za złe działanie

return ocena(gracz, planszaB);

i ta metoda nie jest tą co powinna być, ale jeszcze nie wymyśliła jak powinna wyglądać. Ta metoda wyszukuje na planszy pole z największym współczynnikiem i zwraca dane na temat tego ruchu. Więc jeśli to jest ostatecznym wynikiem algorytmu, to cała reszta nie ma znaczenia (chyba). Bo metoda ocena nic nie bierze z reszty metody minimax.

W jaki sposób mogę wyświetlić najlepszy ruch dla stanu obecnego po analizie określonej głębokości.
Teraz wyświetla mi ostatni najlepszy ruch.

Dziwny jest ten Twój kod

Masz "if(gracz.equals("O")) " i w środku robisz "gracz = "X";" i zaraz potem "if(gracz.equals("X")) {".
Przecież wejdziesz do tego drugiego ifa, bo właśnie ustawiłeś "gracz = "X";"

Do rekurencyjnego wywołania metody powinieneś przekazywać drugiego gracza, tzn.
if(gracz.equals("O")) {
....
foo = MINIMAX(planszaC, generatorRuchow(gracz, planszaC), glebokosc-1, "X");
} else {
...
foo = MINIMAX(planszaC, generatorRuchow(gracz, planszaC), glebokosc-1, "O");
}