BitBoards

[BertTuyt]

Gerard,

in my case I keep the From_position in another location on the stack, so I can access it later. I use a recursive ManKill routine, and I don't pass the From_Position in the Routine parameter-list (do you do this?).
But I agree with you it is not contained in the information which is stored in the Move-Structure.

Regarding the animation of the right capture sequence, I fully agree.
Also in the my implementation I don't save the capture sequence, so I am not able to reconstruct the path as Dam 2.1 .

Bert

[BertTuyt]

Feike, will take a look at your code somewhat later.
But I tend to agree with the remarks as made by Gerard.

Basically I have 4 different KingKillNext routines for every direction, to avoid checking the direction it came from.

Also I did not find an alternative for stepping one by one over leading empty squares.

Bert

[BertTuyt]

I have another idea for the routine actually doing the move, so I will test it these days and if succesfull ( so faster) will share the outcome here.
The basic concept, I use a stack of BitBoards, so moving forward is a copy/modify of the BitBoards (in my case 5), and remove is just a pointer decrement.

The basic idea, if on a specific depth the first move is executed the next level contains all new Bitboards.

So when at this level (and the same node) the next move is processed, basically only the Bitboards which are affected by the Move-type have to be modified.

For example for a KingMove only the King Bitboard and Empty Bitboard needs to be updated (more about the Empty Bitboard modify strategy later this week).

The Bitboards for the Opponent Pieces don't need to be modified as they are not affected by a "normal" move.

As I don't trust my line of reasoning, I will do a test to make sure i didn't made any logical failure.

Bert

[TAILLE]

Hi Bert, Feike

I also have 4 different KingKillNext routines, one per direction, and I also did not find an alternative for stepping one by one over leading empty squares.

The main idea I used in my recursive capture routine is the following : I do not pass any parameter to the routine, I only modify the original bitboard without any copy; to avoid multiple capture of the same piece, instead of marking the corresponding square as empty, I mark it as ghost!

nb. For the fourth time I am grandfather : a grandson after 3 granddaughters.

Gérard

[FeikeBoomstra]

Gerard,

First of all of course my congratulations with the birth of your grandson.

And second: finally I am beating dam2.2. 18-10. The last decision was the most difficult. When I started my career I was heavily involved in real-time programming. And I have seen many big, untraceable problems due to incorrect uses of semaphores.

And now, I just left out all the locks around the hash-table access. The speed-up was enormous. 20-30%. The hash-lookup took about 10% of the time and the hash-store function a liitle bit less then 10%. And I haven't seen any suspicious moves.

So now, I am interested in creating a 64 bit position identity tag. Now I am using 3 x 64(54) bits to identify the position. But from the literature I understand that everybody is trying to generate an almost unique 64 bit signature of a draught position.

I looked at some hashing algorithms, and thought about combining the hash key and the signature, being the hash key only the lowest n-bits of the signature.

Did somebody implement something like that or has somebody some ideas?

kind regards,
Feike.

[TAILLE]

Hi,

Gerard,

First of all of course my congratulations with the birth of your grandson.

And second: finally I am beating dam2.2. 18-10. The last decision was the most difficult. When I started my career I was heavily involved in real-time programming. And I have seen many big, untraceable problems due to incorrect uses of semaphores.

And now, I just left out all the locks around the hash-table access. The speed-up was enormous. 20-30%. The hash-lookup took about 10% of the time and the hash-store function a liitle bit less then 10%. And I haven't seen any suspicious moves.

So now, I am interested in creating a 64 bit position identity tag. Now I am using 3 x 64(54) bits to identify the position. But from the literature I understand that everybody is trying to generate an almost unique 64 bit signature of a draught position.

I looked at some hashing algorithms, and thought about combining the hash key and the signature, being the hash key only the lowest n-bits of the signature.

Did somebody implement something like that or has somebody some ideas?

kind regards,
Feike.

