Feike Boomstra 's Horizon Draughts Program

Discussion about development of draughts in the time of computer and Internet.
Post Reply
MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by MichelG » Wed Jan 19, 2011 23:11

BertTuyt wrote:Michel, do you include only man ( so white and black) or also positions with kings ?

Bert
I didn't include kings in the table, but it might be an idea for future developments.

Unlike jj's table, dragon's isn't limited to 1 white piece in the 5 row area. There can be any number of white and black man.

One problem i see in my current table, is when white can break through, but when it does so, it has to move a man in such a way that black gets a break-through as well. I don't know have to solve that yet.

Michel

Ed Gilbert
Posts: 802
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by Ed Gilbert » Thu Jan 20, 2011 00:33

Several years ago I tried breakthrough tables. They included positions for any configuration of white men on squares 6 through 20, and black men on squares 1 through 20. The tables did not include kings, and I felt they should not be used if there were any black kings at all, or if there were any white kings on squares 1 through 20. IIRC it took about a week to generate the tables, as I did a search for each position that could extend 10 or more plies until quiet. The searches included null moves for either side to account for men that were outside the breakthrough rows. The information stored for each position included the number of breakthroughts (0 - 2), the number of plies for the first breakthrough in plies/2 (1 through 5), and any change in the material balance (-3 to +3). This info took 3*5*7 = 105 of the 256 possible byte values. The remaining byte values were used to compress the table. I don't remember the exact size of the data now but it was a few hundred mbytes. There was a table for black to move and one for white to move. To detect black runaways I reversed the black and white bitboards.

In use the table seemed to work well for identifying breakthroughs, but it was a significant overhead on the search. This varied with position but at its worst it was something like a 35% slowdown. I was never able to get the breakthrough tables to test as well as my hand-coded heuristics in engine matches, and eventually gave up on them.
I only store positions with black (the defender) to move.
Jan-Jaap, does this mean that you always extend your search until you get to a quiet position with black to move?
Is this what Truus and Flits do, and am I correct that Stef Keetman's thesis was about this? Is this text still available somewhere?
This was described in Keetman's thesis, so I assume truus does this. No idea about flits. I tried something like this in 8x8 checkers but found it was not helpful. In Keetman's thesis he describes how he tested it by playing something like 20 or 25 games, not nearly enough to be statistically significant. I will email it to you.

-- Ed

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Feike Boomstra 's Horizon Draughts Program

Post by jj » Thu Jan 20, 2011 11:40

MichelG wrote: Unlike jj's table, dragon's isn't limited to 1 white piece in the 5 row area. There can be any number of white and black man.
That's impressive, Michel! How did you handle the combinatorial explosion of positions, and the index function?
Ed Gilbert wrote:
I only store positions with black (the defender) to move.
Jan-Jaap, does this mean that you always extend your search until you get to a quiet position with black to move?
Not really. If white is to move (in a quiet position), the evaluation function 'generates' the moves a potential runaway can make and checks the table after each move. If the man can be captured after such a move, the table will handle this (black to move). This is not 100% fail safe but it seems to handle the majority of cases pretty well. For black runaways, the position is reversed. Generating the table uses only null moves for black.
Ed Gilbert wrote:
Is this what Truus and Flits do, and am I correct that Stef Keetman's thesis was about this? Is this text still available somewhere?
This was described in Keetman's thesis, so I assume truus does this. No idea about flits. I tried something like this in 8x8 checkers but found it was not helpful. In Keetman's thesis he describes how he tested it by playing something like 20 or 25 games, not nearly enough to be statistically significant. I will email it to you.
Thanks. I think I recall reading somewhere that Flits has a similar mechanism.

Jan-Jaap
www.maximusdraughts.org

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by MichelG » Thu Jan 20, 2011 12:47

jj wrote:
MichelG wrote: Unlike jj's table, dragon's isn't limited to 1 white piece in the 5 row area. There can be any number of white and black man.
That's impressive, Michel! How did you handle the combinatorial explosion of positions, and the index function?
Jan-Jaap
That's a trade secred :-). But the idea is to not store useless positions. Look for example at
Image
White can break through, but this position is extremely unlikely to be reached in the search tree. The same is true for over 99% percent of all possible configuration of men on the last 5 rows.

Michel

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Thu Jan 20, 2011 21:51

Michel,

