kobanium / ray Goto Github PK

View Code? Open in Web Editor NEW

70.0 10.0 81.0 96.04 MB

Computer go engine using Monte-Carlo Tree Search (MCTS)

License: BSD 2-Clause "Simplified" License

Makefile 0.16% C++ 99.84%

ray go weiqi baduk mcts monte-carlo-tree-search

ray's People

Contributors

Stargazers

Watchers

ray's Issues

Can't run ray9.0

After add SearchBoard.cpp in include I suceed compiled it on VC++2015. but ray.exe crashed when I type genmove b. Don't know why

Some question about Gumbel learning.

Yuki Kobayashi,

After reading the paper and source code, I am still a bit confused.

1. What's the Q value?

With Gumbel-Top-k trick, we select the best $A_{t+1}$ child in the $argtop(g + logits, m)$. The $A_{t+1}$ is $argmax(g(a) + logits(a) + \sigma(q(a)))$ [Algorithm 2]. What's Q value? Is it just a average win-rate?

2. What's the completed Q?

The paper says $completedQ = q(a), v_{\pi}$ [Formula (10)]. But seem that the source implementation is $completedQ = (C_{visit} + max_{b}N(b))* C_{scale} * q(a)$ [Formula (8)]. What's the correct completed Q formula?

Thanks!

Ray cannot treat draw simulations

Ray assumes that komi is floating point.
It causes unstable behavior when komi is a integer number.

Virtual Loss does not work

Time Management Error

Using "--const-time" option and "--thread" option at the same time,
Ray consume time as much as the number of thread on Windows OS.

e.g. ) "./ray --const-time 5 --thread 4"
Ray considers 20 seconds at the first move.

Ray becomes weaker

Source

Question about Progressive Widening

Yuki Kobayashi:

According to your paper, I try to add the Progressive Widening in the MCTS. But I find the PV string is too long. Here is it. It is just only around 5000 playouts. I think it is weird result (The most visits child is PV node). The PV string length of Ray in the same condition is 2~4 (use lz-analyze with Sabaki).

Here is my simple implementation.

Progressive Widening

The recursive formula is

$t_{n+1} = t_n + 40 \times 1.4 n,\ t_0 = 0$

Assume $k$ is opened children number of current node. The $v$ is visits number of current node. It must be satisfied

$t_{k-1} < v < t_{k}$

UCT Selection

The UCT formula is borrowed from Ray.

$UCT_i = Q_i + C_{param} \sqrt{ \frac{ \Sigma n_a }{ n_i + 1 } } + 0.35 \times rate \times \sqrt{ \frac{1000}{1000 + \Sigma n_a} }$

$\Sigma n_a$ means the visits of current node.
$rate$ means the MM priority (already be normalized).

Search ordering

I order the child by MM priority. The best priority will be opened first.

I have no ideal what's wrong. What should I doubt first? Thanks!

Superko

Ray cannot recognize positional-superko.

Support CGOS player mode

Resignation threshold

This is a great engine. Is there a way to adjust the threshold of the engine resigning? I find that it rather resigns too quickly - when playing against other engines of course, not myself I always lose against it. Thanks

The life and death estimation gets wrong

TheSgfFile.zip

genmove b
Time Limit    : 5 Sec
Playout Limit : 100000000 PO
      A   B   C   D   E   F   G   H   J   K   L   M   N   O   P   Q   R   S   T
   +----------------------------------------------------------------------------+
