Search Algorithm

[BertTuyt]

So it seems an on-the-fly HashFunction is not impossible .

Any idea about speed compared with Zobrist?

Bert

[Joost Buijs]

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

Still no collisions, it looks very good now. It was a bit stupid of me that I overlooked pieces[color] and put men[color] instead.
I will compare the speed with Zobrist at somewhat lower depth.

Joost

This is with your hash-function:

Code: Select all

TT: num_buckets = 4194304, tt_size = 1140850688
Allocated TT with size 1140850688 in SP memory.

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

Time = 19.38  Matching hashprobes = 125367560  Matching probes/sec. = 6470117.584701

Collisions found 0

And this is with Zobrist:

Code: Select all

TT: num_buckets = 4194304, tt_size = 1140850688
Allocated TT with size 1140850688 in SP memory.

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

Time = 19.14  Matching hashprobes = 123631680  Matching probes/sec. = 6458456.791772

Collisions found 0

Hardly any difference in probe-speed ~0.3%. In time Zobrist used 1% less.
Since I calculate the index from the lower bits of the hash, there will always be differences in the number of matched probes between different hash-functions.
And you must not forget that the incremental update for Zobrist is still in place, I can comment it out and see what it does then.

Code: Select all

TT: num_buckets = 4194304, tt_size = 1140850688
Allocated TT with size 1140850688 in SP memory.

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

Time = 19.06  Matching hashprobes = 125367560  Matching probes/sec. = 6576537.188177

Collisions found 0

Now you are faster!

[BertTuyt]

Joost, seems to look interesting and promising.

Here Woldouby at ply 28, 30.5G HashEntries, and no collisions.

And Cityhash() and SpookyHash() seems to be even faster.......

Bert

[Joost Buijs]

Joost, seems to look interesting and promising.

Here Woldouby at ply 28, 30.5G HashEntries, and no collisions.

And Cityhash() and SpookyHash() seems to be even faster.......

Bert

Bert, Unfortunately it makes no difference for the playing strength (the speed I mean).

I will let the collisions for what it is right now, and start working on finishing my search.
This afternoon I implemented my hash table in the search (only pruning, no move order yet) and it already makes a difference of a factor 10 in search-times.
Next I have to add killers, history and SMP, I have no clue what works or not works with Draughts, but these general things will probably work.

Joost

[BertTuyt]

Joost, I tend to agree.
On the other hand, I like it when something works (derived from the A team)
And basically (but again, this does not change anything with respect to strength), I prefer simplicity (and incremental updates are not always simple).

Suc6 with your next steps.

I go for a Business Trip next week, so will be online next weekend.
I will focus on the Hash implementation in Dwarf, not to make a strong program, just for the demonstration purpose.
And also for me it helps to built things up step by step from the basis, and test new functions somewhat better.

Maybe I check if the program reaches ply 29 , and hopefully without collisions.
And then I will also call it a day for now......

Bert

[Joost Buijs]

Bert, I hope you will have a nice trip this week!

If I can find time next week to work on my search I hope to do some tests with it next weekend.

Joost

[BertTuyt]

Also at ply 29 (Woldouby) and 79G hash entries, no collisions.
So far the tests for today with MurmerHash().

Bert

[BertTuyt]

And just out of curiousity, the older Hash().
And yes, also I found collisions...

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 = 929 Collisions = 0
info Depth 10-1008286 knps 0
Hash Probes = 8286 Hash Entry = 2088 Collisions = 0
info Depth 11017767 knps 0
Hash Probes = 17767 Hash Entry = 4630 Collisions = 0
info Depth 12029759 knps 0
Hash Probes = 29759 Hash Entry = 8539 Collisions = 0
info Depth 13078819 knps 0
Hash Probes = 78819 Hash Entry = 21545 Collisions = 0
info Depth 14-100144301 knps 14430
Hash Probes = 144301 Hash Entry = 39340 Collisions = 0
info Depth 15-100377166 knps 12572
Hash Probes = 377166 Hash Entry = 106267 Collisions = 0
info Depth 16-100797975 knps 15959
Hash Probes = 797975 Hash Entry = 210708 Collisions = 0
info Depth 17-201394363 knps 15492
Hash Probes = 1394363 Hash Entry = 414335 Collisions = 0
info Depth 18-2003817462 knps 14138
Hash Probes = 3817462 Hash Entry = 1004686 Collisions = 0
info Depth 19-1007088960 knps 15082
Hash Probes = 7088960 Hash Entry = 2245543 Collisions = 0
info Depth 20-10020054239 knps 16573
Hash Probes = 20054239 Hash Entry = 5519515 Collisions = 0
info Depth 21-10040641388 knps 15511
Hash Probes = 40641388 Hash Entry = 13728146 Collisions = 0
info Depth 22-100111633402 knps 17497
Hash Probes = 111633402 Hash Entry = 35875513 Collisions = 1
info Depth 23-100282735786 knps 16680
Hash Probes = 282735786 Hash Entry = 111445253 Collisions = 85
info Depth 24-1001027555382 knps 19494
Hash Probes = 1027555382 Hash Entry = 373609660 Collisions = 1343

