EndGame Databases

[BertTuyt]

Gerard, in my global figure I count 1, so not the positions , but really the number the Movegenerator is called.

Im now in the USA and cant test all, but to really compare it would be interesting to measure the time needed to do a (for example) 15 ply search (although some people do count kills sometimes as an additional ply and sometimes not).

Damage doesn't count an additional ply if only 1 possible move is possible in a position.

When im back ( saturday) i will give you the time needed for a 15 Ply search ( from the initial position), i cant remember now exactly.
This gives a good indication about speed, and search efficiency.

Bert

[TAILLE]

Gerard, in my global figure I count 1, so not the positions , but really the number the Movegenerator is called.

Im now in the USA and cant test all, but to really compare it would be interesting to measure the time needed to do a (for example) 15 ply search (although some people do count kills sometimes as an additional ply and sometimes not).

Damage doesn't count an additional ply if only 1 possible move is possible in a position.

When im back ( saturday) i will give you the time needed for a 15 Ply search ( from the initial position), i cant remember now exactly.
This gives a good indication about speed, and search efficiency.

Bert

Bert,
Now I can see that we are not talking about the same things !!
My view is that it is not that easy to find the correct measure for judging performances and, for Damy, I generally prefer to use the number of evaluated positions. The point is the following : by taking for example the initial position, the time to evaluate the 9 succesors is (for Damy) geater than the time to generate these 9 positions. More genrally that means that the number of generated positions (or as an alternative the number of call to the movegenerator) is totally dependant on the number of evaluated positions i.e. the most CPU consuming part of the program.
What is your view concerning performance measure criteria ?

Concerning the time to do a 15 ply search I cannot have such information for Damy because it do not explore the different variants with the same number of plies. A 3 men gambit is not very explored and in addition the alpha-beta procedure cut a lot of branches.

Gérard

[Ed Gilbert]

My experience is that it is meaningless to compare search statistics like nodes/sec or time to depth between different programs. A 15 ply search can mean very different things to different programs because of extensions and truncations. With nodes/sec, even if you can agree on exactly how to count the nodes, the numbers will tell you nothing about the strength of the programs. A program can have very high nodes/sec because it spends little time on important things like position evaluation and move ordering.

-- Ed

[FeikeBoomstra]

I did some experiments with move ordering. I tried to keep the best move for each position in the hash, and that gave as expected a good improvement of the number of nodes evaluated for a given search depth. So that is implemented. I didn't try to keep also the next best move in hash.

The other thing I tried was historical move ordering. Not based on the history of the current game, for in my opinion that won't help at all.

I collected (my son has turbo dambase) say 15.000 games from grandmasters that they won or played a draw (for each color). Then I made an histogram for all moves played on a certain move nr. From the histogram I made an ordered list. I used this list for the movegenerator to order the moves. This worked fine, there was a drop in the number of positions evaluated, but there was an increase of throughput time, the time/node increase was bigger than the evaluatiobs/ply decrease. So I removed all the code from BoomstraDam.

I know that Bert is using some kind of historical move ordering.


Feike.

[Jacques PERMAL]

There is a subject on FFJD FORUM here :

http://www.ffjd.fr/Web/index.php?page=f ... sujet=5730

[BertTuyt]

Jacques, i think it is an interesting discussion.
But as i don't master the French language, useless to me.
Cant't you motivate the French Draughts programmers to join this Forum.

It is a pity that the Draughts Computer Community share so little with each other.
Although Damage has won the last championship in Holland , I am more interested in sharing ideas and improving all programs, then keeping things for myself and trying to maintain this position.

May be im more reluctant to share evaluation source code, but evaluation ideas i also will share.

If people are interested i will even distribute some source code (like the search function or the 64bit Bitboard based Move Generator).

Bert

[TAILLE]

My experience is that it is meaningless to compare search statistics like nodes/sec or time to depth between different programs. A 15 ply search can mean very different things to different programs because of extensions and truncations. With nodes/sec, even if you can agree on exactly how to count the nodes, the numbers will tell you nothing about the strength of the programs. A program can have very high nodes/sec because it spends little time on important things like position evaluation and move ordering.

