I am attempting to create a Tic Tac Toe game using Javascript as part of my learning on FreeCodeCamp and after my 5th attempt still haven't managed to get it to work. I think i'm doing the correct thing, but the computer AI is still making very stupid decisions and loosing.
Here is my entire AI function, which can be called using a console log to see the recommended move from the AI. However when i hard code values for moves already taken and ask for the next move, it doesn't pick what i would expect.
/*
Attempt to inplement a Tic Tac Toe minimax game
5th attempt, so hopefully this time it works!
*/
var util = require("util");
//These are all the winning square sequences, as string to make various things easier
var validRows = [
['00','01','02'], // left column
['10','11','12'], // middle column
['20','21','22'], // right column
['00','10','20'], // top row
['01','11','21'], // middle row
['02','12','22'], // bottom row
['00','11','22'], // Diag TL to BR
['20','11','02'] // Diag BL to TR
];
//Our scoring arrays for evaulating moves
var max1 = ['100','010','001'];
var min1 = ['200','020','002'];
var max2 = ['110','011'];
var min2 = ['220','022'];
var max3 = ['111'];
var min3 = ['222'];
//All the valid squares
var validSquaresFactory = ['00','10','20','01','11','21','02','12','22'];
//Store all the moves somewhere
//var computerMoves = ['10','22'];
//var userMoves = ['00','02'];
//Store all the moves somewhere
var computerMoves = ['11','22'];
var userMoves = ['00','01'];
function Board(minOrMax,computerMoves,userMoves){
this.computer = computerMoves;
this.user = userMoves;
this.minOrMax = minOrMax;
this.remaining = this.genRemaining();
this.complete = this.genComplete();
var results = this.getScore();
this.score = results[0];
this.winOrLoose = results[1];
}
Board.prototype.genRemaining = function(){
//Create an array of all moves taken
var takenMoves = this.computer.concat(this.user);
//Calculate all remaining squares
var validSquares = validSquaresFactory.filter(function(object){
return takenMoves.indexOf(object) === -1;
});
return validSquares;
}
Board.prototype.genComplete = function(){
return ((this.computer.length + this.user.length) === 9);
}
Board.prototype.flipMinOrMax = function(){
return (this.minOrMax === 'max') ? 'min' : 'max'
}
Board.prototype.genArrays = function(minOrMax,square){
var tempUser = this.user.slice(0);
var tempComputer = this.computer.slice(0);
if(minOrMax === 'min'){
tempUser.push(square);
} else {
tempComputer.push(square);
}
return [tempComputer,tempUser];
}
Board.prototype.generateBoards = function(minOrMax){
var boards = [];
var that = this;
this.remaining.forEach(function(remainingSquare){
var moves = that.genArrays(minOrMax,remainingSquare);
boards.push(new Board(minOrMax,moves[0],moves[1]));
})
//console.log(boards);
return boards;
}
Board.prototype.getScore = function(){
var that = this;
var winOrLoose = false;
var returnScore = validRows.reduce(function(storage,row,index,array){
var score = row.reduce(function(storage1,square){
if (that.computer.indexOf(square) !== -1) {
storage1 += '1';
} else if (that.user.indexOf(square) !== -1) {
storage1 += '2';
} else {
storage1 += '0';
}
return storage1;
},'')
var finalScore = 0;
if(max1.indexOf(score) != -1){
finalScore = 1;
} else if(min1.indexOf(score) != -1){
finalScore = -1;
} else if(max2.indexOf(score) != -1){
finalScore = 10;
} else if(min2.indexOf(score) != -1){
finalScore = -10;
} else if(max3.indexOf(score) != -1){
winOrLoose = true;
finalScore = 100;
} else if(min3.indexOf(score) != -1){
winOrLoose = false;
finalScore = -100;
}
storage.push(finalScore);
return storage;
},[])
var condensedReturnScore = returnScore.reduce(function(storage,score){
return storage+score;
})
return [condensedReturnScore,winOrLoose];
}
function generateMove(){
var board = new Board('max',computerMoves,userMoves);
var scores = [];
var boards = board.generateBoards('max');
boards.forEach(function(board){
scores.push(testMove(board,4));
});
scores = scores.map(function(score,index){
return [board.remaining[index],score];
});
var returnValue = scores.reduce(function(storage,score){
return (score[1].score > storage[1].score) ? score : storage;
});
return [returnValue[0],returnValue[1].score];
}
function testMove(masterBoard,count){
count --;
var boards = [];
boards = masterBoard.generateBoards(generateMinOrMax(masterBoard.minOrMax));
//console.log('/////////Master Board/////////');
//console.log(masterBoard);
//console.log(boards);
//console.log('//////////////////////////////');
boards = boards.map(function (move) {
if (move.complete === true || count === 0 || move.winOrLoose === true){
return move;
} else {
var returnScore = testMove(move,count);
return returnScore;
}
});
returnBoard = boards.reduce(function(storage,board,index,array){
if(board.minOrMax === 'max'){
return (board.score > storage.score) ? board : storage;
} else {
return (board.score < storage.score) ? board : storage;
}
});
return returnBoard;
}
function generateMinOrMax(minOrMax){
return (minOrMax === 'max') ? 'min' : 'max'
}
I've checked the scoring function and from what i can see it is returning the expected score for any move i try, but because of the shear number of possibilities calculated it's very hard to debug efficiently.
Any help/pointers on this would be most appreciated as i have really hit a brick wall with this, can't see the forrest for the trees e.t.c
If you would like to test this with the GUI, it's on codepen at - http://codepen.io/gazzer82/pen/yYZmvJ?editors=001
So after banging my head against this for day, as soon as i posted this i found the issues. Firstly using the wrong variable for minormax in my reduce function, so it wasn't flipping correctly and not setting the winOrLoose value correctly for a score of -100. Here is the corrected version.
*
Attempt to inplement a Tic Tac Toe minimax game
5th attempt, so hopefully this time it works!
*/
var util = require("util");
//These are all the winning square sequences, as string to make various things easier
var validRows = [
['00','01','02'], // left column
['10','11','12'], // middle column
['20','21','22'], // right column
['00','10','20'], // top row
['01','11','21'], // middle row
['02','12','22'], // bottom row
['00','11','22'], // Diag TL to BR
['20','11','02'] // Diag BL to TR
];
//Our scoring arrays for evaulating moves
var max1 = ['100','010','001'];
var min1 = ['200','020','002'];
var max2 = ['110','011'];
var min2 = ['220','022'];
var max3 = ['111'];
var min3 = ['222'];
//All the valid squares
var validSquaresFactory = ['00','10','20','01','11','21','02','12','22'];
//Store all the moves somewhere
//var computerMoves = ['10','22'];
//var userMoves = ['00','02'];
//Store all the moves somewhere
var computerMoves = ['00','20','01'];
var userMoves = ['10','11','02'];
//01,21,22 - 01//
function Board(minOrMax,computerMoves,userMoves){
this.computer = computerMoves;
this.user = userMoves;
this.minOrMax = minOrMax;
this.remaining = this.genRemaining();
this.complete = this.genComplete();
var results = this.getScore();
this.score = results[0];
this.winOrLoose = results[1];
}
Board.prototype.genRemaining = function(){
//Create an array of all moves taken
var takenMoves = this.computer.concat(this.user);
//Calculate all remaining squares
var validSquares = validSquaresFactory.filter(function(object){
return takenMoves.indexOf(object) === -1;
});
return validSquares;
}
Board.prototype.genComplete = function(){
return ((this.computer.length + this.user.length) === 9);
}
Board.prototype.flipMinOrMax = function(){
return (this.minOrMax === 'max') ? 'min' : 'max'
}
Board.prototype.genArrays = function(minOrMax,square){
var tempUser = this.user.slice(0);
var tempComputer = this.computer.slice(0);
if(minOrMax === 'min'){
tempUser.push(square);
} else {
tempComputer.push(square);
}
return [tempComputer,tempUser];
}
Board.prototype.generateBoards = function(minOrMax){
var boards = [];
var that = this;
this.remaining.forEach(function(remainingSquare){
var moves = that.genArrays(minOrMax,remainingSquare);
boards.push(new Board(minOrMax,moves[0],moves[1]));
})
//console.log(boards);
return boards;
}
Board.prototype.getScore = function(){
var that = this;
var winOrLoose = false;
var returnScore = validRows.reduce(function(storage,row,index,array){
var score = row.reduce(function(storage1,square){
if (that.computer.indexOf(square) !== -1) {
storage1 += '1';
} else if (that.user.indexOf(square) !== -1) {
storage1 += '2';
} else {
storage1 += '0';
}
return storage1;
},'')
var finalScore = 0;
if(max1.indexOf(score) != -1){
finalScore = 1;
} else if(min1.indexOf(score) != -1){
finalScore = -1;
} else if(max2.indexOf(score) != -1){
finalScore = 10;
} else if(min2.indexOf(score) != -1){
finalScore = -10;
} else if(max3.indexOf(score) != -1){
winOrLoose = true;
finalScore = 100;
} else if(min3.indexOf(score) != -1){
winOrLoose = true;
finalScore = -100;
}
storage.push(finalScore);
return storage;
},[])
var condensedReturnScore = returnScore.reduce(function(storage,score){
return storage+score;
})
return [condensedReturnScore,winOrLoose];
}
function generateMove() {
var board = new Board('max', computerMoves, userMoves);
if (board.remaining.length === 1) {
return [board.remaining[0], 0];
} else {
var scores = [];
var boards = board.generateBoards('max');
boards.forEach(function (board) {
scores.push(testMove(board, 4));
});
scores = scores.map(function (score, index) {
return [board.remaining[index], score];
});
var returnValue = scores.reduce(function (storage, score) {
return (score[1].score > storage[1].score) ? score : storage;
});
return [returnValue[0], returnValue[1].score];
}
}
function testMove(masterBoard,count){
count --;
var boards = [];
boards = masterBoard.generateBoards(generateMinOrMax(masterBoard.minOrMax));
boards = boards.map(function (move) {
if (move.complete === true || count <= 0 || move.winOrLoose === true){
return move;
} else {
var returnScore = testMove(move,count);
return returnScore;
}
});
returnBoard = boards.reduce(function(storage,board,index,array){
if(generateMinOrMax(masterBoard.minOrMax) === 'max'){
return (board.score > storage.score) ? board : storage;
} else {
return (board.score < storage.score) ? board : storage;
}
});
return returnBoard;
}
function generateMinOrMax(minOrMax){
return (minOrMax === 'max') ? 'min' : 'max'
}
function getScore(user,computer,minOrMax){
var that = this;
that.computer = computer;
that.user = user;
that.minOrMax = minOrMax;
var returnScore = validRows.reduce(function(storage,row,index,array){
var score = row.reduce(function(storage1,square){
if (that.computer.indexOf(square) !== -1) {
storage1 += '1';
} else if (that.user.indexOf(square) !== -1) {
storage1 += '2';
} else {
storage1 += '0';
}
return storage1;
},'')
var finalScore = 0;
if(max1.indexOf(score) != -1){
finalScore = 1;
} else if(min1.indexOf(score) != -1){
finalScore = -1;
} else if(max2.indexOf(score) != -1){
finalScore = 10;
} else if(min2.indexOf(score) != -1){
finalScore = -10;
} else if(max3.indexOf(score) != -1){
finalScore = 100;
} else if(min3.indexOf(score) != -1){
finalScore = -100;
}
storage.push(finalScore);
return storage;
},[])
var condensedReturnScore = returnScore.reduce(function(storage,score){
if(that.minOrMax === 'max'){
return (score >= storage) ? score : storage;
} else {
return (score <= storage) ? score : storage;
}
})
return condensedReturnScore;
}