i try to understand your table.
Do you have the breakthroughs for 1 promotion row and 3 breakthrough rows, or (as in your specific example), 1 promotion row and 4 breakthrough rows.
If i do a quick calculation then the first implementation will have 2^5 * 3^15 ~ 4.5 10^8 positions, in the second case i calculate 2^5 * 4^20 ~ 1.1 10^11 positions.

Note: 2 because of empty or black man, 3 for white man, black man or empty.

Bert

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Thu Jan 20, 2011 21:59

Sorry , error in last formula should read 2^5 * 3^20 :)

Bert

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Feike Boomstra 's Horizon Draughts Program

Post by TAILLE » Fri Jan 21, 2011 11:40

MichelG wrote:
jj wrote:
MichelG wrote: Unlike jj's table, dragon's isn't limited to 1 white piece in the 5 row area. There can be any number of white and black man.
That's impressive, Michel! How did you handle the combinatorial explosion of positions, and the index function?
Jan-Jaap
That's a trade secred :-). But the idea is to not store useless positions. Look for example at
Image
White can break through, but this position is extremely unlikely to be reached in the search tree. The same is true for over 99% percent of all possible configuration of men on the last 5 rows.

Michel
I do not like very much these huge breakthrough db because they miss a very important point already mentionned by Michel : there is no need at all to be able to recognise a breakthrough in very unrealistic positions. What is the value of a breakthrough function which can recognize 10^10 positions but is unable to see obvious and extremely common breakthroughs like the following configurations ?

Image
or
Image

For me that sounds not very serious unless another mechanism exists for detecting the breakthrough in my above examples. In that case is'nt it sufficient to have only this other mechanism ?
Gérard

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by MichelG » Fri Jan 21, 2011 19:48

BertTuyt wrote:Michel,

i try to understand your table.
Do you have the breakthroughs for 1 promotion row and 3 breakthrough rows, or (as in your specific example), 1 promotion row and 4 breakthrough rows.
If i do a quick calculation then the first implementation will have 2^5 * 3^15 ~ 4.5 10^8 positions, in the second case i calculate 2^5 * 4^20 ~ 1.1 10^11 positions.

Note: 2 because of empty or black man, 3 for white man, black man or empty.

Bert
That's 1.1 10^11. But as said dragon only encodes a small portion of it. I did the measurement again, and it covers 88% of positions encountered in the search tree.

I did some checked on the source code, and i found i missed that white can do null moves as well, so i have some more work to do :-)

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Sat Jan 22, 2011 11:14

Michel, regarding your:
That's a trade secret :-). But the idea is to not store useless positions. Look for example at
I like trade secrets (especially to crack :) them ).
My educated guess would be that you use some kind of hashing mechanism with a procedure to deal with collisions.
But again just guessing .....

Bert

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Sat Jan 22, 2011 13:30

I have now implemented the evaluation changes related to errors in symmetry based on the work of Ed.
I have not yet changed the function dealing with the Q-search (although we have discussed in this forum that the function implementation is most likely wrong).
To test the stability of the modified Horizon, I have started a new Engine match against damage.
Not that I expect that the changes will be big (as was also experienced by Ed), but to avoid surprises.

Things on my to do list in the next weeks/months.

* Further discussion/explanation of the Horizon architecture.
* Q-Search modification.
* Interior node detection for Endgame positions.
* Re-activate parallel search (YBWC).

In the next phase I will prepare Horizon for GUIDE , so it is able to use the Dragon and Damage GUI.
Most likely I will use the same framework as used for Damage , will inform you in detail about this is the future.

Longer term vision (and hope i get some feedback on this).
As all know, i don't intend to make money with this hobby, it is intellectual curiosity and I really appreciate the long term friendship within our community.
I assume most of you feel the same.
Dam 2.x , Dragon and Damage (lite version) are freely available on the net, and I know that the costs Ed charge is really fair and mostly covering costs.

I think to promote Draughts more in terms of people playing this game (and indirect motivating people to develop abstract thinking) and programmers to provide a lower threshold to start, Horizon could play a role here.
I'm sure that with your suggestions we can improve Horizon to a level exceeding Truus and Flits.
Also if we communicate this in the right way, it will stop people from buying expensive programs they dont really need, as we provide a better alternative.

To be honest the price people have to pay for these programs is maybe not real value for money.
So if we could develop a free alternative, with same functionality or even more features, I'm sure this would serve a purpose.
Horizon as an Engine, and a GUI (for example) based on the work of Michel.
Also via web, we could have access to many games (and even we could incorporate such a function in the package).

