Search Algorithm

[Joost Buijs]

I forgot to initialise h in the previous MurmerHash version.
Which I now changed.

Code: Select all

HASHKEY h=0

I restarted the test, for the initial position I will try to reach ply 23.
As soon as I have the result I will share and forward.

Edit 1: So far so good, no collisions at ply 21.

Bert

I added it to the test program, indeed h is the seed and I set it to 0, at the start position I had no collisions yet, unfortunately with Woldouby it immediately shows collisions.

Edit:

Sorry, forget the above maybe I made a mistake here, at least I see something that should not happen.

[BertTuyt]

Joost thanks, I will see if I can run the test with the initial position to ply 22 or 23, and then do the Woldouby position.
It might be related to Kings, but I have no clue why results are so bad.
Especially while the initial position looks good, and I cant believe that the Murmerhash doesnt scale beyond 16 bytes?

Did you use the 3 BitBoards or expanded the MurmerHash to 4 Bitboards?
Maybe the 3 Bitboards creates problems, as the input string has a hidden correlation.
For all bits set in the King Bitboard, a bit is set in WhitePiece or BlackPiece.
In case of the 4 Bitboards, there is no correlation.
Another option (but Im just guessing), is that the King Bitboard is vers sparse (with only a few bits set).

Anyway interesting, so I will at least continue....

Bert

[Joost Buijs]

Bert,

I see something that I cant explain, maybe I found a hidden bug in my code, I will get back later when I have a clue what is going on.

Joost

Edit:

Fortunately it was not a bug but when I printed the collision-hash I still used your old hash-function, that looked rather strange to me.
It seems that the new hash-function doesn't distinguish between the color of kings, which you can also see when looking at the code.

Code: Select all

Hash = 868f98ca3ce0b340

    -  -  -  -  -
  -  -  -  -  -
    -  -  -  m  -
  -  -  -  -  m
    -  m  m  -  m
  -  -  -  -  -
    -  -  -  -  M
  -  -  M  -  -
    -  -  -  -  -
  -  -  k  -  -

Hash = 868f98ca3ce0b340

    -  -  -  -  -
  -  -  -  -  -
    -  -  -  m  -
  -  -  -  -  m
    -  m  m  -  m
  -  -  -  -  -
    -  -  -  -  M
  -  -  M  -  -
    -  -  -  -  -
  -  -  K  -  -

[BertTuyt]

Ok, will start a Woldouby later.

In the meantime, I have reached 22 ply (initial position) without collisions.
Around 29G probes, so the non-king part seems to work much better.

With the 3 BitBoards , the Kings does not contain color (as the Bitboard contains all kings).
But still, when it is a White King or Black King will also affect the WhitePiece and BlackPiece BitBoards, so I assume it still should work in theory (but apparently not).

Did you test with 3 or 4 BitBoards?

I first want to finalise the 23 ply (that will take some time), and also do something social (some people here dont believe that working on Sunday on computer draughts is considered social ).
So the Woldouby test is scheduled for a little later...

Bert

[Joost Buijs]

Ok, will start a Woldouby later.

In the meantime, I have reached 22 ply (initial position) without collisions.
Around 29G probes, so the non-king part seems to work much better.

With the 3 BitBoards , the Kings does not contain color (as the Bitboard contains all kings).
But still, when it is a White King or Black King will also affect the WhitePiece and BlackPiece BitBoards, so I assume it still should work in theory (but apparently not).

Did you test with 3 or 4 BitBoards?

I first want to finalise the 23 ply (that will take some time), and also do something social (some people here dont believe that working on Sunday on computer draughts is considered social ).
So the Woldouby test is scheduled for a little later...

Bert

I just added the 2 king bitboards together to make it 1.
Probably you have to separate them, otherwise it won't work.
Have a nice day!, talk to you later.

Joost

[BertTuyt]

Last update, initial position 59.4G probes, no collisions.

So now going to the Woldouby, and see why it has problems.....

Bert

[BertTuyt]

Woldouby Position, at ply 25 1.1G probes, no collision?

Bert

Code: Select all

