Explain how the minimax function works for ai in a game of connect 4

[schlulol]

Hi, I've been working on a c++ game of connect 4. It uses a multidimensional array, and I have a function that is capable of checking if someone has won. However, ai is really bugging me. I've tried to do some research on this minimax thing, but I couldn't find anything helpful. If someone could explain how it would work for a game of connect 4 in layman's terms (maybe with psuedocode) or refer me to some websites that will actually help me understand, I would greatly appreciate it.

[Volatile Pulse]

If you're just looking for a dumb AI I'd suggest using the rand() function. And what I did for a slightly smarter AI for my tictactoe game was look to see if there were two blocks in a row and block the user. In your case, look for three blocks in a row and block them. And when I did the hard AI I programmed every possibility, but this isn't ideal for connect four. I'd honestly google array AI and read whatever shows up. AI is AI, regardless of language and it may give you the insight of what you want to do. Think therory before actually being able to code it. You'll understand how an AI is supposed to work before you just jump into programming it. AI scripts can be very long, and as far as I know, there is no easy way of doing it.

[Volatile Pulse]

Sorry about the vague help, as I have never heard of the minimax function. Have you created your own function based off of this algorithm? If yes, then your issue lies within that function. If you borrowed someone else's function, it might not be properly set up for connect four or you're using it incorrectly.
Reading over the algorithm, it seems brilliantly simple in terms of AI, but may cause an issue for coding it. Sorry my previous post wasn't of much help regarding your specific question.

[Peter87]

The minimax algorithm assumes the opponent plays perfectly and tries to find the best possible move.

It is often implemented as a recursive function returning a score. It loops through all the possible moves to check what is the best move (highest score). To decide the score the minimax function is called recursively for each move. The returned value is negated because the returned value will be the best score for the opponent and a good score for the opponent is a bad score for us and vice versa. If the game is in an end state it just returns a value without looping any moves. It could be just as simple as returning 1 for a win and -1 for a loss. You could give a higher score to a win that takes less moves. This will make the AI prefer to win early and lose as late as possible.

Take a look at the pseudocode: http://en.wikipedia.org/wiki/Minimax#Pseudocode

[Volatile Pulse]

I was just reading up about it a little more, a link from stanford, that said the minimax algorithm works, but only works against an opponent equally smart, the computer always focuses on the ideal moves, well a less knowledgable player might not take the smartest move. I don't know if it was trying to imply that it's possible for the minimax algorithm to lose, or if it was implying that it predicts the best moves, and the previous move was based off of the oppponent picking the best move as well, and when they don't, the algorithm needs to reevaluate the situation.

It also so it is impossible to win against a minimax algorithm in a typical board style game where the player who goes first has no advantage. I have an AI book that goes over C++ game AI, which I never read, which I believe I might pull out tonight or tomorrow. I'm looking for some algorithms for tictactoe, battleship, and connect four.

[schlulol]

Hi, thanks for the responses. I took a look at this:

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

I was just wondering, what do node, depth, heuristic value and child mean? How exactly would this work for connect 4? I know this has something to do with looking at a visual tree diagram, but this is very confusing for me. A lot of the stuff online is more reference for people who already know the stuff, rather than to help beginners out. I know this might be an easy topic for others, but I'm in grade 11 c++ for the first time, and I have a crappy teacher lol.

[Volatile Pulse]

I'm really not sure the best way to put that into a function, but I can explain into more detail about how to code a minimax function. The idea behind the function is to find the best possible out come, and by doing so, the computer looks at every possible move available, which is why you see the recursion on line 6. The way minimax finds the best value is by assessing the fastest way to win using the shortest amount of moves without allowing the oppenent a chance to win. Minimax is based off of a give/take algorithm that basically says, what is the least risky move I can make that gives me the best return. That is where the numbers come into play, the +/- values determine what the best possible moves are given the current conditions.

Again, I have no idea how to code it, and it seems there is going to be an infinitely possible amount of choices the computer can select. I have no idea how it determines which move to actually do. Wish I could be more help, sorry.

[Peter87]

A node is a state the game can be in. In Connect 4 the game state contains information of the position and colours of all the discs and what player is next to move. From one state there are a number of moves the user can make to reach new states. These states are what they mean by child nodes.

In many games there are simply too many possibilities to always search until the end of the game. To speed things up we can limit the search to only look a fixed number of moves into the future. That is what the depth value is for. If you call minimax with depth=5 it means that it will never look more than 5 moves into the future.

If we stop before the end of the game is reached we don't know who is going to win. Instead we can have a function that takes a node/state and estimates the chances of winning. This will be the heuristic value for the node/state.

To design a good heuristic is not always simple. A win state should always give a higher value than any other state. Similar a loss should always give lower value than any other state. For the rest of the states it's a bit more complicated. It will depend very much on the kind of game. In Connect 4 you will probably have to look at how many discs the player has in a row that is not blocked and ... well I don't play much Connect Four but I leave this to you to think about. It's the funniest part in my opinion.

[schlulol]

What does the -∞ represent, and how can I put it in my program?

[Peter87]

-∞ is negative infinity. If you use double for heuristic values and infinity values are supported you can use -std::numeric_limits<double>::infinity() to get a negative infinity value. The important thing is that you use a value that is smaller than any possible heuristic value.