NNUE

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Sat Mar 19, 2022 11:08

I started a next iteration of the neural-net (NN) implementation.
So far i only used a value-NN for evaluating positions.
However, it is also possible to use a NN (policy-NN) for move-selection, and move-sorting.
This is for example used in leela-zero (chess program), and the Google Go program is also based upon a value- and policy-network.
Although in this case MCTS is used as a search algorithm.

In my case i build a NN for move selection. It (so far) only determines quiet man moves (so no capture and no king moves).
In total for the side to move 81 moves in total (9 rows, 9 moves).
The NN architecture is 90 input (45 positions for white and black), 1st layer 256 neurons, 2nd layer 32, 3th layer 32, and output layer 81.
The NN was trained with the same dataset as for the value-NN, the main difference, that the labels where now the moves (Index) played in the game.

In the current implementation i calculate the moves with white to play, so in case it is black turn i need to mirror the position.
Also i dont use incremental update.

In case of a capture or kings on the board (late middlegame or endgame) the program switches to history for move sorting.

Due to the 2nd NN (which is not incremental updated), the nodes/second (with 1 core) drops to 7.0 mn/s, whereas without the policy implementation i reach around 9.0 mn/s.
In both cases i use avx512, which unfortunately is not supported on many processors, and intel even is switchting this feature off in the new processor family.

Im only starting, so there is much i can (and need) to improve.
But on the other hand it is nice to see that a program can work with (in most cases) history switched off.

I tested this version against KR, conditions 1 core, 1 min/65 moves, 6P DB, and both KR as Damage no book (as i wanted to compare pure algorithms). Result (perspective KR), 7 Win, 1 Lost, 150 Draw, which yields an ELO difference of 13.
This is not (yet) as good as my program without policy-NN which is (only) 5-10 ELO weaker as KR (with similar conditions).

As policy-NN is new for me (and new for Draughts), i need to experiment further before the strength is as good as a history based program, but anyway an interesting exercise.

When both value-NN and policy-NN work optimal, it also enables tools for reinforcement learning, which is a next step, but that will take some time.

Keep you posted.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Sat Mar 19, 2022 16:26

Hi Bert,

Thanks again for this return, it's very awesome to see all these news ideas.

I imagine that the final version will be so stronger.
Can it be, at the end of course, compiled in avx2 or bmi2?

I see also that it's a little weaker than Damage 16.1 NNUE, compared to test result!?

Thanks again for all this awesome job you and the others are doing for our pleasure.

Friendly, Sidiki

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Sat Mar 19, 2022 19:15

Sidiki, yes it is now not as strong as the previous version damage 16.1

Sometimes new ideas do not work immediately, or dont work at all in the end.
History heuristics is a proven approach with limited calulcation overhead, compared with a NN.

So we will see if we can make any significant progress.
But if you never try somthing new, you will never innovate, and we end up doing all the same....

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Mon Mar 21, 2022 10:44

Hi Bert,

It's true that news ideas take sometime a very long time, do to test that must be done, to be efficient.
We are very enjoyed to see that you and the others, bring news ideas in world draughts community.

We hope, and I'm sure that's it will be a great project, because have a win against Kingsrow itsn't so easy. If at the beginning of the project, the engine got a win against Kingsrow, it's a good thing.

Friendly, Sidiki.

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Mon Mar 21, 2022 13:06

Sidiki,

even KR is not perfect, although very close.
The win against KR was based upon a missed combination (by KR) towards a king.
Think this is related to the "heavy" pruning in KR, it is very balanced and most likely very optimized, but once in 100+ games a mistake can occur.
But anyway KR is the absolute benchmark, and although it might be possible to get on par, I assume that due to the strength, winning a 158 games match against KR with a large margin with normal time-control (and multi-core) is totally impossible.

In chess you see constant improvement, im afraid that in Computer Draughts we are already close to the maximum.
Nevertheless I hope that people are still motivated to improve their programs (although it is quite silent in this forum, compared with many years ago).

But the good news, i know that at least 2 people (under the radar screen) are working to implement a neural network in their program.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Mon Mar 21, 2022 13:20

Hi Bert,

Yes, even the strenght of KR, itsn't perfect.
What i was saying it's that if this new draughts approach was so good to take advantage of Kingsrow's mistake and win, it's a good thing.
Damage 16.1 NNUE, Scan 3.1 and Ares are in the same league.
And this compared to the lost rate of this new program compared to KR (used for the test).
Yes, on another point, the forum it's so quiet compared to 2 years ago.
We hope that, compared to many chess forums that I visit, our's will be so animated.

Friendly, Sidiki

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Mon Mar 21, 2022 17:07