We could even collaborate with the KNDB to put a (really low cost) version on DVD (so people also have sufficient Endgame DB's for analysis).
Next to that (and in contradiction with Truus/Flits), we could provide updates and bug fixes via the Internet.

And last but not least we have a forum for people who have questions, suggestions or whatever.
I also think this would link perfectly with the 100 year anniversary of the KNDB this year !!

I'm not sure who is all reading this blog, but if all agree (and as the Horizon intellectual rights are from Feike, I think we also need permission from Roel Boomstra), we can move forward.
So I'm interested in your thoughts, and if someone form the KDB is interested , you can always react via this forum.

Bert

Ed Gilbert
Posts: 802
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by Ed Gilbert » Sat Jan 22, 2011 15:14

BertTuyt wrote:Michel, regarding your:
That's a trade secret :-). But the idea is to not store useless positions. Look for example at
I like trade secrets (especially to crack :) them ).
My educated guess would be that you use some kind of hashing mechanism with a procedure to deal with collisions.
But again just guessing .....
I don't think a hashtable works for this application because the data stored for each position is only a single bit and a hashtable needs some kind of value to confirm the position. You need something that is an efficient at a sparse representation of booleans. As Michel said, 99% of positions can be ignored. You can throw out all positions that have captures. That probably eliminates 75% of them. You can ignore positions where black has 5 men on his back row. You can probably ignore positions that have more than some small number of white men in the breakthrough rows (maybe 5 or 6 is sufficient) as the probability for these to occur is very small.

A trie might work http://en.wikipedia.org/wiki/Trie, using a scheme similar to the way Gerard represents his endgame dbs.

-- Ed
Last edited by Ed Gilbert on Sat Jan 22, 2011 16:03, edited 1 time in total.

Rein Halbersma
Posts: 1691
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by Rein Halbersma » Sat Jan 22, 2011 15:53

BertTuyt wrote: I'm not sure who is all reading this blog, but if all agree (and as the Horizon intellectual rights are from Feike, I think we also need permission from Roel Boomstra), we can move forward.
So I'm interested in your thoughts, and if someone form the KDB is interested , you can always react via this forum.

Bert
The Horizon license makes it perfectly OK for anyone to sell it on a DVD as long as the GPL parts of the code (mainly the parallel search parts, which are copied from Stockfish) are distributed along with it.

Rein

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Thu Jan 27, 2011 19:29

With the modified evaluation function (+ voorpost), with corrected symmetry bugs (as detected and corrected by Ed), I did another Horizon Damage 158 games test.
The end result: 33+ 3- 122=, in comparison with the previous match (with the bugged evaluation) not really better (in reality somewhat worse, 25+ 5- 128=).

But I think this is a statistical fluctuation (at least I hope) also observed by others.
If I remember well also Ed did not reveal a huge (or any) difference with the modified eval.

So I will now seek for other Horizon improvement opportunities, and when implemented, will run another match.
Attached, the pdn file containing all games, for those who are interested.

Bert
Attachments
DXPMatch Horizon Damage Jan 2011.pdn
(171.59 KiB) Downloaded 160 times

BertTuyt
Posts: 1470
Joined: Wed Sep 01, 2004 19:42

Re: Feike Boomstra 's Horizon Draughts Program

Post by BertTuyt » Thu Jan 27, 2011 22:23

Just a question for the frequent readers here, interested in a future windows copy of Horizon.
So far the version used is 64bit and optimized for bit handling instructions (like pop count).
Is this a problem for you, based on the OS and processor you use??

Bert

Wieger Wesselink
Posts: 1127
Joined: Sat Jun 28, 2003 13:22
Location: Eindhoven, The Netherlands
Contact:

Re: Feike Boomstra 's Horizon Draughts Program

Post by Wieger Wesselink » Fri Jan 28, 2011 08:24

BertTuyt wrote:Just a question for the frequent readers here, interested in a future windows copy of Horizon.
So far the version used is 64bit and optimized for bit handling instructions (like pop count).
Is this a problem for you, based on the OS and processor you use??

Bert
What do you mean by a 'Windows copy' of Horizon? I think the goal should be to make the code portable, which means that platform specific code is put behind a common interface. Personally I'm not in favor of cluttering code with assembly instructions, since this will most likely make the code less portable.

Post Reply