#include <iostream.h>
#include "Hash.h"
#ifdef __GNUC__
#include "Hash.cpp"
#endif
struct Position
{
int Board[ 3 ][ 3 ];
int Value;
Position( ) { }
Position( int TheBoard[ 3 ][ 3 ] );
const Position & operator= ( const Position & Rhs );
int operator==( const Position & Rhs ) const;
int operator!=( const Position & Rhs ) const
{ return !( operator==( Rhs ) ); }
};
class TicTacToe
{
public:
enum Side { Human, Computer, Empty };
enum PositionVal { HumanWin, Draw, Unclear, ComputerWin };
TicTacToe( ) { ClearBoard( ); }
int ChooseMove( Side S, int & BestRow, int & BestColumn,
int Alpha = HumanWin, int Beta = ComputerWin, int Depth = 0 );
int PlayMove( Side S, int Row, int Column );
void ClearBoard( );
void GetMove( );
int BoardIsFull( ) const;
int IsAWin( Side S ) const;
friend ostream & operator <<( ostream & Out, const TicTacToe & B );
private:
HashTable<Position> Transpositions;
int Board[ 3 ][ 3 ];
void Place( int Row, int Column, int Piece = Empty )
{ Board[ Row ][ Column ] = Piece; }
int SquareIsEmpty( int Row, int Column ) const
{ return Board[ Row ][ Column ] == Empty; }
int PositionValue( ) const;
};
int
TicTacToe::PositionValue( ) const
{
return IsAWin( Computer ) ? ComputerWin :
IsAWin( Human ) ? HumanWin :
BoardIsFull( ) ? Draw : Unclear;
}
int
Position::operator==( const Position & Rhs ) const
{
for( int i = 0; i < 3; i++ )
for( int j = 0; j < 3; j++ )
if( Board[ i ][ j ] != Rhs.Board[ i ][ j ] )
return 0;
return 1;
}
const Position &
Position::operator=( const Position & Rhs )
{
for( int i = 0; i < 3; i++ )
for( int j = 0; j < 3; j++ )
Board[ i ][ j ] = Rhs.Board[ i ][ j ];
Value = Rhs.Value;
return *this;
}
Position::Position( int TheBoard[ 3 ][ 3 ] )
{
for( int i = 0; i < 3; i++ )
for( int j = 0; j < 3; j++ )
Board[ i ][ j ] = TheBoard[ i ][ j ];
}
unsigned int
Hash( const Position & Key, int TableSize )
{
unsigned int HashVal = 0;
for( int i = 0; i < 3; i++ )
for( int j = 0; j < 3; j++ )
HashVal = HashVal * 4 ^ Key.Board[ i ][ j ];
return HashVal % TableSize;
}
int
TicTacToe::ChooseMove( Side S, int & BestRow, int & BestColumn,
int Alpha, int Beta, int Depth )
{
Side Opp; int Reply; int Dc; int SimpleEval; Position ThisPosition = Board;
int & Value = ThisPosition.Value;
static const TableDepth = 5;
if( ( SimpleEval = PositionValue( ) ) != Unclear )
return SimpleEval;
if( Depth == 0 )
Transpositions.MakeEmpty( );
else if( Depth >= 3 && Depth <= TableDepth )
{
const Position & LookupVal =
Transpositions.Find( ThisPosition );
if( Transpositions.WasFound( ) )
return LookupVal.Value;
}
if( S == Computer )
{
Opp = Human; Value = Alpha;
}
else
{
Opp = Computer; Value = Beta;
}
for( int Row = 0; Row < 3; Row++ )
for( int Column = 0; Column < 3; Column++ )
if( SquareIsEmpty( Row, Column ) )
{
Place( Row, Column, S );
Reply = ChooseMove( Opp, Dc, Dc, Alpha, Beta, Depth + 1 );
Place( Row, Column, Empty );
if( S == Computer && Reply > Value ||
S == Human && Reply < Value )
{
if( S == Computer )
Alpha = Value = Reply;
else
Beta = Value = Reply;
BestRow = Row; BestColumn = Column;
if( Alpha >= Beta )
goto Done; }
}
Done:
if( Depth <= TableDepth )
Transpositions.Insert( ThisPosition );
return Value;
}