I now introduced something which i called delayed policy.
In short, it is common practice (also with history) to play (if available) the tt-move first.
And in many cases this already could give a beta-cutoff.
Therefore there is basically (when the tt-move is valid) no need for move-sorting before the tt-move is played.
Think in Chess this is common practice (and knowledge), not sure all apply this principle in Draughts.

As a history sort is relatively inexpensive, i always applied history movesort at the start of the search.
However as policy calculations are more expensive it makes sense to wait for the tt-move result.

This yielded in my case a real (but not hyper) speed-increase (in terms of nodes/second).

A match against KR (with the same conditions a usual) also confirmed this improvement.

158 games, KR 3 win, 0 Lost, 155 draw, which yields an elo difference of 7.

Think due to statistics this is most likely a too positive result, and next matches will show a slightly worse result.
On the other hand is seems to prove that policy-nn is not completely a dead end, and might have some future potential.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Mon Mar 21, 2022 19:15

Bert,
Wow, what good ideas, this compilation of great ideas, this's draughtsEStein.
From 7 losses to 3, in 3 days this's awesome for a new experience.
It's so clear that tt-move does a background powerful job.
If i understood, if the tt-move it's perfectly synchronised, it give a powerful game.

From what, if itsn't too asked do you think to this great idea ?

Congratulations for this new idea, that i'm sure will be a great success, once again for our pleasure.

God bless you and all the others programers on this forum.

Friendly, Sidiki

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Mon Mar 21, 2022 20:34

Sidiki,

this is not my idea, as i mentioned before this is common practice in Chess.
Maybe it is already used by the other Draughts programmers.
So basically nothing special, relatively straightforward and certainly no rocket science.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Mon Mar 21, 2022 20:51

OK Bert,

Thanks again for taking time for us.
I see, yes of course, as you wrote it, it's an adaptation from chess.
We are very enjoyed to see how it will grow.
And with the speed that things are going, we will be glad to be awarded for the next tests.
We hope that the others will come to say something to support this implementation in draughts community.

Thanks and congratulations,
Friendly, Sidiki

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Mon Mar 21, 2022 22:39

BertTuyt wrote:
Sat Mar 19, 2022 19:15
Sidiki, yes it is now not as strong as the previous version damage 16.1

Sometimes new ideas do not work immediately, or dont work at all in the end.
History heuristics is a proven approach with limited calulcation overhead, compared with a NN.

So we will see if we can make any significant progress.
But if you never try somthing new, you will never innovate, and we end up doing all the same....

Bert
Hi Bert,
Please can we know how this implementation has an impact on the program.
I mean is't more agressive or strategic or both together.

Friendly, Sidiki

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Mon Mar 21, 2022 23:23

Sidiki, i honestly have no clue.
The move sorting is now based upon a neural network, in the past this was history heuristics.
Maybe that now sometimes the search makes another choice, but ballpark i expect the same behavior.
As you have received the latest match games, you can maybe help here.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Thu Mar 24, 2022 00:39

BertTuyt wrote:
Mon Mar 21, 2022 23:23
Sidiki, i honestly have no clue.
The move sorting is now based upon a neural network, in the past this was history heuristics.
Maybe that now sometimes the search makes another choice, but ballpark i expect the same behavior.
As you have received the latest match games, you can maybe help here.

Bert
Hi Bert,

Damage 16.2 it's more agressive and tactically stable.
I love it playing style.
The difference between him and his young brother 16.1, it's that this last one has a reserved and also stable game. It wait that you make a tactical mistake to punish.

Go ahead Bert, congratulations. Damage 16.2 has a good future in your hands.

God bless you and the others programers of this forum.

Friendly, Sidiki

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Re: NNUE

Post by BertTuyt » Thu Mar 24, 2022 11:34

Sidiki,

I believe that in general Draughts programs with a neural network have a good future.
And this combined with reinforcement learning.

Future processors will have more and more cores and neural accelerators, which enable larger networks without penalty in search speed.

For example, see the announement of the Nvidea Grace Superchip (processor with 144 cores).
Certainly too expensive, and not for the normal users, but it shows what is already possible.

Only a pity that a few programmers are working on this, so progress is relatively slow, as we dont learn from each other.

Bert

Sidiki
Posts: 313
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: NNUE

Post by Sidiki » Fri Mar 25, 2022 19:03

Hi Bert,

Yes, i think that, as in chess world that already got a very respectable level with learning. If the programers on this forum, very smarts put together they ideas, certainly, things will grow up quickly.
Joost, Fabien, Ed, Michel, Jaap and the others, please can you try the implementation of this programming option ?

Friendly, Sidiki

Post Reply