Komodo 12.3 is out

[lkaufman]

Hi Larry,

why MCTS search in Komodo is non-determinicstic despite using 1 thread only? I see some randomness during the search. Each run gives slightly different output. For example Leela's search is deterministic on single thread. Here is Komodo 12.3 on 1 CPU in starting position:

First run:
0.02: +0.39/9 1.e4 Nc6 2.d4 d5
0.04: +0.35/11 1.e4 e5 2.Nc3 Nc6
0.06: +0.33/12 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6
0.10: +0.28/13 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.O-O
0.18: +0.20/14 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Nc3 Nxe4
0.32: +0.17/15 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.36: +0.18/16 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.50: +0.17/16 1.c4 c5 2.e3 e6 3.a3 Nf6
1.02: +0.20/17 1.c4 c5 2.e3 e6 3.a3 Nf6
1.18: +0.20/17 1.e3 Nf6 2.d4 d5 3.c4 c6 4.cxd5 cxd5
1.56: +0.20/18 1.e3 c5 2.Nf3 d5 3.c4 d4 4.exd4 cxd4 5.b4 a5
3.06: +0.21/19 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
3.46: +0.23/20 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
4.48: +0.20/20 1.Nf3 c5 2.e4 e6 3.c4 Nc6 4.Be2 Nf6 5.Nc3 d5 6.exd5 exd5 7.cxd5
7.24: +0.18/21 1.Nf3 c5 2.e4 e6 3.h3 Nc6 4.Bb5 Nd4 5.Be2 d5 6.Nxd4
8.10: +0.18/22 1.Nf3 c5 2.e4 e6 3.h3 Be7 4.Nc3 Nc6 5.Bb5 Nf6 6.e5

Second run:
0.02: +0.39/9 1.e4 Nc6 2.d4 d5
0.04: +0.35/11 1.e4 e5 2.Nc3 Nc6
0.06: +0.33/12 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6
0.12: +0.25/13 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.O-O
0.18: +0.20/14 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Nc3 Nxe4
0.32: +0.17/15 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.36: +0.17/16 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.52: +0.17/16 1.c4 c5 2.e3 e6 3.a3 Nf6
1.02: +0.20/17 1.c4 c5 2.e3 e6 3.a3 Nf6
1.18: +0.20/17 1.e3 Nf6 2.d4 d5 3.c4 c6 4.cxd5 cxd5
1.56: +0.20/18 1.e3 c5 2.Nf3 d5 3.c4 d4 4.exd4 cxd4 5.b4 a5
3.06: +0.22/19 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
3.44: +0.24/20 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
4.46: +0.20/20 1.Nf3 c5 2.e4 e6 3.c4 Nc6 4.Be2 Nf6 5.Nc3 d5 6.exd5 exd5 7.cxd5
7.20: +0.18/21 1.Nf3 c5 2.e4 e6 3.Nc3 Nc6 4.Bb5 Nd4 5.O-O a6 6.Bd3 Nxf3+ 7.Qxf3
11.04: +0.17/22 1.Nf3 c5 2.e4 e6 3.h3 Nc6 4.Bb5 Nd4 5.Be2 d5 6.d3 Be7

Best
Karol

Maybe Mark has another answer, but since the two outputs are so similar it looks to me just to be due to cutoff being based on time or approximate node counts. With normal komodo on one thread an N ply search should give identical results every time, but with MCTS "Ply" is just an arbitrary function of nodes and I don't believe that an N ply search will always cut off at exactly the same number of nodes. When time is involved, results will very because NPS is not constant.

[mjlef]

Hi Larry,

why MCTS search in Komodo is non-determinicstic despite using 1 thread only? I see some randomness during the search. Each run gives slightly different output. For example Leela's search is deterministic on single thread. Here is Komodo 12.3 on 1 CPU in starting position:

First run:
0.02: +0.39/9 1.e4 Nc6 2.d4 d5
0.04: +0.35/11 1.e4 e5 2.Nc3 Nc6
0.06: +0.33/12 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6
0.10: +0.28/13 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.O-O
0.18: +0.20/14 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Nc3 Nxe4
0.32: +0.17/15 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.36: +0.18/16 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.50: +0.17/16 1.c4 c5 2.e3 e6 3.a3 Nf6
1.02: +0.20/17 1.c4 c5 2.e3 e6 3.a3 Nf6
1.18: +0.20/17 1.e3 Nf6 2.d4 d5 3.c4 c6 4.cxd5 cxd5
1.56: +0.20/18 1.e3 c5 2.Nf3 d5 3.c4 d4 4.exd4 cxd4 5.b4 a5
3.06: +0.21/19 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
3.46: +0.23/20 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
4.48: +0.20/20 1.Nf3 c5 2.e4 e6 3.c4 Nc6 4.Be2 Nf6 5.Nc3 d5 6.exd5 exd5 7.cxd5
7.24: +0.18/21 1.Nf3 c5 2.e4 e6 3.h3 Nc6 4.Bb5 Nd4 5.Be2 d5 6.Nxd4
8.10: +0.18/22 1.Nf3 c5 2.e4 e6 3.h3 Be7 4.Nc3 Nc6 5.Bb5 Nf6 6.e5

