algorithm - чтобы - Каков оптимальный алгоритм игры 2048?




скрипт для игры 2048 (10)

Меня заинтересовала идея AI для этой игры, в которой нет жестко закодированного интеллекта (т. Е. Нет эвристики, функции подсчета очков и т. Д.). ИИ должен «знать» только правила игры и « определять» игру. Это контрастирует с большинством ИИ (например, в этой теме), где игра представляет собой по существу грубую силу, управляемую функцией подсчета, представляющей человеческое понимание игры.

Алгоритм ИИ

Я нашел простой, но удивительно хороший игровой алгоритм. Чтобы определить следующий ход для данной доски, ИИ играет в игру в памяти, используя случайные ходы, пока игра не закончится. Это делается несколько раз, отслеживая конечный результат игры. Затем вычисляется средний конечный балл за начальный ход . В качестве следующего шага выбирается начальный ход с наивысшим средним конечным счетом.

Всего за 100 прогонов (т. Е. В играх с памятью) за ход AI достигает 2048 плит в 80% случаев, а 4096 - в 50% случаев. При использовании 10000 трасс получается 2048 плитка 100%, 70% для 4096 плиток и около 1% для плитки 8192.

Смотрите это в действии

Показатель наилучшего результата показан здесь:

Интересный факт об этом алгоритме заключается в том, что в то время как игры с произвольным воспроизведением неудивительно плохи, выбор лучшего (или наименее плохого) хода приводит к очень хорошей игре: типичная игра AI может достигать 70000 очков и последних 3000 ходов, однако в играх с произвольной игрой в памяти из любой заданной позиции дают в среднем 340 дополнительных очков примерно за 40 дополнительных ходов перед смертью. (Вы можете это увидеть сами, запустив ИИ и откройте консоль отладки.)

Этот график иллюстрирует этот момент: синяя линия показывает оценку доски после каждого хода. Красная линия показывает наилучший случайный выигрыш в игре с конечной игрой с этой позиции. По сути, красные значения «тянут» синие значения вверх к ним, поскольку они являются наилучшим предположением алгоритма. Интересно видеть, что красная линия находится всего лишь чуть выше синей линии в каждой точке, но синяя линия продолжает расти все больше и больше.

Я нахожу довольно удивительным, что алгоритм не должен фактически предвидеть хорошую игру, чтобы выбрать ходы, которые ее производят.

Поиск позже я нашел, что этот алгоритм может быть классифицирован как алгоритм поиска чистого Монте-Карло .

Реализация и ссылки

Сначала я создал версию JavaScript, которую можно увидеть здесь . Эта версия может запустить 100-ые прогоны в достойное время. Откройте консоль для дополнительной информации. ( source )

Позже, чтобы поиграть еще немного, я использовал @nneonneo высоко оптимизированную инфраструктуру и реализовал мою версию на C ++. Эта версия позволяет до 100000 ходов за ход и даже 1000000, если у вас есть терпение. Указания по строительству. Он запускается в консоли и также имеет пульт дистанционного управления для воспроизведения веб-версии. ( source )

Результаты

Удивительно, но увеличение числа проходов не приводит к существенному улучшению игры. Кажется, что предел этой стратегии составляет около 80000 пунктов с плитой 4096 и всеми меньшими, очень близкими к достижению плитки 8192. Увеличение количества пробегов от 100 до 100000 увеличивает шансы попасть на этот счет (от 5% до 40%), но не пробивать его.

Выполнение 10000 пробегов с временным увеличением до 1000000 вблизи критических позиций позволило преодолеть этот барьер менее чем в 1% случаев, достигнув максимального значения 129892 и плитки 8192.

улучшения

После реализации этого алгоритма я попробовал много улучшений, включая использование минимальных или максимальных значений или комбинацию min, max и avg. Я также попытался использовать глубину: вместо того, чтобы пытаться выполнить К за каждый ход, я попробовал K движений на один список перемещения заданной длины (например, вверх, вверх, влево) и выбора первого хода списка наилучшего скоринга.

Позже я реализовал табличное дерево, в котором учитывалась условная вероятность того, что вы сможете сыграть движение после определенного списка перемещений.

Однако ни одна из этих идей не показала реального преимущества над простой первой идеей. Я оставил код для этих идей, прокомментированных в коде C ++.

Я добавил механизм «Глубокий поиск», который временно увеличил количество прогона до 1000000, когда любой из прогонов удалось случайно достичь следующей самой высокой плитки. Это позволило улучшить время.

