Deterministic chess algorithm

[Hood]

Hello,
it is the matter about algorithm which in the same conditions (time, processor, clock) will choose the same move.
What the disturbances have to be eliminated and how to measure the conditions.

Algorithm is sth like optimization task but why it selects differrent solutions in the same position with the same time on move ?
I think that the proposed solutions shall be the same.
There is a lot of noise which disturbs the engine algorithm how to prevent that or eliminate or bypass ?

Rgds
Hood.

[Edmund]

Hello,
it is the matter about algorithm which in the same conditions (time, processor, clock) will choose the same move.
What the disturbances have to be eliminated and how to measure the conditions.

Algorithm is sth like optimization task but why it selects differrent solutions in the same position with the same time on move ?
I think that the proposed solutions shall be the same.
There is a lot of noise which disturbs the engine algorithm how to prevent that or eliminate or bypass ?

Rgds
Hood.

1) adding more processors creates randomness

2) prior information; must be reset before each move to ensure determinism
2.1) Transposition Tables
2.2) Position Learning
2.3) History Tables
2.4) Killer Moves

3) time vs fixed node/depth search; running fixed time creates randomness because the processor might not be used exactly equally much.

4) additional noise eg. not initializing variables properly at startup

[Hood]

1) adding more processors creates randomness

2) prior information; must be reset before each move to ensure determinism
2.1) Transposition Tables
2.2) Position Learning
2.3) History Tables
2.4) Killer Moves

3) time vs fixed node/depth search; running fixed time creates randomness because the processor might not be used exactly equally much.

4) additional noise eg. not initializing variables properly at startup

Thanks for reply.
My task and experiment is to check if the algorithm is deterministic and good or not. Not to write the stronger player which is using history, learning from history etc.

My questions are ?
a. do i need many processors environment ?
b. do i need position learning
c. do i need history tables

I need to select the best move(s) in determined time.
I am starting every time from the scratch with the position on the desk only ?

What is the danger with fixed depth, it shall eliminate time measurement problems.

I am curious if anyone before was testing that problem. It is unbelieveabe that choosing the differrent move in the same position was not mentioned and no one wanted to answer the question ?

rgds Hood

[hyatt]

Hello,
it is the matter about algorithm which in the same conditions (time, processor, clock) will choose the same move.
What the disturbances have to be eliminated and how to measure the conditions.

Algorithm is sth like optimization task but why it selects differrent solutions in the same position with the same time on move ?
I think that the proposed solutions shall be the same.
There is a lot of noise which disturbs the engine algorithm how to prevent that or eliminate or bypass ?

Rgds
Hood.

Let's re-set the stage here.

The basic problem can be summed up in two ways.

(1) if a program searches the same position for the same number of nodes, all else being the same as well, it will play the same move with the same score. But if you let it search only one node more the second time, you may get a different move or score. Or you may change something (killer moves, hash table entries, history counters, etc) that doesn't change this move, but changes the next, or the next. Several of us have run "fixed node" tests, where you tell a program to search exactly 1,000,000 nodes before it makes a move. And it will play the exact same moves, with the exact same scores, game after game after game. But if you change that to let it search 1,000,001 nodes, then most of the time, somewhere in the game, it will choose a different move. It may lead to a different result, or it might not. But the game moves will not be the same.

(2) programs use time to determine how long to search. If their NPS varies by only 1, in a 1 second search, then as above in (1) you will see a difference in the game. Crafty typically searches 25M nodes per second on my 8-core 3-year-old box. which means roughly 1 node every 40 nanoseconds. Or taken another way, if you measure time and use that to stop the search, and you are off by 40 ns, it will play a different game. That's a tiny amount of time. The time taken to handle an interrupt. The time required for an extra cache miss due to different memory pages being used the second time around. Etc. If you can't do something to get the timer resolution/accuracy down to considerably less than that, then complete determinism is hopeless. And since I don't want to disable interrupts and kill everything else (how can someone enter a move while interrupts are disabled among other problems) I don't see any possible solution. If I somehow fix that problem, then how do I guarantee my program uses the same physical set of real pages each time I start it and load it into memory? Operating systems don't do that, so I get to write that code as well. And I eventually have millions of lines of code _besides_ my chess engine, to try to produce that consistency. And I will still fail, most likely, as there are still hardware issues to deal with, such as an occasional memory refresh, or a one cycle bus delay (the hardware is highly asynchronous).

