ENGINE SPEED AND STRONG

[Joost Buijs]

Fabien,

For me this is a fun project, now that my engine starts to play decently I don't know what to do with it. I want to add somewhat larger patterns (5 x 5 comes to mind) and maybe I will spend some time on calculating an opening book. Another thing is that I don't know how to make it usable for other people, it lacks an interface and all parameters are hard-coded, I guess I have to add at least a configuration file which is what most others seem to be doing here.

Without the help of your source (I studied your evaluation function in detail), and without the help of Ed's Kingsrow which enabled me to run tests without having to write anything with respect to this myself, my program would not have gotten at the level it is right now in just a couple of months time.

Joost

[Joost Buijs]

I don't know if the increase in performance (measured in ELO) is linear, and that the value (as we tested) is independent on evaluation implementation.
What we have seen in some tests, that definitely there seems to be some diminishing returns with increasing search depth.
It would be interesting to test this with the new programs like Argus, who are able to reach search depth into a domain we have not tested before.
Bert

Bert,

Although my program runs roughly twice as fast (on hardware with BMI2) as the other programs with pattern evaluation it still does not reach the main depth that Scan reaches, my program is comparable to Kingsrow with respect to depth, this has everything to do with pruning and the amount of work done in qsearch. Just like Kingsrow, the latest version of my program doesn't allow the quiescence to 'stand pat' when there are off-side captures (unfortunately this takes a considerable amount of time), Scan does not seem to do this. You can argue that it is not the main depth that is important but the terminal depth that qsearch reaches when it returns the evaluation score, my program doesn't keep track of this, this is something I have to add.

With chess we see some diminishing returns with increased search-depth when doubling the number of nodes visited, but not by much, maybe draughts behaves differently, I guess Fabien already checked this. When I have my self-play module ready I will try to do some experiments regarding this phenomena.

Joost

[BertTuyt]

Joost, Im quite interested in some tests to really understand how the underlying model could look like.

Maybe going deeper reveals some secrets.
Next to that maybe Fabien can make a simple evaluation where iso the patterns one only uses piece-square tables (maybe for some game phases), next to the additional items which we need to provide global balance (like piece distribution).

As stated in a previous post, the generic model could look like :

R = R0 * ( 1- f(d)*g(e)), Where R0 is maximum rating, and d = depth, and e evaluation strength.

for d --> infinite and e --> infinite f(d) and g(e) approach 0.

Maybe (quite sure) there are many more alternatives.

If this model is okish, I expect that the increase in rating (as a function of search depth) is (slightly) dependant on the evaluation

If we (however) also assume that f(d) and g(e) can be expressed as a exponential function (also a wild guess based on nothing), and that we are far from the optimum, than:

R = R0 * ( 1- exp(-d/d0)*exp(-e/e0)) d/d0 << 1 and e/e0 << 1

R ~ R0 * ( 1 - ( 1- d/d0)(1-e/e0))

R ~ R0 * ( d/d0 + e/e0)


Bert

[Catherine]

Joost, Im quite interested in some tests to really understand how the underlying model could look like.

Maybe going deeper reveals some secrets.
Next to that maybe Fabien can make a simple evaluation where iso the patterns one only uses piece-square tables (maybe for some game phases), next to the additional items which we need to provide global balance (like piece distribution).

As stated in a previous post, the generic model could look like :

R = R0 * ( 1- f(d)*g(e)), Where R0 is maximum rating, and d = depth, and e evaluation strength.

for d --> infinite and e --> infinite f(d) and g(e) approach 0.

Maybe (quite sure) there are many more alternatives.

If this model is okish, I expect that the increase in rating (as a function of search depth) is (slightly) dependant on the evaluation

If we (however) also assume that f(d) and g(e) can be expressed as a exponential function (also a wild guess based on nothing), and that we are far from the optimum, than:

R = R0 * ( 1- exp(-d/d0)*exp(-e/e0)) d/d0 << 1 and e/e0 << 1

R ~ R0 * ( 1 - ( 1- d/d0)(1-e/e0))

R ~ R0 * ( d/d0 + e/e0)


Bert

Hi Bert,