Мне было бы интересно услышать, есть ли у кого-нибудь другие идеи улучшения, которые поддерживают независимость домена от ИИ.

2048 Варианты и клоны

Просто для удовольствия, я также реализовал AI как букмарклет , подключившись к элементам управления игры. Это позволяет ИИ работать с оригинальной игрой и многими ее вариантами .

Это возможно из-за не зависящей от домена природы ИИ. Некоторые из вариантов довольно различны, например, шестиугольный клон.

Я недавно наткнулся на игру 2048 . Вы объединяете подобные плитки, перемещая их в любом из четырех направлений, чтобы сделать «большие» плитки. После каждого шага новая плитка появляется в случайном пустом месте со значением 2 или 4 . Игра заканчивается, когда все поля заполняются, и нет движений, которые могут объединять плитки, или вы создаете плитку со значением 2048 .

Во-первых, мне нужно следовать четко определенной стратегии достижения цели. Итак, я подумал о написании программы для нее.

Мой текущий алгоритм:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

То, что я делаю, в какой-то момент, я попытаюсь объединить плитки со значениями 2 и 4 , то есть я попытаюсь иметь 2 и 4 плитки как можно меньше. Если я попробую так, все остальные плитки автоматически объединяются, и стратегия кажется хорошей.

Но, когда я использую этот алгоритм, я добираюсь до 4000 очков до того, как игра закончится. Максимальные баллы AFAIK составляют чуть более 20 000 очков, что намного больше, чем мой текущий балл. Есть ли лучший алгоритм, чем выше?


Моя попытка использует expectimax как другие решения выше, но без битов. Решение Nneonneo может проверять 10 миллионов движений, что составляет приблизительно 4 глубины с 6 плитами слева и возможно 4 хода (2 * 6 * 4) 4 . В моем случае эта глубина занимает слишком много времени, чтобы исследовать, я настраиваю глубину ожидаемого поиска в соответствии с количеством оставшихся свободных фрагментов:

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

Оценки досок вычисляются с помощью взвешенной суммы квадрата числа свободных плиток и точечного произведения 2D-сетки:

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

который заставляет организовать плитку, спускающуюся в виде змеи с верхней левой плитки.

Код ниже или 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>


Я копирую здесь содержание сообщения в своем блоге

Решение, которое я предлагаю, очень просто и легко реализовать. Хотя, он достиг отметки 131040. Представлены несколько эталонных характеристик алгоритма.

Алгоритм

Эвристический алгоритм подсчета очков

Предположение, на котором основан мой алгоритм, довольно просто: если вы хотите достичь более высокого балла, совет должен быть максимально аккуратным. В частности, оптимальная установка задается линейным и монотонным убывающим порядком значений плитки. Эта интуиция даст вам также верхнюю границу для значения плитки: где n - количество плиток на доске.

(Есть возможность дойти до плитки 131072, если 4-плитка случайно генерируется вместо 2-х плит, когда это необходимо)

Два возможных способа организации доски показаны на следующих изображениях:

Чтобы обеспечить координацию плиток в монотонном убывающем порядке, оценка si вычисляется как сумма линеаризованных значений на доске, умноженная на значения геометрической последовательности с общим отношением r <1.

Несколько линейных путей можно оценить сразу, окончательный счет будет максимальным счетом любого пути.

Правило принятия решений

Реализованное правило решения не совсем разумно, здесь представлен код в Python:

@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);

Реализация minmax или Expectiminimax наверняка улучшит алгоритм. Очевидно, что более сложное правило принятия решения замедлит алгоритм, и для его выполнения потребуется некоторое время. В ближайшем будущем я попытаюсь выполнить минимаксную реализацию. (Оставайтесь в курсе)

эталонный тест

  • T1 - 121 тест - 8 различных путей - r = 0.125
  • T2 - 122 испытания - 8-разные пути - r = 0,25
  • T3 - 132 испытания - 8-разные пути - r = 0,5
  • T4 - 211 тест - 2-разные пути - r = 0.125
  • T5 - 274 испытания - 2-разные пути - r = 0,25
  • Тесты Т6 - 211 - 2-разные пути - r = 0,5

В случае T2 четыре теста из десяти генерируют 4096 плитку со средним баллами 42000

Код

Код можно найти на GiHub по следующей ссылке: https://github.com/Nicola17/term2048-AI Он основан на term2048 и написан на Python. Я как можно скорее реализую более эффективную версию на C ++.


