UCT surprise for checkers !

[Daniel Shawul]

For my Go program I wanted to try out UCT ( Upper Confidence bounds applied to Trees )
and did a quick implementation of the algorithm. To my disapointement, it only searches
depth = 3 for a 9x9 go with the default UCTK coefficient sqrt(1/5) ~ 0.44. Lowering that value
did not improve it that much. It can reach depth=8 with UCTK = 0.1. It got beaten by heavy reducing alpha-beta searcher quite easily.

Algorithm is described here http://senseis.xmp.net/?UCT

So I decided to change games, and wanted to try it on checkers. Earlier I had a monte-carlo
program which did random playouts from the root only i.e d = 1 (without expanding promising children).
I noticed even that resulted in a decent checkers playing program due to
- forced nature of captures. The montecarlo playout will not likely miss out on tactics
here unlike the case of Go and other games, where there could be only one good move
out of 80 f.i
- Narrow tree so deeper UCT tree (less likely to miss tactics). If the tactics got resolved
strategy, the UCT would be better as it brings distant information. The alpha-beta searcher
had only material eval. And also at the tips the UCT searcher uses the same eval to decide
if terminal nodes are WDL.

I think this two combined have given it a good strength. This was really surprising to m
I did only a partial playout i.e when the MC playout reaches MAX_PLY I stop and decide the game
based on material. If it is close , I assign draw otherwise win or loss.

It got a draw on my first game and it was even winning for most of the game. Agains an alpha-beta
searcher averaging a depth = 25 !!


Here is the game which you can replay using winboard and NebiyuCheckers !

Code: Select all

[FEN "1p1p1p1p/p1p1p1p1/1p1p1p1p/8/8/P1P1P1P1/1P1P1P1P/P1P1P1P1 w - - 0 1"]

1.a3b4 b6a5 2.b2a3 a7b6 3.a1b2 b6c5 4.e3d4 c5e3 5.f2d4 d6e5 6.g3f4 e5g3 7.h2f4 f6g5 8.g1h2 g5e3 
9.d2f4 g7f6 10.e1d2 f6g5 11.b4c5 g5e3 12.d2f4 h8g7 13.c1d2 g7f6 14.f4e5 f6g5 15.c5b6 e7d6 16.e5f6 d6c5 
17.d4e5 c5d4 18.f6g7 g5f4 19.g7h8Q d4e3 20.h8g7 e3c1q 21.g7f6 f8e7 22.f6g7 f4e3 23.g7f8 e3f2 24.f8d6 f2e1q 
25.h2g3 e1f2 26.c3d4 f2h4 27.d6e7 d8f6 28.b6d8Q f6g5 29.e5f6 g5f4 30.f6e7 f4g3 31.e7f8Q g3h2 32.d4e5 h6g5 
33.f8e7 g5f4 34.e5f6 f4e3 35.f6g7 e3d2 36.b2c3 d2e1q 37.c3d4 h2g1q 38.d4e5 e1f2 39.g7h8Q f2g3 40.e5f6 g3f4 
41.f6g7 f4g5 42.e7d6 g5h6 43.g7f8Q g1h2 44.d6c5 c1b2 45.c5d4 h2g1 46.h8g7 h4g3 47.d4e5 g3f2 48.g7f6 g1h2 
49.f8e7 h2g3 50.e7d6 f2e3 51.f6e7 e3d2 52.e5d4 g3f2 53.e7f6 d2e3 54.d4e5 f2g3 55.f6e7 g3h2 56.e7f6 h2g3 
57.f6e7 g3h2 58.e5f6 e3f2 59.d8c7 h2g3 60.e7d8 g3h4 61.f6e5 f2g3 62.d8e7 h4g5 63.e5f6 g5h4 64.f6e5 h6g5 
65.e5d4 g3f2 66.c7d8 f2g3 67.d6e5 g5f4 68.e7d6 h4g5 69.d8c7 g5h4 70.e5f6 f4g5 71.f6e5 g5h6 72.e5f6 h6g5 
73.f6e5 b2a1 74.d4c3 g5h6 75.e5d4 h6g7 76.c7b6 g7f8 77.d6e5 h4g5 78.a3b4 g5f4 79.e5d6 f8g7 80.d6e7 b8a7 
81.b6c5 g7f8 82.e7d6 g3f2 83.d4e5 f2g3 84.e5d4 g3f2 85.d4e5 f2g3 86.e5f6 g3h4 87.f6e5 h4g3 88.e5f6 g3h4 
89.f6e5 h4g3 90.e5d4 g3f2 91.d4e5 f4e3 92.c3d4 a5c3 93.d4b2 a1c3 94.c5b6 a7c5 95.d6b4,b4d2,d2f4 f8e7 96.f4g5 f2e1 
97.g5h4 e7f8 98.h4g5 e1f2 99.g5f4 f8e7 100.f4g5 f2g1 101.g5h4 e7d8 102.h4g3 g1h2 103.g3f4 d8c7 104.f4e3 h2g1 
105.e5f6 c7d6 106.f6g5 g1h2 107.g5f4 h2g1 108.e3d2 g1f2 109.d2e1 f2g1 110.f4e3 g1h2 111.e1f2 h2g1 112.f2g3 g1h2 
113.e3d4 h2f4 
1/2-1/2

