EndGame Databases

[ildjarn]

Gerard,

My only practical database usage is to see if human players played an endgame missed a draw or not. And since humans don't play perfectly, the last moves in the position you have given could very well have been 4-13 15-4, thus resulting in a position where one only has 24 moves left to win. And perhaps 1. .. 35-40? would be a major blunder in this case, because black has a defense which would take 48 king moves in a row (yes, I know this isn't the case in this position, but there are probably enough position in which the above reasoning is valid). In the given position that wouldn't be enough for a draw, in the position including the history it would. And as long as one has a database that obeys the 25-move rule but doesn't include all possible situations (which basically would mean that every position should be in the database 50 (51?) times, in case of a 25-move rule!)

In computer tourneys, the 25 move rule should not be applied IMO. This rule only exists to avoid playing around endlessly, and winning by tirening the opponent, a reason that only exists for humans.

At the moment I am against extending the 25 move rule in human games by the way. It implies that one expects people to play these kind of endgames perfectly, which is, at the moment, a ridiculous assumption. How many human players would know that 13-36 is the only winning move? Or that only 2. 33-28 would win after 1. .. 35-40, the rest would be a draw? Perhaps there are a few, but one could count them on one hand, I think.

[TAILLE]

Gerard,

My only practical database usage is to see if human players played an endgame missed a draw or not. And since humans don't play perfectly, the last moves in the position you have given could very well have been 4-13 15-4, thus resulting in a position where one only has 24 moves left to win. And perhaps 1. .. 35-40? would be a major blunder in this case, because black has a defense which would take 48 king moves in a row (yes, I know this isn't the case in this position, but there are probably enough position in which the above reasoning is valid). In the given position that wouldn't be enough for a draw, in the position including the history it would. And as long as one has a database that obeys the 25-move rule but doesn't include all possible situations (which basically would mean that every position should be in the database 50 (51?) times, in case of a 25-move rule!)

In computer tourneys, the 25 move rule should not be applied IMO. This rule only exists to avoid playing around endlessly, and winning by tirening the opponent, a reason that only exists for humans.

At the moment I am against extending the 25 move rule in human games by the way. It implies that one expects people to play these kind of endgames perfectly, which is, at the moment, a ridiculous assumption. How many human players would know that 13-36 is the only winning move? Or that only 2. 33-28 would win after 1. .. 35-40, the rest would be a draw? Perhaps there are a few, but one could count them on one hand, I think.

Iljard,

I do not understand your point.

First of all the last moves could not have been 4-13 15-4 due to the presence of the white man on 33 but this is not important. Let’s suppose that it would have been possible to reach the position with 4-13 15-4 moves. These moves have no influence on the course of the game because the move 1…35-40 2.33-28 40-45 are conversion moves so that the counter of consecutive non conversion moves is reinitialized.
The point is that after 2…40-45 the position is a “WLD db” draw because of 25 move rule. As a consequence, by propagation in the db, the initial position is also a draw.
Of course after 2…35-40 2.26-17 the position reached is a “WLD db” win but, with a correct main engine, it is not a contradiction.

I tried to show how the main engine can work without contradiction with a “real” WLD db and a DTC db, taking into account the history of previous consecutive non conversion moves.
May be my explanation was not very clear and I will be happy to give you some more details if necessary.

Due to my bad English I do not know the meaning of IMO acronym.
What do you mean by “In computer tourneys, the 25 move rule should not be applied IMO” ?
Does that imply that computer and human may play with different rules ?

Gérard

[ildjarn]

First of all the last moves could not have been 4-13 15-4 due to the presence of the white man on 33

Your last position had a black man on 33.

but this is not important. Let’s suppose that it would have been possible to reach the position with 4-13 15-4 moves. These moves have no influence on the course of the game because the move 1…35-40 2.33-28 40-45 are conversion moves so that the counter of consecutive non conversion moves is reinitialized.

