Stuck with Tic Tac Toe

Stuck with Tic Tac Toe
0

#1

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


#2

One of the problems with Tic tac toe is trying to follow someone else’s logic. I also used winning combos but I also had an array of scores for the 8 possible combos. They all started a 0 and if the computer move all affected combos would have 1 point added. If the user moved 5 points added. Then I could scan for a 2 in the array to see if the computer could win - if none scan for 10 to see if the computer needed to stop the user. And if found I knew which line to check


#3

Debugging recursive algorithms can be a pain, and this could take a while. As much as I’d love to help, I just don’t have it in me. I do have a few tips, though:

  1. Don’t take shortcuts with your code. There’s really no reason to omit curly braces of code blocks, for instance, but it can make the code harder to read, and it can introduce bugs.

  2. CodePen has a debug view that will let you use the browser’s code debugger. That should help you follow what your code is doing. CodeSchool has a free and in-depth course on using the dev tools in Chrome (link) if you need a lesson or a refresher.

  3. Since it’s not picking a winner, but it seems to be picking moves, you can set your first breakpoint somewhere around where the code evaluates winning solutions and see what it’s saying for (what should be) a winning state.

I feel for you. This was one of the most daunting projects in the whole course if you go for the working A.I. It looks like you’re really close, though, and your code is otherwise pretty well organized. Good luck!


#4

I appreciate the replies. I ended up recreating it from scratch, but it still has a few bugs. Definitely one of my least favorite projects so far.


#5

Same thing is happening to me here!! :unamused:


#6

Okay, for anyone who comes across this topic, and sees my code. The issue was my misunderstanding that Javascript would check for index of an element in successfully without checking for the type. As in, if you have an array of [1,2,“3”,4], doing indexOf(3) would return 2, instead of -1. I fixed the problem after tons of console.log() abuse and just had to add a “+” in my code.

It goes to show that the smallest mistakes can cause the biggest problems. Also that I prefer C++ and strict typing for a reason.

To anyone stuck with this project, try doing the (far easier) Simon project, come back and you might find the issue with your code like I did. Good luck!

Working logic: http://codepen.io/imtoobose/pen/MeJZRp?editors=0011


#7

Great Project mate! I just wanna ask did u make the code of minimax on your own after getting the basic idea of how the algorithm works. Or u took some help from somewhere else. Actually, the reason I am asking this is that I found a really good article on implementing this algorithm in tic tac https://medium.freecodecamp.org/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37. I get the basic idea of the algorithm from there and also used most of his logic/code and tried to blend in my code with the code he used in minmax. I am just concerned and kinda embarrassed too that I am using someone else code (even though I know how the code works) and then there is you who wrote his own minmax !!


#8

I saw a part of your code that I think is not easy to manage. For instance if you remove the element or the class once the player click on a cell, would be simpler than manage what’s available or not. I hope that it will help you.