[BertTuyt]

I also tested the HashFunction Ed shared ( Ed thanks ).
I slightly changed the code.
See below:

Code: Select all

HASHKEY Hash_Ed(BITBOARD* b)
{
	int i;
	uint64_t hash = 0, *k;

	k = (uint64_t *)b;

	for (i = 0; i < 3; ++i) {
		hash += (k[i] << 25) - k[i];
		hash ^= (hash >> 23);
		hash += (hash << 4);
		hash ^= (hash >> 6);
		hash += (hash << 8);
		hash ^= (hash >> 10);
		hash += (hash << 26);
		hash ^= (hash >> 31);
	}

	return (hash);
}

At least also this function seems to be robust, at the famous Woldouby position and 25 ply, no collisions.

Edit: and also at ply 26 , 3.9G hash entries no collision, so sure that the function also works (but to be honest , everything from Ed is high quality...).

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 = 929 Collisions = 0
info Depth 10-1008286 knps 0
Hash Probes = 8286 Hash Entry = 2087 Collisions = 0
info Depth 11017767 knps 0
Hash Probes = 17767 Hash Entry = 4625 Collisions = 0
info Depth 12029759 knps 0
Hash Probes = 29759 Hash Entry = 8534 Collisions = 0
info Depth 13078819 knps 0
Hash Probes = 78819 Hash Entry = 21526 Collisions = 0
info Depth 14-100144301 knps 14430
Hash Probes = 144301 Hash Entry = 39389 Collisions = 0
info Depth 15-100377166 knps 12572
Hash Probes = 377166 Hash Entry = 106234 Collisions = 0
info Depth 16-100797975 knps 13299
Hash Probes = 797975 Hash Entry = 210639 Collisions = 0
info Depth 17-201394363 knps 12676
Hash Probes = 1394363 Hash Entry = 414193 Collisions = 0
info Depth 18-2003817462 knps 13633
Hash Probes = 3817462 Hash Entry = 1004683 Collisions = 0
info Depth 19-1007088960 knps 12889
Hash Probes = 7088960 Hash Entry = 2246208 Collisions = 0
info Depth 20-10020054239 knps 14324
Hash Probes = 20054239 Hash Entry = 5519737 Collisions = 0
info Depth 21-10040641388 knps 13592
Hash Probes = 40641388 Hash Entry = 13730447 Collisions = 0
info Depth 22-100111633402 knps 15208
Hash Probes = 111633402 Hash Entry = 35876067 Collisions = 0
info Depth 23-100282735786 knps 14150
Hash Probes = 282735786 Hash Entry = 111446420 Collisions = 0
info Depth 24-1001027555382 knps 16396
Hash Probes = 1027555382 Hash Entry = 373619406 Collisions = 0
info Depth 25-1002469792688 knps 13997
Hash Probes = 2469792688 Hash Entry = 1111136629 Collisions = 0

[Joost Buijs]

Bert,

It certainly looks good, indeed a lot better than the previous function.

I decided to keep Zobrist in, it slows perft() down by 10% but on the overall program I didn't notice much difference in speed, maybe in the future I will change to another hash-function.

The last 2 day I've been working on the search(), I'm struggling a bit with move-sorting in finding a way to do this fast and elegant, I have to scan at least one time through the move-list to find the killers and score history values for the other moves. I can move the killers to the beginning of the list and only sort the list when the killers didn't generate a cutoff, there are many other schemes possible though. I treat the hash-move entirely separated from the rest of the moves because I want this to be as fast as possible, since I don't need a move-generation the hash-move generates a quick cutoff very often.

I'm just trying to find out what gives the least overhead, atm. my search() runs at ~12 to 16 mnps (single core) and I don't want to destroy performance by using a dumb sorting routine. As usual it takes more of my time than expected.

Joost

[BertTuyt]

Joost,

