Can someone please help me with this? I'm trying to program an AI for my Tic-Tac-Toe game, all relevant searches have brought me to the minimax algorithm. From everything I read and watched I have a basic understanding of the theory behind the algorithm. What I'm having trouble with is the actual application of it in my game. I know that this algorithm is essentially supposed to play out each move and return a score based on the state of the board. How do I make it play a different combination every time? How do I make sure I get every combo? After it finds a winning state how do I return the correct move from that? Am I supposed to store each state in an array? Sorry for all the questions I'm just trying to solidify my understanding and make sure I can actually put into practice the things I'm reading. I am providing my javascript code for the game and hopefully someone can point me in the right direction here. Thank You.
$(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();
});
});
First you need a score :: Configuration -> N function. A configuration is the current state of the board.
We can draw the tree of all possible configurations. Leaves contain the score of the board. MAX is you, MIN is your opponent:
Configuration Player
A MAX
/ \
B C MIN
/ \ / \
D,1 E,3 F,2 G,1 MAX
minmax is a recursive algorithm traversing this tree. It computes the best choice (based on your score function) for the given configuration and the player. Note that MAX's goal is to maximize the score and MIN's goal is to minimize it.
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) returns the greatest score that the MIN player can force you to achieve, i.e. it guarantees that no matter what strategy you opponent plays you can always achieve at least minMax(c, MAX) score.
- How do I make it play a different combination every time?
Your score function can be random. For example: score(c) = deterministic_score(c) + rand() * 0.0001.
- How do I make sure I get every combo?
You have to properly implement the move generating algorithm.
- After it finds a winning state how do I return the correct move from that?
If your score function returns +inf for the winning state and you always choose the move returned by the getBestMove then you'll always end up in the winning state (provided your opponend does not have a counter strategy for it and the depth of the search is unlimited).
- Am I supposed to store each state in an array?
You can just generate all the moves and modify the board on the fly.