C# minimax algorithm implementation returning values such as -1000, -3000, -8000, etc

StackOverflow https://stackoverflow.com/questions/19805631

  •  04-07-2022
  •  | 
  •  

Question

I am trying to implement minimax in my C# code for tictactoe. For some reason, when the depth = 1 and I debug it to check to see all of the values returned from different paths; I see crazy values like -1000, -5000, -1000, etc! How is this possible? What is happening? This is my full code,

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace Minimax_TicTacToe
{
    public partial class Main : Form
    {
        //Definition constants
        private const int EMPTY = 0;
        private const int PLAYER = 1;
        private const int COMPUTER = 2;
        private const int PLAYER_WON = 0;
        private const int COMPUTER_WON = 1;
        private const int DRAW = 2;
        private const int GAME = 3;
        private const int OVER = 4;

        //Internals
        private int turns = 0;
        private int turn = PLAYER;
        private String player_mark = "X";
        private String computer_mark = "O";

        //Grid
        private byte[] grid = { 
                                  0, 0, 0,
                                  0, 0, 0,
                                  0, 0, 0
                              };

        public Main()
        {
            InitializeComponent();
        }

        private void Main_Load(object sender, EventArgs e)
        {

        }
        /*
        private int Minimax(byte[] ngrid, int depth = 0, int score = 0)
        {
            if (depth == 0)
            {
                return Minimax(new byte[] { grid[0], grid[1], grid[2], 
                                            grid[3], grid[4], grid[5], 
                                            grid[6], grid[7], grid[8] },
                                            depth + 1);
            }
            else
            {
                int status = GameStatus(ngrid);
                if (status == PLAYER_WON) return -1;
                else if (status == COMPUTER_WON) return 1;
                else if (status == DRAW) return 0;
                int i;

                for (i = 0; i < grid.Length; i++)
                {
                    if (ngrid[i] == 0)
                    {
                        byte[] board = new byte[] { 
                            ngrid[0], ngrid[1], ngrid[2], 
                            ngrid[3], ngrid[4], ngrid[5], 
                            ngrid[6], ngrid[7], ngrid[8]
                        };

                        board[i] = (depth % 2 == 0) ? (byte)PLAYER : (byte)COMPUTER;
                        score = Minimax(board, depth + 1);
                        if (score == 1 && depth == 1) return i;
                        if (score == 1) return 1;

                    }
                }

                return 0;

            }


        }*/

        private int Minimax(byte[] ngrid, int depth = 0)
        {
            if (depth == 0)
            {
                return Minimax(new byte[] { grid[0], grid[1], grid[2], 
                                            grid[3], grid[4], grid[5], 
                                            grid[6], grid[7], grid[8] },
                                            depth + 1);
            }
            else
            {
                int status = GameStatus(ngrid);
                if (status == PLAYER_WON) return -1;
                else if (status == COMPUTER_WON) return 1;
                else if (status == DRAW) return 0;
                int i;
                int score = 0;

                List<Carrier> carry = new List<Carrier>();

                for (i = 0; i < grid.Length; i++)
                {
                    if (ngrid[i] == 0)
                    {
                        byte[] board = new byte[] { 
                            ngrid[0], ngrid[1], ngrid[2], 
                            ngrid[3], ngrid[4], ngrid[5], 
                            ngrid[6], ngrid[7], ngrid[8]
                        };

                        board[i] = (depth % 2 == 0) ? (byte)PLAYER : (byte)COMPUTER;
                        score += Minimax(board, depth + 1);

                        if (depth == 1)
                        {
                            Carrier c = new Carrier();
                            c.offset = i;
                            c.score = score;
                            carry.Add(c);
                        }

                    }
                }

                if (depth == 1)
                {
                    MessageBox.Show("");
                }

                return score;

            }


        }

        private void ComputersTurn()
        {
            turn = COMPUTER;
            turns++;
            int status = GameStatus(grid);

            switch (status)
            {
                case GAME:
                    int offset = Minimax(grid);
                    grid[offset] = COMPUTER;                    
                    turn = PLAYER;
                    UpdateBoard();
                    break;                
            }

            switch (GameStatus(grid))
            {
                case PLAYER_WON:
                    turn = COMPUTER;
                    MessageBox.Show("You win!");
                    break;

                case COMPUTER_WON:
                    turn = COMPUTER;
                    MessageBox.Show("You lost!");
                    break;

                case DRAW:
                    turn = COMPUTER;
                    MessageBox.Show("DRAW!");
                    break;
            }
        }

        private void UpdateBoard()
        {
            int n = 0;
            grid0.Text = (grid[n] != 0) ? ( (grid[n] == PLAYER ? player_mark : computer_mark) ) : "";
            n++;
            grid1.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid2.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid3.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid4.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid5.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid6.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid7.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
            grid8.Text = (grid[n] != 0) ? ((grid[n] == PLAYER ? player_mark : computer_mark)) : "";
            n++;
        }

        private int GameStatus(byte[] pgrid)
        {
            for (int i = 0; i < 3; i++)
            {
                if (pgrid[i * 3] == pgrid[i * 3 + 1] && pgrid[i * 3] == pgrid[i * 3 + 2] && pgrid[i * 3] != 0)
                    return SelectWinner(pgrid[i * 3]);
                if (pgrid[i] == pgrid[i + 3] && pgrid[i] == pgrid[i + 6] && pgrid[i] != 0)
                    return SelectWinner(pgrid[i]);
            }

            if (pgrid[0] == pgrid[4] && pgrid[0] == pgrid[8] && pgrid[0] != 0)
                return SelectWinner(pgrid[0]);
            if (pgrid[2] == pgrid[4] && pgrid[2] == pgrid[6] && pgrid[2] != 0)
                return SelectWinner(pgrid[2]);

            if (turns == 4)
                return DRAW;

            return GAME;

        }

        private int SelectWinner(byte item)
        {
            if (item == PLAYER)
                return PLAYER_WON;
            else if (item == COMPUTER)
                return COMPUTER_WON;

            throw new Exception("SELECTION ERROR");
        }

        private void grid0_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;

            grid[0] = PLAYER;
            grid0.Text = player_mark;
            ComputersTurn();
        }

        private void grid1_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[1] = PLAYER;
            grid1.Text = player_mark;
            ComputersTurn();
        }

        private void grid2_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[2] = PLAYER;
            grid2.Text = player_mark;
            ComputersTurn();
        }

        private void grid3_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[3] = PLAYER;
            grid3.Text = player_mark;
            ComputersTurn();
        }

        private void grid4_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[4] = PLAYER;
            grid4.Text = player_mark;
            ComputersTurn();
        }

        private void grid5_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[5] = PLAYER;
            grid5.Text = player_mark;
            ComputersTurn();
        }

        private void grid6_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[6] = PLAYER;
            grid6.Text = player_mark;
            ComputersTurn();
        }

        private void grid7_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[7] = PLAYER;
            grid7.Text = player_mark;
            ComputersTurn();
        }

        private void grid8_Click(object sender, EventArgs e)
        {
            if (turn == COMPUTER)
                return;
            grid[8] = PLAYER;
            grid8.Text = player_mark;
            ComputersTurn();
        }
    }

    class Carrier
    {
        public int score;
        public int offset;
    }
}
Was it helpful?

Solution

The one thing that jumps out at me is this piece:

score += Minimax(...

I think you'll want your minimax to select the move with the best score and return that score, not the sum of the scores for all possible moves from that position.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top