Jump to content
  • Advertisement
Sign in to follow this  
Narf the Mouse

Tic-Tac-Toe using NegaMax

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!