Parital log for the UCT engine

Code: Select all

Description :
    Tree : nodes 31485 depth 17 pps 40412
    nodes -> the maximum number of nodes in the dynamic tree
    depth -> the maximum UCT depth
    pps -> playouts per second (40k in this case)

<000000000547>setboard 1p1p1p1p/p1p1p1p1/1p1p1p1p/8/8/P1P1P1P1/1P1P1P1P/P1P1P1P1 w - - 0 1
<000000000563>computer
<000000000563>name NebiyuCheckers_1.2
Hello NebiyuCheckers_1.2!
<000000003360>time 12000
<000000003360>otim 11715
<000000003360>usermove a3b4
<000000003360>go
[st = 2813ms, mt = 59250ms , moves_left 40]
Tree : nodes 31485 depth 17 pps 40412
h6g5 0.49 1018 2068
f6e5 0.49 788 1615
f6g5 0.48 552 1148
d6c5 0.48 505 1055
d6e5 0.48 535 1114
b6a5 0.52 55241 106005
b6c5 0.48 619 1281
<000000006188>move b6a5

<000000008360>time 11717
<000000008360>otim 11498
<000000008360>usermove b2a3
[st = 2816ms, mt = 57835ms , moves_left 39]
Tree : nodes 32633 depth 24 pps 41839
h6g5 0.51 828 1630
c7b6 0.52 2723 5207
a7b6 0.55 58035 106048
f6e5 0.52 1881 3623
f6g5 0.45 116 255
d6c5 0.46 123 269
d6e5 0.50 649 1289
<000000011188>move a7b6

<000000014031>time 11434
<000000014031>otim 11214
<000000014031>usermove a1b2
[st = 2820ms, mt = 56420ms , moves_left 38]
Tree : nodes 32633 depth 22 pps 42241
b6c5 0.62 73362 117503
h6g5 0.37 12 34
b8a7 0.37 12 34
f6e5 0.55 220 400
f6g5 0.56 309 550
d6c5 0.53 122 232
d6e5 0.57 427 748
<000000016860>move b6c5

<000000019281>time 11151
<000000019281>otim 10972
<000000019281>usermove e3d4
[st = 2824ms, mt = 55005ms , moves_left 37]
Tree : nodes 34048 depth 27 pps 43077
c5e3 0.62 75066 121866
<000000022110>move c5e3

<000000024781>time 10868
<000000024781>otim 10704
<000000024781>usermove f2d4
[st = 2828ms, mt = 53590ms , moves_left 36]
Tree : nodes 34173 depth 21 pps 44428
h6g5 0.57 766 1341
b8a7 0.53 187 350
c7b6 0.51 96 189
f6e5 0.57 682 1198
f6g5 0.59 2322 3954
d6c5 0.57 859 1498
d6e5 0.62 72537 117159
<000000027610>move d6e5

<000000029813>time 10585
<000000029813>otim 10484
<000000029813>usermove g3f4
[st = 2831ms, mt = 52175ms , moves_left 35]
Tree : nodes 36202 depth 22 pps 44323
e5g3 0.63 79156 126010
<000000032656>move e5g3

<000000032750>time 10301
<000000032750>otim 10475
<000000032750>usermove h2f4
[st = 2835ms, mt = 50755ms , moves_left 34]
Tree : nodes 36431 depth 22 pps 45030
h6g5 0.38 13 36
b8a7 0.61 1664 2728
e7d6 0.59 487 831
c7b6 0.57 245 434
c7d6 0.56 187 336
f6e5 0.62 4294 6915
f6g5 0.63 74130 116787
<000000035594>move f6g5

<000000037844>time 10017
<000000037844>otim 10250
<000000037844>usermove g1h2
[st = 2840ms, mt = 49335ms , moves_left 33]
Tree : nodes 36431 depth 30 pps 46479
g5e3 0.67 88986 132188
<000000040688>move g5e3

<000000040797>time 9732
<000000040797>otim 10239
<000000040797>usermove d2f4
[st = 2844ms, mt = 47910ms , moves_left 32]
Tree : nodes 36431 depth 26 pps 44874
h6g5 0.55 82 150
b8a7 0.46 23 50
g7f6 0.67 75419 112648
e7d6 0.37 10 27
e7f6 0.66 5681 8663
c7b6 0.62 458 742
c7d6 0.65 3481 5343
<000000043641>move g7f6

<000000048078>time 9448
<000000048078>otim 9795
<000000048078>usermove e1d2
[st = 2849ms, mt = 46490ms , moves_left 31]
Tree : nodes 36863 depth 23 pps 47816
f6e5 0.65 10560 16202
f6g5 0.66 72651 110111
h6g5 0.49 42 86
h8g7 0.63 1118 1782
f8g7 0.56 113 204
b8a7 0.65 4651 7201
e7d6 0.58 203 349
c7b6 0.55 103 188
c7d6 0.60 381 633
<000000050938>move f6g5

<000000054860>time 9162
<000000054860>otim 9403
<000000054860>usermove b4c5
[st = 2853ms, mt = 45060ms , moves_left 30]
Tree : nodes 36863 depth 25 pps 46410
g5e3 0.66 87218 132687
<000000057719>move g5e3

