I decided recently to start working on some small projects to gain experience on my own outside of class, and after some looking around, decided to settle on tic-tac-toe for a nice easy first project which I'll move on from when I'm finished. Well, I started it and most of the project was a piece of cake, the only trouble I'm having is with my hardest difficulty setting. Of course I know there are other ways to do this, but I decided to use the negamax algorithm so that I can gain experience working with it and hopefully at least understand it to a degree. While I found several sights talking about it and giving pseudocode, I can't find an actual example in c++ and now that I am having problems with my code, I'm having trouble using it. Here is what I have so far, I'm sure that I've just done some stupid newbie mistake or am missing something simple, but this is the last thing till this project is finished really and I can't seem to figure it out. Any hints would be greatly appreciated! This is the code for my NegaMax function.

int Driver::NegaMax( int p )
{

	if ( b.CheckWin() == 1 )
	{
		return 1;
	}
	else if ( b.CheckWin() == -1 )
	{
		return -1;
	}
	else if ( b.CheckWin() == 0 && b.IsFull() )
	{
		return 0;
	}

	int max = -10000;

	for ( int count = 0; count <= 8; count++ )
	{
		if ( b.CheckBox( count ) == 0 )
		{
			int x;
			b.Move( count, p );
			x = - NegaMax( -p );
			if ( x > max )
			{
				max = x;
			}
			b.UnMove( count );
		}
	}

	return max;
}

I'm fairly certain that the functions called here work as intended ( I've tested them to be sure ). The parameter passed in is an integer to indicate the player whose current turn it is. 1 is for the player, -1 is for the computer ( or 2nd person if in multiplayer mode ). b.CheckWin returns an integer of the player that won the game, or 0 if their is no winner. b.IsFull returns a boolean true if all of the spaces on the board are filled, false if there are any empty spaces. b.CheckBox checks the box passed in the parameter on the board and returns the value held in that box. Boxes are stores as an integer array 9 units long ( 0-8 ). Boxes can hold either -1 or 1 depending on the player that went in that spot, or 0 if the spot is empty. b.Move places the integer of the player ( 1 or -1 ) as the value of the box of the first parameter. b.UnMove resets the box to 0. If I'm missing something simple and easy, or did everything all wrong, or you need more information, please just let me know and I'll do my best to show what I've done and fix the problem. Thanks a bunch for your help!

Your function should return a number that is positive if the player to move is winning and negative if he is losing. So you shouldn't return 1 when CheckWin gives you 1, because it means that the other player just won. Return -1 always if CheckWin gives you a non-zero value.

Alrighty, so I've made that small change, but it does bring up another question that I have not had much luck in finding an answer to. How to call the function itself. I've tried several different options, and I'm not entirely sure what the correct way to do this would be.

As I understand it, the function returns a score for a given movement. So then should I make each of the first movements outside of the function and call it for each one, then make the move of the one with the highest score? Or is this something that should be programmed completely into the function itself. How is calling this function for the first time generally done in programs?

You generally write another function that looks pretty similar to NegaMax, but works only on the root. Although that function is similar to NegaMax, you are better off keeping them separate to make the code cleaner when you want to do more special things at the root (iterative deepening, time control, printing out information to the user...). Well, tic-tac-toe is so trivial that it doesn't really matter; my advice is more for something like chess or checkers.

I appreciate the help so far <3

I'm still unable to get the algorithm working correctly with my program though. Right now it's looking like this.

int Driver::NegaMax( int p, int depth ){	if ( b.CheckWin() != 0 )	{		return -1;	}	else if ( b.CheckWin() == 0 )	{		return 0;	}	int max = -10000;	for ( int count = 0; count <= 8; count++ )	{		if ( b.CheckBox( count ) == 0 )		{			int x;			b.Move( count, p );			x = - NegaMax( -p, ( depth + 1 ) );			if ( x > max )			{				max = x;				if ( depth == 1 )					best = count;			}			b.UnMove( count );		}	}	return max;}

That was my last attempt at trying to make it store the best move without calling it in a similar function, so when I'm calling it right now it just looks like this:

NegaMax( player, 1 );b.Move( best, player );player = -player;

Any idea what I'm doing wrong now? : (

I figured it out and got the program working. Thanks for the help, it got me on the right track!