Я разработал 2048 AI, используя оптимизацию expectimax , вместо минимаксного поиска, используемого алгоритмом @ ovolve. AI просто выполняет максимизацию по всем возможным ходам, а затем ожидание по всем возможным появлениям плит (взвешенных по вероятности черепицы, то есть 10% для 4 и 90% для 2). Насколько мне известно, невозможно оптимизировать оптимизацию expectimax (за исключением того, что удаляются ветви, которые чрезвычайно маловероятны), поэтому используемым алгоритмом является тщательно оптимизированный поиск грубой силы.

Спектакль

AI в своей конфигурации по умолчанию (максимальная глубина поиска 8) занимает от 10 мс до 200 мс для выполнения перемещения в зависимости от сложности положения платы. При тестировании AI достигает средней скорости перемещения 5-10 ходов в секунду в течение всей игры. Если глубина поиска ограничена 6 ходами, ИИ может легко выполнить 20+ ходов в секунду, что вызывает интересное наблюдение .

Чтобы оценить эффективность оценки AI, я запустил AI 100 раз (подключен к игре браузера с помощью пульта дистанционного управления). Для каждой плитки здесь приведены пропорции игр, в которых эта плитка была достигнута хотя бы один раз:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Минимальный балл по всем проходам составил 124024; максимальный результат составил 794076. Средний балл - 387222. ИИ никогда не получал 2048 плит (поэтому он никогда не терял игру даже один раз в 100 играх); на самом деле, он достиг 8192 плитки хотя бы раз в каждом запуске!

Вот скриншот лучшего запуска:

Эта игра заняла 27830 ходов за 96 минут, или в среднем 4,8 ходов в секунду.

Реализация

Мой подход кодирует всю доску (16 записей) как одно 64-битное целое число (где плитки - это nybbles, то есть 4-битные куски). На 64-битной машине это позволяет передавать всю плату в одном машинном регистре.

Операции сдвига бит используются для извлечения отдельных строк и столбцов. Одна строка или столбец - это 16-разрядное количество, поэтому таблица размером 65536 может кодировать преобразования, которые работают с одной строкой или столбцом. Например, ходы реализованы в виде 4 поисков в предварительно вычисленную «таблицу эффектов перемещения», которая описывает, как каждое перемещение влияет на одну строку или столбец (например, таблица «переместить вправо» содержит запись «1122 -> 0023», описывающая, как строка [2,2,4,4] становится строкой [0,0,4,8] при перемещении вправо).

Оценка также выполняется с помощью поиска в таблице. Таблицы содержат эвристические оценки, рассчитанные на все возможные строки / столбцы, и итоговый балл для доски - это просто сумма значений таблицы для каждой строки и столбца.

Это представление платы, наряду с подходом к поиску таблицы для движения и подсчета очков, позволяет AI быстро искать огромное количество игровых состояний (более 10 000 000 состояний игры в секунду на одном ядре моего ноутбука середины 2011 года).

Сам поиск expectimax кодируется как рекурсивный поиск, который чередуется с шагами «ожидания» (проверяя все возможные места и значения места появления плит и взвешивая их оптимизированные оценки по вероятности каждой возможности) и шаги «максимизации» (тестирование всех возможных ходов и выбрав тот, у которого лучший результат). Поиск дерева заканчивается, когда он видит ранее увиденную позицию (используя таблицу транспонирования ), когда он достигает предопределенного предела глубины или когда он достигает состояния платы, которое маловероятно (например, это было достигнуто путем получения 6 "4" плиток в строке от исходного положения). Типичная глубина поиска - 4-8 ходов.

Эвристика

Несколько эвристик используются для направления алгоритма оптимизации на выгодные позиции. Точный выбор эвристики оказывает огромное влияние на производительность алгоритма. Различные эвристики взвешиваются и объединяются в позиционный балл, который определяет, насколько «хороша» данная позиция на борту. Затем поиск по оптимизации нацелен на максимизацию среднего балла всех возможных позиций на борту. Фактический балл, как показано в игре, не используется для вычисления оценки платы, поскольку он слишком сильно взвешен в пользу слияния плиток (когда отсроченное слияние может принести большую пользу).

Первоначально я использовал две очень простые эвристики, предоставляя «бонусы» для открытых квадратов и для больших значений на краю. Эти эвристики выполнялись довольно хорошо, часто достигая 16384, но никогда не добирались до 32768.