Okay, theoretical position X (I don't have any examples at hand, but they surely exist) :
- With perfect play, 48 non-conversion moves are needed to win. I.e. your 'DTC' database would indicate 'win'.
- This position occurs in a game. Because of time trouble, both players make a switchback move with their king, resulting in the same position, BUT: with the 'DTC' counter set to 4, instead of 0. Now your database still says 'win', but this is a wrong result!

In other words: Your database would need the best move in the case that the DTC counter is 0, the DTC counter is 1, the DTC counter is 2, etc etc. Yes, in computer games this situation is probably nonexistant, because both programs know how to play this endgame perfectly. But in human play, the above situation is possible.

As for the 25 move rule in computer tourneys: As I explained the 25 moves rule isn't a rational rule, but a human rule: without this rule, people would endlessly try to win a drawn game, resulting in games of 200 moves. The 25-move rule is to avoid excesses like that. IMO (In My Opinion) these excesses will be absent in computer tourneys, so it's only natural, I think, to disable this rule, especially in endgames which are in a database.

Compare e.g. the chess databases, where people have constructed 7-piece databases which include wins of over 300 moves, with DTC distance of over 250 moves. The FIDE adjusted the 50-move rule for humans after the first databases which proved that some endgames (I think it was 2 bishops versus a knight) would need more than 50 moves in the maximum positions, but they quickly reversed that because no one could play those endgames perfectly anyway, and the extended rule was abused to produce monstrous games.

[TAILLE]

First of all the last moves could not have been 4-13 15-4 due to the presence of the white man on 33

Your last position had a black man on 33.

but this is not important. Let’s suppose that it would have been possible to reach the position with 4-13 15-4 moves. These moves have no influence on the course of the game because the move 1…35-40 2.33-28 40-45 are conversion moves so that the counter of consecutive non conversion moves is reinitialized.

Okay, theoretical position X (I don't have any examples at hand, but they surely exist) :
- With perfect play, 48 non-conversion moves are needed to win. I.e. your 'DTC' database would indicate 'win'.
- This position occurs in a game. Because of time trouble, both players make a switchback move with their king, resulting in the same position, BUT: with the 'DTC' counter set to 4, instead of 0. Now your database still says 'win', but this is a wrong result!

In other words: Your database would need the best move in the case that the DTC counter is 0, the DTC counter is 1, the DTC counter is 2, etc etc. Yes, in computer games this situation is probably nonexistant, because both programs know how to play this endgame perfectly. But in human play, the above situation is possible.

As for the 25 move rule in computer tourneys: As I explained the 25 moves rule isn't a rational rule, but a human rule: without this rule, people would endlessly try to win a drawn game, resulting in games of 200 moves. The 25-move rule is to avoid excesses like that. IMO (In My Opinion) these excesses will be absent in computer tourneys, so it's only natural, I think, to disable this rule, especially in endgames which are in a database.

Compare e.g. the chess databases, where people have constructed 7-piece databases which include wins of over 300 moves, with DTC distance of over 250 moves. The FIDE adjusted the 50-move rule for humans after the first databases which proved that some endgames (I think it was 2 bishops versus a knight) would need more than 50 moves in the maximum positions, but they quickly reversed that because no one could play those endgames perfectly anyway, and the extended rule was abused to produce monstrous games.

Ildjard,

Let’s then suppose a game Ildjard-Damy where you reach (with white) the position X after a conversion move. In that case the result of WLD db is always correct. Let’s then suppose that it is winning position for white and let’s suppose that the DTC db tell us that a win can be obtained in for example 48 plies (or 30 plies or whatever figure you want).
Now your next move is a non conversion move but is not the best one. After a simple lookup in its WLD db let’s suppose that Damy will find that the position is a WLD db losing position for black. In that case Damy will read the DTC db and let’us suppose that Damy will find that black can resist 49 plies before the next conversion. With this information Damy knows now that the position is a draw because a non conversion move has already been played.

As you can see :
1) The WLD db is always correct if the previous move is a conversion move
2) A WLD db draw is always correct
3) A WLD db win or lost after a non conversion move must be analysed with the DTC db taking into account the number of non conversion moves already played
4) The DTC db does not give the information “win” or “lost”; it gives the information”for winning you need N plies” or “before losing you can resist N plies”

With the relevant main engine you cannot fail to win or to draw if it is possible !

Concerning the usefulness of the 25 moves rule I agree with you that it is a necessary help in order to stop a game between humans. Every body knows, from a theoretical point of view, that, by putting such a rule, you change the result of some positions and as a consequence you change the game.
For practical reasons I think you cannot avoid to have the same rule for computers :
1) Which rules would be relevant for a game between a computer and a human
2) What could be the reference db for a game between computers?

Another example: let’s take a “middle” player knowing how to win the final 5K vs 2K. Against another “middle” player he will then surely win but against a strong player he will certainly not win within the 25 moves. That’s life, the “middle” player has still to progress.
In the same way some computers are far better than other and, especially with the introduction of partial information db, the endgame db of the future strongest programs will be surely different. In addition who can be sure at 100% that there are no errors in its db?
As a consequence, for a game between two computers, we also need a rule to conclude the game, at least when the two computers do not agree on the result.

The 25 moves rule exists. Does it really harm to keep this rule as it is?

Gérard

[Ed Gilbert]

Hi Ed, Ildjarn
I don't see your point. Why a real db is impossible to build?

Not impossible, just not worth complicating the search with it IMO.

-- Ed