-- Ed

Ed,
I agree with you the number of evaluated or generated positions is not a measure of the strength of a program; it is only a measure of your computer environment capacity if you change this environment but you continue to use the same program.

Let's suppose you have the choice between 10 possibilties for each move.
In the "ideal" situation if you want your program to show you the best variant on 15 ply then
1) You have to call your movegenetrator to see the 10 possibities for the first move
2)You evaluate these 10 possibilities with a "magic" evaluation function that will eventualy tell you what is best move !!!
3)You eliminate immediatly (without any new call to the movegenerator)the 9 other possibilities
4) you continue the processes with the best move found

In order to show the best varaint on 15 ply in this "ideal" world you need to call only 15 times the movegenerator and you need to call only 150 times the evaluation function.

When a program call millions of time the movegenerator or the evaluation function that mean 99,999...% of the CPU time is used on ininteresting position and this could not be a measure of the strength of the program

With Damy I use plenty of sophistcated technics for the search algorithm to explored the more relevant part of the game tree but I am not very happy because I cannot say that Damy is better than a GMI while I cannot imagine that a GMI can see more then 10 (or 100 if you prefer) positions per second !

As a consequence, for the future, I will concentrate my attention on the evaluation function and I will certainly not be harmed if the number of evaluated positions is divided for example by 2 or 10 !

Gérard

[BertTuyt]

Although not part of Endgame databases (maybe we should start more specific threads, where draughts programmers can discuss certain ideas), here something about Damage.
In the future i will cover more parts of Damage, hope it will be of any use to other programmers.

BitBoards,

Damage is based on 64bit Bitboards. Already from the beginning when only32bit processors existed, i was convinced that the future was for 64bit systems, and therefore based the design of Damage on 64bits.

As the concept of Bitboars is (i guess) wellknown i wont provide much details about this concept.

Damage basically uses 5 bitboards to describe a position .
bbWhiteMan, bbWhiteKing, bbBlackMan, bbBlackKing, and bbEmpty.

With many 64bit registers and 64bit instructions, one can easily implement for example a movegenerator.

All bitboards are stored in registers, and i use and / or and shift functions to (again for example) generate the possible moves for one side.

Moving upwards for white is only shifting bits 5 or 6 places (i think everyone is familiar with ghost fields, so moving a man always uses the same number of fields, which is not the case on a normal board!).

So generating a bitboard with all possible moves for white in 1 direction is something like :
( bbEmpty<<5 ) & bbWhiteMan

I also use a stack of structures, every structure contains many parameters describing the position and derived information (this way a moveback is only 1 instruction, decrement the pointer to the stack).

To test if a man can kill something (required to define/detect a static position), can also be simple described as a number of ands, ors, and shifts, all working on information in available CPU-registers.

Bert

[Rein Halbersma]

Although not part of Endgame databases (maybe we should start more specific threads, where draughts programmers can discuss certain ideas), here something about Damage.
In the future i will cover more parts of Damage, hope it will be of any use to other programmers.

BitBoards,

Damage is based on 64bit Bitboards. Already from the beginning when only32bit processors existed, i was convinced that the future was for 64bit systems, and therefore based the design of Damage on 64bits.

As the concept of Bitboars is (i guess) wellknown i wont provide much details about this concept.

Damage basically uses 5 bitboards to describe a position .
bbWhiteMan, bbWhiteKing, bbBlackMan, bbBlackKing, and bbEmpty.

With many 64bit registers and 64bit instructions, one can easily implement for example a movegenerator.

All bitboards are stored in registers, and i use and / or and shift functions to (again for example) generate the possible moves for one side.

Moving upwards for white is only shifting bits 5 or 6 places (i think everyone is familiar with ghost fields, so moving a man always uses the same number of fields, which is not the case on a normal board!).