<000000057813>time 8876
<000000057813>otim 9394
<000000057813>usermove d2f4
[st = 2857ms, mt = 43630ms , moves_left 29]
Tree : nodes 36863 depth 25 pps 47963
h6g5 0.43 15 36
a5b4 0.52 47 92
h8g7 0.70 89308 128223
f8g7 0.55 77 141
b8a7 0.65 4027 6209
e7d6 0.61 359 590
e7f6 0.57 123 216
c7b6 0.44 17 40
c7d6 0.63 998 1580
<000000060672>move h8g7

<000000063141>time 8590
<000000063141>otim 9147
<000000063141>usermove c1d2
[st = 2863ms, mt = 42200ms , moves_left 28]
Tree : nodes 36863 depth 21 pps 45668
g7f6 0.71 91454 129379
h6g5 0.36 7 21
a5b4 0.53 39 75
b8a7 0.64 590 928
e7d6 0.62 285 461
e7f6 0.41 12 29
c7b6 0.27 3 13
c7d6 0.61 239 390
<000000066016>move g7f6

<000000070000>time 8302
<000000070000>otim 8748
<000000070000>usermove f4e5
[st = 2868ms, mt = 40760ms , moves_left 27]
Tree : nodes 36863 depth 26 pps 45062
f6g5 0.68 79275 116576
h6g5 0.65 4207 6493
a5b4 0.23 3 13
f8g7 0.65 3158 4896
b8a7 0.63 918 1464
e7d6 0.46 26 57
c7b6 0.36 9 25
c7d6 0.38 11 30
<000000072875>move f6g5

<000000075735>time 8015
<000000075735>otim 8462
<000000075735>usermove c5b6
[st = 2873ms, mt = 39325ms , moves_left 26]
Tree : nodes 36863 depth 39 pps 41254
g5f4 0.67 8871 13223
g5h4 0.66 3354 5061
a5b4 0.54 65 120
f8g7 0.66 2626 3978
b8a7 0.64 734 1149
e7d6 0.68 64442 94887
e7f6 0.52 47 90
c7d6 0.53 52 98
<000000078610>move e7d6

<000000081625>time 7727
<000000081625>otim 8161
<000000081625>usermove e5f6
[st = 2878ms, mt = 37885ms , moves_left 25]
Tree : nodes 36863 depth 28 pps 40133
d6c5 0.71 80337 113916
d6e5 0.58 91 156
g5f4 0.44 15 35
g5h4 0.56 61 110
a5b4 0.55 56 101
f8e7 0.66 932 1416
f8g7 0.56 61 109
d8e7 0.31 5 16
b8a7 0.59 99 168
<000000084516>move d6c5

Log for alpha-beta searcher. Deep searcher (depth = 25 opening and may reach 50 sometiems).

