Beat my noughts and crosses game
Check out my noughts and crosses game here.
Around the year 2000 I was coding in Pearl and began to get interested in artificial intelligence. Since I did not have that much experience with neural nets I decided to build a game AI for the simplest game I could think of, Noughts and Crosses or Luffarschack as we call it in Sweden. I started out creating the game with check boxes and a page reload for each selected box. Then I created a logic function that calculated a score for each available position on the board. Then the game engine selected the position with the highest score. So it was not much of an AI but it proved to be a game quite hard to beat none the less. So I did not bother to spend more time on it, and figured that AI might be more useful in other areas. Maybe I'll give it a try and see if I can create a neural net that can learn to beat my pure logic version. Let's hope for that in a future blog post.
No I have recreated the game in javascript close to what it was back in the days.
After reading Levelling up your JavaScript I thought that I would put his way of writing object to the test, and I must say I think the code looks kind of neat.
If you want to tweak the code and see if you can make it even harder to beat, try tweaking the variables strategy and distanceBonus. Also take a look at the entire function _scoreArrayPlayer that is responsible for generating a score for one direction check for one position. arr is a 9 element array where element 4 is the position you are looking at for example ["", "", "x", "", "", "o", "o", "x", ""]. This particular row should not give a score since it is not possible to fit 5 o:s in a row in there. Element 4 is always "".
// HTML
// CSS
#board {
font-family: verdana;
}
#board table {
border-collapse: collapse;
}
#board table td {
border: 1px solid #999;
height: 20px;
width: 20px;
text-align: center;
line-height: 20px;
}
td {
background: #ccc;
}
td.allowed {
background: #fff;
}
td.allowed:hover {
background: #cfc;
}
td.winner {
font-weight: bold;
}
// JavaScript
"use strict";
// Manage classes in html elements
function hasClass(ele,cls) {
return !!ele.className.match(new RegExp('(s|^)'+cls+'(s|$)'));
}
function addClass(ele,cls) {
if (!hasClass(ele,cls)) { ele.className += " " + cls; }
}
function removeClass(ele,cls) {
if (hasClass(ele,cls)) {
var reg = new RegExp('(s|^)'+cls+'(s|$)');
ele.className=ele.className.replace(reg,' ');
}
}
// addListner make sure that the listner work in all browsers
var addListener = function(element, eventType, handler, capture) {
if (capture === undefined) { capture = false; }
if (element.addEventListener) {
element.addEventListener(eventType, handler, capture);
} else if (element.attachEvent) {
element.attachEvent("on" + eventType, handler);
}
};
// removeListener in order to clean up, so we do not end up with multiple listeners
var removeListener = function(element, eventType, handler, capture) {
if (capture === undefined) { capture = false; }
if (element.removeEventListener) {
element.removeEventListener(eventType, handler, capture);
} else if (element.detachEvent) {
element.detachEvent("on" + eventType, handler);
}
};
// Here is the code for the game
var xoGame = (function() {
var boardData = [];
var element = null;
var turn = 'x';
var winner = false;
if (!boardData[0]) { boardData[0] = []; }
boardData[0][0] = '';
var sizeX = 1;
var sizeY = 1;
return {
init: function(elem) {
element = elem;
this.setX(0, 0);
},
_isAllowed: function(x, y) {
var allowed = false;
if (boardData[x][y] === '') {
if (typeof boardData[x-1] !== 'undefined') {
if (boardData[x-1][y] !== '') {
allowed = true;
}
}
if (typeof boardData[x][y-1] !== 'undefined') {
if (boardData[x][y-1] !== '') {
allowed = true;
}
}
if (typeof boardData[x-1] !== 'undefined') {
if (typeof boardData[x-1][y-1] !== 'undefined') {
if (boardData[x-1][y-1] !== '') {
allowed = true;
}
}
}
if (typeof boardData[x+1] !== 'undefined') {
if (boardData[x+1][y] !== '') {
allowed = true;
}
}
if (typeof boardData[x][y+1] !== 'undefined') {
if (boardData[x][y+1] !== '') {
allowed = true;
}
}
if (typeof boardData[x+1] !== 'undefined') {
if (typeof boardData[x+1][y+1] !== 'undefined') {
if (boardData[x+1][y+1] !== '') {
allowed = true;
}
}
}
if (typeof boardData[x+1] !== 'undefined') {
if (typeof boardData[x+1][y-1] !== 'undefined') {
if (boardData[x+1][y-1] !== '') {
allowed = true;
}
}
}
if (typeof boardData[x-1] !== 'undefined') {
if (typeof boardData[x-1][y+1] !== 'undefined') {
if (boardData[x-1][y+1] !== '') {
allowed = true;
}
}
}
if (allowed) {
return 'allowed';
}
}
return '';
},
renderBoard: function() {
var board = '';
var x = 0;
var y = 0;
var allowed = '';
while (x < sizeX) {
board += '';
y = 0;
while (y < sizeY) {
allowed = this._isAllowed(x, y);
//console.log(allowed);
board += '' + boardData[x][y] + ' ';
y++;
}
board += ' ';
x++;
}
board += '
';
element.innerHTML = board;
},
setX: function(x, y) {
boardData[x][y] = 'x';
turn = 'o';
},
setO: function(x, y) {
boardData[x][y] = 'o';
turn = 'x';
},
_expandBoard: function(expandStartX, expandEndX, expandStartY, expandEndY) {
var x = 0;
var y = 0;
var shiftX = 0, shiftY = 0;
var newBoard = [];
if (!newBoard[0]) { newBoard[0] = []; }
if (expandStartX) {
while (y < sizeY) {
newBoard[0][y] = '';
y++;
}
sizeX++;
shiftX = 1;
}
if (expandStartY) {
while (x < sizeX) {
// In order to manage the multidimentional array in JavaScript we need to declair the new item as an array as well
if (!newBoard[x]) { newBoard[x] = []; }
y = 0;
while (y < sizeY+1) {
newBoard[x][y] = '';
y++;
}
x++;
}
sizeY++;
shiftY = 1;
}
// Fill previous array in the new
x = 0;
while (x < sizeX-shiftX) {
y = 0;
while (y < sizeY-shiftY) {
if (!newBoard[x + shiftX]) { newBoard[x + shiftX] = []; }
newBoard[x + shiftX][y + shiftY] = boardData[x][y];
y++;
}
x++;
}
if (expandEndX) {
sizeX++;
// In order to manage the multidimentional array in JavaScript we need to declair the new item as an array as well
if (!newBoard[sizeX-1]) { newBoard[sizeX-1] = []; }
y = 0;
while (y < sizeY) {
newBoard[sizeX-1][y] = '';
y++;
}
}
if (expandEndY) {
sizeY++;
x = 0;
while (x < sizeX) {
// In order to manage the multidimentional array in JavaScript we need to declair the new item as an array as well
if (!newBoard[x]) { newBoard[x] = []; }
newBoard[x][sizeY-1] = '';
x++;
}
}
boardData = newBoard;
},
fillBoard: function() {
var x = 0;
var y = 0;
var expandStartX, expandEndX, expandStartY, expandEndY = false;
while (x < sizeX) {
if (boardData[x][0] !== '') {
expandStartY = true;
}
if (boardData[x][sizeY-1] !== '') {
expandEndY = true;
}
x++;
}
while (y < sizeY) {
if (boardData[0][y] !== '') {
expandStartX = true;
}
if (boardData[sizeX-1][y] !== '') {
expandEndX = true;
}
y++;
}
this._expandBoard(expandStartX, expandEndX, expandStartY, expandEndY);
},
_fiveInARow: function(x, y) {
var current = boardData[x][y];
if (current !== 'x' && current !== 'o') {
return 0;
}
// left - right
var i = -4;
var found = 0;
var maxFound = 0;
while (i < 5) {
if (typeof boardData[x + i] !== 'undefined') {
if (boardData[x + i][y] === current) {
found++;
} else if (found < 5) {
found = 0;
}
}
i++;
}
//console.log(found);
maxFound = found;
// left up - right down
i = -4;
found = 0;
while (i < 5) {
if (typeof boardData[x + i] !== 'undefined') {
if (boardData[x + i][y + i] === current) {
found++;
} else if (found < 5) {
found = 0;
}
}
i++;
}
if (found > maxFound) { maxFound= found; }
// up - down
i = -4;
found = 0;
while (i < 5) {
if (boardData[x][y + i] === current) {
found++;
} else if (found < 5) {
found = 0;
}
i++;
}
if (found > maxFound) { maxFound= found; }
// left down - right up
i = -4;
found = 0;
while (i < 5) {
if (typeof boardData[x - i] !== 'undefined') {
if (boardData[x - i][y + i] === current) {
found++;
} else if (found < 5) {
found = 0;
}
}
i++;
}
if (found > maxFound) { maxFound= found; }
return maxFound;
},
_checkWinner: function() {
var x = 0;
var y = 0;
var winElem = false;
while (x < sizeX) {
y = 0;
while (y < sizeY) {
if (this._fiveInARow(x, y) === 5) {
winner = boardData[x][y];
winElem = document.getElementById(x + '_' + y);
addClass(winElem, 'winner');
}
y++;
}
x++;
}
if (winner) {
//alert(winner + ' is the winner!');
}
},
_scoreArrayPlayer: function(arr, player, opponent) {
var score = 0;
var count = 0;
var open = 0;
var blocked = false;
var distanceBonus = 0;
var i = 0;
while (i < 9 && !blocked) {
distanceBonus = ((4 - Math.abs(i - 4))/ 5);
if (arr[i] === player) {
score = score + 1 + distanceBonus;
open++;
count++;
}
if (arr[i] === '' || arr[i] === undefined) {
score = score + 0.5 - distanceBonus;
open++;
}
if (arr[i] === opponent) {
if (i < 4) {
score = 0;
open = 0;
count = 0;
} else {
blocked = true;
}
}
i++;
}
if (count > 2) { score = score * 2; }
if (count > 3) { score = score * 3; }
if (open < 5) { score = 0; }
return score;
},
_scoreArray: function(arr, strategy) {
//console.log(arr);
// arr: _ o x x _ x x o o
var score = 0;
var totalScore = 0;
var player = turn;
var opponent = 'x';
if (turn === 'x') {
opponent = 'o';
}
score = this._scoreArrayPlayer(arr, player, opponent);
//console.log('+ ' + score);
totalScore = score * strategy;
// Check if we need to block the opponent at some place
score = this._scoreArrayPlayer(arr, opponent, player);
totalScore += score / strategy;
//console.log('- ' + score);
//console.log('-----');
//console.log(totalScore);
return totalScore;
},
_positionScore: function(x, y) {
var strategy = 0.9; // 1.5 is 50% more offencive. 0.5 is 50% more defencive
/*
Using the following rules to calculate a score for each direction
The score for each direction is the summarized
*/
// left - right
var i = -4;
var score = 0;
var maxScore = 0;
var testArr = [];
while (i < 5) {
if (typeof boardData[x + i] !== 'undefined') {
testArr[i + 4] = boardData[x + i][y];
} else {
testArr[i + 4] = '';
}
i++;
}
score += this._scoreArray(testArr, strategy);
maxScore = score;
//console.log(score);
// left up - right down
i = -4;
while (i < 5) {
if (typeof boardData[x + i] !== 'undefined') {
testArr[i + 4] = boardData[x + i][y + i];
} else {
testArr[i + 4] = '';
}
i++;
}
score += this._scoreArray(testArr, strategy);
if (score > maxScore) { maxScore = score; }
//console.log(score);
// up - down
i = -4;
while (i < 5) {
testArr[i + 4] = boardData[x][y + i];
i++;
}
score += this._scoreArray(testArr, strategy);
if (score > maxScore) { maxScore = score; }
//console.log(score);
// left down - right up
i = -4;
while (i < 5) {
if (typeof boardData[x - i] !== 'undefined') {
testArr[i + 4] = boardData[x - i][y + i];
} else {
testArr[i + 4] = '';
}
i++;
}
score += this._scoreArray(testArr, strategy);
if (score > maxScore) { maxScore = score; }
//console.log(score);
return score + maxScore;
},
_calculatePositions: function() {
var allowed = document.getElementsByClassName('allowed');
var bestPos = [];
var bestScore = 0;
var i = 0;
while (i < allowed.length) {
var x = parseInt(allowed[i].attributes['data-x'].value, 10);
var y = parseInt(allowed[i].attributes['data-y'].value, 10);
var score = this._positionScore(x, y);
if (bestScore < score) {
bestScore = score;
bestPos = [x, y];
}
//console.log(x + ' ' + y + ' => ' + turn + ' = ' + score);
//var scoreElem = document.getElementById(x + '_' + y);
//scoreElem.innerHTML = score.toPrecision(3);
i++;
}
return bestPos;
},
mainPlay: function() {
this.fillBoard(); // Expand the playable board grid if needed
this.renderBoard(); // Render the new board
this._checkWinner(); // Check if there is a winner
var bestPos = this._calculatePositions();
// If no winner then allow the next player to select a location
if (!winner) {
if (turn === 'o') {
var allowed = document.getElementsByClassName('allowed');
var i = 0;
while (i < allowed.length) {
//console.log(allowed[i]);
addListener(allowed[i], 'click', function(e) {
e.srcElement.innerHTML = turn;
var x = parseInt(e.srcElement.attributes['data-x'].value, 10);
var y = parseInt(e.srcElement.attributes['data-y'].value, 10);
if (turn === 'x') {
xoGame.setX(x, y);
} else {
xoGame.setO(x, y);
}
//console.table(boardData);
xoGame.mainPlay();
});
i++;
}
} else {
xoGame.setX(bestPos[0], bestPos[1]);
xoGame.mainPlay();
}
}
//console.table(allowed);
}
};
}());
var elem = document.getElementById('board');
xoGame.init(elem);
xoGame.mainPlay();
- javascript, game, software
Comment
0 comment