[Ed Gilbert]

According to many published articles (e.g. this one: http://www.hkepc.com/bbs/itnews.php?tid=789466), Intel is cutting prices on its Q6600 quad-core processor on July 22 from $530 to $266. This is a very cost effective processor for building endgame databases. With one of these the 7-piece database can be built in about 2 weeks.

-- Ed

[BertTuyt]

Ed, I also heard the news.
So most likely I will order a Quad very soon, and besides building larger databases I will focus on parallel search algorithms.
Guess this is a topic which is also quite difficult.
Im very interested in the next months to learn if other draughts programmers have succesfully utilized all cores in a multi-core processor.

By the way, is there also a straightforward approach to use all cores in database generation?

Bert

[Ed Gilbert]

Hi Bert,

>By the way, is there also a straightforward approach to use all cores in database generation?

I bought a dual core processor recently, and to use both cores for building databases I simply run two instances of the build program. Each instance runs at nearly full speed and seems not to be affected very much by the other one, except of course that I can only give each one half the RAM to use. I expect this to be the case for the quad core CPUs also, but I haven't actually tried one. In a multi-computer build I designate one computer as a master. The other machines get the next subdivision to be built from it over the LAN, and when they finish they send the new subdivision to the master so that the other satellites can get it. With a dual-core it works the same as having 2 separate machines, except that they both share the same local database of already built subdivisions.

I never tried to do a parallel search. I read a paper that Schaeffer wrote about it and was not very encouraged by the results he got. I have several other projects which will probably help the engine more than parallel search. I have not implemented 'pondering' yet, and I need to get my runaway (breakthrough) table stuff converted from 8x8, etc.

-- Ed

[FeikeBoomstra]

I will focus on parallel search algorithms.
Guess this is a topic which is also quite difficult.
Im very interested in the next months to learn if other draughts programmers have succesfully utilized all cores in a multi-core processor.
Bert

My previous computer went down, so I had to buy a new one. I bought an Intel d915 dual core with 2 Gb memory. As OS I use Linux Fedora FC6 with the intel compiler (all 64 bits). I tried to use vtune as a profiler, but until now I am not succesfull with it. The 64 bits environment gives a lot of problems.

I use OMP to get the search process parallel. The first issue I ran into was: the clock() function. In general with more than one thread, you are not sure what you measure. This is OS dependent. It took me a lot of time to discover this. In the beginning I thought that none of my efforts had any effect, until I discovered that clock() measures the cpu time in both threads together!. Use the wall_clock() function in OMP to measure the real number of evaluations.

This is how I implemented it: I copied the alpha-beta function and used at at the first level alpha-beta. The recursion starts one level deeper. In the first level I made the for loop parallel.

This all works rather straight forward. The only problem I found was that in rare cases your best move on the top level get clobbered.
You to have your hashtable reads and updates in a critical region. One critical region for the entire hash table gives to much overhead, one lock for each entry is too much for the OMP system (the initialization took forever), so I ended up with 255 locks.

The result was not overwhelming. The OMP overhead is quit large and the overall gain is limited. I can't find the numbers right now, I will redo the experiment later and publish it here.

One of the problems is still the endgame. The database routines are not re-entrant, so I could not paralyze that part.

[TAILLE]

I will focus on parallel search algorithms.
Guess this is a topic which is also quite difficult.
Im very interested in the next months to learn if other draughts programmers have succesfully utilized all cores in a multi-core processor.
Bert

My previous computer went down, so I had to buy a new one. I bought an Intel d915 dual core with 2 Gb memory. As OS I use Linux Fedora FC6 with the intel compiler (all 64 bits). I tried to use vtune as a profiler, but until now I am not succesfull with it. The 64 bits environment gives a lot of problems.

I use OMP to get the search process parallel. The first issue I ran into was: the clock() function. In general with more than one thread, you are not sure what you measure. This is OS dependent. It took me a lot of time to discover this. In the beginning I thought that none of my efforts had any effect, until I discovered that clock() measures the cpu time in both threads together!. Use the wall_clock() function in OMP to measure the real number of evaluations.

This is how I implemented it: I copied the alpha-beta function and used at at the first level alpha-beta. The recursion starts one level deeper. In the first level I made the for loop parallel.

This all works rather straight forward. The only problem I found was that in rare cases your best move on the top level get clobbered.
You to have your hashtable reads and updates in a critical region. One critical region for the entire hash table gives to much overhead, one lock for each entry is too much for the OMP system (the initialization took forever), so I ended up with 255 locks.

The result was not overwhelming. The OMP overhead is quit large and the overall gain is limited. I can't find the numbers right now, I will redo the experiment later and publish it here.

One of the problems is still the endgame. The database routines are not re-entrant, so I could not paralyze that part.

Parallel search algorithms is indeed a very interesting topic. I now have a first version of Damy using my dual core processor. Concerning the endgame databases it seems not necessary to build such algorithm because, as mentionned by Ed, it seems suffisant to simply launch two instances of the programm, on different slices.
Gérard

[Ed Gilbert]

I'm wondering how the 10x10 programmers test their changes to the evaluation function? In 8x8 my standard test was to run an engine match against Martin Fierz's program cake. After 288 games played at 5sec/move, I could usually tell if the change I made was an improvement or not. Do you run matches against other programs, against another version of your own program, or something else? I have run some matches against Dam2.2 using the DamExchange protocol. Are there other programs available like Dam that use this protocol? I tried to do this with Dragon Draughts but the Dam Exchange implementation is not complete and it was unsuitable for an engine match.

-- Ed

[TAILLE]

I'm wondering how the 10x10 programmers test their changes to the evaluation function? In 8x8 my standard test was to run an engine match against Martin Fierz's program cake. After 288 games played at 5sec/move, I could usually tell if the change I made was an improvement or not. Do you run matches against other programs, against another version of your own program, or something else? I have run some matches against Dam2.2 using the DamExchange protocol. Are there other programs available like Dam that use this protocol? I tried to do this with Dragon Draughts but the Dam Exchange implementation is not complete and it was unsuitable for an engine match.

-- Ed

Hi Ed,
As far as I am concerned I did not program the DamExchange protocol on Damy. Surely such engine match may help for improving your evaluation function if your program is less strong than your opponent.
As soon as your programm begin to win I think the test becomes less significant because your evaluation function improvment may simply be a better way to take advantage of a weakness of the opponent program.
That means that you are totally rigth to look for several programs to test your own program.
Anyway, as for human, the best place to test your program, is probably to take opportunity to participate to computer tournaments
Gérard

[steenslag]

I'm wondering how the 10x10 programmers test their changes to the evaluation function? In 8x8 my standard test was to run an engine match against Martin Fierz's program cake. After 288 games played at 5sec/move, I could usually tell if the change I made was an improvement or not. Do you run matches against other programs, against another version of your own program, or something else? I have run some matches against Dam2.2 using the DamExchange protocol. Are there other programs available like Dam that use this protocol? I tried to do this with Dragon Draughts but the Dam Exchange implementation is not complete and it was unsuitable for an engine match.

-- Ed

How did KingsRow 10x10 do against Dam2.2 ? Just curious, please ignore the question if you don't feel like answering it.

I noticed KingRow uses opening books. Does KingsRow10x10 have opening books? As far as I know, chess programming teams make extensive use of chess opening theory, and most have an opening expert. His job is to get the game into middlegame positions well-suited for the program. I'm not aware of 10x10 programs doing this.

[Ed Gilbert]

How did KingsRow 10x10 do against Dam2.2 ? Just curious, please ignore the question if you don't feel like answering it.

I noticed KingRow uses opening books. Does KingsRow10x10 have opening books? As far as I know, chess programming teams make extensive use of chess opening theory, and most have an opening expert. His job is to get the game into middlegame positions well-suited for the program. I'm not aware of 10x10 programs doing this.

I am no longer able to get useful information from matches against Dam for the reason that Gerard described.

In 8x8 I have created opening books using an algorithm of systematic searches. This has been highly successful, and usually by the time the game drops out of the opening book kingsrow can either see a database draw or it has a clear advantage. I intend to try this for 10x10 also but I have not got very far with it yet. My feeling is that opening books in 10x10 can be a little helpful, but they cannot carry very far into the game because the branching factor is too high. In 8x8 there are typically between 1 and 3 reasonable moves at each position. In 10x10 there are perhaps 5 or 6. The tree expands too rapidly.

-- Ed

[BertTuyt]

Ed, i don't use the DamExchange protocol in Damage. My program are basically 2 separate executables , the GUI and Engine. Communication between the 2 is with a TCP/IP protocol.

Similar to Chess where they have UCI-protocol (and others) I have defined/proposed the GUIDE (Graphical Universal Interface Draughts Engines) protocol how Engines and GUI communicate with each other.

Via this way it is also possible to organize Engine Matches.
I have an older version (GUI and Engine) on the webside http://members.chello.nl/h.tuyt

If you want I can sent a .doc with the current GUIDE standard defined.
Also Michel Grimminck has implemented this in his Dragon program.
I think the standard is very draft so my engine does not work most likely with his GUI,and the other way around.

On the other hand if we could define such a standard then life for many programmers would be very easy.
Choose a GUI (Damage2000 or Dragon) and focus only on Engine development.

Bert