setup (P...Q.p...q.) 8x8+0 1p1p1p1p/p1p1p1p1/1p1p1p1p/8/8/P1P1P1P1/1P1P1P1P/P1P1P1P1 w - - 0 1
<000000000500>level 40 2 0
<000000000500>post
<000000000500>hard
<000000000500>easy
<000000004984>option montecarlo=0
<000000009516>force
<000000010047>computer
<000000010047>name NebiyuCheckers_1.2
Hello NebiyuCheckers_1.2!
<000000010047>time 12000
<000000010047>otim 12000
<000000010047>go
[st = 2813ms, mt = 59250ms , moves_left 40]
[0] 2 0 0 42 a3b4 h6g5
[0] 3 0 0 164 a3b4 b6c5 b2a3
[0] 4 -5 0 429 g3f4 d6e5 f4d6 c7e5
[0] 5 15 0 683 g3f4 b6c5 e3d4 c5e3 f2d4
[0] 5 15 0 790 g3f4 b6c5 e3d4 c5e3 f2d4
[0] 6 5 0 1111 g3f4 b6c5 h2g3 d6e5 f4d6 c7e5
[0] 6 5 0 1562 g3f4 b6c5 h2g3 d6e5 f4d6 c7e5
[0] 7 15 0 2311 g3f4 b6c5 h2g3 a7b6 e3d4 c5e3 f2d4
[0] 7 15 0 2779 g3f4 b6c5 h2g3 a7b6 e3d4 c5e3 f2d4
[0] 8 -15 0 3442 g3f4 b6c5 h2g3 a7b6 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5
[0] 8 -15 0 6617 g3f4 b6c5 h2g3 a7b6 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5
[0] 9 -15 0 7694 g3f4 b6c5 h2g3 a7b6 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5
[0] 9 15 0 13618 a3b4 b6c5 b2a3 a7b6 a1b2 f6g5 e3d4 c5e3 d2f4 g5e3 f2d4
[0] 9 15 0 13777 a3b4 b6c5 b2a3 a7b6 a1b2 f6g5 e3d4 c5e3 d2f4 g5e3 f2d4
[0] 10 15 0 15288 a3b4 b6c5 b2a3 a7b6 a1b2 f6g5 e3d4 c5e3 d2f4 g5e3 f2d4
[0] 10 15 1 16489 a3b4 b6c5 b2a3 a7b6 a1b2 f6g5 e3d4 c5e3 d2f4 g5e3 f2d4
[0] 11 5 1 21612 a3b4 b6c5 b2a3 a7b6 a1b2 b6a5 g3f4 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 11 5 1 24143 a3b4 b6c5 b2a3 a7b6 a1b2 b6a5 g3f4 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 12 -5 1 30523 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 12 -5 1 34367 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 13 15 1 45336 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 e3d4 g5e3 d2f4 c5e3 f2d4
[0] 13 15 3 50083 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 e3d4 g5e3 d2f4 c5e3 f2d4
[0] 14 5 3 64858 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 h2g3 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 14 5 3 74549 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 h2g3 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 15 15 4 111322 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 h2g3 h8g7 e3d4 c5e3 f2d4 g5e3 d2f4
[0] 15 15 6 122058 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 a1b2 g7f6 h2g3 h8g7 e3d4 c5e3 f2d4 g5e3 d2f4
[0] 16 15 7 165930 a3b4 b6c5 b2a3 f6g5 g3f4 g7f6 h2g3 h8g7 c3d4 g5h4 d4b6 c7a5c3 d2b4 a7b6 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 16 15 7 182148 a3b4 b6c5 b2a3 f6g5 g3f4 g7f6 h2g3 h8g7 c3d4 g5h4 d4b6 c7a5c3 d2b4 a7b6 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 17 5 10 253756 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 c7b6 c1b2 f6g5 c3d4 a5c3 d2b4 e7f6 b2c3 f6e5 d4f6 g7e5
[0] 17 5 12 284318 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 c7b6 c1b2 f6g5 c3d4 a5c3 d2b4 e7f6 b2c3 f6e5 d4f6 g7e5
[0] 18 10 14 348571 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 c7b6 c1b2 f6g5 c3d4 a5c3 d2b4 e7f6 g3h4 f6e5 d4f6 g7e5g3 h4f6
[0] 18 10 15 389083 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 c7b6 c1b2 f6g5 c3d4 a5c3 d2b4 e7f6 g3h4 f6e5 d4f6 g7e5g3 h4f6
[0] 19 10 21 536137 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 g1f2 h6g5 f4h6 e5d4 c3e5 a5c3 d2b4 d6f4h2
[0] 19 10 25 603970 a3b4 b6c5 b2a3 a7b6 g3f4 b6a5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 g1f2 h6g5 f4h6 e5d4 c3e5 a5c3 d2b4 d6f4h2
[0] 20 0 37 958920 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 h2g3 e7f6 c3d4 b6a5 d4b6 a5c3 d2b4 c7a5c3 c1d2 d6e5 d2b4 d8c7 f4d6 c7e5
[0] 20 0 76 1960256 a3b4 b6c5 b2a3 f6g5 g3f4 a7b6 h2g3 e7f6 c3d4 b6a5 d4b6 a5c3 d2b4 c7a5c3 c1d2 d6e5 d2b4 d8c7 f4d6 c7e5
[0] 21 5 93 2400877 a3b4 b6c5 b2a3 f6g5 g3f4 g7f6 h2g3 h8g7 a1b2 g5h4 e3d4 c5e3 f2d4 h4f2 e1g3 d6c5 d4b6 a7c5 b4d6 c7e5 f4d6 e7c5
[0] 21 5 96 2507968 a3b4 b6c5 b2a3 f6g5 g3f4 g7f6 h2g3 h8g7 a1b2 g5h4 e3d4 c5e3 f2d4 h4f2 e1g3 d6c5 d4b6 a7c5 b4d6 c7e5 f4d6 e7c5
[0] 22 5 129 3364274 a3b4 f6e5 b2a3 g7f6 g3f4 e5g3 h2f4 b6c5 c1b2 h8g7 f2g3 f6e5 c3d4 e5c3 b2d4b6 a7c5 a1b2 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 22 5 145 3785320 a3b4 f6e5 b2a3 g7f6 g3f4 e5g3 h2f4 b6c5 c1b2 h8g7 f2g3 f6e5 c3d4 e5c3 b2d4b6 a7c5 a1b2 d6e5 f4d6 c7e5 b4d6 e7c5
[0] 23 5 170 4422398 a3b4 f6e5 b2a3 g7f6 g3f4 e5g3 h2f4 d6e5 f4d6 c7e5 f2g3 h8g7 g1h2 d8c7 e3d4 c7d6 a1b2 b6c5 d4b6 a7c5 g3f4 e5g3 h2f4
[0] 23 5 190 4981012 a3b4 f6e5 b2a3 g7f6 g3f4 e5g3 h2f4 d6e5 f4d6 c7e5 f2g3 h8g7 g1h2 d8c7 e3d4 c7d6 a1b2 b6c5 d4b6 a7c5 g3f4 e5g3 h2f4
nodes = 7420001 <31 qnodes> time = 2844ms nps = 2609001
splits = 0 badsplits = 0
<000000012891>move a3b4