id name Dwarf 0.0
id author Draughts Community
ready
HashTable Allocated, Entries = 1048576
pos XW XB 10 10
info Depth 107 knps 0
Hash Probes = 7 Hash Entry = 0 Collisions = 0
info Depth 2019 knps 0
Hash Probes = 19 Hash Entry = 0 Collisions = 0
info Depth 310043 knps 0
Hash Probes = 43 Hash Entry = 6 Collisions = 0
info Depth 4072 knps 0
Hash Probes = 72 Hash Entry = 14 Collisions = 0
info Depth 50161 knps 0
Hash Probes = 161 Hash Entry = 39 Collisions = 0
info Depth 60325 knps 0
Hash Probes = 325 Hash Entry = 85 Collisions = 0
info Depth 70549 knps 0
Hash Probes = 549 Hash Entry = 170 Collisions = 0
info Depth 8-1001566 knps 0
Hash Probes = 1566 Hash Entry = 344 Collisions = 0
info Depth 904051 knps 0
Hash Probes = 4051 Hash Entry = 931 Collisions = 0
info Depth 10-1008286 knps 0
Hash Probes = 8286 Hash Entry = 2091 Collisions = 0
info Depth 11017767 knps 0
Hash Probes = 17767 Hash Entry = 4634 Collisions = 0
info Depth 12029759 knps 0
Hash Probes = 29759 Hash Entry = 8549 Collisions = 0
info Depth 13078819 knps 0
Hash Probes = 78819 Hash Entry = 21538 Collisions = 0
info Depth 14-100144301 knps 14430
Hash Probes = 144301 Hash Entry = 39349 Collisions = 0
info Depth 15-100377166 knps 12572
Hash Probes = 377166 Hash Entry = 106259 Collisions = 0
info Depth 16-100797975 knps 15959
Hash Probes = 797975 Hash Entry = 210998 Collisions = 0
info Depth 17-201394363 knps 15492
Hash Probes = 1394363 Hash Entry = 414584 Collisions = 0
info Depth 18-2003817462 knps 15906
Hash Probes = 3817462 Hash Entry = 1005097 Collisions = 0
info Depth 19-1007088960 knps 15082
Hash Probes = 7088960 Hash Entry = 2245998 Collisions = 0
info Depth 20-10020054239 knps 16711
Hash Probes = 20054239 Hash Entry = 5519023 Collisions = 0
info Depth 21-10040641388 knps 15813
Hash Probes = 40641388 Hash Entry = 13729930 Collisions = 0
info Depth 22-100111633402 knps 17918
Hash Probes = 111633402 Hash Entry = 35872187 Collisions = 0
info Depth 23-100282735786 knps 16910
Hash Probes = 282735786 Hash Entry = 111449821 Collisions = 0
info Depth 24-1001027555382 knps 19457
Hash Probes = 1027555382 Hash Entry = 373613797 Collisions = 0
info Depth 25-1002469792688 knps 16319
Hash Probes = 2469792688 Hash Entry = 1111109312 Collisions = 0
move 25-20

[Joost Buijs]

Hi Bert,

That is strange indeed, I will check what it does here.

Joost

I find collisions immediately, I wonder what the difference is?

This is the function as I use it:

Code: Select all

	uint64_t zhash()
	{
		uint64_t h = 0, k;
		const uint64_t m = 0xc6a4a7935bd1e995;
		const int r = 47;

		k = board.men[White];
		k *= m;
		k ^= k >> r;
		k *= m;

		h ^= k;
		h *= m;

		k = board.men[Black];
		k *= m;
		k ^= k >> r;
		k *= m;

		h ^= k;
		h *= m;

		k = board.kings[Black] | board.kings[White];
		k *= m;
		k ^= k >> r;
		k *= m;

		h ^= k;
		h *= m;

		h ^= h >> r;
		h *= m;
		h ^= h >> r;

		return h;
	}

It always collides in positions where the color of the kings is reversed, can be a bug at my side, I will take a look again.
With Zobrist it is perfectly ok, and when I look at the code that I use right now it can't work, maybe you skip promotions?

[BertTuyt]

Joost, thanks for checking.
As it could also be a bug here, indicating no problem, but in reality.....
In the meantime 26 ply, 3.9G HashEntries, 0 collisions.

Bert

[Joost Buijs]

Joost, thanks for checking.
As it could also be a bug here, indicating no problem, but in reality.....
In the meantime 26 ply, 3.9G HashEntries, 0 collisions.

Bert

Not difficult to see that when you have 1 field for the kings only you can't distinguish between White and Black kings, you have to treat them separately.
It beats me why you don't see collisions.

Joost

[BertTuyt]

Joost , because the 3 BitBoards are WhitePiece ( White Man | White King), BlackPiece ( Black Man | Black King) and King ( White King | Black King).

Think your 2 first bitBoards are only man....

Bert

[Joost Buijs]

Joost , because the 3 BitBoards are WhitePiece ( White Man | White King), BlackPiece ( Black Man | Black King) and King ( White King | Black King).

Think your 2 first bitBoards are only man....

Bert

I guess you are right, it was not clear from the code, but now that I think about it I see the problem.
I will change it, and let you know what it does here.

Ok, it is running at 25 ply, so far it looks good, it will take a while. It will take ages because it is still alpha-beta only.

[BertTuyt]

Joost, it is still possible that you will see collisions, but I hope not so dramatic , as before.
The Woldouby here is now at ply 27 and 7.67G HashEntries, without collision.

Bert

[Joost Buijs]

Joost, it is still possible that you will see collisions, but I hope not so dramatic , as before.
The Woldouby here is now at ply 27 and 7.67G HashEntries, without collision.

Bert

Bert,

It works fine now, it is already running for several minutes and no collision yet, the new hash-function is a lot better indeed.

Joost

[BertTuyt]

Also not sure you need the last 3 instructions:

Code: Select all

	h ^= h >> r;
	h *= m;
	h ^= h >> r;

And also dont know, if this is compared with Zobrist faster.
But at least it is elegant

And according the web the alternatives CityHash and SpookyHash should be faster......

Bert