This is very interesting. I don't know if i can conclude this, but, i notice that if an engine A have a search deep average of 16 plies and an other one has a search deep average of 14 plies; the fisrt engine has 20% of "chance" to beat the second.
It's this little difference of deep between Scan, Kingsrow, Argus, Damage and Dragon that make the number of win so closer.

[Sidiki]

Hi Bert,

This is very interesting. I don't know if i can conclude this, but, i notice that if an engine A have a search deep average of 16 plies and an other one has a search deep average of 14 plies; the fisrt engine has 20% of "chance" to beat the second.
It's this little difference of deep between Scan, Kingsrow, Argus, Damage and Dragon that make the number of win so closer.

Hi all,

I think that this concept of deep search is very important but without a good evaluation function, this is nothing.
I done quickly a game between Scan an Dam 2.2, Scan had 19 pieces against 20 for Dam 2.2.

Dam 2.2 used pondering and 6 pieces egdb with 5 min for 75 moves
Scan 2.0 no pondering and 5 pieces egdb (because i used Damage 2016, i don't know how to import FEN into Scan text mode with the function fen <s>)
Scan won the game.

Sorry, because i don't save the game to proove this, but everybody can do the test.
Just to say that The 4x4 patterns concepts help, like i seeing, to improve the deep and speed search. But the strange thing it's that Dragon use a full 6x6 pattern but it's strongless than Kingsrow and Scan.
Like i said, the eval function and speed node/s contribute to the strenght of an engine
All this to say that a deep search with a good eval function are a big advantage for an engine.

Sidiki

[Joost Buijs]

Just to say that The 4x4 patterns concepts help, like i seeing, to improve the deep and speed search. But the strange thing it's that Dragon use a full 6x6 pattern but it's strongless than Kingsrow and Scan.
Like i said, the eval function and speed node/s contribute to the strenght of an engine
All this to say that a deep search with a good eval function are a big advantage for an engine.

Hi,

The order of importance probably is:

1) Evaluation-quality
2) Branching-factor / search-depth
3) Search-speed

All these things are closely related, a better evaluation-function enables you to prune larger parts of the tree which in turn gives you a lower branching-factor and a greater search-depth. Search-speed is not unimportant either, when doubling your speed (assuming an average branching-factor of 1.5) you will get almost 2 plies extra depth.

I have the feeling that the 6x6 pattern evaluation of Dragon might be better than the 4x4 pattern evaluation used by Scan, somehow Dragon seems to be 5.5 times slower (at least this is what I read somewhere), this will make a difference in search-depth of ~3 plies which in turn has a considerable impact on playing strength.

When done in the usual way calculating the indices for 6x6 patterns will be more than 2 times as slow as calculating them for 4x4 patterns, and the much larger weight-tables will have an enormous impact on the TLB, this might explain why Dragon runs much slower.

As an alternative I'm working on a evaluation-function with 5x5 patterns, in the way I calculate the indices it won't be slower, I have the TLB problem though, but I can largely overcome that by allocating the weight-tables in large-page memory. The evaluation function as such is already finished and I'm working right now on software to tune the weights, this will take at least a couple of weeks (or months since I don't have the time to work on it continuously).

Joost

[MichelG]

...

I have the feeling that the 6x6 pattern evaluation of Dragon might be better than the 4x4 pattern evaluation used by Scan, somehow Dragon seems to be 5.5 times slower (at least this is what I read somewhere), this will make a difference in search-depth of ~3 plies which in turn has a considerable impact on playing strength.

When done in the usual way calculating the indices for 6x6 patterns will be more than 2 times as slow as calculating them for 4x4 patterns, and the much larger weight-tables will have an enormous impact on the TLB, this might explain why Dragon runs much slower.

As an alternative I'm working on a evaluation-function with 5x5 patterns, in the way I calculate the indices it won't be slower, I have the TLB problem though, but I can largely overcome that by allocating the weight-tables in large-page memory. The evaluation function as such is already finished and I'm working right now on software to tune the weights, this will take at least a couple of weeks (or months since I don't have the time to work on it continuously).

Joost

There will be no simple answer why program X is better than program Y. It all depends on the balance between speed and knowledge.