Петр Моравек (@xificurk) взял мой ИИ и добавил две новые эвристики. Первая эвристика была штрафом за немонотонные строки и столбцы, которые увеличивались по мере увеличения рангов, гарантируя, что немонотонные строки небольших чисел не будут сильно влиять на оценку, но немонотонные ряды больших чисел существенно повредят. Вторая эвристика подсчитала количество потенциальных слияний (смежных равных значений) в дополнение к открытым пространствам. Эти две эвристики служили для того, чтобы подтолкнуть алгоритм к монотонным доскам (которые легче слить) и к посадкам на полях с большим количеством слияний (поощряя его выравнивать слияния, где это возможно, для большего эффекта).

Кроме того, Петр также оптимизировал эвристические веса с использованием стратегии «мета-оптимизации» (используя алгоритм CMA-ES ), где сами веса были скорректированы для получения максимально возможного среднего балла.

Эффект этих изменений чрезвычайно важен. Алгоритм пошел от достижения плитки 16384 около 13% времени, чтобы достичь ее более 90% времени, и алгоритм начал добиваться 32768 в течение 1/3 времени (тогда как старые эвристики никогда не производили 32768 плит) ,

Я считаю, что по эвристике еще есть возможности для улучшения. Этот алгоритм определенно еще не «оптимален», но я чувствую, что он приближается.

То, что ИИ достигает 32768 плит в более чем одной трети своих игр, является огромной вехой; Я с удивлением узнаю, достигли ли какие-либо игроки в игре 32768 в официальной игре (т. Е. Без использования таких инструментов, как спасение или отмена). Я думаю, что плитка 65536 находится в пределах досягаемости!

Вы можете попробовать ИИ для себя. Код доступен по адресу https://github.com/nneonneo/2048-ai .


Алгоритм

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

    choose the maximum evaluation
}

оценка

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)

Информация об оценке

128 (Constant)

Это константа, используемая в качестве базовой линии и для других целей, таких как тестирование.

+ (Number of Spaces x 128)

Больше пробелов делает состояние более гибким, умножаем на 128 (что является медианом), так как сетка, заполненная 128 грани, является оптимальным невозможным состоянием.

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

Здесь мы оцениваем лица, которые имеют возможность слиться, оценивая их назад, плитка 2 становится значащей 2048, а плитка 2048 оценивается 2.

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

Здесь нам еще нужно проверить значения в виде стеков, но в меньшей степени, которые не прерывают параметры гибкости, поэтому мы имеем сумму {x в [4,44]}.

+ (Number of possible next moves x 256)

Состояние более гибкое, если у него больше свободы возможных переходов.

+ (Number of aligned values x 2)

Это упрощенная проверка возможности слияния в этом состоянии, не заглядывая в будущее.

Примечание. Константы могут быть изменены.


Это не прямой ответ на вопрос OP, это больше из материалов (экспериментов), которые я до сих пор пытался решить одну и ту же проблему, и получил некоторые результаты и получил некоторые замечания, которые хочу поделиться, мне интересно, можем ли мы Дальнейшее понимание этого.

Я просто попытался реализовать минимаксную реализацию с альфа-бета-обрезкой с обрезкой глубины поиска в 3 и 5. Я пытался решить ту же проблему для сетки 4x4 как назначение проекта для курса edX ColumbiaX: CSMM.101x Artificial Intelligence ( AI) .

Я применил выпуклую комбинацию (испробовал различные эвристические веса) пары эвристических оценочных функций, в основном из интуиции и из тех, которые обсуждались выше:

  1. Монотонность
  2. Свободное пространство доступно

В моем случае компьютерный плейер полностью случайный, но все же я принял состязательные настройки и реализовал агент игрока AI в качестве максимального игрока.

У меня есть сетка 4x4 для игры.

Наблюдение:

Если я назначаю слишком много веса первой эвристической функции или второй эвристической функции, то оба случая, на которые попадает игрок AI, являются низкими. Я играл со многими возможными назначениями веса для эвристических функций и принимал выпуклую комбинацию, но очень редко игрок AI мог забивать 2048. В большинстве случаев он либо останавливается на 1024, либо на 512.

Я также испробовал угол эвристический, но почему-то он делает результаты хуже, любую интуицию почему?

Кроме того, я попытался увеличить отключение глубины поиска с 3 до 5 (я не могу увеличить его больше, так как поиск этого пространства превышает допустимое время даже с обрезкой) и добавил еще одну эвристику, которая смотрит на значения соседних плит и дает больше очков, если они слияния, но все же я не могу получить 2048.

Я думаю, что лучше использовать Expectimax вместо минимаксного, но все же я хочу решить эту проблему только с минимаксным и получить высокие оценки, такие как 2048 или 4096. Я не уверен, что у меня что-то не хватает.

