Hello Campers. I’ve been unsuccessfully trying to make a Tic Tac Toe game for a while. First I tried to make an algorithm myself, but it often led to bad predictions by the AI. I ended up trying to implement a Minimax algorithm, but as of now it simply takes forever to get the result, and actually doesn’t even give an output. It seems that the winner is never set, as far as I can tell, but I cannot figure out why this is happening. I would really appreciate some help.
Here is the JS code:
var state = {
player: computer,
win : 0,
};
var computer = {
token : 'x',
name : 'computer',
avail : []
};
var human = {
token : 'o',
name : 'human',
avail : []
};
var game = {
board : [0,0,0,0,0,0,0,0,0],
win_combos : [[0,1,2], [0,3,6], [0,4,8],
[1,4,7], [2,4,6], [2,5,8],
[6,7,8], [3,4,5]] ,
possible : function(board){
var b=[];
for(var i in board){
if(board[i]===0) b.push(i);
}
return b;
},
isWinner :
function(){
var list=[human, computer];
for (var p in list){
var player = list[p];
var pos = player.avail;
var combo = this.win_combos;
var won;
for(var i in combo){
won=true;
var combo_now=combo[i];
for(var j in combo_now){
if(pos.indexOf(combo_now[j])==-1)
{
won=false;
break;
}
}
if(won){
return player;
}
}
}
return false;
},
isComplete : function(){
if((this.possible(this.board)).length===0) return true;
else if (this.isWinner()!= false) return true;
else return false;
},
getOpposite : function(player){
if(player.name=='computer')
return human;
else return computer;
}
};
function minimax(player){
if(game.isComplete()){
var winner = game.isWinner();
if(winner==false)
return 0;
else if (winner.name=='computer')
return 100;
else
return -100;
}
var moves = game.possible(game.board);
if(player.name=='computer')
var best = -10000;
else
best= 10000;
var now = 0;
for(var i in moves){
game.board[moves[i]] = player.token;
player.avail.push(moves[i]);
var score = minimax(game.getOpposite(player));
var t = player.avail.pop();
game.board[moves[i]]=0;
if(player.name=='computer'){
if(score>best){$
best=score;
}
}
else{
if(score<best){
best=score;
}
}
}
return best;
}
function play(){
var best = null;
var bestmove = null;
var p = game.possible(game.board);
for(var i in p){
game.board[p[i]]=computer.token;
var now = minimax(computer);
game.board[p[i]]=0;
if(now>best){
best=now;
bestmove=+p[i];
}
}
game.board[bestmove]=computer.token;
computer.avail.push(bestmove);
console.log(bestmove);
$('#val-'+bestmove+' > div').html(computer.token);
$("#val-"+bestmove).addClass('disabled');
}
$('.box').on('click', function(e){
var id= '#'+e.target.id;
var val= id.slice(-1);
game.board[val]=human.token;
$(id+' > div').html(human.token);
$(id).addClass('disabled');
human.avail.push(+val);
play();
});
Codepen.io link: http://codepen.io/imtoobose/pen/xOOpwa?editors=0011