So generating a bitboard with all possible moves for white in 1 direction is something like :
( bbEmpty<<5 ) & bbWhiteMan

I also use a stack of structures, every structure contains many parameters describing the position and derived information (this way a moveback is only 1 instruction, decrement the pointer to the stack).

To test if a man can kill something (required to define/detect a static position), can also be simple described as a number of ands, ors, and shifts, all working on information in available CPU-registers.

Bert

Interesting, Bert. How are you generating capture paths when you can jump multiple pieces?

Rein

[TAILLE]

Although not part of Endgame databases (maybe we should start more specific threads, where draughts programmers can discuss certain ideas), here something about Damage.
In the future i will cover more parts of Damage, hope it will be of any use to other programmers.

BitBoards,

Damage is based on 64bit Bitboards. Already from the beginning when only32bit processors existed, i was convinced that the future was for 64bit systems, and therefore based the design of Damage on 64bits.

As the concept of Bitboars is (i guess) wellknown i wont provide much details about this concept.

Damage basically uses 5 bitboards to describe a position .
bbWhiteMan, bbWhiteKing, bbBlackMan, bbBlackKing, and bbEmpty.

With many 64bit registers and 64bit instructions, one can easily implement for example a movegenerator.

All bitboards are stored in registers, and i use and / or and shift functions to (again for example) generate the possible moves for one side.

Moving upwards for white is only shifting bits 5 or 6 places (i think everyone is familiar with ghost fields, so moving a man always uses the same number of fields, which is not the case on a normal board!).

So generating a bitboard with all possible moves for white in 1 direction is something like :
( bbEmpty<<5 ) & bbWhiteMan

I also use a stack of structures, every structure contains many parameters describing the position and derived information (this way a moveback is only 1 instruction, decrement the pointer to the stack).

To test if a man can kill something (required to define/detect a static position), can also be simple described as a number of ands, ors, and shifts, all working on information in available CPU-registers.

Bert

Damy works in "only" a 32bits environment and I used exactly the same approach.
Basically Damy uses 4 bitboards for a position :
bbWhitePieces, bbBlackPieces, bbKings, and bbEmpty.
I chose this representation because when searching for a capture I do not need to know if the opponent piece is a man or a king. I saw some advantages of your representation which is more logical and I confess I hesitated a long time before finally chosing this last representation.

Of course I intensively use AND, OR, XOR and SHIFT functions in order to generate quickly all the possible moves, and I also use ghost fields which help me to know that I move really inside the board !

Gérard

[FeikeBoomstra]

My representation of the board is bbEmpty_Occupied, bbWhite_Black and bbMan_King. During move generation I use the (derived) representation like gerard did,
empty, own_men, own_king, other_piece, during evaluation I use:
empty, white_men, black_men, white_king, black_king, white_man_or_empty and black_man_or_empty.

Feike.

[steenslag]

Although not part of Endgame databases (maybe we should start more specific threads, where draughts programmers can discuss certain ideas), here something about Damage.
In the future i will cover more parts of Damage, hope it will be of any use to other programmers.

BitBoards,

Damage is based on 64bit Bitboards. Already from the beginning when only32bit processors existed, i was convinced that the future was for 64bit systems, and therefore based the design of Damage on 64bits.

As the concept of Bitboars is (i guess) wellknown i wont provide much details about this concept.

Damage basically uses 5 bitboards to describe a position .
bbWhiteMan, bbWhiteKing, bbBlackMan, bbBlackKing, and bbEmpty.

With many 64bit registers and 64bit instructions, one can easily implement for example a movegenerator.

All bitboards are stored in registers, and i use and / or and shift functions to (again for example) generate the possible moves for one side.

Moving upwards for white is only shifting bits 5 or 6 places (i think everyone is familiar with ghost fields, so moving a man always uses the same number of fields, which is not the case on a normal board!).

So generating a bitboard with all possible moves for white in 1 direction is something like :
( bbEmpty<<5 ) & bbWhiteMan