Effectively I used a 64bits signature for a position, by using the Zoobrist approach (see http://en.wikipedia.org/wiki/Zobrist_hashing).
From this signature I derived 3 hash table index in order to limit collisions as far as possible.

Gérard

[FeikeBoomstra]

But if you use a zobrist hash-key calculation (like me too), then you need the index of the start, stop and captured location. Or do you re-generate the entire key for every position?

[TAILLE]

Feike,

But if you use a zobrist hash-key calculation (like me too), then you need the index of the start, stop and captured location. Or do you re-generate the entire key for every position?

Yes, I use the index of the start, stop and captured location in order to calculate the hash key from the previous position

Gérard

[BertTuyt]

Feike/Gerard.

I also use a Zobrist type of implementation for the Hash-key , based on the Xor . For every Board Position / Piecetype (WhiteMan, BlackMan, WhiteKing, BlackKing) I have another HashValue.
I guess this is what all people use.

I have a 64bit HashData, containing the next data:
Flags (to indicate low/high bound, real value), SearchDepth, SearchValue, BestMoveIndex.

I use a shared Hash-Table for the parallel search without Lock, based on the ideas of Hyatt (XOR Data with the Key).

As I don't use the index in the MoveGenerator anymore, I now use the BitScan (intrinsic) to find the index within a bitstring for both the MoveBitBoard (only containing To and From Position ) and The Capture BitBoard. Gerard/Feike do you also use this intrinsic, or did you write your own routine for this ( i never did a timing to find out which is the fastest way).

Gerard, I still don't understand why use use 3 Hash Table Index ?

Note: Ed has a different approach, he calculates the hash-Key not incrementally, but based directly on the BitBoards (in this way you also can omit finding/retrieving the Bit-Index).

Bert

[FeikeBoomstra]

Yes, same approach for obtaining the index. (bitscanforward)

Do you know this trick to remove the least significant bit from a bitboard:

temp = temp & (temp - 1);
and to get that single bit as a bitboard:

bb = temp ^ (temp&(temp-1));

Feike.

[Rein Halbersma]

Yes, same approach for obtaining the index. (bitscanforward)

Do you know this trick to remove the least significant bit from a bitboard:

temp = temp & (temp - 1);
and to get that single bit as a bitboard:

bb = temp ^ (temp&(temp-1));

Feike.

I use the following:

Code: Select all

                from_sq = jumpers & (0 - jumpers);      // isolate LS1B
                jumpers ^= from_sq;                     // clear LS1B

Rein

[TAILLE]

Yes, same approach for obtaining the index. (bitscanforward)

Do you know this trick to remove the least significant bit from a bitboard:

temp = temp & (temp - 1);
and to get that single bit as a bitboard:

bb = temp ^ (temp&(temp-1));

Feike.

Yes, of course, see in particular http://chessprogramming.wikispaces.com/ ... OneBitLS1B

Gérard

[Ed Gilbert]

It seems now that our move generators are rather close from each other and very optimised but now I have a new question :
do you need two generators, one very optimised for the tree exploration and another for man machine needs ?

The points are the following :

In the above diagram the "optimised" generator do not keep as a result that the capture is made by white 29

Gerard, yes I use 2 move generators for the reasons you mentioned. I have what I think is a nice solution to this problem in my 8x8 checkers program. When I tried to do the same for 10x10 I had some problem with the compiler which I could not immediately solve, and so for the time being it is done differently, but I want to go back and use this technique for international draughts.

The basic idea recognizes that 95% of the source code for the fast generator and the one which also returns details of capture sequences is identical. I created a single source file with the source for the most complete move generator that returns all the capture info, and then used conditional compilation #if statements to bracket those portions of the code that are not needed by the fast generator. The #if statements also select which function declaration gets compiled. Example:

Code: Select all

#if SAVE_CAPTURE_PATH
int build_jump_list_path(BOARD *board, MOVELIST *movelist, int color, CAPTURE_INFO cap[MAXMOVES])
#else
int build_jump_list(BOARD *board, MOVELIST *movelist, int color)
#endif

Throughout the source file segments of code only needed for build_jump_list_path are similarly bracketed by #if SAVE_CAPTURE_PATH. Now the problem is how to compile two instances of the source file into the same program, one instance with the macro set to 0, and other with it set to 1. Suppose the source file is named move.cpp. I created 2 additional source files, move_sans_capture_path.cpp and move_with_capture_path.cpp. These files are simply shells which #include move.cpp with the macro set to the desired value. So for example, move_with_capture_path.cpp looks like this:

Code: Select all

#define SAVE_CAPTURE_PATH 1
#include "move.cpp"

and similarly move_sans_capture_path.cpp:

Code: Select all

#define SAVE_CAPTURE_PATH 0
#include "move.cpp"

Now just add both these shell files to the project and you end up compiling two instances of move.cpp.

-- Ed

[FeikeBoomstra]

Maybe I am very special. I wrote my GUI in python. This part has a move generator too. Not fast, but that's not needed, because it is a single shot uses. In python you have a very nice list structure, so that is the way I keep the captures ordered. And I can also easily remember the intermediate landing points.

By the way, I didn't optimize my move generator in my real program yet, just in the perft environment. The consequences of a bitboard as start an stop field have a lot of impact.
So That's for after december 14.