<000000015719>time 11715
<000000015719>otim 11717
<000000015719>usermove b6a5
[st = 2816ms, mt = 57825ms , moves_left 39]
[0] 2 5 0 75 e3d4 f6e5 d4f6 g7e5
[0] 3 10 0 214 b2a3 d6c5 b4d6 c7e5
[0] 4 10 0 265 b2a3 d6c5 b4d6 c7e5
[0] 5 10 0 610 b2a3 a7b6 a1b2 d6c5 b4d6 c7e5
[0] 5 10 0 924 b2a3 a7b6 a1b2 d6c5 b4d6 c7e5
[0] 6 10 0 1171 b2a3 a7b6 a1b2 d6c5 b4d6 c7e5
[0] 6 10 0 1288 b2a3 a7b6 a1b2 d6c5 b4d6 c7e5
[0] 7 25 0 2289 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4
[0] 7 25 0 2572 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4
[0] 8 20 0 3668 b2a3 f6g5 a1b2 g5f4 g3e5 d6f4 e3g5 h6f4
[0] 8 20 0 4287 b2a3 f6g5 a1b2 g5f4 g3e5 d6f4 e3g5 h6f4
[0] 9 15 0 6395 b2a3 a7b6 c1b2 d6c5 b4d6 e7c5 c3b4 a5c3 b2d4
[0] 9 15 0 7230 b2a3 a7b6 c1b2 d6c5 b4d6 e7c5 c3b4 a5c3 b2d4
[0] 10 20 0 10701 b2a3 a7b6 g3f4 d6c5 b4d6 e7c5 c3b4 a5c3 d2b4d6 c7e5g3 h2f4
[0] 10 20 1 12114 b2a3 a7b6 g3f4 d6c5 b4d6 e7c5 c3b4 a5c3 d2b4d6 c7e5g3 h2f4
[0] 11 20 1 14098 b2a3 a7b6 g3f4 d6c5 b4d6 e7c5 c3b4 a5c3 d2b4d6 c7e5g3 h2f4
[0] 11 20 1 16027 b2a3 a7b6 g3f4 d6c5 b4d6 e7c5 c3b4 a5c3 d2b4d6 c7e5g3 h2f4
[0] 12 20 1 24131 b2a3 a7b6 a1b2 f6g5 e3d4 d6e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 12 20 1 26512 b2a3 a7b6 a1b2 f6g5 e3d4 d6e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 13 15 1 31659 b2a3 a7b6 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 13 15 1 36007 b2a3 a7b6 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 14 15 3 53911 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 h6g5 h4f6 g7e5
[0] 14 15 3 61449 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 h6g5 h4f6 g7e5
[0] 15 15 3 71453 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 b8c7 g1f2 h6g5 h4f6 g7e5
[0] 15 15 4 82830 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 b8c7 g1f2 h6g5 h4f6 g7e5
[0] 16 15 4 98381 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 b8c7 g1f2 h6g5 h4f6 g7e5
[0] 16 15 4 115811 b2a3 a7b6 a1b2 f6e5 g3f4 e5g3 h2f4 d6c5 b4d6 c7e5g3 f2h4 b8c7 g1f2 h6g5 h4f6 g7e5
[0] 17 15 6 157947 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 g3f4 c7d6 c3d4 f8e7 b2c3 b8c7 c1b2 f6e5 d4f6 g7e5g3 h2f4
[0] 17 15 7 185217 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 g3f4 c7d6 c3d4 f8e7 b2c3 b8c7 c1b2 f6e5 d4f6 g7e5g3 h2f4
[0] 18 25 10 268923 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 f8e7 f2e3 e7d6 g1f2 b6c5 c1d2 d6e5 f4d6 c7e5
[0] 18 25 12 306553 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 f8e7 f2e3 e7d6 g1f2 b6c5 c1d2 d6e5 f4d6 c7e5
[0] 19 10 17 407451 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5 g3f4 e5g3 h2f4 d6e5 f4d6 c7e5 d2e3 e5f4 e3g5 h6f4
[0] 19 10 23 569463 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5 g3f4 e5g3 h2f4 d6e5 f4d6 c7e5 d2e3 e5f4 e3g5 h6f4
[0] 20 20 28 685799 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 e7g5 g1f2 d8e7 d2e3 c7b6 g3h4 g5f4 e3g5 h6f4 f2e3 f4d2 c1e3
[0] 20 20 31 771223 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 e7g5 g1f2 d8e7 d2e3 c7b6 g3h4 g5f4 e3g5 h6f4 f2e3 f4d2 c1e3
[0] 21 20 37 935595 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 e7g5 g1f2 d8e7 d2e3 c7b6 g3h4 g5f4 e3g5 h6f4 f2e3 f4d2 c1e3
[0] 21 20 42 1071783 b2a3 a7b6 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 e7g5 g1f2 d8e7 d2e3 c7b6 g3h4 g5f4 e3g5 h6f4 f2e3 f4d2 c1e3
[0] 22 20 62 1583281 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 d8e7 f2e3 f6e5 f4d6 e7c5 c1d2 f8e7 g1f2 e7d6 g3f4 d6e5 f4d6 c7e5
[0] 22 20 70 1793784 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 d8e7 f2e3 f6e5 f4d6 e7c5 c1d2 f8e7 g1f2 e7d6 g3f4 d6e5 f4d6 c7e5
[0] 23 20 96 2483209 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 d8e7 f2e3 f6e5 f4d6 e7c5 c1d2 f8e7 g3f4 e7d6 h2g3 g7f6 e1f2 d6e5 f4d6 c7e5
[0] 23 20 107 2791257 b2a3 a7b6 a1b2 d6c5 b4d6 e7c5 e3d4 c5e3 d2f4 d8e7 f2e3 f6e5 f4d6 e7c5 c1d2 f8e7 g3f4 e7d6 h2g3 g7f6 e1f2 d6e5 f4d6 c7e5
[0] 24 5 179 4685376 b2a3 a7b6 a1b2 h6g5 e3f4 g5e3 f2d4 f6e5 d4f6 e7g5 d2e3 g7h6 g3h4 f8e7 h4f6 e7g5 h2g3 h8g7 e1f2 d8e7 g3f4 g7f6 c1d2 b6c5
[0] 24 5 217 5653811 b2a3 a7b6 a1b2 h6g5 e3f4 g5e3 f2d4 f6e5 d4f6 e7g5 d2e3 g7h6 g3h4 f8e7 h4f6 e7g5 h2g3 h8g7 e1f2 d8e7 g3f4 g7f6 c1d2 b6c5
nodes = 5653811 <30 qnodes> time = 2172ms nps = 2603043
splits = 0 badsplits = 0
<000000017891>move b2a3

