Here is the code. It has minimax, alpha-beta, and a transposition table. Any comments or critiques welcome. Next I'd like to convert to negamax.
The next project I'll do is a checkers game, which will require eval to stop a some fixed depth. Maybe I can also add quiecence search and iterative deepening at that point. I also read that transposition tables usually don't store all positions (my tic-tac-toe game storoes all positions though). What is the usual strategy for selecting which positions to keep and which to discard?
// --------------------------------------------------------------
// File: tic_tac_toe.cpp
//
// This program makes use of minimax, alpha-beta pruning, and
// transposition tables to immplement tic-tac-toe. The program
// runs in three modes:
// 1) Minimax only
// 2) Minimax with alpha-beta pruning
// 3) Minimax with transposition tables only
// 4) Minimax with alpha beta pruning and transposition tables
//
// A counter is maintained, that tracks the number of recursive
// calls to max_value() & min_value(). This allows the user
// to verify the performance gains of alpha beta over simple
// minimax, and the additional gains of transposition tables.
//
// The code for minimax and alpha beta pruning was based on
// the pseudo-code provided in the book,
// "Artificial Intelligence: A Modern Approach", by
// Stuart Russell and Peter Norvig. The transposition tables
// are a simple extension, making use of the STL map class.
//
// The tic-tac-toe board representation is a simple bitboard,
// where the board-state is represented in the 9 low-order bits
// of two short integers. The moves made by MAX are maintained
// in game_state.x_ and the moves by MIN are maintained in the
// field game_state.o_.
//
// The game is coded so that MAX always plays first, and the
// human player will always play the role of 'MIN'. The human
// player is prompted with a question mark prompt ("? "), and
// should enter a number from 0-8. The number entered corresponds
// to a particular square. The squares are laid out as follows:
//
// 0 1 2
// 3 4 5
// 6 7 8
//
// Enjoy the game!
//
// --------------------------------------------------------------
# include <list>
# include <map>
# include <iostream>
using namespace std;
// --------------------------------------------------------------
// Some program constants
const int MAX_WINNING = 1;
const int MIN_WINNING = -1;
const int EQUAL_GAME = 0;
const int MAXIMUM_SQUARES = 9;
// Turn on Alpha-beta pruning algorithm
bool alpha_beta_on = false;
// Used to judge performance differences between
// use of minimax, alpha-beta pruning, and transposition
// tables
static int counter = 0;
// Helper functions to manipulate the bitboards
// --------------------------------------------------------------
// Top row, all bits on
inline bool TOP_ROW(short x)
{
return (x & 7) == 7;
}
// --------------------------------------------------------------
// Mid row, all bits on
inline bool MID_ROW(short x)
{
return (x & 0x38) == 0x38;
}
// --------------------------------------------------------------
// Bottom row, all bits on
inline bool BOT_ROW(short x)
{
return (x & 0x1C0) == 0x1C0;
}
// --------------------------------------------------------------
// left column, all bits on
inline bool LEFT_COL(short x)
{
return (x & 0x49) == 0x49;
}
// --------------------------------------------------------------
// middle column, all bits on
inline bool MID_COL(short x)
{
return (x & 0x92) == 0x92;
}
// --------------------------------------------------------------
// right column, all bits on
inline bool RIGHT_COL(short x)
{
return (x & 0x124) == 0x124;
}
// --------------------------------------------------------------
// first diagonal, all bits on
inline bool DIAG_1(short x)
{
return (x & 0x111) == 0x111;
}
// --------------------------------------------------------------
// other diagonal, all bits on
inline bool DIAG_2(short x)
{
return (x & 0x54) == 0x54;
}
// --------------------------------------------------------------
// Utility value is the measure of how good a
// position is. There are only three values for
// tic-tac-toe: +1 means MAX is winning, -1 means
// MIN is winning, and 0 means best play is a cat's
// game.
//
typedef int utility;
// --------------------------------------------------------------
// An action is an operation that can be applied to a game
// state to achieve a new game_state. In other words, an
// action represents a move. The class below is fairly simple.
// The a_ member represents the move. The side_ member indicates
// who the move is for (MIN or MAX). The a_ member will have one of the
// nine low order bits set to 1, all others to 0. When this is
// bitwise-OR'ed to the current game state (for either MIN or MAX),
// it will produce a new game state.
class action {
public:
// Simple initialization
action() {
a_ = 0;
side_ = 0;
}
// Initialize with values
action(short a, short side) {
a_ = a;
side_ = side;
}
// Enumeration for setting side_ member
enum { MIN = 1, MAX = 2 };
// The action to be applied to some game_state
short a_;
// What side to apply the action to. If side_ is set
// to action::MIN, then the action a_ will be applied to
// game_state.o_ field. If side_ is set to action::MAX
// then action a_ is applied to some game_state.x_.
short side_;
};
// --------------------------------------------------------------
// This represents the state of the game. The x_ member variable
// holds the representation of MAX's moves (held in 9 low-order
// bits), and o_ is MIN's moves (also 9 low-order bits).
//
class game_state {
public:
short x_;
short o_;
// Simple initialization
game_state() {
x_ = 0;
o_ = 0;
}
// --------------------------------------------------------------
// Equality comparison: Needed for comparisons in std::map<>
bool operator==(const game_state& g) const
{
return (x_ == g.x_) && (o_ == g.o_);
}
// --------------------------------------------------------------
// Less than comparison: Needed for comparisons in std::map<>
bool operator<(const game_state& g) const
{
if (x_ < g.x_) return true;
if (x_ == g.x_ && o_ < g.o_) return true;
else return false;
}
// --------------------------------------------------------------
// Predicate returns true if all board squares are
// occupied
inline bool is_filled() const {
return (x_|o_) == 0x1FF;
}
// --------------------------------------------------------------
// Is the position a win? The input parameter is either
// gs.x_ or gs.o_
inline bool win(short s) const {
return TOP_ROW(s) ||
MID_ROW(s) ||
BOT_ROW(s) ||
LEFT_COL(s)||
MID_COL(s) ||
RIGHT_COL(s)||
DIAG_1(s) ||
DIAG_2(s);
}
// --------------------------------------------------------------
// Did MIN win?
inline bool min_win() const{
return win(o_);
}
// --------------------------------------------------------------
// Did MAX win?
inline bool max_win() const {
return win(x_);
}
// --------------------------------------------------------------
// Print one square
inline char print_one(int index) const
{
if ((x_ & index) != 0) return 'x';
else if (o_ & index) return 'o';
else return '_';
}
// --------------------------------------------------------------
// Play nice with iostreams
friend ostream& operator<<(ostream& s, game_state& gs) {
s << gs.print_one(1) << " " << gs.print_one(2) << " " << gs.print_one(4) << endl;
s << gs.print_one(8) << " " << gs.print_one(16) << " " << gs.print_one(32) << endl;
s << gs.print_one(64) << " " << gs.print_one(128) << " " << gs.print_one(256) << endl;
return s;
}
};
// --------------------------------------------------------------
// The transposition table class. This is a simple
// wrapper for a STL map. It also contains a toggle
// control so that the transposition table can be
// turned off
class ttable {
map<game_state,utility> tbl_;
bool on_;
public:
ttable() {
on_ = false;
}
~ttable() {
tbl_.erase(tbl_.begin(),tbl_.end());
}
// --------------------------------------------------------------
// Toggle the feature on and off
void toggle(bool on) {
on_ = on;
}
// --------------------------------------------------------------
// Get a cached entry
bool get(const game_state& gs, utility& u) {
if (!on_) return false;
if (tbl_.find(gs) == tbl_.end()) return false;
u = tbl_[gs];
return true;
}
// --------------------------------------------------------------
// Add an entry to the table
void put(const game_state& gs, const utility& u) {
if (!on_) return;
tbl_[gs] = u;
}
};
// Global transposition table object
static ttable trans_tbl;
// Prototypes
void minimax(const game_state&,action&,utility&);
void max_value(const game_state&,utility,utility,action&,utility&);
void min_value(const game_state&,utility,utility,action&,utility&);
// --------------------------------------------------------------
// Name: end_state
// Description: predicate that determines if a stopping case has been
// reached.
//
bool end_state(const game_state& gs)
{
if (gs.max_win() || gs.min_win() || gs.is_filled()) return true;
return false;
}
// --------------------------------------------------------------
// Name: eval
// Description: Given a game_state, this returns the corresponding
// utility value.
//
void eval(const game_state& gs, utility& val)
{
if (gs.max_win()) val = MAX_WINNING;
else if (gs.min_win()) val = MIN_WINNING;
else if (gs.is_filled()) val = EQUAL_GAME;
else {
throw logic_error("invalid call to eval()");
}
}
// --------------------------------------------------------------
// Name: get_candidates
// Description: given a game_state as input, this returns a list of
// candidate actions
//
void get_candidates(const game_state& gs, list<action>& candidates, int side)
{
for (short i = 0; i < MAXIMUM_SQUARES; i++) {
if (!((gs.x_|gs.o_) & (1<<i))) {
action a;
a.a_ = (1<<i);
a.side_ = side;
candidates.push_back(a);
}
}
}
// --------------------------------------------------------------
// Name: apply_candidates
// Description: given a game_state G and action A as input, this will return
// a new game state NG which results when A is applied to G.
//
game_state apply_candidate(const game_state& gs, const action& act)
{
game_state next_gs;
if (act.side_ == action::MIN) {
next_gs.x_ = gs.x_;
next_gs.o_ = gs.o_|act.a_;
}
else {
next_gs.o_ = gs.o_;
next_gs.x_ = gs.x_|act.a_;
}
return next_gs;
}
// --------------------------------------------------------------
// Name: minimax
// Description: Run the minimax algorighm
//
void minimax(const game_state& gs, action& act, utility& val)
{
utility alpha = -INT_MAX;
utility beta = INT_MAX;
max_value(gs,alpha,beta,act,val);
}
// --------------------------------------------------------------
// Name: max_value
// Description: Find best action from MAX perspective
//
void max_value(const game_state& gs, utility alpha, utility beta,
action& act, utility& val)
{
utility best_util = -INT_MAX;
action best_action;
// If we reached the end state, get the evalutation
// of the position
if (end_state(gs)) {
eval(gs,val);
return;
}
// Get a list of candidate moves
list<action> candidates;
get_candidates(gs,candidates,action::MAX);
// Iterate over all candidates
list<action>::iterator end = candidates.end();
for (list<action>::iterator itr = candidates.begin();
itr != end; itr++) {
// Apply this candidate move, to get the new
// game state
game_state next_gs = apply_candidate(gs,*itr);
utility next_util;
action next_action;
// Do we have this game_state already in the transposition
// table?
if (!trans_tbl.get(next_gs,next_util)) {
// No, keep searching to get evaluation
min_value(next_gs,alpha,beta,next_action,next_util );
// Save this evaluation for later
trans_tbl.put(next_gs,next_util);
}
// If this utility value is better than the best
// utility found so far, save it, and also save the
// action that produced this utility
if (next_util > best_util) {
best_util = next_util;
best_action = *itr;
}
if (alpha_beta_on) {
// Did we hit a beta cutoff?
if (next_util >= beta) {
break;
}
else {
// Update alpha value
alpha = max(alpha,next_util);
}
}
}
// Assign output parameters
act = best_action;
val = best_util;
// Increment trace counter
counter++;
}
// --------------------------------------------------------------
// Name: min_value
// Description: Find best action from MIN perspective
//
void min_value(const game_state& gs, utility alpha, utility beta,
action& act, utility& val)
{
utility best_util = INT_MAX;
action best_action;
// If we reached the end state, get the evalutation
// of the position
if (end_state(gs)) {
eval(gs,val);
return;
}
// Get a list of candidate moves
list<action> candidates;
get_candidates(gs,candidates,action::MIN);
// Iterate over all candidates
list<action>::iterator end = candidates.end();
for (list<action>::iterator itr = candidates.begin();
itr != end; itr++) {
// Apply this candidate move, to get the new
// game state
game_state next_gs = apply_candidate(gs,*itr);
utility next_util;
action next_action;
// Do we have this game_state already in the transposition
// table?
if (!trans_tbl.get(next_gs,next_util)) {
// No, keep searching to get evaluation
max_value(next_gs,alpha,beta,next_action,next_util );
// Save this evaluation for later
trans_tbl.put(gs,next_util);
}
// If this utility value is better than the best
// utility found so far, save it, and also save the
// action that produced this utility
if (next_util < best_util) {
best_util = next_util;
best_action = *itr;
}
if (alpha_beta_on) {
// Did we hit an alpha cutoff?
if (next_util <= alpha) {
break;
}
else {
// Update the beta value
beta = min(beta,next_util);
}
}
}
// Assign output parameters
act = best_action;
val = best_util;
// Increment trace counter
counter++;
}
// --------------------------------------------------------------
// Prompt for integer value in the range 0-8
short prompt(const char* p)
{
short input;
while(true) {
cout << p;
cin >> input;
if (cin.good()) {
if (input >= 0 && input <= 8)
break;
}
else {
cin.clear();
cin.ignore(INT_MAX,'\n');
}
cout << "Invalid input, expected [0-8]" << endl;
}
return input;
}
// --------------------------------------------------------------
// Prompt for y/n value
bool option_prompt(const char* prompt)
{
char option;
cout << prompt;
cin >> option;
if (option == 'y' ||
option == 'Y') return true;
return false;
}
// --------------------------------------------------------------
// Main driver program
int main()
{
utility val;
action act;
game_state gs;
// Prompt for game controls
alpha_beta_on = option_prompt("Alpha-beta pruning on (y/n) ");
bool on = option_prompt("Transposition tables on (y/n) ");
trans_tbl.toggle(on);
// Enter game loop
try {
while (true) {
counter = 0;
// See what MAX wants to do
minimax(gs,act,val);
// Apply MAX choice
gs = apply_candidate(gs,act);
// Print resulting board
cout << "Total function calls: " << counter << endl;
cout << "Utility: " << val << endl;
cout << gs << endl;
// If MAX wins we're done
if (gs.max_win()) {
cout << "MAX wins!" << endl;
break;
}
// If cat's game we're done
if (gs.is_filled()) {
cout << "Cat's game!" << endl;
break;
}
action o;
o.a_ = 1<<prompt("? ");
o.side_ = action::MIN;
gs = apply_candidate(gs,o);
cout << gs << endl;
if (gs.min_win()) {
cout << "MIN wins!" << endl;
break;
}
if (gs.is_filled()) {
cout << "Cat's game!" << endl;
break;
}
}
}
catch (exception& e) {
cerr << "Exception: " << e.what() << endl;
}
return 0;
}