Second run:
0.02: +0.39/9 1.e4 Nc6 2.d4 d5
0.04: +0.35/11 1.e4 e5 2.Nc3 Nc6
0.06: +0.33/12 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6
0.12: +0.25/13 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.O-O
0.18: +0.20/14 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Nc3 Nxe4
0.32: +0.17/15 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.36: +0.17/16 1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.O-O
0.52: +0.17/16 1.c4 c5 2.e3 e6 3.a3 Nf6
1.02: +0.20/17 1.c4 c5 2.e3 e6 3.a3 Nf6
1.18: +0.20/17 1.e3 Nf6 2.d4 d5 3.c4 c6 4.cxd5 cxd5
1.56: +0.20/18 1.e3 c5 2.Nf3 d5 3.c4 d4 4.exd4 cxd4 5.b4 a5
3.06: +0.22/19 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
3.44: +0.24/20 1.e3 c5 2.Nf3 a6 3.d4 e6 4.d5
4.46: +0.20/20 1.Nf3 c5 2.e4 e6 3.c4 Nc6 4.Be2 Nf6 5.Nc3 d5 6.exd5 exd5 7.cxd5
7.20: +0.18/21 1.Nf3 c5 2.e4 e6 3.Nc3 Nc6 4.Bb5 Nd4 5.O-O a6 6.Bd3 Nxf3+ 7.Qxf3
11.04: +0.17/22 1.Nf3 c5 2.e4 e6 3.h3 Nc6 4.Bb5 Nd4 5.Be2 d5 6.d3 Be7

Best
Karol

Maybe Mark has another answer, but since the two outputs are so similar it looks to me just to be due to cutoff being based on time or approximate node counts. With normal komodo on one thread an N ply search should give identical results every time, but with MCTS "Ply" is just an arbitrary function of nodes and I don't believe that an N ply search will always cut off at exactly the same number of nodes. When time is involved, results will very because NPS is not constant.

That is right. in Komodo MCTS, there is no iteration by depth like there is in alpha-beta. The "depth" displayed is basically log(MCTS nodes)/constant, which was roughly tuned based on PV lengths of earlier Komodo MCTS. So instead of printing out a PV and stats for each new depth, Komodo MCTS just does it every after every 2 seconds of search, plus whenever the search is completed. So tiny differences in available computer resources will mean small variances in the amount of processing available in any 2 second period. We could consider supporting "go nodes" but since we are not doing that in regular alpha-beta search, it would be a bit confusing. And a "node" means different things in the two search modes.

[carldaman]

Could it possibly make sense to have a future version of Komodo using some cores for MCTS while using the others for regular search? Any potential for such an approach to succeed?

[lkaufman]

Could it possibly make sense to have a future version of Komodo using some cores for MCTS while using the others for regular search? Any potential for such an approach to succeed?

Yes, I actually proposed this at various times. Mark says it is difficult to implement, but difficult does not mean impossible. There are an infinite variety of ways in which the two searches might be combined. But the incentive to try this is less now than before, since it is starting to look likely that MCTS will just surpass normal Komodo without any tricks like this.

[Nordlandia]

As tablebases technology advances. Will it make sense in the near future to allocate 1-core for tablebase handling / probing?.

Allocating 1-core solely for tablebase consuling, with all the benefits for this purpose.

Idea #1: egtb probing can be initiated after intelligent algorithm when it make sense than probing egtb very early in the game and sacrificing speed.

Is this something to consider?

[lkaufman]

As tablebases technology advances. Will it make sense in the near future to allocate 1-core for tablebase handling / probing?.

Allocating 1-core solely for tablebase consuling, with all the benefits for this purpose.

Idea #1: egtb probing can be initiated after intelligent algorithm when it make sense than probing egtb very early in the game and sacrificing speed.

Is this something to consider?

Maybe I misunderstand your idea, but if you are just trying to save the time it takes to determine whether we are down to seven men or less on the board when an evaluation is done, that amount of time is too tiny to be of interest.

[Dann Corbit]

Has splitting the cores between MCS and ordinary alpha-beta been tried?

It looks to me like the MCS version is fast at finding a stable, good move and the alpha-beta version solves tricky positions faster.

[lkaufman]

Has splitting the cores between MCS and ordinary alpha-beta been tried?

It looks to me like the MCS version is fast at finding a stable, good move and the alpha-beta version solves tricky positions faster.

I've been keen on that idea for years, long before we even started on MCTS, but it's not simple to implement and it's far from clear how to combine them. Since our MCTS version already uses short alpha-beta searches we already combine them to some extent now. I suppose if we stall out on MCTS we might try this, but so far no sign of that happening.

[Werewolf]

Has splitting the cores between MCS and ordinary alpha-beta been tried?

It looks to me like the MCS version is fast at finding a stable, good move and the alpha-beta version solves tricky positions faster.

I've been keen on that idea for years, long before we even started on MCTS, but it's not simple to implement and it's far from clear how to combine them. Since our MCTS version already uses short alpha-beta searches we already combine them to some extent now. I suppose if we stall out on MCTS we might try this, but so far no sign of that happening.

Dreaming a bit here but could this work: run MCTS on the GPU, alpha beta on the CPU cores. Both have the same E.F, the one with the higher eval gets picked?

Edit: or more refined - the MCTS always gets picked except when the alpha-beta one is a certain amount greater, say +1.00 (for tricky positions)

[lkaufman]

Has splitting the cores between MCS and ordinary alpha-beta been tried?

It looks to me like the MCS version is fast at finding a stable, good move and the alpha-beta version solves tricky positions faster.

I've been keen on that idea for years, long before we even started on MCTS, but it's not simple to implement and it's far from clear how to combine them. Since our MCTS version already uses short alpha-beta searches we already combine them to some extent now. I suppose if we stall out on MCTS we might try this, but so far no sign of that happening.

Dreaming a bit here but could this work: run MCTS on the GPU, alpha beta on the CPU cores. Both have the same E.F, the one with the higher eval gets picked?

Edit: or more refined - the MCTS always gets picked except when the alpha-beta one is a certain amount greater, say +1.00 (for tricky positions)

MCTS doesn't use GPU, neural networks do, and we don't currently use neural networks. Splitting the cores of CPU that way is possible, but the benefit is less clear than you might think, because Komodo MCTS is already pretty good tactically though it coud be better.