back from my business trip (Cambridge University, amongst others),
in the end it is all about time to depth instead of mnps.
But when you are living in the double digit mnps universum, it is not easy to grow towards and accept single digit mnps performance.
But there might not be an alternative.
Im also trying to built up a new Damage architecture from the ground, and also im now in mnps heaven.
But as I purely base the MoveGen() on new positions, all kind of things which were easy in the past, are now relatively difficult.
Example is indeed move history where you need the from and to position, deriving the pv, and so on.
In the past I had also a very simple (time consuming) sort, but will also have a look at it this weekend.
I guess (my prediction) when you optimise strength, the maximum you could reach (on 4 GHz) is 8 mnps, but I hope im also wrong here...

Bert

[Joost Buijs]

Bert,

I fully agree with you that time to depth is the most important parameter there is, but if you can keep your nps high at the same time it will be even better.
With chess a doubling in speed accounts roughly for 70 Elo points, I have no idea what speed is doing to Draughts performance.
Things like LMR and other pruning tricks are in many cases bogus when they are not very well tuned, it is like 'een sigaar uit eigen doos' we say here in Holland.
It is my goal to get > 50 mnps on my 8 core machine, the effective speedup will be around 5.5 to 6, so I don't want to drop below 10 mnps single core if possible.

Joost

[BertTuyt]

Joost, beginning 2013 I started a (small) study to understand what the ultimate ELO gain could be with infinite resources.
Just start reading at the 1st page of this Search thread, there are many posts related to this topic.

I based results on the Damage - Kingsrow system.
Kingsrow played 1 min/Game (all DXP matches), and Damage had a fixed depth search.

Conclusion at that point in time, was that going to infinite depth, Damage could become 300 points stronger.
See below text (Search Thread Page 2).

Code: Select all

I tried to do some curve fitting on the current data.
As I expect a maximum rating (or pScore), and diminishing returns, I applied the next formula.

pScore = a * ( b - exp ( c * depth ) )

The values found were: a = 1,2665423, b = 0,675251 c - -0,077102341
The regression coefficient 0,99.

With these values I "predicted" the ELO rating for depth = 24 (currently in progress) and higher "virtual" depths.
To my surprise the ELO tops at around 300.
That the ELO tops is a consequence of the formula applied, but i expected something around 150.

It would be interesting (maybe something I can do during Xmas holiday, when Im back in Holland) to redo tests with Scan at fixed depth, compared with a 1 Min/Game Scan.

Bert

[Joost Buijs]

Bert,

Thanks for the info! This can be very useful to make predictions.

In the mean time I still struggle with move sorting, first there was a mistake in the hash-table update, instead of overwriting the worst entry in the bucket I did overwrite the best one, just a matter of > replacing by <, solving this made a difference of a factor of 2 in search-time. And surprisingly nps on Woldouby went up from 12 mil. to 13.6 mil., I'm pretty confident now that I can reach my goal of >10 mnps on a single core.

Now I have to decide whether I want to use 1 or 2 killers, I'm still testing what performs best, so still a lot of things to do.

Joost

[BertTuyt]

Joost,

I remember quite well that debugging the HashTable implementation is APITA ( a pain in the ....).
Also in the past my Search has exploded with all kind of hyper-intelligent features ( ), which in the end as you phrased it, throws away the baby with the bathwater.

Therefore I want to built from the base, and better test everything I add.
So as you Im now working on the HashTable.
Im testing if I could get away with never clearing the HashTable, and also dont introduce an aging mechanism.

Next to that I started with a very simple implementation (which might be subject to change):
* Only 1 bucket.
* Overwrite only in case of a beta cutoff
* Hashcutoff if HashScore >= Beta and HashDepth >= SearchDepth

In the past I also used the HashTable for:
* Start with the move adressed by the HashBestMove Index if there is no cutoff
* Modifiy Alpha, if HashScore > Alpha

Also I (in the past) added some flags in the HashTable (lowerbound higherbound), as I used PVS
But for now (like you) I started with plan Alpha - Beta.

As a sparring partner I use the latest version of Moby Dam.
Dwarf communicates via the Hub protocol, and Moby Dam via DXP.
Works well, although (so far) Moby Dam wins all the time

But thats the consequence of using an Evaluation function with material only.
Im curious if simple additions could improve the overall picture.
Such as a simple left right count to better distribute the pieces, and a simple count to maximize neighbours, and this way simple patterns are favoured, like count(whiteman>>5 & whiteman) + count(whiteman>>6 & whiteman).

Bert