Реализация минимакса
Может кто-нибудь помочь мне с этим? Я пытаюсь запрограммировать ИИ для моей игры в крестики-нолики, все соответствующие поиски привели меня к минимаксному алгоритму. Из всего, что я читал и смотрел, у меня есть базовое понимание теории, лежащей в основе алгоритма. У меня проблемы с фактическим применением этого в моей игре. Я знаю, что этот алгоритм, по сути, должен проигрывать каждый ход и возвращать очки в зависимости от состояния доски. Как мне заставить ее разыгрывать разные комбинации каждый раз? Как мне убедиться, что я получаю все комбо? После того, как он находит выигрышное состояние, как мне вернуть правильный ход из этого? Я должен хранить каждое состояние в массиве? Извините за все вопросы, которые я просто пытаюсь укрепить в моем понимании и убедиться, что я действительно могу применить на практике то, что я читаю. Я предоставляю свой код JavaScript для игры, и, надеюсь, кто-то может указать мне правильное направление здесь. Благодарю вас.
$(document).ready(function() {
var x = 'X';
var o = 'O';
var newgame = function() {
turn = x;
sqrData = '';
xMoves = [false,false,false,false,false,false,false,false,false,false,false,false];
oMoves = [false,false,false,false,false,false,false,false,false,false,false,false];
squareFree = [false,true,true,true,true,true,true,true,true,true];
moveCount = 0;
compPlayer = false;
playboard = [false,[false,true,true,true],[false,true,true,true],[false,true,true,true]]
$('div').html('');
$('#reset').html('Reset Game');
};
newgame();
$('#fir').click(function() {
turnchange(1,1,1,$(this));
});
$('#sec').click(function() {
turnchange(2,1,2,$(this));
});
$('#thir').click(function() {
turnchange(3,1,3,$(this));
});
$('#four').click(function() {
turnchange(4,2,1,$(this));
});
$('#fiv').click(function() {
turnchange(5,2,2,$(this));
});
$('#six').click(function() {
turnchange(6,2,3,$(this));
});
$('#sev').click(function() {
turnchange(7,3,1,$(this));
});
$('#eight').click(function() {
turnchange(8,3,2,$(this));
});
$('#nine').click(function() {
turnchange(9,3,3,$(this));
});
var turnchange = function(playerSquare,playRow,playCol,sqrData) {
playboard[playRow][playCol] = turn;
console.log(playboard);
if (squareFree[playerSquare] == true) {
$(sqrData).html(turn);
if (turn == x) {
xMoves[playerSquare] = true;
turn = o;
}
else if (turn == o) {
oMoves[playerSquare] = true;
turn = x;
}
squareFree[playerSquare] = false;
moveCount++;
checkwin($(this));
}
};
var checkwin = function() {
if ((xMoves[1] && xMoves[2] && xMoves[3]) || (xMoves[1] && xMoves[4] && xMoves[7]) ||
(xMoves[1] && xMoves[5] && xMoves[9]) || (xMoves[2] && xMoves[5] && xMoves[8]) ||
(xMoves[3] && xMoves[6] && xMoves[9]) || (xMoves[4] && xMoves[5] && xMoves[6]) || (xMoves[7] && xMoves[8] && xMoves[9]) ||
(xMoves[3] && xMoves[5] && xMoves[7])) {
$('#game').html('Game Over - X Wins');
deactivateSquares();
}
else if ((oMoves[1] && oMoves[2] && oMoves[3]) || (oMoves[1] && oMoves[4] && oMoves[7]) ||
(oMoves[1] && oMoves[5] && oMoves[9]) || (oMoves[2] && oMoves[5] && oMoves[8]) ||
(oMoves[3] && oMoves[6] && oMoves[9]) || (oMoves[4] && oMoves[5] && oMoves[6]) || (oMoves[7] && oMoves[8] && oMoves[9]) ||
(oMoves[3] && oMoves[5] && oMoves[7])) {
$('#game').html('Game Over - O Wins');
deactivateSquares();
}
else if (moveCount == 9) {
$('#game').html('Its a Draw');
}
};
var deactivateSquares = function() {
for (var e in squareFree) {
squareFree[e]= false;
}
};
$('#reset').click(function(){
newgame();
});
});
1 ответ
Сначала тебе нужен score :: Configuration -> N функция. Конфигурация - это текущее состояние платы.
Мы можем нарисовать дерево всех возможных конфигураций. Листья содержат счет доски. MAX это ты, MIN Ваш противник:
Configuration Player
A MAX
/ \
B C MIN
/ \ / \
D,1 E,3 F,2 G,1 MAX
minmax рекурсивный алгоритм, пересекающий это дерево Он рассчитывает лучший выбор (на основе вашего score функция) для данной конфигурации и игрока. Обратите внимание, что MAXЦель состоит в том, чтобы максимизировать score а также MINЦель - минимизировать это.
minMax(c, player)
if c is leaf:
return score(c)
if player == MAX:
bestScore = -inf
moves = generateAllMoves(c)
for each move m in moves:
c = makeMove(c, m)
currScore = minMax(c, MIN)
if currScore > bestScore
bestScore = currScore
c = undoMove(c, m)
return bestScore
if player == MIN:
bestScore = +inf
moves = generateAllMoves(c)
for each move m in moves:
c = makeMove(c, m)
bestScore = minMax(c, MAX)
if currScore < bestScore
score = currScore
c = undoMove(c, m)
return bestScore
getBestMove(c):
bestScore = -inf
bestMove = null
for each move m in c:
c = makeMove(c, m)
currScore = minMax(c, MIN)
if currScore > bestScore
bestScore = currScore
bestMove = m
c = undoMove(c, m)
return bestMove
minMax(c, MAX) возвращает наибольшее количество очков, что MIN игрок может заставить вас достичь, то есть он гарантирует, что независимо от того, какую стратегию играет ваш оппонент, вы всегда можете достичь по крайней мере minMax(c, MAX) Гол.
- Как мне заставить ее разыгрывать разные комбинации каждый раз?
Ваша функция оценки может быть случайной. Например: score(c) = deterministic_score(c) + rand() * 0.0001,
- Как мне убедиться, что я получаю все комбо?
Вы должны правильно реализовать алгоритм генерации ходов.
- После того, как он находит выигрышное состояние, как мне вернуть правильный ход из этого?
Если твой score функция возвращает +inf для состояния победы, и вы всегда выбираете ход, возвращаемый getBestMove тогда вы всегда окажетесь в выигрышном состоянии (при условии, что у вашего противника нет контрстратегии для него и глубина поиска не ограничена).
- Я должен хранить каждое состояние в массиве?
Вы можете просто генерировать все ходы и изменять доску на лету.