19:| 97  98  98  98  97  91  50  12   3   2   2   2   3   3   3   3   4   5   5 |
18:| 95  98  98  98  98  99  57   2   2   2   4   1   6   2   2   2   3   5   5 |
17:| 82  99  99  99  94  99   2   2  99   2  29  43  48   0   1   1   0   5   5 |
16:| 42   5  99   6  53  99  99  99  99  99  64  68  91   0   1   0   1   6   5 |
15:|  7   5   5   6   6  99  98  97  94  90  85  83  91  91   0   0   0   4   4 |
14:|  3  10  45  57  98  97  96  94  90  87  83  81  53   8   9   3   7   1   2 |
13:|  0   0 100  92  96  97  96  95  88  74  81  91  53   8   9   7   7   1   1 |
12:|  0   0 100  97 100  98  98  99  99  59  11  50  44   8   9   9   0   1   2 |
11:|  0   0 100 100 100 100  98  96  99  63  30   2   6  11   0   4   0   2   6 |
10:|  0   0   0   0 100  98  98  96  99  82  59  50   0   3   0   0   1   5   9 |
 9:|  0   0 100 100 100 100 100  96  96  99  99  99  46   0   0   0   0   0  23 |
 8:|  1   1   1 100  99  99  98  98  96  99  96  99  68  50   0   0  89  89  60 |
 7:|  2   1   1 100 100 100 100  98  96  99  96  99  99  99   0  77  69  86  84 |
 6:|  5   4   1   1 100 100 100  99  96  96  96  96  96  99  50  69  89  92  93 |
 5:|  9  12  42  52 100 100  96  96  96  96  96  96  99  99  99  99  99  99  97 |
 4:|  9   9  99  99  99  99  99  96  96  96  96  96   0  99   0  56   1   1  97 |
 3:| 10  11  11  99  99  99  99  96  96  96  96  96   0  99   0   0  12  95  95 |
 2:| 10  10  70  99  96  96  96  96  96  96  96  96   0   0   0   0   0   0  95 |
 1:| 22  57  84  99  99  99  99  96  96  96  96  96  26   0   0   0   0   0  21 |
   +----------------------------------------------------------------------------+
BLACK+38.5
Best Sequence : L13(BLACK : 12698/13563)->K13(WHITE : 404/5171)->K14(BLACK : 2698/2872)->J13(WHITE : 72/945)->K12(BLACK : 447/474)->J14(WHITE : 8/146)->J15(BLACK : 87/90)
Prisoner(Black) : 2
Prisoner(White) : 4
Move : 210
     A B C D E F G H J K L M N O P Q R S T
   +---------------------------------------+
19:| + + + + + + + + + + + + + + + + + + + |
18:| + + + + + B + W W W + W + + + + + + + |
17:| + B B B + B W W B W + + + W + + W + + |
16:| + W B W + B B B B B + + B W + W + B + |
15:| + W W W W B + + B + + + B B W + W + + |
14:| + + + + B + + + W B + + + W B + B W + |
13:| + W B + + + + + W W B B + W + + B W + |
12:| + W B + B + + B B B W + + W B B W + + |
11:| + W B B + B + W B + + W + B W + W + + |
10:| + W W W B W + W B + + + W + W + + + + |
 9:| + W B B B B B W W B B B + W + + W W + |
 8:| + + W B + + W B W B W B + + W W B B + |
 7:| + + W B + B B + W B W B B B W B + + + |
 6:| + + W W B + B + W W W W W B + + + + + |
 5:| + + + + B B W W W B W W B B B B B B + |
 4:| + W B B + W B W W B B B W B W + W W B |
 3:| + + W B B B B W B B W B W B W W + B + |
 2:| + W + B W W W W W B W B W W + W W W B |
 1:| + + + B B B B W W B + B + W + W + W + |
   +---------------------------------------+
All Playouts       :    17854
Pre Simulated      :        0
Win                :    16679
Thinking Time      :    5.001 sec
Winning Percentage :  93.4188%
Playout Speed      :     3570 PO/sec 
= L13

At this position, black is already dead, but it still thinks the black group is alive and the winning percentage is high.

Compiling error in V.S 2019 windows 10 system

Need help. Thanks

Ladder

When the opponent escape captured ladder, ray is too pessimistic.
https://twitter.com/xevixevi/status/806525835368808448

I made quick fix, but this may spoil some useful ladder.
zakki@d0ff2bf

Crash report

Hi， I found an unexpected crash after the move by ray version 11 and 10.3. the ray9.01 is OK. Thanks.

err.zip
e2.sgf.zip

Question about MM algorithm.

Hello, Yuki Kobayashi! I am Hung-Zhe Lin. I raise the new issue here instead of email because it is more easy to write Latex here.

On the Paper

After seeing your and Remi's implementations, I guess that there are some differences between the theories and the implementation. In the paper, simply it says that

$\gamma_{new} = \frac{W}{Den}$
$Den=\sum{\frac{C}{E}}$
$E=C*\gamma_{old}+D$

