Jaki jest optymalny algorytm dla gry 2048?

Jestem autorem programu AI, o którym inni wspominali w tym wątku. Możesz wyświetlić si w Akcji lub przeczytać Źródło .

Obecnie program osiąga około 90% wygranych uruchamianych w javascript w przeglądarce na moim laptopie, biorąc pod uwagę około 100 milisekund czasu myślenia na ruch, więc chociaż nie jest idealny (jeszcze!) działa całkiem dobrze.

Ponieważ gra jest dyskretną przestrzenią stanową, doskonałą informacją, grą turową jak szachy i warcaby, użyłem te same metody, które okazały się działać na tych grach, a mianowicie minimax szukaj z alfa-beta przycinanie . Ponieważ istnieje już wiele informacji na temat tego algorytmu, powiem tylko o dwóch głównych heurystykach, których używam w statyczna funkcja oceny i które formalizują wiele intuicji, które inni ludzie tutaj wyrazili.

Monotoniczność

Ta heurystyka stara się zapewnić, że wartości płytek są wszystkie rosnąco lub malejąco zarówno w kierunku lewo/prawo, jak i góra / dół. Ta sama heurystyka oddaje intuicję, że wielu innych wspomniało, że wyżej cenione płytki powinny być zgrupowane w rogu. Zazwyczaj zapobiega to osieroceniu mniejszych cennych płytek i utrzymuje planszę bardzo zorganizowaną, z mniejszymi płytkami wchodzącymi kaskadowo i wypełniającymi się większymi płytkami.

Oto zrzut ekranu idealnie monotonicznej siatki. Uzyskałem to uruchamiając algorytm z funkcją eval ustawioną w celu pominięcia innych heurystyk i rozważenia tylko monotoniczności.

Gładkość

Powyższa heurystyka ma tendencję do tworzenia struktur, w których sąsiadujące płytki maleją, ale oczywiście, aby połączyć sąsiadujące płytki muszą być tej samej wartości. Dlatego heurystyka gładkości mierzy tylko różnicę wartości między sąsiednimi płytkami, starając się zminimalizować tę liczbę.

Komentator w Hacker News dał ciekawe sformalizowanie tej idei z punktu widzenia teorii grafów.

Oto zrzut ekranu idealnie gładkiej siatki, dzięki uprzejmości tego doskonałego widelca parodii .

Darmowe Płytki

I wreszcie, jest kara za posiadanie zbyt małej ilości wolnych płytek, ponieważ opcje mogą szybko się wyczerpać, gdy plansza stanie się zbyt ciasna.

I tyle! Przeszukiwanie przestrzeni gry przy jednoczesnej optymalizacji tych kryteriów daje niezwykle dobre wyniki wydajność. Jedną z zalet stosowania uogólnionego podejścia, a nie jawnie zakodowanej strategii ruchu, jest to, że algorytm często może znaleźć interesujące i nieoczekiwane rozwiązania. Jeśli oglądasz bieg, często wykonuje zaskakujące, ale skuteczne ruchy, na przykład nagle zmienia ścianę lub narożnik, na którym się buduje.

Edit:

Oto demonstracja mocy tego podejścia. Odkręciłem wartości kafelków (tak dalej szło po osiągnięciu 2048) i oto najlepszy wynik po ośmiu próbach.

Tak, to 4096 obok 2048. = ) Oznacza to, że osiągnął nieuchwytny kamień 2048 trzy razy na tej samej planszy.

EDIT: jest to naiwny algorytm, modelujący ludzki świadomy proces myślowy i uzyskujący bardzo słabe wyniki w porównaniu do sztucznej inteligencji, która przeszukuje wszystkie możliwości, ponieważ wygląda tylko o jeden kafelek do przodu. Został on przesłany na początku czasu odpowiedzi.

