Thread: tic-tac-toe anyone?

  1. #1
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446

    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?
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  2. #2
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    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.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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;
    }
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  4. #4
    Let's do some coding! Welshy's Avatar
    Join Date
    Mar 2005
    Location
    Staffordshire University, UK
    Posts
    168
    When trying to compile the code i get an error 'logic_error undeclared'

  5. #5
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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?
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  6. #6
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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;
    }
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  7. #7
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>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.

  8. #8
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  9. #9
    Let's do some coding! Welshy's Avatar
    Join Date
    Mar 2005
    Location
    Staffordshire University, UK
    Posts
    168
    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

  10. #10
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    >>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().
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  11. #11
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  12. #12
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    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
    hooch

  13. #13
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    Cool stuff!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. tic tac toe
    By holden in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 05-09-2004, 09:59 AM
  3. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  4. tic tac toe game
    By Leeman_s in forum Game Programming
    Replies: 9
    Last Post: 04-24-2002, 03:24 AM
  5. my tic tac toe game, please try it
    By Leeman_s in forum C++ Programming
    Replies: 2
    Last Post: 04-14-2002, 05:16 PM