<000000020719>time 11498
<000000020719>otim 11434
<000000020719>usermove a7b6
[st = 2836ms, mt = 56740ms , moves_left 38]
[0] 2 0 0 51 a1b2 h6g5
[0] 3 20 0 140 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 4 20 0 204 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 5 20 0 288 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 5 20 0 347 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 6 20 0 497 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 6 20 0 534 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 7 20 0 694 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 7 20 0 748 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5
[0] 8 5 0 940 a1b2 h6g5 b4c5 b6d4 c3e5 d6f4 g3e5 f6d4 e3c5
[0] 8 5 0 978 a1b2 h6g5 b4c5 b6d4 c3e5 d6f4 g3e5 f6d4 e3c5
[0] 9 5 0 1185 a1b2 h6g5 b4c5 b6d4 c3e5 d6f4 g3e5 f6d4 e3c5
[0] 9 5 0 1201 a1b2 h6g5 b4c5 b6d4 c3e5 d6f4 g3e5 f6d4 e3c5
[0] 10 20 0 3682 a1b2 f6g5 e3d4 d6e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 10 20 0 3698 a1b2 f6g5 e3d4 d6e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 11 15 0 4478 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 11 15 0 4494 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 12 15 1 6300 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 12 15 1 6316 a1b2 f6g5 e3d4 d6c5 b4d6 c7e5 d4f6 g7e5 g3f4 g5e3 f2d4f6 e7g5
[0] 13 20 1 23849 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 b8c7 e1f2 f6g5 h4f6 g7e5
[0] 13 20 1 23865 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 b8c7 e1f2 f6g5 h4f6 g7e5
[0] 14 25 1 27747 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 f6e5 g1f2 e5f4 e3g5 h6f4
[0] 14 25 1 27763 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 f6e5 g1f2 e5f4 e3g5 h6f4
[0] 15 20 1 38679 a1b2 b6c5 e3d4 c5e3 d2f4 c7b6 f2e3 f6g5 c1d2 d8c7 g1f2 g7f6 f4e5 d6f4 g3e5g7 h8f6
[0] 15 20 3 38695 a1b2 b6c5 e3d4 c5e3 d2f4 c7b6 f2e3 f6g5 c1d2 d8c7 g1f2 g7f6 f4e5 d6f4 g3e5g7 h8f6
[0] 16 10 3 65555 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5 c7d6 g3f4 d6b4 f4h6 e7d6 h2g3 b8c7 d2e3 b4d2 e1c3
[0] 16 10 3 65571 a1b2 h6g5 b4c5 b6d4 e3c5 d6b4 a3c5 c7d6 g3f4 d6b4 f4h6 e7d6 h2g3 b8c7 d2e3 b4d2 e1c3
[0] 17 5 4 74353 a1b2 h6g5 e3f4 g5e3 f2d4 f6e5 d4f6 e7g5 d2e3 g7h6 c1d2 b6c5 g1f2 b8a7 g3h4 g5f4 e3g5 h6f4
[0] 17 5 4 74369 a1b2 h6g5 e3f4 g5e3 f2d4 f6e5 d4f6 e7g5 d2e3 g7h6 c1d2 b6c5 g1f2 b8a7 g3h4 g5f4 e3g5 h6f4
[0] 18 0 4 96870 a1b2 h6g5 e3f4 g5e3 f2d4 f6e5 d4f6 e7g5 d2e3 g7h6 g3f4 d6e5 f4d6 c7e5 g1f2 g5f4 e3g5 h6f4
[0] 18 5 10 270526 g3f4 b6c5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 c1b2 c7b6 g1h2 h8g7 g3h4 e5g3 h2f4 b6c5 h4g5 d6e5 f4d6 h6f4
[0] 18 5 10 270530 g3f4 b6c5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 c1b2 c7b6 g1h2 h8g7 g3h4 e5g3 h2f4 b6c5 h4g5 d6e5 f4d6 h6f4
[0] 19 10 12 295897 g3f4 b6c5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 c1b2 c7b6 g1h2 d8c7 d2e3 h8g7 e3d4 g7f6 g3h4 e5g3 h2f4
[0] 19 10 12 299639 g3f4 b6c5 h2g3 f6e5 e3d4 c5e3 f2d4f6 g7e5 c1b2 c7b6 g1h2 d8c7 d2e3 h8g7 e3d4 g7f6 g3h4 e5g3 h2f4
[0] 20 5 17 404024 g3f4 b6c5 h2g3 c7b6 c1b2 f6e5 g1h2 d8c7 g3h4 e5g3 h2f4 g7f6 f2g3 h8g7 c3d4 a5c3 d2b4 d6e5 f4d6 c7e5c3 b4d6 e7c5 b2d4
[0] 20 5 17 417612 g3f4 b6c5 h2g3 c7b6 c1b2 f6e5 g1h2 d8c7 g3h4 e5g3 h2f4 g7f6 f2g3 h8g7 c3d4 a5c3 d2b4 d6e5 f4d6 c7e5c3 b4d6 e7c5 b2d4
[0] 21 0 23 578951 g3f4 b6c5 h2g3 c7b6 c3d4 a5c3 d2b4 f6e5 d4f6 g7e5 a1b2 e7f6 b2c3 h8g7 c1d2 b8c7 g1h2 f8e7 g3h4 e5g3 h2f4
[0] 21 0 45 1138289 g3f4 b6c5 h2g3 c7b6 c3d4 a5c3 d2b4 f6e5 d4f6 g7e5 a1b2 e7f6 b2c3 h8g7 c1d2 b8c7 g1h2 f8e7 g3h4 e5g3 h2f4
[0] 22 0 54 1407590 g3f4 b6c5 h2g3 c7b6 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5 d2e3 h8g7 g1h2 b6c5 g3h4 e5g3 h2f4 g7f6 c1b2 f6e5 c3d4 e5c3 b2d4b6 a5c3
[0] 22 0 67 1696342 g3f4 b6c5 h2g3 c7b6 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5 d2e3 h8g7 g1h2 b6c5 g3h4 e5g3 h2f4 g7f6 c1b2 f6e5 c3d4 e5c3 b2d4b6 a5c3
[0] 23 0 87 2247718 g3f4 b6c5 c3d4 a5c3 d4b6 c7a5 d2b4 a5c3 h2g3 d8c7 c1d2 f6e5 d2b4 g7f6 b4c5 d6b4 f4d6 c7e5 a3c5 h6g5 g3f4 e5g3 f2h4
[0] 23 0 103 2678014 g3f4 b6c5 c3d4 a5c3 d4b6 c7a5 d2b4 a5c3 h2g3 d8c7 c1d2 f6e5 d2b4 g7f6 b4c5 d6b4 f4d6 c7e5 a3c5 h6g5 g3f4 e5g3 f2h4
[0] 24 0 123 3212507 g3f4 b6c5 c3d4 a5c3 d4b6 c7a5 d2b4 a5c3 h2g3 d8c7 c1d2 f6e5 d2b4 g7f6 a1b2 h8g7 e1d2 d6c5 b4d6 e7c5 f4d6 c7e5 e3f4 e5d4
[0] 24 15 207 5444505 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 b8c7 a3b4 c7d6 g1f2 f6e5 b2a3 g7f6 e3d4 f6g5 d4f6 f8g7 f2e3 g7e5 h4f6 e7g5
[0] 24 15 212 5560846 a1b2 d6e5 g3f4 e5g3 h2f4 b6c5 b4d6 c7e5g3 f2h4 b8c7 a3b4 c7d6 g1f2 f6e5 b2a3 g7f6 e3d4 f6g5 d4f6 f8g7 f2e3 g7e5 h4f6 e7g5
[0] 25 10 264 6909727 a1b2 b6c5 e3d4 c5e3 f2d4 f6e5 d4f6 g7e5 b4c5 d6b4 a3c5 h6g5 d2e3 e5f4 g3e5 h8g7 e3d4 e7d6 c5e7 f8d6f4 e1d2 d8e7 d2e3 f4d2 c1e3
nodes = 7452107 <27 qnodes> time = 2843ms nps = 2621212
splits = 0 badsplits = 0
<000000023562>move a1b2