Udoskonaliłem algorytm i pokonałem grę! Może się nie udać z powodu prostego pecha blisko końca (jesteś zmuszony do przesunięcia w dół, czego nigdy nie powinieneś robić, a kafelek pojawia się tam, gdzie powinien być twój najwyższy. Po prostu staraj się utrzymać szczyt rząd wypełniony, więc poruszanie się w lewo nie łamie wzoru), ale w zasadzie kończy się na części stałej i części ruchomej do zabawy. To jest twój cel:

To jest model, który wybrałem domyślnie.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Wybrany narożnik jest Dowolny, w zasadzie nigdy nie naciskasz jednego klawisza (zakazany ruch), a jeśli to zrobisz, naciśnij ponownie przeciwnie i spróbuj to naprawić. Dla przyszłych płytek model zawsze oczekuje, że następny losowy kafelek będzie 2 i pojawi się na przeciwnej stronie strona do bieżącego modelu (podczas gdy pierwszy wiersz jest niekompletny, w prawym dolnym rogu, po zakończeniu pierwszego wiersza, w lewym dolnym rogu).

Oto algorytm. Około 80% wygrywa (wydaje się, że zawsze można wygrać z bardziej "profesjonalnymi" technikami AI, ale nie jestem tego pewien.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Kilka wskazówek na temat brakujących kroków. Tutaj:

Model zmienił się ze względu na szczęście bycia bliżej oczekiwanego modelu. Model AI jest próba osiągnięcia jest

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

I łańcuch, aby się tam dostać stał się:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O reprezentują zakazane przestrzenie...

Więc naciśnie w prawo, potem ponownie w prawo, następnie (w prawo lub na górę w zależności od miejsca, w którym 4 zostało utworzone) następnie przejdzie do zakończenia łańcucha, aż otrzyma:

Więc teraz model i łańcuch wracają do:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Drugi wskaźnik, miał pecha i jego główne miejsce zostało zajęte. Jest prawdopodobne, że zawiedzie, ale nadal może to osiągnąć:

Oto model i łańcuch:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Gdy uda mu się osiągnąć 128 zyskuje cały wiersz zyskuje ponownie:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

Zainteresował mnie pomysł stworzenia sztucznej inteligencji dla tej gry zawierającej bez kodowanej inteligencji (tj. bez heurystyki, funkcji punktacji itp.). Sztuczna inteligencja powinna "znać" tylko zasady gry, a"rozgryźć" rozgrywkę. Jest to w przeciwieństwie do większości AIs (takich jak te w tym wątku), gdzie gra jest zasadniczo brutalna siła kierowana przez funkcję punktacji reprezentującą ludzkie zrozumienie gry.

Algorytm AI

Znalazłem prosty jeszcze zaskakująco dobry algorytm gry: aby określić następny ruch dla danej planszy, sztuczna inteligencja gra w pamięci za pomocą losowych ruchów aż do zakończenia gry. Odbywa się to kilka razy przy jednoczesnym śledzeniu wyniku końcowego gry. Następnie obliczany jest średni wynik końcowy na ruch początkowy . Ruch początkowy z najwyższym średnim wynikiem końcowym jest wybierany jako następny ruch.

Zobacz to w akcji

Najlepszy wynik pokazany jest tutaj:

Ciekawostką w tym algorytmie jest to, że chociaż gry losowe są dość złe, wybór najlepszego (lub najmniej złego) ruchu prowadzi do bardzo dobrej gry: typowa gra si może osiągnąć 70000 punktów i ostatnie 3000 ruchów, jednak losowe gry w pamięci z dowolnej pozycji dają średnio 340 dodatkowych punktów w około 40 dodatkowych ruchach przed śmiercią. (Możesz to zobaczyć na własne oczy, uruchamiając sztuczną inteligencję i otwierając konsolę debugowania.)

Ten wykres ilustruje ten punkt: Niebieska linia pokazuje wynik planszy po każdym ruchu. Czerwona linia pokazuje najlepszy wynik algorytmu z tej pozycji. W istocie wartości czerwone "ciągną" wartości niebieskie w górę w ich kierunku, ponieważ są algorytm najlepiej zgaduje. Interesujące jest to, że czerwona linia jest tylko trochę powyżej niebieskiej linii w każdym punkcie, ale Niebieska linia nadal rośnie coraz bardziej.

Wydaje mi się dość zaskakujące, że algorytm nie musi właściwie przewidywać dobrej gry, aby wybrać ruchy, które go wytwarzają.

Szukając później znalazłem ten algorytm może być klasyfikowany jako czysty Monte Carlo Tree Search algorytm.

Wdrożenie i Linki

Najpierw stworzyłem wersję JavaScript, która może być widziana w akcji tutaj . Ta wersja może uruchomić 100 z uruchomień w przyzwoitym czasie. Otwórz konsolę, aby uzyskać dodatkowe informacje. (source)

Później, aby się trochę pobawić, użyłem @ nneonneo wysoce zoptymalizowanej infrastruktury i zaimplementowałem swoją wersję w C++. Ta wersja pozwala na do 100000 uruchomień na ruch, a nawet 1000000, jeśli masz cierpliwość. Instrukcje budowlane dostarczone. Działa w konsoli i posiada również pilota do odtwarzania wersji internetowej. ( źródło )

Wyniki

Co zaskakujące, zwiększenie liczby biegów nie poprawia drastycznie gry. Wydaje się, że limit tej strategii wynosi około 80000 punktów z płytką 4096 i wszystkimi mniejszymi, bardzo zbliżonymi do osiągnięcia płytki 8192. Zwiększenie liczby runów ze 100 do 100000 zwiększa szanse na osiągnięcie tego limitu punktów (z 5% do 40%), ale nie przełamanie go.

Przebiegnięcie 10000 przebiegów z tymczasowym wzrostem do 1000000 w pobliżu krytycznych pozycji udało się przełamać tę barierę mniej niż 1% razy, osiągając maksymalny wynik 129892 i 8192.

Ulepszenia

Po zaimplementowaniu tego algorytmu wypróbowałem wiele ulepszeń, w tym użycie wyników min lub max, lub kombinacji min, max i avg. Próbowałem również użyć głębokości: zamiast próbować K działa na ruch, próbowałem K ruchy na ruch Lista o danej długości (np." w górę,w górę,w lewo") i wybranie pierwszego ruchu z listy najlepiej punktowanych ruchów.

Później zaimplementowałem drzewo punktacji, które uwzględniało warunkowe prawdopodobieństwo zagrania ruchu po danej liście ruchów.

Jednak żaden z tych pomysłów nie wykazał żadnej rzeczywistej przewagi nad prostym pierwszym pomysłem. Zostawiłem kod dla tych pomysłów skomentowanych w kodzie C++.

Dodałem mechanizm "głębokiego wyszukiwania", który tymczasowo zwiększył liczbę uruchomień do 1000000 gdy którykolwiek z przebiegów udało się przypadkowo osiągnąć następny najwyższy kafelek. Zapewniło to poprawę czasu.

Chciałbym usłyszeć, czy ktoś ma inne pomysły poprawy, które utrzymują niezależność domeny sztucznej inteligencji.

2048 warianty i klony

To jest możliwe ze względu na niezależny od domeny charakter sztucznej inteligencji. Niektóre z wariantów są dość wyraźne, np. Klon sześciokątny.

Kopiuję tu treść posta na moim blogu

Proponowane przeze mnie rozwiązanie jest bardzo proste i łatwe do wdrożenia. Chociaż osiągnął wynik 131040. Przedstawiono kilka benchmarków wydajności algorytmu.

Algorytm

Algorytm punktacji heurystycznej

Założenie, na którym opiera się mój algorytm, jest dość proste: jeśli chcesz osiągnąć wyższy wynik, plansza musi być tak uporządkowana, jak możliwe. W szczególności optymalne ustawienie jest podane przez liniowy i monotoniczny porządek malejący wartości płytek. Ta intuicja daje również górną granicę dla wartości płytki: gdzie n jest liczbą płytek na planszy.

Dwa możliwe sposoby organizacji planszy są pokazane na poniższych obrazkach:

Aby wyegzekwować uporządkowanie płytek w monotonicznym porządku malejącym, wynik si obliczony jako suma zlinearyzowanych wartości na planszy pomnożonych przez wartości ciągu geometrycznego o wspólnym stosunku r

Kilka ścieżek liniowych może być ocenianych jednocześnie, końcowy wynik będzie maksymalnym wynikiem dowolnej ścieżki.

Reguła decyzyjna

Zaimplementowana reguła decyzyjna nie jest do końca inteligentna, kod w Pythonie jest prezentowany tutaj:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Implementacja minmax lub Expectiminimax z pewnością poprawi algorytm. Oczywiście bardziej wyrafinowana reguła decyzyjna spowolni algorytm i będzie wymagała trochę czasu na wdrożenie.W najbliższym czasie wypróbuję implementację minimax.

Benchmark

• testy T1-121-8 różnych ścieżek-r=0,125
• T2-122 testy-8-różne ścieżki-r=0,25
• T3-132 testy-8-różne ścieżki - r = 0,5
• T4-211 testy-2-różne ścieżki-r=0,125
• T5-274 testy-2-różne ścieżki-r=0,25
• T6-211 testy-2-różne ścieżki-r=0,5

W przypadku T2, cztery testy na dziesięć generują płytkę 4096 ze średnim wynikiem 42000

Kod

Kod można znaleźć na GiHub pod następującym linkiem: https://github.com/Nicola17/term2048-AI Opiera się na term2048 i jest napisane w Pythonie. Jak najszybciej zaimplementuję bardziej wydajną wersję w C++.

Moja próba wykorzystuje expectimax jak inne powyższe rozwiązania, ale bez bitboardów. Rozwiązanie Nneonneo może sprawdzić 10 milionów ruchów, co jest w przybliżeniu głębokością 4 z 6 kafelkami w lewo i 4 ruchy możliwe (2*6*4)⁴. W moim przypadku eksploracja tej głębokości trwa zbyt długo, dostosowuję głębokość wyszukiwania expectimax w zależności od liczby wolnych płytek:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Wyniki plansz są obliczane z ważonej sumy kwadratu liczby wolnych płytek i kropki iloczyn siatki 2D z tym:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

Który zmusza do uporządkowania płytek w rodzaju węża z lewej górnej płytki.

Kod poniżej lub jsbin :

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}