where W is the hyperparameter for each gammas.
where C is the participants which relate to $\gamma_{old}$.
where D is the participants which do not relate to $\gamma_{old}$.

Yours

(it is simplification formula, ignore i and j)

$\gamma_{new} = \frac{win + 1}{\sigma + V}$
$\sigma = \sum{\frac{C}{E}}$
$E=\sum{G}$
$V=\frac{2}{1 + \gamma_{old}}$

where G is the legal move gammas in this turn (per move).
where E is all gammas in this turn (per move).

I know that it update the new $\gamma$ after gathering all $\sigma$ and $\gamma$ , I skip this process.

Remi's

(it is simplification formula, ignore i and j)

$\gamma_{new} = \frac{win + 1}{\sigma + V}$
$\sigma = \sum{\frac{C}{E}}$
$E=\sum{G}$
$V=\frac{2}{1 + \gamma_{old}}$

where G is each updating participants gammas in this updating step.
where E is all relation gammas in this updating step.

Question

Look like that your implementations and updating conditions are differences with paper. Why? Or may I wrong?

Ownership and Criticality bug when pondering option is effective

B>> genmove b
Reuse : 61016 Playouts
Time Limit    : 120 Sec
Playout Limit : 475101 PO
Reuse : 237943 Playouts
      A   B   C   D   E   F   G   H   J   K   L   M   N   O   P   Q   R   S   T
   +----------------------------------------------------------------------------+
19:| 33  20  16  13  11  11  15  29  29  33  53  79 103 122 131 135 134 133 132 |
18:| 73  20  33  10  10  10  10  10  32  29  59  90 115 111 141 134 136 132 130 |
17:|110 146  33 152 152 152  10  10  30   6  91  91   6 129 123 141 136 130 129 |
16:|140 146 107 107 107 152 152 152   6   6   6   6   6  56 106 151 135 128 125 |
15:|137 141 143 139 152 152 132 127  78  55  40  34  38  59  97 123 124 120 120 |
14:|120 134 151 135 122 116 117 122 134  96  68  52  55  69  86 105 111 114 115 |
13:| 88  93 104 106  94  79  88 102  94  83  60  52  54  67  83  97 111 113 114 |
12:| 54  56  69  88  69  46  69  84  68  46  45  40  41  59  86 102 116 117 115 |
11:| 30  27  27 104 103   3  48  91  10  19  10  42  10  54  89 109 133 117 111 |
10:| 28  29  29   3   3   3  32  51  15  23  10  42  10  59 116  95 101 101  97 |
 9:| 19  14   0  10   3   7   8   6   6  23  24   7  30  52  50  75  75  78  78 |
 8:|  7   4   0  10  10  10  10  10  10   0   0  31  46  71  56  51  51  56  63 |
 7:|  5   0   1   1   1  10   0   0   0   0  53  53  43  39  21  21  21  60  68 |
 6:| 46   0   0 133   1   1  14  32  30   0   0  53  34  46  32  72 149 111  98 |
 5:|102 133 133 133  58  50  45  72  60  65 141  23  23  23  26  23 149 142 132 |
 4:|121 125 128 133 133  44 102 102 107 116 141 141  81  23  23  23 149 146 144 |
 3:|122 124 126 122 108 125 115 147 131 131 134 135 139 139  23  23 149 146 146 |
 2:|124 125 124 119 117 117 129 136 136 132 132 130 126  87  23 149 149 146 146 |
 1:|124 125 123 120 117 120 127 133 134 132 130 125 110  67  51 109 147 148 146 |
   +----------------------------------------------------------------------------+
BLACK+99.5
Best Sequence : O9(BLACK : 70395/250850)->Q10(WHITE : 44248/60234)->Q9(BLACK : 9304/33800)->R10(WHITE : 8765/11962)->Q11(BLACK : 2076/7478)->S10(WHITE : 1703/2342)->R9(BLACK : 153/517)->S9(WHITE : 287/400)->P8(BLACK : 44/137)
Prisoner(Black) : 1
Prisoner(White) : 1
Move : 142
     A B C D E F G H J K L M N O P Q R S T
   +---------------------------------------+
