Game tree

[Reconman]

Hi everyone! I've been using GE for quite some time now but this is my first ever post. Recently I created a simple tic-tac-toe program to introduce me into board game representation etc. It worked rather well; being able to tie or beat me almost always, however there was a small glitch that annoyed me to no end so I started again. This time I want to use a different technique that uses a game tree to determine what the best move is. Minimax.

Here is an example of what I am hoping to figure out. :p


The current program knows how to search a grid (board[9]) for available moves and win moves (for X's a win is +10 and O's is -10) and assign a -1 (computers O) to open spaces. I however have no idea how to compare the outcomes. If anyone has some experience with this that would be great. Help is always awesome.

[skydereign]

The current program knows how to search a grid (board[9]) for available moves and win moves (for X's a win is +10 and O's is -10) and assign a -1 (computers O) to open spaces. I however have no idea how to compare the outcomes. If anyone has some experience with this that would be great. Help is always awesome.

So you can detect wins but don't know how to compare them? How much do you know about recursion? The minmax algorithm is pretty straight forward if you are comfortable with recursion. The comparing of values happens as the recursion unwinds (triggered by it finding end games). Also if you haven't already there are tons of good explanations on how to do minmax with tic-tac-toe, for example http://www.neverstopbuilding.com/minimax.

[Reconman]

Sadly I don't know anything about recursions. :/

[skydereign]

Recursion is one of the harder topics to grasp for a lot of intro programmers. The idea is you have a function that calls itself. This can get problematic because you can easily create an infinite recursion where the program gets stuck. To prevent this you need a condition in the function to prevent it from calling itself infinitely. Here's a simple recursive function.

Code: Select all

int
factorial (int number)
{
    if(number<=1) // this is the condition that prevents the recursion from happening forever
    {
        return 1; // when this is returned, the recursion stops, and it unfolds
    }
    else
    {
        return number*factorial(number-1); // in all other cases, recurse on this function
    }
}

// to call this function you just do this
int value = factorial(3);

The function calculates a factorial. Here's how it works.
factorial(3)
returns the value 3*factorial(2)

factorial(2)
returns the value 2*factorial(1)

factorial(1)
returns 1 (notice recursion ends)

All of that expanded out looks like
3*2*1
Which equals 6.


That's a very cursory explanation of recursion, which is something you'll need to understand before implementing minimax for your game. If you need any more explanation feel free to ask.

[Reconman]

Thank you for the help!