[Daniel Shawul]

Wow this algorithm is really good at capturing long term strategy.
My alpha-beta searcher can't keep up with in the following games, in order of decreasing performance

- Amazons (really pathetic performance by the alpha-beta searcher). Look
at this total anhilation by the UCT searcher

Code: Select all

[FEN "3a2a3/10/10/a8a/10/10/A8A/10/10/3A2A3 w - - 0 1"]

1.g0g3,g3g2 g9g6,g6h7 2.a3c5,c5c2 d9d8,d8f6 3.c5e5,e5e1 g6e8,e8j8 4.d0d4,d4b4 a6f1,f1j1 5.j3h3,h3h5 j6g9,g9b9 6.d4e3,e3c1 f1g1,g1f1 7.h3i4,i4i2 g9e9,e9g7 8.e5d5,d5d7 d8a5,a5a9 
9.e3i7,i7g9 e8g6,g6g5 10.g3f4,f4j0 g1h2,h2f0 11.i7i6,i6i8 h2h3,h3g3 12.i4g4,g4j4 g6e4,e4e7 13.f4e5,e5b8 e4e2,e2e3 14.e5e6,e6f7 a5a3,a3c3 15.d5f5,f5f3 e9c9,c9c5 16.e6c6,c6c8 e2d3,d3c4 
17.g4d4,d4g4 h3i3,i3i5 18.c6e6,e6a6 a3a4,a4c6 19.i6j6,j6j5 c9e9,e9c7 20.j6g6,g6i6 e9e8,e8d8 21.e6e4,e4e6 e8f8,f8h8 22.e4f4,f4e4 f8g8,g8f8 23.f4e5,e5d5 g8f9,f9e9 24.e5f4,f4d6 f9e8,e8f9 
25.g6h6,h6i7 e8d9,d9c9 26.f5g6,g6f5 d9e8,e8d9 27.f4e5,e5f4 a4a5,a5b5 

