Tic-Tac-Toe using NegaMax

This topic is 3204 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

MinMax/NegaMax sounded like a useful thing to learn, so I've written up a Tic-Tac-Toe implementation. The problem is, it's not picking the best move. So, I've decided to ask for help. I suspect the problem is that it doesn't find the quickest path to victory, only *A* path to victory. The NegaMax implementation:
    static class NegaMax
{
public static Int32[] sign = new int[2] { 1, -1 };   //0 is blue, 1 is red

public static void Analyze(BoardTicTacToe board, Int32 depth, Int32 color, out MoveTicTacToe m)
{
List<Tuple2<Int32, MoveTicTacToe>> moves = new List<Tuple2<int, MoveTicTacToe>>();
BoardTicTacToe c;
foreach (MoveTicTacToe m2 in board.LegalMoves)
{
c = new BoardTicTacToe(board);
c.MakeMove(m2, sign[color]);
moves.Add(new Tuple2<int, MoveTicTacToe>(-Analyze(c, depth + 1, 1 - color), m2));  //Note the "-" before "NegaMax"
}

moves.Sort((a, b) =>
{
if (a.Item1 * sign[color] > b.Item1 * sign[color])
return -1;
else if (a.Item1 * sign[color] < b.Item1 * sign[color])
return 1;
else return 0;
}
);
m = moves[0].Item2;
}

public static Int32 Analyze(BoardTicTacToe b, Int32 depth, Int32 color)
{
if (b.GameOver())
{
Int32 result = sign[color] * b.Analyze();
/* if (result > 0)
result -= depth;
else if (result < 0)
result -= depth;
return result; */
}
Int32 max = -Int32.MaxValue;
BoardTicTacToe c;
foreach (MoveTicTacToe m in b.LegalMoves)
{
c = new BoardTicTacToe(b);
c.MakeMove(m, sign[color]);
Int32 x = -Analyze(c, depth + 1, 1 - color);  //Note the "-" before "NegaMax"
if (x > max)
max = x;
}
return max;
}
}



Share on other sites
Negamax (and all other minimax variants) will not prefer a short victory to any victory unless you do something like assign short victories larger values.

What's an example where you think it's picking the wrong move?

Share on other sites
Quite simply, it'll sometimes ignore an "instant" victory move or let the other "player" get a win.

Share on other sites
Well, then you have a bug. The good news is that tic-tac-toe is a very small game and it should be easy to find the problem by using a debugging and/or printing out a few intermediate values. Good luck.

The only mistake I can see in a quick glance through your code is that you commented out a useful return statement when the game is over.

Share on other sites
I guess your negamax implementation is wrongly done.
I think you have to give the first call as
Analyze(...)
{
...
...
int score=-Negamax(.....and the parameters.)
}

For quick wining than longer wining, make use of returning higher values for quicker win
hint, use variable depth in this case.

Share on other sites
Thanks for the help.

I found a bug - It wasn't correctly calculating in .GameOver() I also edited that return back in. In seems to be playing better, but still makes mistakes.

