Hi all, I''m currently working on a connect4 AI that is ment to be played against other AI systems, so it has to be incredibly good. I currently have a working gametree that uses alpha beta pruning. The problem is, our system is limited to a timelimit of 1 min per move. With my current setup i''m able to easily search through 8 ply in about 10 seconds max, but when i bump the search up to 10 ply it takes about 80-90 seconds (9ply takes way too long, i think there''s too many good looking options with odd ply). So my question: Is there away to do better?? I would really like to be able to do 10 ply or greater searches for every move. I''ve gone through my code several times and optimized it for space and speed as best i could. So, any suggestions related to improved gametree searching would be great. (i tried the variation principle search allready, but it was slower). Thanks in advance to any help i recieve. --Ninj4D4n

If 8 ply takes 10 secs I don''t think it is strange that 10 ply takes 90 secs. You increase the search space with 49 times, and the alpha beta pruning reduces it to 9 times -- seems resonable.

I assume you have an heuristic function to value each game position. Here is probably where you should focus your optimisation work.

I do have a very fast, simple evaluator to score the board in order for the prunning/min max to work.

What would make AB go faster though, make bad nodes look worse?? or make good nodes look better?? right now i have it split even. (that is if a board is scored -560, meaning the player is winning, and you just changed all the piece colors... it would be scored +560 meaning the comp is winning)

--Ninj4D4n

It''s been a long time since I worked with min max so I don''t remember if there are any golden rules on how the evaluating funtion should be constructed. But I will tell you my spontanoius thoughts, based on what I remember, with the reservation that all I say might be wrong...

I would say that it should be constructed with these two aims:

1) It should minimize the search space
2) It should be fast

And I beleive attribute 1 is more important than 2. Minimizing the search space basically means what you mentioned: make as good distinction between good nodes and bad nodes as possible. The evaluation function is supposed to be an estimation of the result you would get if you would recurse into all possibilities all the way to the leaf nodes. The better the estimation, the smaller the search space will be.

Not sure if this helps you anything. Maybe you should experiment a bit with different evaluation functions. Since you have the alpha beta part already done, all you have to do is to replace the function.

quote: Original post by Ninj4D4n
I do have a very fast, simple evaluator to score the board in order for the prunning/min max to work.

What would make AB go faster though, make bad nodes look worse?? or make good nodes look better?? right now i have it split even. (that is if a board is scored -560, meaning the player is winning, and you just changed all the piece colors... it would be scored +560 meaning the comp is winning)

Try pruning a fixed percentage of the lowest value nodes and see if your AI still plays well enough. The idea behind this is that even though a board may offer some small advantage over the opponent at the evaluation depth, there may be many other candidate boards that offer a better advantage... and while these don't guarantee a win, you only have the limited horizon of information on which to base the decision, so the rational choice is to take consider the higher value boards over the lower value boards.

Cheers,

Timkin

[edited by - Timkin on November 20, 2002 6:09:53 PM]

I''ll assume you are using plain jane alpha-beta searching without any extensions. First of all, this is a huge area, but there is a ton of literature out there (and source), so research is your friend.

Now onto the good stuff .

A quick run-down of the features in my Othello AI (relating directly to game search):
- Negascout
- Iterative deepening w/ move reordering
- Hash tables
- Forward pruning (using multi prob-cut)

It also has fun stuff like a learning opening book and perfect endgame play, but that is mostly unrelated. A quick rundown of what each features means and how it helps follows:

1. Negascout

The heart of the game search. Negascout is an enhanced alpha-beta that will provably search less nodes. Check out this page for starting source to Negascout (scroll down a bit past the mtd(f) stuff, which btw is also really good, but I prefer Negascout).

2. Iterative deepening w/ move reordering

A key element for speeding things up. The basic idea is that alpha-beta (or negascout, mtd(f), etc.) wants to have the best move first in the game tree. Well how do we find the best node in the game tree, after all, that''s what we are searching for right? Well, how about if we search to a lower ply then use those results to reorder our move list? Tada, great performance . You worry about recalculating moves? Don''t. The vast majority of search time is spent in your last ply anyhow, but once we add hash tables this won''t matter in any case.

3. Hash tables (or Transposition tables)

Basically once we have searched a board, don''t do it again! We are bound to come by the same position in our search tree and if we''ve already done the work, why do it again? Storing hash tables across moves also gives a nice boost as we get our first n-2 plies for free (where n is our search depth).

The basic idea behind this is to keep a key that represents our board. Of course we only have finite memory so there will be collisions and since we want it to be lightning quick we''ll probably use a simple solution, like overwrite the current data . Look up Zobrist''s algorithm for calculating hash keys, it can be done very quickly while you are making the moves.

4. Forward pruning

In my case (Othello), I was able to use multi prob-cut as it has been researched well for othello. However it requires having a large game library available and a stable evaluation function (generally trained using neural nets, or solving large linear equation systems).

The general idea is that if a move sucks really bad at a low ply, then don''t bother searching it any more. You will note that is hardly an exact definition and indeed this is one part of game AI design that is very much still being researched.

Overview

Using the first 3 techniques I mentioned above will almost certainly give your program a huge boost in speed. I didn''t get into any specific low-level optimizations (although that can also make a huge difference), but that should be enough to get you started . Good luck!

Good link:

Great Game AI tutorial for chess on gamedev.net.

ummm... yeah... i think i''ll have to get back to you on that one.

First, do you have to use a Game Tree? There is a algorithmic solution to Connect Four.

I wrote a Connect-4 game last year around this time. There isn''t really anything you can do to your Alpha/Beta to speed things up. MTD(f) and NegaScout, while improvements over Alpha/Beta, will not help that much. Shaving 10 seconds off of a 60 second search still leaves you with the same depth searched in 60 seconds.

Keep your evaluator really simple. Only look for 4 in a row. Don''t bother assinging scores to 3 in a row, etc... Optimize the heck out of it. Ply 10 in 60 seconds sounds a bit slow for Connect Four. If you optimize your code you should be able to do much better.

Hash tables should be your first order of business. If you''re lucky you might get 1 more ply out of the game. Be REALLY careful when doing this. Hash tables and Alpha/Beta need some coaxing to become compatible.

Next, get your program working so that it can think while the opponent is thinking.

Then create a HUGE opening move database. The more moves in your database the better. It''s quite possible that you could win the game from the opening database alone (as Connect Four has only 42 moves). You can use the hash tables here so it will be dirt simple and take no memory.

Good luck,
Will

I have a question... from my paltry understanding of alpha-beta pruning, it seems to me that there is always the possibility of missing a really awesome move, in this case an AI might go for a spot that produces two connect threes versus one that connects 4. Am I wrong and if not how can this be avoided?

That sounds like more of an evaluation issue than a search issue. Connecting 4 in a row should be a win, and a win should be scored higher than all other possible scores, so 4 in a row *should* be found as the "best" move.