Archived

This topic is now archived and is closed to further replies.

Alpha Beta, the next step??

This topic is 5501 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
quote:
Original post by DarkHamster
right, but with alpha-beta dont you sometimes cut off parts of the tree which are potentially better?


No, alpha-beta is guarenteed to return the exact same score that min-max would have returned. Alpha-beta only prunes a branch after it proves that the branch cannot produce anything better than what you already know you can get.

For example, you search the first move, and the search tells you that you can get 3 in a row if you play this first move. That''s pretty good for you. Then you search the second move, and during that search, alpha-beta realizes that your opponent can get 4 in a row if you play this second move. So even though it hasn''t searched that entire branch for the second move yet, it stops searching that entire branch and bails out, because no matter what else the search finds in that branch, the result is still going to be a win for your opponent.

So at this point, there is zero possibility that you are going to get anything better than a loss (4 in a row for your opponent), so you aren''t going to prune away anything meaningful. That''s why it''s safe to prune away branches wihtout searching them. If you continued to search the rest of that branch after you found out that your opponent could win, the search would basically be saying:

"Can I do better than a loss? No."
"Can I do better than a loss? No."
"Can I do better than a loss? No."
"Can I do better than a loss? No."
"Can I do better than a loss? No."
"Can I do better than a loss? No."
...

Over, and over, and over, until it searched the rest of that branch. Whenever you find out that the move you are searching is a loss, you know it can''t get any worse, so you can stop wasting time asking a question you already know the answer to. It works the same way with regular scores too.

For example, you search the entire first legal move and get a score of +2. Now if you play this first move, you know for sure that you can get a score of +2. So now you search the second move. You start searching, you try the second move, and you see that your opponent can play a move that will force a score of +1 (and the decision is up to your opponent now, because it''s his turn, so it''s out of your control now). So you''ve only looked at two moves here, and you know two things for sure:

1. If I play the first move I can get a score of +2
2. If I play the second move, my score is going to be AT MOST a +1 (it could get worse, you''ve only looked at two moves so far)

So, at this point, you can decide that the second move is trash and throw it away without even bothering to search the rest of it.

Share this post


Link to post
Share on other sites
There''s a huge paper by Victor Allis about solving Connect 4, looking very deep into the subtelties of the game. I suggest you read that and improve your evaluation function as much as you can, because you''ll get _a lot_ more power from a good evaluation function than from 1 or 2 extra ply. Not to mention that a solid evaluation function allows deeper searches by itself.

Then, definitely go for iterative deepening, even without the best move optimisation or transposition table. As table columns fill up, or players are forced to avoid or make certain moves, the branch factor drops a lot, so you''ll be able to search deeper. If only one empty column remains (very frequent occurance in C4), you can do a 6 ply search with 6 moves. Fixed depth searches are plain bad.

Share this post


Link to post
Share on other sites
I think this hasn''t been mentioned: move ordering is critical to the performance of alpha-beta.

For Connect4, I developed a variation on chess'' history heuristic. If you are using a hash table for transpositions (as you should), use the move from the hash table as your first try and sort the rest based on the history heuristic that I describe below.

Version 1:
Keep a table: unsigned hh[2][42];
The first index is side and the second is the square. After each alpha-beta loop, add 2^depth to the entry in the table that corresponds to the best move (the one with the best score, or the one that triggered a beta-cut). Before the alpha-beta loop, sort your moves based on the score they get in the table.

Version 2:
Keep two tables: unsigned hh[2][42], hh2[2][42][42];
hh is the same as in version 1. hh2 uses an additional index, which is the previous move (the opponent''s move), and is updated with the same formula (adding 2^depth to the best move). When sorting, combine the results from the two tables. I used hh[side][square]+42*hh2[side][square][previous_square].


But the most important part in a Connect4 game is evaluation. You should learn about the relative importance of threats on even and odd rows. I spend three months working on that with two other math students. I found similar results on the web recently:
http://www.pomakis.com/~pomakis/c4/expert_play.html


Post again if you need more help. Good luck!

Share this post


Link to post
Share on other sites
alvaro, how does a simple alpha-beta search (no transposition table, no opening book) with a simple heuristic function (threat count) fare against the average human C4 player? I am unwilling to try to improve it anymore, unless I really have to.

Share this post


Link to post
Share on other sites
Ok, i''ve really gotten some boots from some simple suggestions on the forum, but I still don''t get the whole hash table thing (at all). Where can i find some more explenation on that?? I''ve tried searching, but nothing special shows up.

--Ninj4D4n

Share this post


Link to post
Share on other sites