ENGINE SPEED AND STRONG

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Catherine
Posts: 129
Joined: Tue Aug 14, 2012 22:24
Real name: Catherine Bourneuf

ENGINE SPEED AND STRONG

Post by Catherine » Sat Jan 07, 2017 06:59

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 134 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 124 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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: ENGINE SPEED AND STRONG

Post by TAILLE » Tue Jan 10, 2017 20:04

Catherine wrote: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!
Gérard

Catherine
Posts: 129
Joined: Tue Aug 14, 2012 22:24
Real name: Catherine Bourneuf

Re: ENGINE SPEED AND STRONG

Post by Catherine » Tue Jan 10, 2017 22:43

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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: ENGINE SPEED AND STRONG

Post by TAILLE » Tue Jan 10, 2017 23:23

Catherine wrote: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.
Gérard

Catherine
Posts: 129
Joined: Tue Aug 14, 2012 22:24
Real name: Catherine Bourneuf

Re: ENGINE SPEED AND STRONG

Post by Catherine » Wed Jan 11, 2017 00:56

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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: ENGINE SPEED AND STRONG

Post by TAILLE » Wed Jan 11, 2017 16:00

Catherine wrote: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
Image
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
Image
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.
Gérard

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: ENGINE SPEED AND STRONG

Post by Rein Halbersma » Wed Jan 11, 2017 17:42

TAILLE wrote: 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
Posts: 129
Joined: Tue Aug 14, 2012 22:24
Real name: Catherine Bourneuf

Re: ENGINE SPEED AND STRONG

Post by Catherine » Wed Jan 11, 2017 21:40

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
Posts: 1303
Joined: Wed Sep 01, 2004 19:42

Re: ENGINE SPEED AND STRONG

Post by BertTuyt » Wed Jan 11, 2017 22:23

Catherine wrote: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
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: ENGINE SPEED AND STRONG

Post by Joost Buijs » Fri Jan 13, 2017 21:29

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
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: ENGINE SPEED AND STRONG

Post by Rein Halbersma » Fri Jan 13, 2017 22:34

Joost Buijs wrote: 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
Posts: 129
Joined: Tue Aug 14, 2012 22:24
Real name: Catherine Bourneuf

Re: ENGINE SPEED AND STRONG

Post by Catherine » Sat Jan 14, 2017 02:14

Rein Halbersma wrote:
Joost Buijs wrote: 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
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: ENGINE SPEED AND STRONG

Post by Joost Buijs » Sat Jan 14, 2017 07:47

Rein Halbersma wrote:
Joost Buijs wrote: 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
Posts: 748
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: ENGINE SPEED AND STRONG

Post by Ed Gilbert » Sat Jan 14, 2017 14:17

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
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: ENGINE SPEED AND STRONG

Post by Joost Buijs » Sat Jan 14, 2017 16:06

Ed Gilbert wrote:
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

Post Reply