I wrote mine a while ago in PHP. I decided to write a complete class and engine as I actually made a presentable game out of it, which is above the scope.
I used a minimax function (although technically I think I implemented a variation on a negamax function, since minimax seemed to be a bit redundant). Can be further optimised via using an a/b pruning technique, or a similar alternative. I think in the example they provide, there are 12 moves to the end, whereas I was only able to go 11 nodes deep. If you wanted to go 12 and beyond you'd have to improve on this function.
I also used a terribly greedy evaluation function :p It just uses the amount of pieces on the board - it doesn't consider the position of the game (i.e. it's more advantageous to have a piece on the edge/corner than middle of the board).
reversi.engine.class.php - the brains of the operation
PHP Code:
<?php
/** * Reversi Artificial Intelligence class * * @author Alex Roxon * @file reversi.engine.class.php */ class ReversiAI extends Reversi {
/** * Public data values - poor design, sure, but I know what I'm doing, so let's * just grant permission to these values. */ public $gameBoard = array(); public $possibleMoves = array();
// Who the active player is private $activePlayer = 'w';
// The path to the correct solution private $treePath = array();
// How many nodes deep we should search private $nodes = 5;
// Debug purposes private $outString = '';
// Possible moves private $moves = array();
/** * Evaluate the score * * Fairly weak evaluation function. Proper AI engine should have a function * significantly smarter. As we're approaching the endgame though, I think this * should be fine. * * @param $gameBoard * The gameboard to evaluate a position * @param $player * The player we're looking for * * @return * The score of the game relative to the $player */ public function evaluateScore( $gameBoard, $player ) { // Fetch amount of coloured discs $scores = $this->calculateScore( $gameBoard );
// Use the difference as our score (score will change depending on who is fetching the max & min score) $score = ( $player == 'w' ) ? $scores['w'] - $scores['b'] : $scores['b'] - $scores['w'];
return $score; }
/** * Let's run the AI algorithm * * @param $gameboard * The gameboard to run on */ public function runAi( $gameboard ) { $this->possibleMoves = array(); $this->gameBoard = $gameboard;
// Run the minmax algorithm $this->minmax( $gameboard, $this->possibleMoves, 1, $this->getNodes(), $this->getActivePlayer() ); }
/** * Set the node * * @param $node * The amount of nodes deep to search */ public function setNodes( $node = 5 ) { if ( ! is_int( $node ) ) { throw new Exception( "Please enter a valid amount of nodes." ); } if ( $node < 1 || $node > 14 ) { throw new Exception( "Node must be within the range 0 < node < 15" ); }
$this->nodes = $node; }
/** * Get the amount of nodes */ public function getNodes() { return $this->nodes; }
/** * Returns the possible moves */ public function getPossibleMovesProperty() { $scoreObj = new stdClass; $scoreObj->value = $this->possibleMoves; return $scoreObj; }
/** * Loops throughs the scores to find the best path * * @param $scores * An array of scores * @param $score * An individual score */ public function loopScores( $scores, $score ) { foreach( $scores as $ide => $val ) { if( is_array( $val ) && isset( $val['score'] ) && $val['score'] == $score ) { // call recursive function $this->treePath[] = $ide; $this->loopScores( $val, $score, $path ); break; } } }
/** * Makes the moves */ public function makeMoves( $debug = false ) { $player = $this->getActivePlayer(); $gameboard = $this->gameBoard; $this->outString = ''; $this->moves = array();
// Let's go through each branch foreach( $this->treePath as $id ) { $moves = $this->getPossibleMoves( $gameboard, $player );
// Go through each set of possible moves on said branch foreach( $moves as $ide => $move ) { if( $ide == $id ) { list( $x, $y, $whereToMove ) = $move;
// Make the move $gameboard = $this->commitMove( $whereToMove, $player, $gameboard );
// Append to the moves array $this->moves[] = $gameboard;
// Swap the player $player = ( $player == 'w' ) ? 'b' : 'w'; } } } }
/** * Set the active player */ public function setActivePlayer( $player ) { if( ! is_string( $player ) || ! in_array( $player, array( 'w', 'b' ) ) ) { throw new Exception( 'Active player must be either \'w\' or \'b\'' ); } $this->activePlayer = $player; }
/** * Get the active player */ public function getActivePlayer() { return $this->activePlayer; }
/** * Get the output */ public function getOutput() { return $this->outString; }
/** * Get moves */ public function getMoves() { $obj = new stdClass; foreach( $this->moves as $id => $move ) { $obj->move[ $id ] = $move; } return $obj; }
/** * Minimax function (really a variation of a negamax function) * * @param $gameboard * The gameboard to perform the calculations on * @param $searchArr * Array of scores to search through * @param $node * The current node we're in * @param $depth * The amount of nodes deep to search * @param $player * The player to evaluate the score for. * * @return * the score we should take */ private function minmax( $gameboard, &$searchArr, $node = 1, $depth = 3, $player = 'w' ) { // >: We've reached our maximum depth. Let's just treat these child nodes as leaves and end it here. if( $node > $depth ) { $searchArr['score'] = $this->evaluateScore( $gameboard, $this->getActivePlayer() ); // Always evaluate the score for the active player return $searchArr['score']; }
// Get the next mover $nextMover = ( $player == 'w' ) ? 'b' : 'w';
// Otherwise, let's look for all possible moves on the gameboard $moves = $this->getPossibleMoves( $gameboard, $player );
// We've got a leaf, signalling an end to the game, meaning a definite winner. if( sizeOf( $moves ) == 0 ) { // Check to see if the opponent can move - if they can, we have to hand over to them (and forego our own turn - only just realised this) $opponentsMoves = $this->getPossibleMoves( $gameboard, $nextMover );
// If the opponent can move, let's just give them a go (WIP) if( sizeOf( $opponentsMoves ) > 0 && 1 == 2 ) { $searchArr[] = array(); //$activeScore = 123; $activescore = $this->minmax( $gameboard, $searchArr[ sizeOf( $searchArr ) - 1 ], $node + 1, $depth, $nextMover ); }
// Otherwise, the opponent can't move, meaning the game has well and truly ended else if( sizeOf( $opponentsMoves ) == 0 ||*1 == 1 ) { // We can't actually use an infinite value, so let's just use +-999 $score = $this->evaluateScore( $gameboard, $this->getActivePlayer() ); if( $score == 0 ) $activeScore = 0; // It's a draw. else if( $player == $this->getActivePlayer() ) $activeScore = ( $score > 0 ) ? 999 : -999; else $activeScore = ( $score < 0 ) ? 999 : -999; } }
reversi.class.php - the interface between the AI class and end user
PHP Code:
<?php
class Reversi {
// Private variables. Use the setter/getter functions to access. private $board = array(); private $rows = 8; private $nextTurn = 'black'; private $reversiAi;
// Constants const NL = PHP_EOL;
public function __construct() { $this->reversiAi = new ReversiAI; }
// Start the game public function newGame() { // Let's initialise the game board. $this->initialiseBoard(); }
// Let's test out a move - is it valid, how many will we reverse? public function testMove( $x, $y, $move, $board = null ) { // What gameboard are we using? Current gameboard is default, or user supplied gameboard (for AI analysis) $gameBoard = ( $board == null ) ? $this->getGameBoard() : $board;
// Out of bounds? if( $x > ( $this->getRows( $gameBoard ) - 1 ) || $x < 0 || $y > ( $this->getRows( $gameBoard ) - 1 ) || $y < 0 ) { throw new Exception( 'x/y coordinates out of bounds.' ); }
// Current position already taken? if( $this->getPiece( $x, $y, $gameBoard ) != '.' ) { throw new Exception( 'x/y coordinate is not available to move on.' ); }
// Let's test each of the ranges $availableMoves = array(); foreach( $ranges as $range ) { $availableMoves = array_merge( $availableMoves, $this->reverseXYBlocks( $range[0], $range[1], $move, $gameBoard ) ); }
// Loop through diagonal coordinates and test each for squares to reverse foreach( $this->diagonalCoordinates( array( $x, $y ) ) as $diag ) { $availableMoves = array_merge( $availableMoves, $this->testDiag( $diag, $move, $gameBoard ) ); }
return $availableMoves; }
// Commit move - should be called after testMove. public function commitMove( $testResults, $colour, $board = null ) { // Data checks if( ! is_array( $testResults ) ) { throw new Exception( 'Invalid format for commitMove. $testResults must be an array.' ); }
// Let's loop through the gameboard and increment the scores. foreach( range( 0, sizeOf( $gameBoard ) - 1 ) as $x ) { foreach( range( 0, sizeOf( $gameBoard[0] ) - 1 ) as $y ) { $block = $gameBoard[ $x ][ $y ]; if( isset( $scores[ $block ] ) ) $scores[ $block ] += 1; } }
return $scores; }
// Reversi AI class public function aiClass() { return $this->reversiAi; }
// Set a piece public function setPiece( $piece ) { // Data checks if( ! is_array( $piece ) || sizeOf( $piece ) == 0 ) { throw new Exception( 'You have attempted to assign an invalid piece.' ); }
// Are we dealing with an array of pieces, or a single piece? if( is_array( $piece[0] ) ) { foreach( $piece as $addPiece ) { $this->_setPiece( $addPiece ); } }
// Otherwise we only want to add a single piece else $this->_setPiece( $piece ); }
// Retrieve a piece public function getPiece( $x, $y, $board = null ) { // Numeric x, y within propery range? if( ! is_numeric( $x ) || ! is_numeric( $y ) || $x >= $this->rows || $y >= $this->rows ) { throw new Exception( 'x, y paramaters must be numeric and within the range 0 <= x/y <= ' . ( $this->rows - 1 ) ); }
// Set the active gameboard public function setGameBoard( $board ) { // Some data integrity checks if( ! is_array( $board ) || sizeOf( $board ) !== $this->getRows() ) { throw new Exception( 'Invalid gameboard.' ); } foreach( $board as $subBoard ) { if( ! is_array( $subBoard ) || sizeOf( $subBoard ) !== $this->getRows() ) { throw new Exception( 'Invalid gameboard #2' ); } }
// Otherwise it appears to be okay, so let's overwrite the existing gameboard. $this->board = $board; }
// Fetch the active gameboard public function getGameBoard() { return $this->board; }
// Set the next turn. public function setNextTurn( $next ) { // Valid data? if( ! is_string( $next ) || ! in_array( $next, array( 'b', 'w' ) ) ) { throw new Exception( 'Invalid config setting for next move. Must be either \'b\' or \'w\'' ); } $this->nextTurn = $next; }
// Get the user to make the next turn. public function getNextTurn() { return $this->nextTurn; }
// Set the amount of rows to use public function setRows( $rows ) { // Valid data? if( ! is_numeric( $rows ) ) { throw new Exception( 'The amount of rows must be a valid integer.' ); }
// Let's just impose some limits. if( $rows < 4 || $rows > 12 ) { throw new Exception( 'That\'s a bit ambitious! Let\'s keep the game simple, shall we?' ); }
$this->rows = $rows; }
// Get the amount of rows we're using public function getRows( $gameBoard = null ) { return ( $gameBoard == null ) ? $this->rows : sizeOf( $gameBoard ); }
// Initialise the game board private function initialiseBoard() { // Create an empty game board. foreach( range( 0, $this->rows - 1 ) as $x ) { foreach( range( 0, $this->rows - 1 ) as $y ) { $this->board[ $x ][ $y ] = '.'; } }
// Set a piece private function _setPiece( $piece ) { // Do we have an array and is it the correct amount of arguments? if( ! is_array( $piece ) || sizeOf( $piece ) <> 3 ) { throw new Exception( '$piece argument must be in the form of array( x, y, [ w, b ] )' ); }
// Let's fetch the values now we know the arguments have been correctly passed through. list( $x, $y, $colour ) = $piece;
// Numeric x, y within propery range? if( ! is_numeric( $x ) || ! is_numeric( $y ) || $x >= $this->rows || $y >= $this->rows ) { throw new Exception( 'x, y paramaters must be numeric and within the range 0 <= x/y <= ' . ( $this->rows - 1 ) ); }
// Correct colour? if( ! in_array( strtolower( $colour ), array( 'w', 'b' ) ) ) { throw new Exception( 'Colour paramater must be either \'x\' or \'y\'' ); }
// Passed all of the checks, let's add it to the game board $this->board[ $x ][ $y ] = strtolower( $colour );
}
// Retrieve all of the diagonal coordinates for a pt(x,y) private function diagonalCoordinates( $coord, $board = null ) { $arr = array(); $counter = 0; $gameBoard = ( $board == null ) ? $this->getGameBoard() : $board; list( $x, $y ) = $coord;
// Test diagonal ranges for squares to reverse private function testDiag( $range, $move, $board = null ) { // Gameboard $gameBoard = ( $board == null ) ? $this->getGameBoard() : $board;
// If we don't have enough coordinates (<=2), let's just return an empty array. if( sizeOf( $range ) <= 2 ) return array();
// Return array $return = array();
// Who is our opponent? Opposite of $move $opponent = ( $move == 'w' ) ? 'b' : 'w';
// Loop through the ranges $res = array(); foreach( $range as $coords ) { // Retrieve x/y values list( $xOrd, $yOrd ) = $coords;
// If we've found a valid piece. if( $this->getPiece( $xOrd, $yOrd, $gameBoard ) == $opponent ) { $res[] = array( $xOrd, $yOrd ); }
// Otherwise, we've found our own piece! Do what we gotta do, and then let's break out! else if( $this->getPiece( $xOrd, $yOrd, $gameBoard ) == $move ) { // If we've found anything, let's append it to the results if( sizeOf( $res ) > 0 ) $return = array_merge( $res, $return ); break; }
// Otherwise we've found empty space, return empty every time else if( $this->getPiece( $xOrd, $yOrd, $gameBoard ) == '.' ) { break; } }
return $return; }
// Calculate the pieces to turn between two points. private function reverseXYBlocks( $start, $end, $move, $board = null ) { // If the two co-ordinates are the same, just return. if( $start == $end ) return array();
// Return array $return = array();
// Who is our opponent? Opposite of $move $opponent = ( $move == 'w' ) ? 'b' : 'w';
// Default x/y values list( $x, $y ) = $start;
// What gameboard to use? $gameBoard = ( $board == null ) ? $this->getGameBoard() : $board;
// Horizontal axis $xy = ( $start[0] <> $end[0] ) ? 0 : 1; // Should we use the x or y oordinate (changes depending on axis to search) 0 = horizontal 1 = vertical $startLoop = ( $start[ $xy ] > $end[ $xy ] ) ? 0 : $start[ $xy ] + 1; $endLoop = ( $start[ $xy ] > $end[ $xy ] ) ? $start[ $xy ] - 1 : $this->getRows( $gameBoard ) - 1;
// Let's loop through foreach( range( $startLoop, $endLoop ) as $coord ) { if( $start[ $xy ] > $end[ $xy ] ) $coord = $endLoop - $coord; // If going left, we need to account for that.
// What x/y should we use? Changes depending on horizontal/vertical. Use the active loop count or revert to default. $xOrd = ( $xy == 0 ) ? $coord : $x; $yOrd = ( $xy == 1 ) ? $coord : $y;
// If we've found a valid piece. if( $this->getPiece( $xOrd, $yOrd, $gameBoard ) == $opponent ) { $res[] = array( $xOrd, $yOrd ); }
// Otherwise, we've found our own piece! Do what we gotta do, and then let's break out! else if( $this->getPiece( $xOrd, $yOrd, $gameBoard ) == $move ) { // If we've found anything, let's append it to the results if( sizeOf( $res ) > 0 ) $return = array_merge( $res, $return ); break; }
// Otherwise we've found empty space, return an empty array every time else if( $this->getPiece( $xOrd, $yOrd,$gameBoard ) == '.' ) { break; } }
return $return; }
// Output the board public function outputBoard( $board = null, $return = false ) { $gameBoard = ( $board == null ) ? $this->getGameBoard() : $board;
// Instantiate the Reversi class. $Reversi = new Reversi;
// Let's play reversi! try { // Let's load the game data if( ! file_exists( GAMEFILE ) || ! is_readable( GAMEFILE ) ) { throw new Exception( 'Unable to load game config file: ' . GAMEFILE ); }
// Data -> lower case array + remove white space. $config = array_map( 'strtolower', array_map( 'trim', file( GAMEFILE ) ) );
// Let's check the validity of some of the user data and toggle game settings if( ! is_array( $config ) || sizeOf( $config ) <= 1 ) { throw new Exception( 'Invalid format for game config file.' ); }
// Let's set next move. After we've done it, don't need that line anymore, so let's just remove it from the array so we can easily loop through. $Reversi->setNextTurn( substr( $config[0], 0, 1 ) ); // Only needs first letter. unset( $config[0] );
// Let's set the amount of rows $Reversi->setRows( sizeOf( $config ) );
// Let's start a new game! $Reversi->newGame();
// Loop through the gameboard and retrieve necessary character values. Want to create a gameboard as set by Gaiaonline. foreach( $config as $lineNum => $vals ) { // Sort out the y oordinate. $y = $Reversi->getRows() - $lineNum; foreach( range( 0, strlen( $vals ) - 1 ) as $x ) { // If it's black or white, let's append it to our game board. If it's not, we can just ignore it. if( in_array( $vals[ $x ], array( 'b', 'w' ) ) ) { $Reversi->setPiece( array( $x, $y, $vals[ $x ] ) ); } } }
// Output the board $Reversi->outputBoard();
// Run the AI engine $Reversi->aiClass()->setActivePlayer( $Reversi->getNextTurn() ); $Reversi->aiClass()->setNodes( NODES ); $Reversi->aiClass()->runAi( $Reversi->getGameBoard() );
// Loop through the scores to produce our tree path $Reversi->aiClass()->loopScores( $Reversi->aiClass()->getPossibleMovesProperty()->value, $Reversi->aiClass()->getPossibleMovesProperty()->value['score'] );
// Make the moves! $Reversi->aiClass()->makeMoves( DEBUG );