19:| + + + + + + + B + + + + + + + + + + + |
18:| + W + W W W W W B + + + B W B + + + + |
17:| + B W B B B W W B W B B W B + + + + + |
16:| + B + W W B B B W W W W W + + B + + + |
15:| + + + + B B + + + + + + + + + + + + + |
14:| + + B + + + + + B + + + + + + + + + + |
13:| + + + + + + + + + + + + + + + + + + + |
12:| + + + + + + + + + + + + + + + + + + + |
11:| + W W B B W + B W + W B W + + B B + + |
10:| + B B W W W + + + B W B W + B W W W + |
 9:| + + W B W + + W W B B W + B + B B W + |
 8:| + + W B B B B B B W W + + B B + + + + |
 7:| + W + W W B W W W W B B + + W W W + + |
 6:| + W W B W W + + + W W B + B + + B + + |
 5:| + B B B + + + + + + B W W W + W B + + |
 4:| + + + B B W + + + + B B + W + W B + + |
 3:| + + + + W B + B + + + + B B W W B + + |
 2:| + + + + + + + + + + + + + + W B B + + |
 1:| + + + + + + + + + + + + + + + + + + + |
   +---------------------------------------+
All Playouts       :   290128
Pre Simulated      :    61016
Win                :    79998
Thinking Time      :   57.854 sec
Winning Percentage :  27.5733%
Playout Speed      :     3960 PO/sec

B>> genmove b
Reuse : 691 Playouts
Time Limit    : 120 Sec
Playout Limit : 526264 PO
Reuse : 222502 Playouts
      A   B   C   D   E   F   G   H   J   K   L   M   N   O   P   Q   R   S   T
   +----------------------------------------------------------------------------+
19:| 38  23  18  15  12  11  15  30  30  35  55  84 111 129 140 145 145 145 142 |
18:| 86  22  37  11  11  11  11  11  33  29  60  92 123 117 151 145 148 142 139 |
17:|129 171  37 182 182 182  11  11  29  17  93  93  17 135 128 154 148 139 135 |
16:|164 171 122 122 122 182 182 182  17  17  17  17  17  55 112 168 145 133 127 |
15:|160 166 168 164 182 182 156 153 106  75  58  69  68  75 110 133 127 115 112 |
14:|141 158 179 159 145 137 137 148 177 127  96 130 123 111 101 111 104  98  94 |
13:|104 110 123 124 110  93 100 119 133 147 134 174 174 100  90  91  92  75  75 |
12:| 64  66  83 104  82  56  79  93  91 174 174 174  28  28  61  80  70  58  50 |
11:| 36  32  32 123 123   3  57 101  14 174 174 174  28  58  90  67  88  20  28 |
10:| 33  34  34   3   3   3  30  62  14 174 174 174  28  28  90  15  14  23  18 |
 9:| 22  17   0  16   3   9  15  14  14 174 174  24  36  41  14  13  14   6  14 |
 8:|  9   5   0  16  16  16  16  16  16   1   1  27  29  41  41  41   3  16  25 |
 7:|  5   0   1   0   1  16   1   1   1   1  33  33  19  16   3   3   3  49  61 |
 6:| 53   0   0 155   1   1  18  38  36   1   1  33  12  22   3 168 168 122 108 |
 5:|120 155 155 155  68  69  55  81  69  75 161   4   4   4   4   4 168 161 147 |
 4:|142 146 150 155 155  59 115 117 123 133 162 161  82   4   4   4 168 164 163 |
 3:|143 145 147 143 128 147 134 169 152 152 155 156 160 159   4   4 169 165 165 |
 2:|145 146 145 140 137 138 151 158 157 153 152 149 144  91   4 168 169 165 164 |
 1:|145 146 144 140 138 141 148 155 155 153 149 142 122  61  39 115 166 168 165 |
   +----------------------------------------------------------------------------+
BLACK+87.5
Best Sequence : M8(BLACK : 36061/150065)->N9(WHITE : 109007/142809)->N8(BLACK : 16771/68855)->O13(WHITE : 40752/53339)->O14(BLACK : 9696/39582)->K18(WHITE : 9505/12442)->P14(BLACK : 598/2303)->M18(WHITE : 519/699)->O19(BLACK : 104/384)->L18(WHITE : 110/147)->J19(BLACK : 23/66)
Prisoner(Black) : 1
Prisoner(White) : 4
Move : 168
     A B C D E F G H J K L M N O P Q R S T
   +---------------------------------------+
