Jump to content

  • Log In with Google      Sign In   
  • Create Account

Connect 4 opening book


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 lazyguy123   Members   -  Reputation: 130

Like
0Likes
Like

Posted 20 June 2014 - 03:04 AM

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.

 

 



Sponsor:

#2 Mats1   Members   -  Reputation: 312

Like
1Likes
Like

Posted 20 June 2014 - 07:21 AM

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, 20 June 2014 - 07:22 AM.


#3 Álvaro   Crossbones+   -  Reputation: 13897

Like
1Likes
Like

Posted 20 June 2014 - 09:13 AM

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, 20 June 2014 - 09:29 AM.


#4 lazyguy123   Members   -  Reputation: 130

Like
0Likes
Like

Posted 20 June 2014 - 11:39 AM

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.



#5 Álvaro   Crossbones+   -  Reputation: 13897

Like
0Likes
Like

Posted 20 June 2014 - 09:11 PM

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.

#6 lazyguy123   Members   -  Reputation: 130

Like
0Likes
Like

Posted 20 June 2014 - 09:29 PM

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:

 

 

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, 20 June 2014 - 09:42 PM.


#7 Álvaro   Crossbones+   -  Reputation: 13897

Like
0Likes
Like

Posted 20 June 2014 - 10:15 PM

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.

#8 Álvaro   Crossbones+   -  Reputation: 13897

Like
0Likes
Like

Posted 20 June 2014 - 10:23 PM

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.

#9 lazyguy123   Members   -  Reputation: 130

Like
0Likes
Like

Posted 21 June 2014 - 12:12 AM

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, 21 June 2014 - 12:46 PM.


#10 Álvaro   Crossbones+   -  Reputation: 13897

Like
0Likes
Like

Posted 21 June 2014 - 03:35 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS