2048 solver

Hej. Próbuję ogarnąć algorytm min-max, ale nie radzę sobie.
Zrobiłem w javie grę 2048 i jakiś prymitywny algorytm szukający rozwiązania, ale on patrzy tylko na kolejny ruch a min-max przeszukuje drzewo ruchów. Jak je utworzyć? Mam metodę sprawdzającą jakie ruchy są możliwe do wykonania i metodę wykonującą ruch. Ale nie wiem jak zrobić żeby program mógł przewidzieć kilka ruchów w przód i wybrać najlepszy.
Dużo czytałem rozwiązań, rozumiem jak działa algorytm ale nie umiem sam go zaimplementować. Jakieś rady?

Musisz opracowac sobie jakas heurystyke, funkcje celu. Jezeli chcemy uzyskac kwadracik 2048 to moze to byc np:
Przyklad 1. Suma wartosci kwadracikow musi byc najwieksza (dążenie do uzyskania kwadracików o wysokich wartosciach)
Przyklad 2. Ilosc dostepnych kwadracikow powinna byc jak najmniejsza. (dazenie do jak najszybszego tworzenia połączen)

Mozna tez dac heurystyke, ktora dazy aby byl spelniony zarowno warunek z przykladu 1 i jednoczesnie warunek z przykladu 2. i nadac im jakieś wagi.

Właśnie taką funkcję mam, i tyle. Nie wiem jak użyć samego minimaxu, jak sprawdzać kolejne ruchy.

Algorytm minimax ma zastosowanie w grach dwuosobowych, a 2048 to gra jednoosobowa.

Wiem o tym, ale można to ominąć. Może masz inny sposób na stworzenie skutecznego rozwiązania? Może jest jakiś algorytm o którym nie słyszałem?

Twoje cele to mogą być na przykład:

• jak najmniej kwadracików na planszy
• wartości powinny być jak najbardziej posortowane (np. w rogu wartość największa, potem coraz mniejsze)
  wydaje mi się, że z powyższych warunków patrząc na kilka ruchów do przodu (do 5) powinieneś dać radę to rozwiązać

EDIT:
słabo google przeglądasz. W jednym z 3 pierwszych linków:
http://2048strategy.com/2048-strategy/
http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048

Widziałem te linki.
Nie zrozumiałeś mnie, ja wiem jak mam oceniać sytuację w grze, ale nie wiem jak przewidywać kolejne 5 ruchów, zapisywać, wybierać najlepszy.

1. Wymyśl w jaki sposób efektywnie zapisać stan gry - da się to zrobić w jednym unsigned int64.
2. Funkcja która przesuwa w każdym kierunku (generuje nowy stan gry) stan wykonaj_ruch(ruch)

później dokładnie to co tu jest napisane:
http://en.wikipedia.org/wiki/Minimax#Pseudocode

child node dla maksymalizującego to jest stan, po każdym z możliwych ruchów (lewo, góra, prawo, dół) - wyklucz niemożliwe ruchy (np. nie da się ruszyć w ogóle)
child node dla minimalizującego - wszystkie możliwe dostawienia 2 i 4

Ok, myślę, że już powinno pójść do przodu. W grze plansza jest zapisywana do dwuwymiarowej tablicy. Więc ten algorytm powinien dla każdego węzła tworzyć 4 kolejne takie tablice?

public static int minimax(int[][] board, int depth, boolean maximizingPlayer) {
		if(depth==0 || (!w && !s && !a && !d))
			return ocena(board);
		if(maximizingPlayer) {
			najWynik = -10000;
			for(int i=0; i<4; i++) {
				for(int k=0; k<game2048.wielkosc; k++) {
					for(int j=0; j<game2048.wielkosc; j++) {
						planszaL[k][j] = board[k][j];
					}
				}
				if(i==0 && !w) continue;
				if(i==1 && !s) continue;
				if(i==2 && !a) continue;
				if(i==3 && !d) continue;
				val = minimax(zrobRuch(planszaL,ruchy[i]), depth - 1, false);
				if(val>najWynik) {
					k2 = ruchy[i];
				}
				najWynik = Math.max(najWynik, val);
			}
			return najWynik;
		}
		else {
			for(int k=0; k<game2048.wielkosc; k++) {
				for(int j=0; j<game2048.wielkosc; j++) {
					planszaL[k][j] = board[k][j];
				}
			}
			najWynik = 10000;
			val = minimax(dodajKlocek(planszaL), depth - 1, true);
			najWynik = Math.min(najWynik, val);
			return najWynik;
		}
	}

Nie mogę ogarnąć tej rekurencji. To co zrobiłem jest na pewno złe, ale może nie tak bardzo i ktoś podpowie? Nie wiem jak zwracać na końcu ruch, nie wartość stanu (jest tam próba zrobienia tego). I wydaję mi się, że to działa nie tak jak powinno czyli, nie analizuje drzewa od końca do pierwszego ruchu tylko zwraca już na końcu stan po n ruchach.

Dodam jeszcze tylko, że dla głębokość równej 1 algorytm działa, a tego czego nie umiałem na początku zrobić dalej nie umiem.

public static int minimax(int[][] sytuacja, int glebokosc, boolean gracz, int limitglebokosci) {
		if(glebokosc > limitglebokosci || (!w && !s && !a && !d))
			return ocena(sytuacja);
		int[] r = wygenerujRuchy(sytuacja);
		if(gracz) minimax = -10000;
		else minimax = 10000;
		for(int i=0; i<r.length; i++) {
			if(gracz) {
				sytuacja = zrobRuch(sytuacja, r[i]);
				t = minimax(sytuacja, glebokosc + 1, przeciwnik(gracz), limitglebokosci);
				if(t > minimax) { minimax = t; k2 = r[i]; }
			}
			else { 
				sytuacja = dodajKlocek(sytuacja);
				t = minimax(sytuacja, glebokosc + 1, przeciwnik(gracz), limitglebokosci);
				if(t < minimax) minimax = t;
				continue;
			}
		}
		System.out.println(glebokosc + "\t" + minimax + "\t" + gracz + "\t" + k2);
		return minimax;
	}

Jeszcze coś próbuję zrobić, ale jak rozrysowałem sobie to jak pracuje ten kod to on nie wybiera węzłów tak jak to by wynikało z kodu, coś, ktoś?

1 1064 false 87
Głębokość | Ocena stanu | CzyGracz | Ruch
1 986 false 87
1 910 false 83
1 818 false 65
2 818 true 68
3 818 false 68
1 1032 false 87
1 976 false 87
1 874 false 83
1 942 false 65
2 942 true 68
3 942 false 68
1 952 false 83
1 992 false 87
1 1014 false 83
1 906 false 65
2 906 true 68
3 906 false 68
4 906 true 68

Może ktoś zechce spojrzeć i powie co jest nie tak, tak liczy algorytm dla głębokości = 4.

Temat można zamknąć, już wszystko wiem, zrozumiałem, zrobiłem. Dla pochwalenia się:
Kompletnie randomowa rozgrywka, pod koniec słabo wybierał już ruchy temu takie pomieszanie.

Ładnie, może udostępnisz?

Jeśli chodzi o kod to nie, na razie nie, musiałbym go uporządkować. Chyba, że chcesz skompilowaną grę.

Marcindddd napisał(a):

Jeśli chodzi o kod to nie, na razie nie, musiałbym go uporządkować. Chyba, że chcesz skompilowaną grę.

Przydałoby się i to i to.