19:| + + + + + + + B B + + + + B + + + + + |
18:| + W + W W W W W B W W W B + B + + + + |
17:| + B W B B B W W B W + + W B + + + + + |
16:| + B + W W B B B W W W W W + + B + + + |
15:| + + + + B B + + + + + + + + + + + + + |
14:| + + B + + + + + B + + + + B B + + + + |
13:| + + + + + + + + + + + B B W + + + + + |
12:| + + + + + + + + + B + B W W + + + + + |
11:| + W W B B W + B W B W B W + B + B W + |
10:| + B B W W W + + W B W B W W B W W B + |
 9:| + + W B W + W W W B B W W B W W + W + |
 8:| + + W B B B B B B W W B B B B B W + + |
 7:| + W + W W B W W W W B B + + W W W + + |
 6:| + W W B W W + + + W W B + B W B B + + |
 5:| + B B B + + + + + + B W W W + W B + + |
 4:| + + + B B W + + + + B B + W + W B + + |
 3:| + + + + W B + B + + + + B B W W B + + |
 2:| + + + + + + + + + + + + + + W B B + + |
 1:| + + + + + + + + + + + + + + + + + + + |
   +---------------------------------------+
All Playouts       :   489215
Pre Simulated      :      691
Win                :   114377
Thinking Time      :  109.951 sec
Winning Percentage :  23.3797%
Playout Speed      :     4443 PO/sec

make doesn't compile anmy more

"make" command just returns an error