- Reversi I do not have too much eval except mobility for the alpha-beta searcher. In two games I did quickly UCT won

- checkers I would say they are more or less equal. This was really surprising for me because I thought checkers was more closer to chess than anything else..

- Go It is starting to work for me now especially in the endgame. I think the improvement was not as impressive for go because I spent some time working on the alpha-beta engine with some strategic terms as well.

- chess this is the _only_ game I implemented where UCT sucks.

[Daniel Shawul]

I found a paper which literally confirms my observation ! I swear I didn't read it before I made my post

"Simulation-Based Approach to General Game Playing"
Hilmar Finnsson and Yngvi Bjornsso http://www.aaai.org/Papers/AAAI/2008/AAAI08-041.pdf

They discuss UCT and mentioned in their conclustions that it works best for convergin games such as Amazons, go etc.. and also that it doesn't for that well for chess.
This is really a good algorithm for general game playing programs (GGP), if you don't want to get involved with the details of the nature of the game. This is my goal for Nebiyu !
Their GGP gets the rules of the game at run time and uses UCT with some king of learing to play the game well. I am amazed really.
You should be too if you think alpha-beta is the "alpha-omega" of game play

Sorry for the self-talk. But I welcome comments and discussions.

[bob]

I think the idea works pretty well for a program with an ill-defined evaluation. An eval for GO is very difficult to do. Chess and checkers, however, I do not believe fit this approach. you should first have a go at chinook, which you can probably get a copy of from Jonathan Schaeffer. It is a hellishly strong checker player. Strongest in the world in fact if you use his endgame databases since it has solved the game. But even without them, Tinsley was amazed at the strength of the thing. And it was a traditional searcher...

[Michel]

I do not understand how the playouts work in Monte Carlo search. Do both sides really do completely random moves?

[Daniel Shawul]

Agreed about the ill defined eval. But I think it works very well too for any 'converging' game. This is also confirmed by the paper I gave a link to. The game of Amazons has a branching factor of ~3000 but average game length of 80. The monte carlo agent really outperforms the alpha beta searcher there.

Checkers, I thought for a long time , was little brother of chess. But it is different due to the 'converging' nature of game due to the captures!
Yngvi Bjornsson's paper has this same conclusion and they mentioned checkers as one of the good applications. I found also other papers where UCT is used for multi-player games such as chineese checkers, and pretty much the only option in stochastic games etc... Very general and yet very fantastic. Also the monte-carlo playouts do not make too many tactical mistakes in checkers, since at the point where you have a capture, you do not have non-captures to confuse it. I am going to try similar idea in CHESS and give bigger weight to the captures so they be played more often..

Chinook also benefited a lot from its TBs because the game converges. However I do not think there are that many evaluation terms in checkers. Infact I read somewhere that 'kingsrow' (very strong checkers program ,2nd to chinook I guess) has only a few eval terms configurable from a GUI. Also a loss of one checker is almost game over in checkers.. I use this fact to quickly end the playouts . After MAX_PLY = 96 , I force game termination and do a material eval and return either a WDL score. I think checkers has many features suitable for UCT

Code: Select all

   - converging
   - forced captures improving random MC playouts. You have to do pattern matching and other staff in Go
   - even if the game was not converging, the fact that a loss of one checker is game over means, you can terminate the playouts early without going to the real end of the game. Chinook uses EGTBs which can be used for ending random playouts.

I think that for the international checkers version played on by 10x10 UCT would give alpha-beta a run for its money , atleast !

[Daniel Shawul]

Smarter (heavy) playouts are preferable but the light playout version is pretty competitive too. If the game reaches a won/loss state quickly, you can gather a lot of strategic information by doing many quick simulations of a random or biased playout. The method is also used in strategic war games !

[bob]

I do not understand how the playouts work in Monte Carlo search. Do both sides really do completely random moves?

No. But there has to be a randomness factor thrown in so that you don't play the same game over and over.

[zamar]

I do not understand how the playouts work in Monte Carlo search. Do both sides really do completely random moves?

There are two versions:

- light: (almost) completely random.
- heavy: game-specific knowledge is applied to move selection.

[Michel]

There are two versions:

- light: (almost) completely random.
- heavy: game-specific knowledge is applied to move selection.

Thanks.

In chess I do not see how a light playout could give any information at all. The randomness of the subsequent moves would quickly obliterate any strength differences between the initial moves.

For light playouts to work games should have mostly non-reversible moves it seems to me. Then the effect of a bad move has some permanence.