Feike Boomstra 's Horizon Draughts Program

[MichelG]

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]

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]

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?

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.

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

[MichelG]

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

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]

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]

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

Bert

[TAILLE]

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

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 ?


or


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 ?

[MichelG]

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]

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]

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]

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

[Rein Halbersma]

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]

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

[BertTuyt]

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]

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.