$ make
g++ -O3 -Wall -std=c++11 -c src/Command.cpp -o src/Command.o
g++ -O3 -Wall -std=c++11 -c src/DynamicKomi.cpp -o src/DynamicKomi.o
g++ -O3 -Wall -std=c++11 -c src/GoBoard.cpp -o src/GoBoard.o
g++ -O3 -Wall -std=c++11 -c src/Gtp.cpp -o src/Gtp.o
src/Gtp.cpp:29:28: error: ‘GTP_quit’ was not declared in this scope
{ "quit", GTP_quit },
^
src/Gtp.cpp:30:28: error: ‘GTP_protocolversion’ was not declared in this scope
{ "protocol_version", GTP_protocolversion },
^
src/Gtp.cpp:31:28: error: ‘GTP_name’ was not declared in this scope
{ "name", GTP_name },
^
src/Gtp.cpp:32:28: error: ‘GTP_version’ was not declared in this scope
{ "version", GTP_version },
^
src/Gtp.cpp:33:28: error: ‘GTP_boardsize’ was not declared in this scope
{ "boardsize", GTP_boardsize },
^
src/Gtp.cpp:34:28: error: ‘GTP_clearboard’ was not declared in this scope
{ "clear_board", GTP_clearboard },
^
src/Gtp.cpp:35:28: error: ‘GTP_komi’ was not declared in this scope
{ "komi", GTP_komi },
^
src/Gtp.cpp:36:28: error: ‘GTP_getkomi’ was not declared in this scope
{ "get_komi", GTP_getkomi },
^
src/Gtp.cpp:37:28: error: ‘GTP_play’ was not declared in this scope
{ "play", GTP_play },
^
src/Gtp.cpp:38:28: error: ‘GTP_fixed_handicap’ was not declared in this scope
{ "fixed_handicap", GTP_fixed_handicap },
^
src/Gtp.cpp:39:28: error: ‘GTP_fixed_handicap’ was not declared in this scope
{ "place_free_handicap", GTP_fixed_handicap },
^
src/Gtp.cpp:40:28: error: ‘GTP_set_free_handicap’ was not declared in this scope
{ "set_free_handicap", GTP_set_free_handicap },
^
src/Gtp.cpp:41:28: error: ‘GTP_genmove’ was not declared in this scope
{ "genmove", GTP_genmove },
^
src/Gtp.cpp:42:28: error: ‘GTP_timesettings’ was not declared in this scope
{ "time_settings", GTP_timesettings },
^
src/Gtp.cpp:43:28: error: ‘GTP_timeleft’ was not declared in this scope
{ "time_left", GTP_timeleft },
^
src/Gtp.cpp:44:28: error: ‘GTP_finalscore’ was not declared in this scope
{ "final_score", GTP_finalscore },
^
src/Gtp.cpp:45:28: error: ‘GTP_final_status_list’ was not declared in this scope
{ "final_status_list", GTP_final_status_list },
^
src/Gtp.cpp:46:28: error: ‘GTP_showboard’ was not declared in this scope
{ "showboard", GTP_showboard },
^
src/Gtp.cpp:47:28: error: ‘GTP_listcommands’ was not declared in this scope
{ "list_commands", GTP_listcommands },
^
src/Gtp.cpp:48:28: error: ‘GTP_knowncommand’ was not declared in this scope
{ "known_command", GTP_knowncommand },
^
src/Gtp.cpp:49:28: error: ‘GTP_kgs_genmove_cleanup’ was not declared in this scope
{ "kgs-genmove_cleanup", GTP_kgs_genmove_cleanup },
^
src/Gtp.cpp:180:1: warning: ‘void GTP_boardsize()’ defined but not used [-Wunused-function]
GTP_boardsize( void )
^
src/Gtp.cpp:218:1: warning: ‘void GTP_clearboard()’ defined but not used [-Wunused-function]
GTP_clearboard( void )
^
src/Gtp.cpp:236:1: warning: ‘void GTP_name()’ defined but not used [-Wunused-function]
GTP_name( void )
^
src/Gtp.cpp:246:1: warning: ‘void GTP_protocolversion()’ defined but not used [-Wunused-function]
GTP_protocolversion( void )
^
src/Gtp.cpp:256:1: warning: ‘void GTP_genmove()’ defined but not used [-Wunused-function]
GTP_genmove( void )
^
src/Gtp.cpp:303:1: warning: ‘void GTP_play()’ defined but not used [-Wunused-function]
GTP_play( void )
^
src/Gtp.cpp:346:1: warning: ‘void GTP_knowncommand()’ defined but not used [-Wunused-function]
GTP_knowncommand( void )
^
src/Gtp.cpp:371:1: warning: ‘void GTP_listcommands()’ defined but not used [-Wunused-function]
GTP_listcommands( void )
^
src/Gtp.cpp:394:1: warning: ‘void GTP_quit()’ defined but not used [-Wunused-function]
GTP_quit( void )
^
src/Gtp.cpp:405:1: warning: ‘void GTP_komi()’ defined but not used [-Wunused-function]
GTP_komi( void )
^
src/Gtp.cpp:425:1: warning: ‘void GTP_getkomi()’ defined but not used [-Wunused-function]
GTP_getkomi( void )
^
src/Gtp.cpp:442:1: warning: ‘void GTP_finalscore()’ defined but not used [-Wunused-function]
GTP_finalscore( void )
^
src/Gtp.cpp:471:1: warning: ‘void GTP_timesettings()’ defined but not used [-Wunused-function]
GTP_timesettings( void )
^
src/Gtp.cpp:497:1: warning: ‘void GTP_timeleft()’ defined but not used [-Wunused-function]
GTP_timeleft( void )
^
src/Gtp.cpp:520:1: warning: ‘void GTP_version()’ defined but not used [-Wunused-function]
GTP_version( void )
^
src/Gtp.cpp:530:1: warning: ‘void GTP_showboard()’ defined but not used [-Wunused-function]
GTP_showboard( void )
^
src/Gtp.cpp:687:1: warning: ‘void GTP_kgs_genmove_cleanup()’ defined but not used [-Wunused-function]
GTP_kgs_genmove_cleanup( void )
^
src/Gtp.cpp:634:1: warning: ‘void GTP_final_status_list()’ defined but not used [-Wunused-function]
GTP_final_status_list( void )
^
src/Gtp.cpp:605:1: warning: ‘void GTP_set_free_handicap()’ defined but not used [-Wunused-function]
GTP_set_free_handicap( void )
^
src/Gtp.cpp:541:1: warning: ‘void GTP_fixed_handicap()’ defined but not used [-Wunused-function]
GTP_fixed_handicap( void )
^
make: *** [src/Gtp.o] Error 1