Hi, As my first attempt at gamedev I implemented an 8x8 connect 4 game (http://ninjamonkeys.co.za/fourinrow) with an AI that uses a minimax algo with alphabeta pruning. The AI isn't too bad, but sometimes it plays a daft move that gives you a win straight away, and when I look at it's choice all the successors lead to losses (score of the node is -100). Should I trust my algorithm to see that all possible moves 4 steps ahead are going to lose, or is there a bug in it? It can only search to depth 4 in any reasonable amount of time, so maybe this is a limitation of the depth? What should I do to improve it? Apart from rewriting it in c++ and implementing Victor Allis' expert strategies that is. I'm looking for the easy fix ;) The source code is at http://ninjamonkeys.co.za/fourinrow/src.zip Thanks for your help!

Allocating all those debug statements is likely killing your performance. Also, if you're going to limit your depth you really need a heuristic.

Doesn't the JVM optimize out the Util.debug calls when there is an if(false) in it?

Do I just need a heuristic in the utility function? Any pointers for a decent heuristic?

Quote: Original post by jerichau
Doesn't the JVM optimize out the Util.debug calls when there is an if(false) in it?

Not necessarily. And even if it did, it wouldn't necessarily optimize out the string building.

Quote: Do I just need a heuristic in the utility function? Any pointers for a decent heuristic?

The best heuristic is a stupid one. That is, don't go overboard trying to catch special cases in your heuristic function. Instead, do something simple (like counting consecutive chains of 3 pieces, or rows with your piece on top) and let minimax worry about the intelligence part. The important thing is that your heuristic be very very fast.

Do you really need to be limiting your depth to 4 steps? I haven't done the math, but I can't believe that it gets out of hand THAT quickly.

Unfortunately it does. Anything more than 10 seconds is unacceptable.

I'm going to try to keep the search tree in memory and expand it as needed, because it's repeating the search from scratch each time right now.

Quote: Original post by jerichau
Unfortunately it does. Anything more than 10 seconds is unacceptable.

Ten seconds? 7^4 is 2401. 7^5 is 16807. That's 0.6 milliseconds per terminal state. If your algorithm is really taking that long, you're doing something really REALLY wrong.

EDIT: You're also allocating iterators per state expansion, which is a no-no. Don't allocate things. Also, if max_value returns both the maximum value and the choice which generated that, your code will be much simpler.

Quote: Original post by Sneftel

Quote: Do I just need a heuristic in the utility function? Any pointers for a decent heuristic?

The best heuristic is a stupid one. That is, don't go overboard trying to catch special cases in your heuristic function. Instead, do something simple (like counting consecutive chains of 3 pieces, or rows with your piece on top) and let minimax worry about the intelligence part. The important thing is that your heuristic be very very fast.

Actually, that's not true. Well, it's true for some games, but not for connect 4. Let's define a "threat" as a group of 4 squares in a line with 3 of them being disks of the same color and the other one being empty. A threat will be considered "even" if its empty square is on the top row, or an even number of rows below, and odd otherwise. A good evaluation function will value odd threats much more than even threats. You also have to be careful about not considering something a threat if its empty square is immediately above the empty square in an enemy threat. There's a few more things to consider that can be learned by analyzing the endgame mathematically. An evaluation function that knows about these things will result in a much stronger player than one that doesn't, even if it takes more time.

About only reaching depth 4, you should really be able to get a lot more. Using alpha-beta with good ordering heuristics will nearly double the depth you can reach in a given amount of time. Using transposition tables will also give you a nice boost. Programming in C++ I bet you can reach depth 14 or so in 10 seconds. Programming in Java and being careful about not doing expensive operations, you may drop to depth 12. Anything below that probably means you are doing something wrong.

Some really simple optimizations that could make a big improvement:

Don't clone the board. Just add a way to undo moves. The minimax function can perform a move, call itself recursively, and then undo the move. No more pointless copying of the entire board. You can also get rid of the Node class.

Don't search the entire board for a victory. You only need to check the winning conditions that involve the piece that was just placed.

Quote: Original post by Vorpy
Don't search the entire board for a victory. You only need to check the winning conditions that involve the piece that was just placed.

Are you talking about the win condition on the actual play or the testing for win conditions for each node of planning? Obviously they are both using the same algorithm and need to be streamlined. If you do this one thing, you can cut your search time in half, probably.