tic-tac-toe anyone?

I just finished a tic-tac-toe game that uses minimax with alpha-beta pruning. Should I post it? Would anyone be interested in showing me how to switch it to 'negamax' algorithm?

Should I post it?

Sure

Would anyone be interested in showing me how to switch it to 'negamax' algorithm?

If I have no homework tonight I might be able to help.

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?

Code:

// --------------------------------------------------------------
// 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;
}

When trying to compile the code i get an error 'logic_error undeclared'

Hm...I didn't get a compile error using VC7.1. I think logic_error is in the following header. I'll correct it, thanks for the info.

Code:

# include <stdexcept>

Also, in trying to correct the problem I noticed that VC6 complains about min and max, but VC7.1 and gcc do not. I was looking online, and it seems that '# include <algorithm>' should fix the problem, but it does not. Any ideas on this one?

I modified the algorithm to be negamax, and now I am getting incorrect results. (I also changed the constants action::MAX and action::MIN to be 1 & -1, so that I can switch the side to move by flipping the sign. Here is the code...maybe someone who has implemented negamax before can spot the problem?

Also, another question I have is that the pseudo-code that I usually see does not return the action (i.e. the move to make), but does undo the move before returning. This confuses me, because this creates a situation where the caller has the evaluation for a positon, but no suggestion of which move leads to the evaluation. Or am I missing something?

Code:

utility negamax(const game_state& gs, action& act, int side = action::MAX,
				  utility alpha = INT_MIN, utility beta = INT_MAX)
{
                    utility best_util = INT_MIN;
  
	// If we reached the end state, get the evalutation
	// of the position
	if (end_state(gs)) {
		eval(gs,best_util);
		return best_util;
	}

	// Get a list of candidate moves
	list<action> candidates;
	get_candidates(gs,candidates,side);

	// 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;

		next_util = -negamax(next_gs,next_action, -side, -alpha, -beta);

		// 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;
            act = *itr;
        }

		if (alpha_beta_on) {
			// Update alpha
			if (next_util > alpha) {
				alpha = best_util;
			}
			// Did we hit a cutoff?
			if (alpha >= beta) {
				return alpha;
			} 
		}
	}

	counter++;

	return best_util;
}

>>Also, another question I have is that the pseudo-code that I usually see does not return the action (i.e. the move to make), but does undo the move before returning. This confuses me, because this creates a situation where the caller has the evaluation for a positon, but no suggestion of which move leads to the evaluation. Or am I missing something?<<

Do you have a link or can you write an example? Sometimes its assumed that there is another loop outside the minimax function that goes through all of the first possible moves in which case theres no need to return a move.

No, just the code from my AI book. But what you say makes sense, since the action/move isn't needed except at the first call to minimax. Thanks.

sorry, i cant really help you on AI, im learning C++ myself at the minute, i just fancied trying out your program since it looked impressive glad to have been of some help

>>Also, in trying to correct the problem I noticed that VC6 complains about min and max, but VC7.1 and gcc do not. I was looking online, and it seems that '# include <algorithm>' should fix the problem, but it does not. Any ideas on this one?

If you're referring to INT_MIN and INT_MAX, I believe you should #include <limits> and use std::numeric_limits<int>::max() and std::numeric_limits<int>::min().

I should probably do that also (i.e. use numeric_limits<int>::max instead of INT_MAX), but I mean the function max() that returns the greater of two values. I think it is defined in <algorithm> as a template function.

I ran it in .NET compiler and it works fine well except i had to add the #include "stdafx.h"

other im 0-3 against it lol

very nice

defently must keep this one around for reference sometime whenever i get that good

Cool stuff!