body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}

<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>

Jestem autorem kontrolera 2048, który osiąga lepsze wyniki niż jakikolwiek inny program wymieniony w tym wątku. Efektywna implementacja kontrolera jest dostępna na github . W oddzielnym repo znajduje się również kod używany do szkolenia funkcji oceny stanu kontrolera. Metoda szkolenia jest opisana w artykule .

Kontroler wykorzystuje wyszukiwanie expectimax z funkcją oceny stanu wyuczoną od podstaw (bez ekspertyzy human 2048) przez wariant czasowego uczenia różnicowego (technika uczenia wzmacniającego). Funkcja wartości stanu wykorzystuje sieć N-krotną , która jest zasadniczo ważoną funkcją liniową wzorców obserwowanych na tablicy. W sumie wzięło w nim udział ponad 1 miliard wag .

Wydajność

Przy 1 Ruchu / s: 609104 (100 gry średnie)

Przy 10 ruchach / s: 589355 (300 gry średnie)

W 3-warstwowej (ok. 1500 ruchów / s): 511759 (1000 gry średnie)

Statystyki płytek dla 10 ruchów/S są następujące:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Ostatni wiersz oznacza posiadanie na planszy jednocześnie podanych płytek).

Dla 3-warstwowych:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Jednak nigdy nie zauważyłem, aby uzyskać płytkę 65536.