In short, this is a hunt for fool's goal. If you go back to a 1mhz 8086, you might have a chance because instead of 25M nodes per second, we would be talking maybe 1,000 nodes per second (optimistic probably) which means we only need 1ms accuracy in the hardware and we could likely get that. I have run on hardware that took Crafty beyond 100M nodes per second, which gets down to 10ns per node. And it will only get worse as hardware continues to evolve.

[Hood]

Hi,

after time to think over it looks that i will have to return to time measurement issue. Fixed equal depth is OK only when playing the program itself and in that case all games shall be identical. It will be prove for determinism and correctness of the algorithm.

rgds
Hood

[hyatt]

1) adding more processors creates randomness

2) prior information; must be reset before each move to ensure determinism
2.1) Transposition Tables
2.2) Position Learning
2.3) History Tables
2.4) Killer Moves

3) time vs fixed node/depth search; running fixed time creates randomness because the processor might not be used exactly equally much.

4) additional noise eg. not initializing variables properly at startup

Thanks for reply.
My task and experiment is to check if the algorithm is deterministic and good or not. Not to write the stronger player which is using history, learning from history etc.

My questions are ?
a. do i need many processors environment ?
b. do i need position learning
c. do i need history tables

I need to select the best move(s) in determined time.
I am starting every time from the scratch with the position on the desk only ?

What is the danger with fixed depth, it shall eliminate time measurement problems.

I am curious if anyone before was testing that problem. It is unbelieveabe that choosing the differrent move in the same position was not mentioned and no one wanted to answer the question ?

rgds Hood

A few points.

1. For _any_ circumstance, a parallel search will introduce non-determinism. That doesn't mean that given position P, you will get a different move M or different score S every time. But it does mean that you will get a different move or score in a significant number of positions. It doesn't matter whether you play a whole game, or search a single position. DIfferent threads search different parts of the tree, and they execute completely asynchronously. On one run a key hash table entry gets overwritten and changes the search result. In another run, it does not and you get a different result. Sometimes you will search deeper. Why? The so-called "super-linear speedup effect. Take a position where you have several move choices, and one of them is a sacrifice but leads to an almost instant mate. If you search this move first, the rest are quickly pruned by alpha/beta and you are done. If you search this move last, you have to first wade thru the large trees produced by the earlier moves, which changes the hash table, takes far longer, which changes other key data like history counters and such.

Suppose that best move doesn't lead to mate so that the search will continue on to the next iteration. Look at how different things will be if a parallel search is started, and one of the threads picks up that move and quickly finds it is a winner, even before the other earlier moves have been completed. Non-deterministic behaviour ahead.

2. Without SMP search, if you use a time threshold to terminate the search, you get a similar effect. If you search a different number of nodes each time you search the same position, this can produce a different score or move, and also alters the ingoing state to the next search since history counters, killer moves and hash entries get altered.

3. If you search to a fixed depth, this goes away for non-SMP searches, but the instant you add a second thread, the original non-deterministic behaviour comes right back. Ditto for searching a fixed number of nodes rather than using a time limit.

It is just a fact of life in parallel search. It could be eliminated with a lot of work, but the cost in loss of efficiency would be a killer.

[Nale]

How about this?

* Fixed search depth for each thread
* Deterministic assignment of tasks to threads. E.g. you can have them each serach a tree begining with a different node
* Disable interthread communication while searching and give each thread a local cache for transpositions, killer moves, etc. You can combine the tables after each move for better performance, as long as you don't do it while the search is running in any thread.


Edit: Oops, sorry for the necro

[hyatt]

How about this?

* Fixed search depth for each thread
* Deterministic assignment of tasks to threads. E.g. you can have them each serach a tree begining with a different node
* Disable interthread communication while searching and give each thread a local cache for transpositions, killer moves, etc. You can combine the tables after each move for better performance, as long as you don't do it while the search is running in any thread.


Edit: Oops, sorry for the necro

Will not work. How can you guarantee that two independent threads will search exactly the same each time? One processor has to stop to handle an interrupt. That delays that thread by a few microseconds. And now that thread will not yet have had time to store a hash entry that the other thread used the last time. And you get a different result.

Deterministic search is an intractable problem. You can do it, but you are going to slow things down so badly you would likely be better off doing a single-thread search to start with and forget about parallel search.

[Nale]

That's why I suggested not using time based interrupts. Deterministic processing is trivial as long as you are willing to put up with potentially unbounded running times and slightly decreased performance.

[hyatt]

Not "slightly decreased". _significantly_ decreased. Shared hash is a big win.