I also use a stack of structures, every structure contains many parameters describing the position and derived information (this way a moveback is only 1 instruction, decrement the pointer to the stack).

To test if a man can kill something (required to define/detect a static position), can also be simple described as a number of ands, ors, and shifts, all working on information in available CPU-registers.

Bert

Interesting, Bert. How are you generating capture paths when you can jump multiple pieces?

Rein

In my long-abandoned effort to make a problemgenerator (in visual basic 4 haha) I remember having a Ghostpiece, for pieces already taken. It prevented the program from endlessly taking the same pieces. Nobody in this thread has such a thing, so it's probably a very bad idea. There were a lot of very bad ideas in that wretched program...

[FeikeBoomstra]

Nobody mentions it, because it is not a specific design tric. Of course you need in your move generator a means that you don't capture the same piece twice.
If you use a bit representation for the position, it is quite obvious to use also a bit representation for the pieces already captured. Is this what you mean by GhostPiece?

The main advantage of using a bitmap is that you can select the possible moves and captures all in once. (sort of parallel)
Captures may take more than one piece. I was not able to design an algorithm that explore the possible next legs of a path in parallel. Especially because of the detection of the pieces already taken.

Feike

[BertTuyt]

Rein, I solve the mutiple kill problem, by calling the Kill_routine recursively.
In the header of the routine i put the relevant bitmaps.
So when a piece is killed, the bit is cleared, and therefore, in the next call it will not be possible to kill the piece again, this way i don't need ghost pieces.

The bitfields are updated locally, the function keeps a "global" structure with the maximum path-length.

For kings i basically use the same method although the algoritm is more complicated.

I don't have a one - pass algorithm do determine the max-length of a kill.
But because most kills are only dealing with 1 man, i don't think this would improve overall computing time dramatically.

Bert

[TAILLE]

Jacques, i think it is an interesting discussion.
But as i don't master the French language, useless to me.
Cant't you motivate the French Draughts programmers to join this Forum.

It is a pity that the Draughts Computer Community share so little with each other.
Although Damage has won the last championship in Holland , I am more interested in sharing ideas and improving all programs, then keeping things for myself and trying to maintain this position.

May be im more reluctant to share evaluation source code, but evaluation ideas i also will share.

If people are interested i will even distribute some source code (like the search function or the 64bit Bitboard based Move Generator).

Bert

Bert,
Because I am one big contibutor to the discussion mentioned by Jacques I can tell you what the subject was.
The initial question was "can computers take calculated risks in order to improve the probabity of winning ?"
The example done was the following

White to move

One of my answers was the following :

At the 14th Damy level (a Damy level is not exactly the number of ply but this is not the point) Damy find the 7 "good" moves with the following evaluations (from the white side) :
38-32 : +0,07
41-36 : +0,05
47-42 : +0,00
44-40 : -0,01
43-39 : -0,01
44-39 : -0,04
41-37 : -0,05

After 38-32 there is the trap 23-29? (level 1)
After 44-40 there is the trap 23-29? (level 4)
After 43-39 there is the threat 26-21, 38-32 (level 1)
After 44-39 there is the threat 26-21, 38-32 (level 1) but also the trap 17-22? (level 9), the trap 09-13? (level 9) and the trap 23-29? (level 4)
After 41-37 there is the trap 23-29? (level 5)

As you see it appears that 44-39 may be an interesting move for winning when facing a human body. In addition when I restrict Damy to the 8th level (in order it does not discover that 17-22 and 09-13 are bad moves) Damy chooses the move 17-22. We are then in a ideal situation; 44-39 is not the strongest move but it is not too far from the best move and it tries the trap 17-22?, which is the best move at the 8th level !

My conclusion was that it will be certainly very intersting to program such algorithm against a human. Of course it will be (very?) time consuming to calculate these traps but finally I think that it will be very profitable.
Of course this kind of algorithm must not be used against another computer !!

Have you experimented some specific algorithms when playing against human ?
Do somebody know if such specific algorithm has been experimented for example in the chess world ?

Gérard