Ниже анимации показаны последние несколько шагов игры, которую играет агент AI с компьютерным проигрывателем:

Любые идеи будут очень полезными, спасибо заранее. (Это ссылка моего сообщения в блоге для статьи: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )

Следующая анимация показывает последние несколько шагов игры, в которых агент AI-игрока может получить 2048 баллов, на этот раз добавив также эвристику абсолютного значения:

На следующих рисунках показано игровое дерево, изученное агентом игрока игрока, предполагающим, что компьютер является противником всего за один шаг:


Я думаю, что нашел алгоритм, который работает достаточно хорошо, так как я часто достигаю более 10000 баллов, мой личный опыт составляет около 16000. Мое решение не нацелено на то, чтобы держать самые большие числа в углу, но держать его в верхнем ряду.

См. Следующий код:

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);
}

Я написал 2048-решатель в Haskell, главным образом потому, что сейчас изучаю этот язык.

Моя реализация игры немного отличается от реальной игры тем, что новая плитка всегда «2» (а не 90% 2 и 10% 4). И то, что новая плитка не случайна, но всегда первая из доступных слева вверху. Этот вариант также известен как Det 2048 .

Как следствие, этот решатель детерминирован.

Я использовал исчерпывающий алгоритм, который поддерживает пустые плитки. Он работает довольно быстро для глубины 1-4, но на глубине 5 он замедляется примерно на 1 секунду за ход.

Ниже приведен код реализации алгоритма решения. Сетка представлена ​​как массив из 16-ти целых чисел. И подсчет очков производится просто путем подсчета количества пустых квадратов.

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] ]

Я думаю, что это довольно успешно для его простоты. Результат, который он достигает, начиная с пустой сетки и решения на глубине 5:

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

Game Over

Исходный код можно найти здесь: https://github.com/popovitsj/2048-haskell


Многие из других ответов используют ИИ с вычислительно дорогостоящим поиском возможных фьючерсов, эвристики, обучения и тому подобного. Это впечатляющий и, вероятно, правильный путь вперед, но я хочу внести еще одну идею.

Моделируйте стратегию, которую используют хорошие игроки игры.

Например:

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

Прочтите квадраты в порядке, указанном выше, до тех пор, пока следующее значение квадрата больше текущего. Это представляет проблему попыток слить еще одну плиту того же значения в этот квадрат.

Чтобы решить эту проблему, у них есть два способа перемещения, которые не остаются или хуже, и рассмотрение обеих возможностей может сразу выявить больше проблем, это составляет список зависимостей, каждая проблема, требующая решения первой проблемы. Я думаю, что у меня есть эта цепочка или в некоторых случаях дерево зависимостей внутри, когда я решаю свой следующий ход, особенно когда застрял.

Плитка нуждается в слиянии с соседом, но слишком мала: объедините другого соседа с этим.

Увеличенная плитка в пути: Увеличьте значение меньшего размера вокруг плитки.

так далее...

Весь подход, вероятно, будет более сложным, чем это, но не намного сложнее. Это может быть эта механическая в ощущении нехватки баллов, весов, нейронов и глубоких поисков возможностей. Дерево возможностей rairly даже должно быть достаточно большим, чтобы потребоваться какое-либо разветвление вообще.


Я являюсь автором контроллера 2048, который лучше, чем любая другая программа, упомянутая в этом потоке. Эффективная реализация контроллера доступна на github.com/aszczepanski/2048 . В отдельном репо есть также код, используемый для обучения функции оценки состояния контроллера. Метод обучения описан в paper .

Контроллер использует expectimax-поиск с функцией оценки состояния, полученной с нуля (без экспертизы человека 2048) по варианту обучения с временным различием (метод обучения усилению). Функция состояния-значения использует сеть n-кортежей , которая в основном представляет собой взвешенную линейную функцию шаблонов, наблюдаемых на доске. Всего в нем было более 1 миллиарда весов .

Спектакль

При 1 ходу / с: 609104 (100 игр в среднем)

При 10 ходах / с: 589355 (300 игр в среднем)

При 3-слойном (около 1500 ходов / с): 511759 (в среднем по 1000 игр)

Статистика черепицы для 10 ходов / сек выглядит следующим образом:

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

(Последняя строка означает наличие заданных фрагментов одновременно на плате).

Для 3-слойного:

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

Тем не менее, я никогда не видел, чтобы он получал плиту 65536.





2048