I want to create an opening book for game of connect4. My program can search entire tree after 20 plys. What I have done is made another class and it contains a function with a parameter type array. Now I have two ways to do this, 1.Make another array which compares the position on board with the position that is fed into this method if they are equal then it returns the move which it is programmed to return. 2.Make another array which contains the move order that is played. and then compare an and return the possible value. I think that method 1 is better as same position can arise out of different move orders but then it is very tedious to feed 20 starting moves of every position, i.e 7^20=7.97922663×10^16. Surely I think there is some better method which I am missing what should I do?

If you had a look-up table with the exact theoretical value (win/draw/loss) of each possible board after 8 disks have been played, you could very easily make the first few moves optimally, by performing a shallow search. This is what John Tromp did: see here. The database is available for downloading.

@Alvaro

Thanks for replying,
but I am not sure how to download the database.
Clicking on your link opens Mr.John's website but then after clicking on the database, I am not sure how to proceed.

If I click on the download data set description then it gives me a general overview of the database.
If I click on the data folder then it gives me an apache page with 3 links.
Then again if I click on the connect-4.data.Z file, some encrypted text appears.Is there an access to database to download it?


Also I had one more query,
This database is 8-ply deep. i.e just 4 moves out of 21.
In my previous post I wrote that my engine can search entire tree after 11 moves.
So the program can make wrong moves in between 5-11(It can search after 11moves, not on 11th move,so even if it is winning it wont come to know as it does not search the entire tree on 11th move,and thus can make a bad move because of horizon effect.)So any pointers on this?

Quote: Original post by alvaro
If you had a look-up table with the exact theoretical value (win/draw/loss) of each possible board after 8 disks have been played, you could very easily make the first few moves optimally, by performing a shallow search

Actually I didn't get you on this point,I dont think there are fixed values on board,what I mean to tell is a square can be a good square or bad square depending on the position of the coins that are place and not by the fixd position of the square. or have I skipped something or misread your post?
So this means I have to program almost 7^7 positions as I assume I have database of first 4 moves(so 11-4=7 ). but then programing 8,23,543 positions by hand is too tedious(or I am finding out this to be a bit tough because its the first game which I am coding at such perfection, let me know.)

Quote: Original post by mandar9589
@Alvaro

Thanks for replying,
but I am not sure how to download the database.
Clicking on your link opens Mr.John's website but then after clicking on the database, I am not sure how to proceed.

If I click on the download data set description then it gives me a general overview of the database.
If I click on the data folder then it gives me an apache page with 3 links.
Then again if I click on the connect-4.data.Z file, some encrypted text appears.Is there an access to database to download it?

The .Z format is what the Unix command `compress' creates.

Quote: Also I had one more query,
This database is 8-ply deep. i.e just 4 moves out of 21.
In my previous post I wrote that my engine can search entire tree after 11 moves.
So the program can make wrong moves in between 5-11(It can search after 11moves, not on 11th move,so even if it is winning it wont come to know as it does not search the entire tree on 11th move,and thus can make a bad move because of horizon effect.)So any pointers on this?

Well, you can try to improve your program to be able to search further. John's Java applet in that page does it, so it's definitely doable.

Quote:

Quote: Original post by alvaro
If you had a look-up table with the exact theoretical value (win/draw/loss) of each possible board after 8 disks have been played, you could very easily make the first few moves optimally, by performing a shallow search

Actually I didn't get you on this point,I dont think there are fixed values on board,what I mean to tell is a square can be a good square or bad square depending on the position of the coins that are place and not by the fixd position of the square. or have I skipped something or misread your post?
So this means I have to program almost 7^7 positions as I assume I have database of first 4 moves(so 11-4=7 ). but then programing 8,23,543 positions by hand is too tedious(or I am finding out this to be a bit tough because its the first game which I am coding at such perfection, let me know.)

That whole paragraph was very confusing. I think you understood what I said already: If you had John's database, you could easily play the first 4 moves perfectly.

@Alvaro
I think before including the database,it would be better if I program for faster search.

My game consists of:
Negamax as move deciding algorithm.To speed up the search, It uses alpha-beta pruning with beta cutoffs. It has some move ordering stuff(which I don't really know what to call,whether killer-move heuristics or history heuristics.)

Now I guess I have only one thing to add in this program, i.e transposition tables.

I am looking forward to implement a transposition table using zobrist hashing technique.

Will addition of transposition table increase the speed efficiency, I have already added history/killer heuristic move ordering.
Here is the code for move ordering(HH/KM)

where curr_vals contain the values of the moves which are searched,later on they are sorted in descending order and then this order is provided to new search.

I am currently looking at Mr.John's code,but the level of code seems too high for me and also its programed in bit boards which makes tougher to understand. More over I am not able to understand his board system as to why he did not take numbers like 6,13,20,27,34,41 in his code,he skipped it and used the succeeding number.