Myślę, że znalazłem algorytm, który działa całkiem dobrze, ponieważ często osiągam wyniki powyżej 10000, mój osobisty najlepszy wynik to około 16000. Moje rozwiązanie nie ma na celu utrzymanie największych liczb w rogu, ale utrzymanie go w górnym rzędzie.

Zobacz poniższy kod:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

Jest już implementacja AI dla tej gry: tutaj . Fragment README:

Algorytm jest iteracyjny. Funkcja ewaluacji stara się utrzymać monotoniczność wierszy i kolumn (wszystkie malejące lub rosnące) przy jednoczesnym zminimalizowaniu liczby płytek na siatce.

Istnieje również dyskusja na tematycombinator o tym algorytmie, który może okazać się przydatny.

Algorytm

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Ocena

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Szczegóły Oceny

128 (Constant)

Jest to stała, używana jako linia bazowa i do innych zastosowań, takich jak testowanie.

+ (Number of Spaces x 128)

Więcej przestrzeni sprawia, że stan jest bardziej elastyczny, mnożymy przez 128 (co jest medianą), ponieważ siatka wypełniona 128 twarzami jest optymalnym stanem niemożliwym.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Tutaj oceniamy twarze, które mają możliwość połączenia, oceniając je do tyłu, płytka 2 staje się wartością 2048, podczas gdy płytka 2048 jest oceniana na 2.

+ Sum of other faces { log(face) x 4 }

Tutaj nadal musimy sprawdzić wartości stacked, ale w mniejszym stopniu, który nie przerywa parametrów elastyczności, więc mamy sumę { X w [4,44]}.

+ (Number of possible next moves x 256)

Stan jest bardziej elastyczny, jeśli ma większą swobodę możliwych przejść.

+ (Number of aligned values x 2)

Jest to uproszczona Kontrola możliwości połączenia się w tym stanie, bez patrzenia w przyszłość.

Uwaga: Stałe mogą być modyfikowane..

To nie jest bezpośrednia odpowiedź na pytanie OP, to jest więcej rzeczy (eksperymentów) próbowałem do tej pory rozwiązać ten sam problem i uzyskał pewne wyniki i kilka obserwacji, które chcę podzielić się, jestem ciekaw, czy możemy mieć jakieś dalsze spostrzeżenia z tego.

Właśnie wypróbowałem moją implementację minimax z przycinaniem alfa-beta z odcięciem głębokości drzewa na 3 i 5. Próbowałem rozwiązać ten sam problem dla siatki 4x4, co zadanie projektu dla kursu edX Csmm.101x sztuczna inteligencja (AI) .

Zastosowałem kombinację wypukłą (próbowałem różnych wag heurystycznych) kilku heurystycznych funkcji oceny, głównie z intuicji i z tych omówionych powyżej:

1. Monotoniczność
2. Wolne Miejsce Dostępne

W moim przypadku gracz komputerowy jest całkowicie losowy, ale mimo to założyłem ustawienia przeciwstawne i zaimplementowałem agenta gracza si jako gracza max.

Mam siatkę 4x4 dla gramy w grę.

Obserwacja:

Jeśli przypisam zbyt dużą wagę do pierwszej funkcji heurystycznej lub drugiej funkcji heurystycznej, oba przypadki, w których wyniki gracza si są niskie. Grałem z wieloma możliwymi przypisaniami wagi do funkcji heurystycznych i wziąłem kombinację wypukłą, ale bardzo rzadko gracz AI jest w stanie zdobyć 2048. Najczęściej zatrzymuje się na 1024 lub 512.

Próbowałem też heurystyki narożnej, ale z jakiegoś powodu sprawia, że wyniki co gorsza, jakaś intuicja dlaczego?

