# tic-tac-toe anyone?

• 03-22-2005
IfYouSaySo
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?
• 03-22-2005
Quote:

Should I post it?
Sure
Quote:

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.
• 03-22-2005
IfYouSaySo
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; }```
• 03-23-2005
Welshy
When trying to compile the code i get an error 'logic_error undeclared'
• 03-23-2005
IfYouSaySo
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?
• 03-23-2005
IfYouSaySo
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; }```
• 03-23-2005
PJYelton
>>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.
• 03-24-2005
IfYouSaySo
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.
• 03-25-2005
Welshy
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
• 03-25-2005
JaWiB
>>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().
• 03-26-2005
IfYouSaySo
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.
• 04-21-2005
ssjnamek
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
• 04-21-2005
Queatrix
Cool stuff!