Dragon's has a complicated evaluation function, including global mobility, complex patterns, breakthrough tables and on top of that 6x6 patterns. Recently i also added a bias correction to better correlate evaluation values to measured game-results.

All of this makes the evaluation powerful, but also time consuming. Dragon is running at about 1 to 1.5 m evaluations per second per thread. Even so, it's strength approaches that of scan.

The 6x6 patterns take up a large amount of memory (about 1 gb), and even with large tables, i think the random access time of the memory is the speed-determining factor; any uncached memory access will take 50-100 nanoseconds. There is little you can do about that.

The evaluation function of dragon has a long history, and I am considering rewriting it from scratch to reassess which components are worth the thinking time.

Michel

[Joost Buijs]

...

I have the feeling that the 6x6 pattern evaluation of Dragon might be better than the 4x4 pattern evaluation used by Scan, somehow Dragon seems to be 5.5 times slower (at least this is what I read somewhere), this will make a difference in search-depth of ~3 plies which in turn has a considerable impact on playing strength.

When done in the usual way calculating the indices for 6x6 patterns will be more than 2 times as slow as calculating them for 4x4 patterns, and the much larger weight-tables will have an enormous impact on the TLB, this might explain why Dragon runs much slower.

As an alternative I'm working on a evaluation-function with 5x5 patterns, in the way I calculate the indices it won't be slower, I have the TLB problem though, but I can largely overcome that by allocating the weight-tables in large-page memory. The evaluation function as such is already finished and I'm working right now on software to tune the weights, this will take at least a couple of weeks (or months since I don't have the time to work on it continuously).

Joost

There will be no simple answer why program X is better than program Y. It all depends on the balance between speed and knowledge.

Dragon's has a complicated evaluation function, including global mobility, complex patterns, breakthrough tables and on top of that 6x6 patterns. Recently i also added a bias correction to better correlate evaluation values to measured game-results.

All of this makes the evaluation powerful, but also time consuming. Dragon is running at about 1 to 1.5 m evaluations per second per thread. Even so, it's strength approaches that of scan.

The 6x6 patterns take up a large amount of memory (about 1 gb), and even with large tables, i think the random access time of the memory is the speed-determining factor; any uncached memory access will take 50-100 nanoseconds. There is little you can do about that.

The evaluation function of dragon has a long history, and I am considering rewriting it from scratch to reassess which components are worth the thinking time.

Michel

I agree that there will always be a tradeoff between speed and knowledge and that it is not so easy to determine the optimal balance.

My current evaluation function mimics the 4x4 and 3x6 patterns of Scan, besides this I look at material, wing-balance and mobility (most of it incrementally updated), nothing else. The whole evaluation function runs in roughly 100ns. which translates to 12 to 15 mnps for the search overall on a single core (depending upon the compiler and optimization in use). I determined the running time of the evaluator with RDTSCP(), knowing the clock-frequency of the processor the timing is rather accurate.

I've been thinking about adding a breakthrough-table with magic multiplication, this is easy to do but on the other hand I have the feeling that most of that information is already encoded into the pattern evaluation and that it won't add much besides consuming time. I adhere the KISS principle, the more I can throw out without hurting the program too much the better it feels.

It is my experience that when you have very large randomly accessed tables (>1GB) the slowdown is largely caused by the TLB that gets overstressed and that it helps a lot when you put these tables into large-page memory, maybe your weight-table is not big enough yet to trigger this problem but for things like ML with CG it will certainly help.

Joost

[Joost Buijs]

Hi Caterine, Sidiki,

I see that you are both interested in trying my engine, however there are still a few things I have to do before it is usable, first of all I have to add a configuration file to enable you to change parameters like hash-size, number of threads and so on and I still have to add pondering. Another restriction is that my engine only works as socket-server in DXP follower mode and that I have no intention to add another protocol on a short term (I still have no clue what protocol I need to add to make the engine usable).

When I have some time the coming week I will add a configuration file and pondering and put the executables on my server for download, there will be two versions, one for modern CPU's (>= Intel Haswell) which runs very fast and another one for older CPU's which is approximately 2 to 2.5 times slower. Don't expect too much of it, the fast version is roughly comparable in strength to Kingsrow and the slower version will of course be weaker (actually I never tried).