Również, próbowałem zwiększyć głębokość wyszukiwania odcięcia od 3 do 5 (nie mogę zwiększyć go więcej, ponieważ wyszukiwanie tej przestrzeni przekracza dozwolony czas, nawet przycinanie) i dodał jeszcze jeden heurystyczny, który patrzy na wartości sąsiednich płytek i daje więcej punktów, jeśli są one merge-able, ale nadal nie jestem w stanie uzyskać 2048.

Myślę, że lepiej będzie użyć Expectimax zamiast minimax, ale nadal chcę rozwiązać ten problem tylko z minimax i uzyskać wysoki wyniki takie jak 2048 lub 4096. Nie jestem pewien, czy coś przeoczyłem.

Poniżej animacja pokazuje kilka ostatnich kroków gry granej przez agenta AI z graczem komputerowym:

Wszelkie spostrzeżenia będą naprawdę bardzo pomocne, z góry dziękuję. (To jest link mojego posta na blogu do artykułu: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/)

Poniższa animacja pokazuje kilka ostatnich etapów gry, w których Agent gracza AI mógł uzyskać 2048 punktów, tym razem dodając również wartość bezwzględną heurystyczną:

Poniższe rysunki przedstawiają drzewo gry badane przez agenta si gracza zakładając komputer jako przeciwnika dla tylko jeden krok:

Napisałem solver 2048 w Haskell, głównie dlatego, że właśnie uczę się tego języka.

Moja implementacja gry różni się nieco od rzeczywistej gry, tym, że nowa płytka jest zawsze "2"(zamiast 90% 2 i 10% 4). I że nowa płytka nie jest przypadkowa, ale zawsze pierwsza dostępna od lewego górnego rogu. Wariant ten jest również znany jako Det 2048 .

Użyłem wyczerpującego algorytmu, który faworyzuje puste płytki. Wykonuje dość szybko na głębokości 1-4, ale na głębokości 5 robi się dość powolny w około 1 sekundzie na ruch.

Poniżej znajduje się kod implementujący algorytm rozwiązywania. Siatka jest reprezentowana jako tablica liczb całkowitych o długości 16. A punktacja odbywa się po prostu przez policzenie liczby pustych kwadratów.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Kod źródłowy może znajdziesz tutaj: https://github.com/popovitsj/2048-haskell

Ten algorytm nie jest optymalny do wygrania gry, ale jest dość optymalny pod względem wydajności i ilości potrzebnego kodu:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

Wiele innych odpowiedzi wykorzystuje sztuczną inteligencję z kosztownymi obliczeniowo poszukiwaniami możliwej przyszłości, heurystyki, uczenia się i tym podobnych. Są one imponujące i prawdopodobnie poprawne, ale chciałbym wnieść inny pomysł.

Modeluj rodzaj strategii, którą używają dobrzy gracze w grze.

Na przykład:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Czytaj kwadraty w kolejności pokazanej powyżej, aż wartość kolejnych kwadratów będzie większa od bieżącej. Przedstawia to problem próby połączenia kolejna płytka o tej samej wartości na ten kwadrat.

Aby rozwiązać ten problem, ich są 2 sposoby poruszania się, które nie są w lewo lub gorzej, a badanie obu możliwości może natychmiast ujawnić więcej problemów, tworzy to Listę zależności, każdy problem wymaga innego problemu, aby rozwiązać pierwszy. Myślę, że mam ten łańcuch lub w niektórych przypadkach drzewo zależności wewnętrznie przy podejmowaniu decyzji mój następny ruch, szczególnie gdy zatrzymany.

Płytka wymaga połączenia z sąsiadem, ale jest zbyt mały: Połącz innego sąsiada z tym.

Większy kafelek w sposób: zwiększ wartość mniejszego otaczającego kafelka.

Itd...

Całe podejście będzie prawdopodobnie bardziej skomplikowane niż to, ale nie dużo bardziej skomplikowane. Może to być ten mechaniczny w odczuciu braku punktów, ciężarów, neuronów i głębokich poszukiwań możliwości. Drzewo możliwości musi być nawet na tyle duże, aby w ogóle wymagało rozgałęzień.