Sign in to follow this  
lazyguy123

Connect 4 opening book

Recommended Posts

lazyguy123    130

Hey everybody,

 

I'm making a connect 4 game and I want to make it stronger by using an opening book. I've looked all over, and the only one I can find is by John Tromp.

 

http://homepages.cwi.nl/~tromp/c4/c4.html

 

I thought the book would be a list of moves that I could read into a tree. However, it consists of positions at 8-ply and whether they eventually lead to a win, loss, or draw for the first player. My question is how do I incorporate this into my program?

 

Any help is appreciated. Thanks.

 

 

Share this post


Link to post
Share on other sites
Mats1    1047

You should be able to make a Connect Four AI that is sufficiently effective without any use of opening books. Unlike say, chess, there are very few openings and no considerations to be made for openings that might lead to bad positions in a dozen moves or more, other than your program should definitely play a central stone on its first turn (if it goes first). That is assuming you're doing a standard 7 x 6 board.

Edited by Mats1

Share this post


Link to post
Share on other sites
alvaro    21246

You should be able to make a Connect Four AI that is sufficiently effective without any use of opening books. Unlike say, chess, there are very few openings and no considerations to be made for openings that might lead to bad positions in a dozen moves or more, other than your program should definitely play a central stone on its first turn (if it goes first). That is assuming you're doing a standard 7 x 6 board.


I couldn't disagree with you more. The first few moves in connect 4 can be very counterintuitive and an opening book is essential.

EDIT: Let's number the columns 1 through 7. Take 2-ply position after the first player plays 4 and the second player plays 1. What should player 4 play next? There is only one winning move!

The way you use John's database is quite simple: Write a minimax searcher that treats 8-ply positions as leaves and uses the values from the database at those nodes. Edited by Álvaro

Share this post


Link to post
Share on other sites
lazyguy123    130

Thanks for your reply Alvaro.

 

So are you saying that for the first 8 moves, if n moves have been played, then i do minimax with a depth of (8-n) and use the database values instead of my evaluation function? And then after 8 moves have been played, then I switch back to my evaluation function and increase depth back to normal?

 

Also I noticed that the database contains 67557 positions at depth 8, while my perft function returns around 180,000 positions at depth 8. How should I evaluate positions that are not in the database? Should I give them a value so that they won't be considered over the other nodes?

 

Thanks.

Share this post


Link to post
Share on other sites
alvaro    21246
John is a personal friend of mine, and knowing how careful he is with this kind of thing, I can assure you that there are only 67,557 8-ply positions. Did you take transpositions into account in your perft count?

If you still think John is wrong, please produce an 8-ply position that is not in the database.

Share this post


Link to post
Share on other sites
lazyguy123    130

I'm not saying that John is wrong. On his website he says that he only includes positions where neither player has won yet, and in which the next move isn't forced. I believe this is why there are less positions.

 

I did take into account transposition and made sure not to count the same position twice. Also my numbers agree with this numberphile video:

 

http://www.youtube.com/watch?v=yDWPi1pZ0Po

 

If I run into one of these nodes not in the database, should I set its value to + infinity so that the minimizer at depth 7 will cut them off and not look at them?

Edited by lazyguy123

Share this post


Link to post
Share on other sites
alvaro    21246
Oh, I see. I thought the database contained all 8-ply positions except those that are terminal (player 2 just won) and those where player 1 has an immediate winning move. But that doesn't quite match the description.

I'll ask John about it. I'm probably missing something.

Share this post


Link to post
Share on other sites
alvaro    21246
John was still up and answered my question: The applet uses a more complete database, which also includes positions where the next move is forced.

If I were you, I would probably use Fhourstones to compute the value of the missing positions.

Share this post


Link to post
Share on other sites
lazyguy123    130

Thanks for your reply. I ran the Fhourstones benchmark with command prompt and I got a printout similar to what is listed on this site:

 

http://homepages.cwi.nl/~tromp/c4/fhour.html

 

How can I use the benchmark to generate a database with values for all of the 8-ply positions? Is there a command that I can use to output a text file of all 8-ply positions? I tried looking at the java source code but I don't understand it.

Edited by lazyguy123

Share this post


Link to post
Share on other sites
alvaro    21246
If you look at the `inputs' file, you'll see that you can ask about the theoretical value of any position, by entering the moves. For instance, you can enter 414 and the program will compute if that's a winning position or a losing position. You can first create a file with all the positions you are interested in, then give them to SearchGame and parse its output.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this