ENGINE SPEED AND STRONG

[Catherine]

HAPPY NEW YEAR TO EVERYBODY.

I come today to write about speed of node/s and strong of game.
I mean, a friend runned some dxp games beetwen Scan 2.0 and Kingsrow 1.58 with the same condition:

1rst condition
6 egdb
no pondering
15 min/ 75 moves
Perspective for Kingsrow 4 wins, 7 losses, 147 draws, 0 unknowns

KVS 4-7 15min.pdn

(159.37 KiB) Downloaded 881 times

2nd condition
6 egdb
no pondering
1 min/ 75 moves
Perspective for Kingsrow 2 wins, 19 losses, 134 draws, 3 unknowns

KVS 2-19 1min.pdn

(170.78 KiB) Downloaded 863 times

My question is the following: It's the speed of search of the best evaluation wich done the strenght of a engine?

Thank.
PS: I took just these two programs among the best, just to have an idea.
Best regards, Catherine

[TAILLE]

HAPPY NEW YEAR TO EVERYBODY.

I come today to write about speed of node/s and strong of game.
I mean, a friend runned some dxp games beetwen Scan 2.0 and Kingsrow 1.58 with the same condition:

1rst condition
6 egdb
no pondering
15 min/ 75 moves
Perspective for Kingsrow 4 wins, 7 losses, 147 draws, 0 unknowns

KVS 4-7 15min.pdn

2nd condition
6 egdb
no pondering
1 min/ 75 moves
Perspective for Kingsrow 2 wins, 19 losses, 134 draws, 3 unknowns

KVS 2-19 1min.pdn

My question is the following: It's the speed of search of the best evaluation wich done the strenght of a engine?

Thank.
PS: I took just these two programs among the best, just to have an idea.
Best regards, Catherine

Hi Catherine,

I do not quite understand your question.
Obviously if you give more time to a program it becomes stronger but your question seems a little different because you talk about the "speed of the search". If you use a time consuming eval function the speed of the search will of course decrease and you see you have to find the best compromise between evaluation and search. In addition, given an eval function, the search algorithm is very important: if you can evaluate 100 millions of positions before choosing your move, it is essential to try to evaluate 100 millions positions which are really relevant!

[Catherine]

Hi Taille,

Thank very much for taking time to answer to my question that's in others words : why with 15 minutes Scan won only 7 games and with 1 minute won 19. It's seem that some program need more time to 'express themselves'
In others words, deep search in a little is it the key of a good eval fonction or is't positionnal concepts like 4x4 's of Fabien or Roozenburg, classical, Keller....

I take an example of trop programs : program A programmed to search 1.000.000 positions in 3 secondes without any positionnal concept, just brute force like main weapon
and another program B, programmed to search 500.000 positions in 3 secondes with an eval function
focused on positionnal concept and have a good book of classical, Roozenburg, Keller, half classical concept incorporate.

Wich can be the best in speed and or slow match ?
---------------------------------------
Catherine

[TAILLE]

Hi Taille,

Thank very much for taking time to answer to my question that's in others words : why with 15 minutes Scan won only 7 games and with 1 minute won 19. It's seem that some program need more time to 'express themselves'
In others words, deep search in a little is it the key of a good eval fonction or is't positionnal concepts like 4x4 's of Fabien or Roozenburg, classical, Keller....

I take an example of trop programs : program A programmed to search 1.000.000 positions in 3 secondes without any positionnal concept, just brute force like main weapon
and another program B, programmed to search 500.000 positions in 3 secondes with an eval function
focused on positionnal concept and have a good book of classical, Roozenburg, Keller, half classical concept incorporate.

Wich can be the best in speed and or slow match ?
---------------------------------------
Catherine