When I have the executables ready I will post a link where you can download them.

Joost

[Krzysztof Grzelak]

Hi Caterine, Sidiki,

I see that you are both interested in trying my engine, however there are still a few things I have to do before it is usable, first of all I have to add a configuration file to enable you to change parameters like hash-size, number of threads and so on and I still have to add pondering. Another restriction is that my engine only works as socket-server in DXP follower mode and that I have no intention to add another protocol on a short term (I still have no clue what protocol I need to add to make the engine usable).

When I have some time the coming week I will add a configuration file and pondering and put the executables on my server for download, there will be two versions, one for modern CPU's (>= Intel Haswell) which runs very fast and another one for older CPU's which is approximately 2 to 2.5 times slower. Don't expect too much of it, the fast version is roughly comparable in strength to Kingsrow and the slower version will of course be weaker (actually I never tried).

When I have the executables ready I will post a link where you can download them.

Joost

Joost

Something strange and incomprehensible writing for me. Why the program is about 2.5 times slower on some older processors.The only difference should be only in the calculation of the program by the processor, and besides, nothing.

[Joost Buijs]

Something strange and incomprehensible writing for me. Why the program is about 2.5 times slower on some older processors.The only difference should be only in the calculation of the program by the processor, and besides, nothing.

Hi,

I calculate the indices for the pattern evaluation by using the PEXT instruction which is only supported by the latest processors, my evaluator runs several times faster compared to the ones which calculate indices with multiply-add, on older processors I have to emulate the PEXT instruction which makes the program ~2 times slower overall, since this speed is about the same as I get when using multiply-add I will leave it like it is. It is not very useful to add a second index-function which runs at nearly the same speed.

In the nearby future all processors will have this instruction, including the AMD 'RyZen' processor which will be released next month.

After all the speed seems to have very little impact on draughts, out of curiosity I'm running a match with the slow version against Kingsrow and it is still very equal, atm. the standing for Kingsrow is: 2 wins, 1 losses, 50 draws and 7 unknowns. The unknowns are probably due to the fact that I play these matches without EGDB that the games are terminated after 90 moves. Most of the time the programs are shuffling back and forth without seeing any progress when this happens.

Joost

[Krzysztof Grzelak]

Thank you for your answer Joost. Excuse me for asking, when are you going to share your engine to take part in the tournament program.

[Joost Buijs]

Thank you for your answer Joost. Excuse me for asking, when are you going to share your engine to take part in the tournament program.

Hi,

I'm thinking about releasing the executables within a week or so, it depends a little bit upon how much time I have the coming week. I still have to add a configuration file and pondering. I don't know what kind of protocol you need to have my engine taking part of your tournament, at the moment it can only work with DXP in follower mode, maybe you need something else like 'hub' or 'guide' ??? I also want to make DXP a bit more reliable, when it looses the connection it is 'game-over', fortunately Kingsrow runs very stable with DXP and I don't have any problems running matches with that interface.

I stopped the match with the slow version of my program against Kingsrow after 100 games, it scored 48% or ~14 Elo less, this is completely in line with expectations. I expect that tuning the program somewhat better can add some Elo but this is not relevant because in the nearby future I want to change the evaluation-function completely and after this I have to start all over again. For the time being I will leave it like it is.

Joost

[Krzysztof Grzelak]

Hi Joost

For me, the tournament takes place as follows. There are two laptops with processor I3 350M processor with 8 GB of ram. Each of the programs playing on a separate laptop. The program uses its own GUI and base endings as they are. The tournament runs as they play today at the Olympics and in the Championship Netherlands.

[Joost Buijs]

Hi Joost

For me, the tournament takes place as follows. There are two laptops with processor I3 350M processor with 8 GB of ram. Each of the programs playing on a separate laptop. The program uses its own GUI and base endings as they are. The tournament runs as they play today at the Olympics and in the Championship Netherlands.

Hi,

Do you mean that you have to enter all the moves by hand?

I've been thinking about making a simple GUI just to enter moves with the mouse, nothing fancy, I can make that within a couple of days. Or will it be enough when the program runs in console-mode and you have to enter moves as coordinates?

Joost