Further updates as I find further problems.
    static class NegaMax    {        public static Int32[] sign = new int[2] { 1, -1 };   //0 is blue, 1 is red        public static void Analyze(BoardTicTacToe board, Int32 color, out MoveTicTacToe m)        {            List<Tuple2<Result, MoveTicTacToe>> moves = new List<Tuple2<Result, MoveTicTacToe>>();            BoardTicTacToe c;            Int32 depth = 0;            foreach (MoveTicTacToe m2 in board.LegalMoves)            {                c = new BoardTicTacToe(board);                c.MakeMove(m2, sign[color]);                moves.Add(new Tuple2<Result, MoveTicTacToe>(-Analyze(c, depth + 1, 1 - color), m2));  //Note the "-" before "NegaMax"            }            moves.Sort((a, b) =>            {                if (a.Item1.Score * sign[color] > b.Item1.Score * sign[color])                    return -1;                else if (a.Item1.Score * sign[color] < b.Item1.Score * sign[color])                    return 1;                else                    if (a.Item1.Score * sign[color] == b.Item1.Score * sign[color]                        && a.Item1.Depth < b.Item1.Depth)                        return -1;                    else if (a.Item1.Score * sign[color] == b.Item1.Score * sign[color]                            && a.Item1.Depth > b.Item1.Depth)                        return 1;                    else                        return 0;                                    }            );            m = moves[0].Item2;        }        public struct Result        {            #region Body            public Result(Int32 score, Int32 depth)            {                this.Score = score;                this.Depth = depth;            }            public Int32 Score;            public Int32 Depth;            public static Result operator -(Result a)            {                a.Score = -a.Score;                return a;            }            public override string ToString()            {                return "Score: " + Score + ", Depth: " + Depth;            }            #endregion        }        public static Result Analyze(BoardTicTacToe b, Int32 depth, Int32 color)        {            if (b.GameOver())            {                Int32 result = sign[color] * b.Analyze();                /* if (result > 0)                    result -= depth;                else if (result < 0)                    result -= depth;                return result; */                return new Result(result, depth);            }            Result max = new Result(-Int32.MaxValue, Int32.MaxValue);            BoardTicTacToe c;            foreach (MoveTicTacToe m in b.LegalMoves)            {                c = new BoardTicTacToe(b);                c.MakeMove(m, sign[color]);                Result x = -Analyze(c, depth + 1, 1 - color);  //Note the "-" before "NegaMax"                if (x.Score > max.Score                    || (x.Score == max.Score && x.Depth < max.Depth))                     max = x;            }            return max;        }    }

Share on other sites
[font=arial,helvetica,sans-serif]I hacked together something in C++ that does the right thing. It's sort of a fun implementation.[/font]
#include <iostream> #include <ctime> #include <cstdlib> #include <algorithm> struct Board { static unsigned const code[9]; unsigned player_sum[2]; int board[9]; Board() { player_sum[0]=0x11111111; player_sum[1]=0x11111111; for (int i=0; i<9; ++i) board=-1; } void play(int player, int square) { player_sum[player]+=code[square]; board[square]=player; } void undo(int player, int square) { player_sum[player]-=code[square]; board[square]=-1; } bool finished(int &winner) { if (player_sum[0]&0x44444444){ winner=0; return true; } if (player_sum[1]&0x44444444){ winner=1; return true; } if (player_sum[0]+player_sum[1] == 0x55555555) { winner=-1; return true; } return false; } }; unsigned const Board::code[9] = { 0x10010010, 0x10001000, 0x10000101, 0x01010000, 0x01001011, 0x01000100, 0x00110001, 0x00101000, 0x00100110 }; int nega_max(Board &b, int player, int alpha, int beta, int from_root) { int winner; if (b.finished(winner)) { if (winner==-1) return -500+(std::rand()%1001); return (winner == player ? 1 : -1) *(1000000000 - from_root*1000 -500 + (std::rand()%1001)); } for (int i=0; i<9; ++i) { if (b.board==-1) { b.play(player, i); int v = -nega_max(b, 1-player, -beta, -alpha, from_root+1); b.undo(player, i); if (v>alpha) { alpha = v; if (v>beta) { return v; } } } } return alpha; } int pick_move(Board &b, int player) { int best_score=-1000000000; int best_move=0; for (int i=0; i<9; ++i) { if (b.board==-1) { b.play(player, i); int v = -nega_max(b, 1-player, -1000000000, -best_score, 1); b.undo(player, i); if (v>best_score) { best_score=v; best_move=i; } } } std::cout << "best=" << best_move << " score=" << best_score << '\n'; return best_move; } std::ostream &operator << (std::ostream &os, Board const &b) { for (int j=0; j<3; ++j) { for (int i=0; i<3; ++i) os << ".xo"[b.board[3*j+i]+1] << ' '; os << " "; for (int i=0; i<3; ++i) os << (3*j+i) << ' '; os << '\n'; } return os; } int main() { std::srand(time(0)); Board b; int winner; int human_player; std::cout << "Enter which player you want to be (0 or 1): "; std::cin >> human_player; for (int i=0; !b.finished(winner); i=1-i) { std::cout << b; int m; if (i==human_player) std::cin >> m; else m=pick_move(b,i); b.play(i,m); } std::cout << b; switch(winner) { case -1: std::cout << "It's a draw!\n"; break; case 0: std::cout << "x' wins!\n"; break; case 1: std::cout << "o' wins!\n"; break; } } 

Share on other sites
Thanks - I'll look it over.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 31
• 16
• 11
• 10
• 11
• Forum Statistics

• Total Topics
634113
• Total Posts
3015592
×