For my experience I think program A will be better than program B in the endgame (let's us say 8x8 ore less men) but program B will be far better in the beginning and in the middle game. As a consequence program A will have great difficulties to reach a difficult endgame in which it might be able to surpass program B and I am convinced program B will be the best for an entire game.

[Catherine]

Hi Taille

If i understood, for you, program B is the best due to the fact that it will have a good beginning and middle game also due to the fact that it have positionnal eval. Not bad.
Just another question, the strenght of Scan isn't due to his deep search ability ? And it seem that his opening book it's poor but produce a good entire game. Also concept like Keller, Roozenburg and classical aren't specially programmed in his eval function.
The program A for me was the kind of Scan.
Thank again
Catherine

[TAILLE]

Hi Taille

If i understood, for you, program B is the best due to the fact that it will have a good beginning and middle game also due to the fact that it have positionnal eval. Not bad.
Just another question, the strenght of Scan isn't due to his deep search ability ? And it seem that his opening book it's poor but produce a good entire game. Also concept like Keller, Roozenburg and classical aren't specially programmed in his eval function.
The program A for me was the kind of Scan.
Thank again
Catherine

Hi Catherine,

I think you underestimate Scan eval function. If a specific function for classical, Roozenburg, Keller game etc may be very efficient, it is really quite impossible to cover all kind of strategies by a specific treatment. As a consequence Scan eval function may be (far) better than Kingsrow eval function when the position is not clearly in a known and programmed strategy.

Let's take the game 58 won by Scan
After the 32th white move the following position is reached

Black to move

White has a clear advantage due to a far better control of the centre (in one hand Black cannot occupy square 22, 23 or 24 and in the other hand white already occupies square 27 and 29 and in addition white has a good attacking position threatening to advance on new center square). Because Kingsrow lets Scan reached such position my feeling is that Scan has a better understanding of center control and this is confirm by the next black move.
Any human player will immediately see that white is threatening to play 33-28 in order to build an even stronger center and I guess the majority of players will play the logical move 2-8 to reinforce black centre, to avoid 33-28, to develop the strong right wing of black and to avoid playing on the weak left black wing.
Instead of that, black plays the doubtful 11-17 move which misses the opportunity to avoid 33-28 and to reinforce black center. White answers 33-28! forcing black to concede more space in the center and on the right of the board and white advantage increases. Clearly, in such situation Scan eval of the center control is far better than Kingrow's.
Some moves later the following position is reached

Black to move

The centre control of white (24, 27, 28) is impressive and any human player here will see that allowing 28-23 is quite equivalent to give up the game! The move 12-18 is then quite mandatory and do not need a deep analysis because it looks like the only move to try to draw the game.
Instead of that black plays 6-11? and after 28-23! the white position is a winning one. Here again Kingsrow eval function appears quite weak on centre control compare to Scan eval function.

To summarize Scan wins this game because the style of this game (centre control) was dealt in a better way in Scan eval function.

[Rein Halbersma]

I think you underestimate Scan eval function. If a specific function for classical, Roozenburg, Keller game etc may be very efficient, it is really quite impossible to cover all kind of strategies by a specific treatment. As a consequence Scan eval function may be (far) better than Kingsrow eval function when the position is not clearly in a known and programmed strategy.

As far as I know, Kingsrow has a self-tuned machine learning eval similar in spirit to the one by Scan since version 1.58. I think any differences in the eval are due to the way the training positions are created. IIRC, Scan uses more randomized self-play and Kingsrow uses more regular opening book guided positions, but I'm not sure. Maybe Ed can elaborate.

[Catherine]

Hi Taille

I saw that the most wins of Scan are from the center control and those of Kingsrow are classical and attack on piece 24 or 27. I perhaps thought that the main strenght of Scan was his deep search and the principle behind his 4x4 pattern.

Catherine

[BertTuyt]

Hi Taille

I saw that the most wins of Scan are from the center control and those of Kingsrow are classical and attack on piece 24 or 27. I perhaps thought that the main strenght of Scan was his deep search and the principle behind his 4x4 pattern.

Catherine

Interesting remark.
I remember Fabien saying that his worry during the 2015 tournament was attack on outposts, as this could not be covered by the local 4x4 patterns.

Bert

[Joost Buijs]

Strange enough I don't see much difference in playing strength between Scan 2.0 and Kingsrow 1.58, at least not on my machines.

About a week ago Bert ran a match on his 8 core machine between Scan 2.0 and Kingsrow 1.58 and Kingsrow came out with a positive score (+22 Elo), running 158 games is statistically not very significant but it is clear that both engines are in the same league.

I have the feeling that the search of Scan is tuned somewhat better and that Fabian gets away with very aggressive pruning without hurting playing strength too much, maybe this gives a tactical advantage when running on slow hardware or with very short time-controls.

Evaluation wise both engines are very much alike, when you compare scores during a match most of the time there is no more than a few hundreds of a disc difference between both evaluation functions, which is to be expected if Kingsrow uses the same patterns albeit tuned a bit different.

The 4x4 and the 6x3 patterns seem a little bit too small to model all patterns that are known from draughts theory, may be 5x5 would be better and having them overlap is another possibility. When I have my self play module ready I'm certainly going to try using larger patterns.

Joost

[Rein Halbersma]

The 4x4 and the 6x3 patterns seem a little bit too small to model all patterns that are known from draughts theory, may be 5x5 would be better and having them overlap is another possibility. When I have my self play module ready I'm certainly going to try using larger patterns.

Joost

Another way to get larger patterns is to use deep convolutional networks. This means using multiple layers of small (3x3) overlapping patterns. For a 10x10 draughts board, you need about 4 layers to model global positional features (left/right balance, terrain control). However, the number of parameters and memory required quickly increases with the number of layers. During engine searches, the eval could have to compute millions of floating point operations for a such a network. The question is whether the potentially much greater accuracy would outweigh the computational cost.

See http://cs231n.github.io/convolutional-networks/ for a good introduction.

[Catherine]

The 4x4 and the 6x3 patterns seem a little bit too small to model all patterns that are known from draughts theory, may be 5x5 would be better and having them overlap is another possibility. When I have my self play module ready I'm certainly going to try using larger patterns.

Joost

Another way to get larger patterns is to use deep convolutional networks. This means using multiple layers of small (3x3) overlapping patterns. For a 10x10 draughts board, you need about 4 layers to model global positional features (left/right balance, terrain control). However, the number of parameters and memory required quickly increases with the number of layers. During engine searches, the eval could have to compute millions of floating point operations for a such a network. The question is whether the potentially much greater accuracy would outweigh the computational cost.

See http://cs231n.github.io/convolutional-networks/ for a good introduction.

If i understood, the engine that will have an eval function that will take the maximum number patterns into account must be strongest.But this must require a lot of RAM for the computing isn't it?
It's also true that the level between Scan 2.0 and Kingsrow 1.58 are quit the same. i remember that the first dxp matchs between Scan and the previous versions of Kingsrow ended without a lost of Scan.
Kingsrow also integrate the pattern eval that like we seeing it's a great improvment in the draughts computer community.

Catherine.

[Joost Buijs]

The 4x4 and the 6x3 patterns seem a little bit too small to model all patterns that are known from draughts theory, may be 5x5 would be better and having them overlap is another possibility. When I have my self play module ready I'm certainly going to try using larger patterns.

Joost

Another way to get larger patterns is to use deep convolutional networks. This means using multiple layers of small (3x3) overlapping patterns. For a 10x10 draughts board, you need about 4 layers to model global positional features (left/right balance, terrain control). However, the number of parameters and memory required quickly increases with the number of layers. During engine searches, the eval could have to compute millions of floating point operations for a such a network. The question is whether the potentially much greater accuracy would outweigh the computational cost.

See http://cs231n.github.io/convolutional-networks/ for a good introduction.

In the future there will be CPU's with programmable NN inside and only then it will become feasible to use 'deep learning' as they call it nowadays, for the time being I will stick to the usual way of doing things.

The engine I'm working on temporarily uses the same patterns like Scan and Kingsrow, before I release the executable or the source I want to have this replaced by something else. The only thing I have to build is a self play module to produce a large number of games in a short time, gradient descent or conjugate gradient is no problem because in Intel MKL there is a very high performance and heavily optimized HPGC routine build in that runs under MPI.

I still haven't decided how to let the 2 different engines communicate, there are many ways to do this, pipes, sockets, shared memory, RPC etc. Of course the fastest way is to have both engines run in the same process, but having a means to run both engines on different computers seems handy because you can also test the influence of pondering and large egdb.

Joost

[Ed Gilbert]

I still haven't decided how to let the 2 different engines communicate, there are many ways to do this, pipes, sockets, shared memory, RPC etc. Of course the fastest way is to have both engines run in the same process, but having a means to run both engines on different computers seems handy because you can also test the influence of pondering and large egdb.

Joost, why wouldn't you use DXP to create training games for logistic regression, since you already have DXP implemented? I ran 8 simultaneous matches on an 8-core machine to create approximately 1M games this way.

-- Ed

[Joost Buijs]

I still haven't decided how to let the 2 different engines communicate, there are many ways to do this, pipes, sockets, shared memory, RPC etc. Of course the fastest way is to have both engines run in the same process, but having a means to run both engines on different computers seems handy because you can also test the influence of pondering and large egdb.

Joost, why wouldn't you use DXP to create training games for logistic regression, since you already have DXP implemented? I ran 8 simultaneous matches on an 8-core machine to create approximately 1M games this way.
-- Ed

Ed,

Yes... that is a possibility, in that case I have to modify DXP a little to have it accept msec. or usec. timings (maybe your modification already does this?). Lets say that I want to run at least 1 complete game each second, in that case a move will take ~8 msec. for each side, this is still doable over a local socket.

I've only implemented a socket server and DXP in follower mode, I can extend this of course, another option is to build a tourney manager for 2 (or more) engines with a simple GUI (like Little Blitzer for chess), this means extra work but in the end it will make life a lot easier.

Running these games ultra fast is not really needed for the ML part, but I want to have the possibility to check each modification to the engine in a short period of time, lets say within 1 hour or so.

Joost