Game descrition - advanced tic-tac-toe for mobile and stationary devices
The game was written in pure javascript and HTML5, CSS3. It includes only one library: modernizr, which is used to check if the web browser has been embedded in Canvas and "Web Workers". In case of lack of this technology the web browser sends appropriate message to users and running the game is impossible. This library is available at: http://modernizr.com.
There is initiation game, check of the width of device, definition of configuration variable such as: translations, max-depth of algorithm and set colors in the loader.js file in json structure. You can also set the number of columns and rows. Below I change my settings to the classic noughts and crosses, i.e. 3x3 board:
action :{ rows : 3, // it was 9 cols : 3, // it was 9 len : 3, // it was 5 max_level : 3, max_depth : 2, inf : 1000000, human : 1, blank : 0, comp : -1, who_first : 1 }
File display.canvas.js is responsible only for display of the game (with Canvas technology) and receives data from "Web Workers".
Thanks to the use "Web Workers" computer moves are calculated in the background, so the game runs faster. "Web Workers" is responsible for computer move, which is calculated by "Alpha-beta pruning" algorithm. More information about this algorithm you can find at: http://en.wikipedia.org/wiki/Alpha-beta_pruning. There is implementation "Alpha-beta pruning" in game.logic.worker.js file and the core of this algorithm constitutes alphaBetaPruning function, which is shown below:
function alphaBetaPruning( node, depth, alpha, beta, player ){
var eval = evaluate( node, player );
if( (eval['win'] != 0 ) || ( eval['score'] == 0 ) || (depth >= max_depth ) ){
return { 'alphabeta': eval['score'], 'tree' : null };
}
var children = possibleMoves( node, player );
depth++;
if( player == human ){
var tree = [];
for( var i=0; i<children.length; i++ ){
tree[i] = {};
tree[i].matrix = children[i];
var tree_children = alphaBetaPruning( children[i], depth, alpha, beta, -player );
var alpha = ( tree_children['alphabeta'] > alpha ) ? tree_children['alphabeta'] : alpha;
tree[i].alphabeta = alpha;
if( beta <= alpha ){
break;
}
}
return { 'alphabeta': alpha, 'tree': tree };
}else{
var tree = [];
for( var i=0; i<children.length; i++ ){
tree[i] = {};
tree[i].matrix = children[i];
var tree_children = alphaBetaPruning( children[i], depth, alpha, beta, -player );
var beta = ( tree_children['alphabeta'] < beta ) ? tree_children['alphabeta'] : beta;
tree[i].alphabeta = beta;
if( beta <= alpha ){
break;
}
}
return { 'alphabeta': beta, 'tree': tree };
}
}
This function is mirror pseudo code from wiki. There are two important functions: evaluate and possibleMoves in this algorithm. Function possibleMoves returns all possible moves and 'evaluate' evaluates the board, based on number of items in the same: row, column or diagonally. Below I show the code of this function:
function evaluate( matrix, player ){
var eval_entity =getEvalEntity( matrix ); //all avaliable combinations winner movement.
var score = 0;
var win = 0;
var win_xy = {};
for( i=0; i<eval_entity.length; i++ ){
var item = eval_entity[i];
var is_min = inArray( -1, item );
var is_max = inArray( 1, item );
if( is_min && is_max ){
score += 0;
}else{
if( !is_min && !is_max ){
score += 1*player;
}else{
var sum = 0;
for( j=0; j<item.length; j++ ){
sum += parseInt( item[j].v );
}
var sign = ( sum > 0 ) ? 1 : -1
var sum_abs = Math.abs(sum);
if( len == sum_abs ){
win = sign;
win_xy = item;
}
score += sign * Math.pow( 10, (sum_abs + 1) ) ;
}
}
}
return { score: score, win: win, win_xy : win_xy };
}