Nebiyu-MCTS vs TSCP 1-0
Moderators: hgm, Rebel, chrisw
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Nebiyu-MCTS vs TSCP 1-0
Very nice! I hope it leads somewhere.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Nebiyu-MCTS vs TSCP 1-0
Have you tried an N.E.G.-like algorithm for move selection, which basically would be to just count number of attackers and protectors of each square, and then play with high probability the moves that are expected to gain material based on that (i.e. LxH captures, or when there are more attackers than protectors)? And suppress the probability of non-captures to squares that are not attacked more than protected?
This seems much cheaper to calculate than a 4-ply search, and should quickly find more complex tactics (like pins or batteries) by MCTS and the high efficiency of generating the refutation.
This seems much cheaper to calculate than a 4-ply search, and should quickly find more complex tactics (like pins or batteries) by MCTS and the high efficiency of generating the refutation.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Nebiyu-MCTS vs TSCP 1-0
If I understand Daniel correctly then the 4-ply search is only done in the leaf nodes of the MC-tree as a replacement for the neural network. The move selection is done by the UCB rule.hgm wrote:Have you tried an N.E.G.-like algorithm for move selection, which basically would be to just count number of attackers and protectors of each square, and then play with high probability the moves that are expected to gain material based on that (i.e. LxH captures, or when there are more attackers than protectors)? And suppress the probability of non-captures to squares that are not attacked more than protected?
This seems much cheaper to calculate than a 4-ply search, and should quickly find more complex tactics (like pins or batteries) by MCTS and the high efficiency of generating the refutation.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Nebiyu-MCTS vs TSCP 1-0
I'm sorry I have been too direct, but I was writing from my smatphone and I had no time to write a longer message.
When I tried to study and implement mcts i didn't found a elegant solution to the problem of mcts tree storage.
Usually in chess we traverse a tree of some million nodes without storing it anywhere. we simply use a depth-first recursive approach without saving the data and using the stack to store temporary imformations, and the engine will oly occupy the memory assigned for the hashtable.
From what I have understood when building mcts tree I have to store it in ram and let it grow while the algorithm evolve in a breadth-first approach.
There is some result I don't know that let us traverse the mcts tree without storing it? or my interpretation is correct and the whole mcts tree shall be saved in ram while we perform the search occupying MB of ram?
I'm sorry if my request offended someone, but my actual interest is to understand this info.
thank you and good luck with your mcts effort
When I tried to study and implement mcts i didn't found a elegant solution to the problem of mcts tree storage.
Usually in chess we traverse a tree of some million nodes without storing it anywhere. we simply use a depth-first recursive approach without saving the data and using the stack to store temporary imformations, and the engine will oly occupy the memory assigned for the hashtable.
From what I have understood when building mcts tree I have to store it in ram and let it grow while the algorithm evolve in a breadth-first approach.
There is some result I don't know that let us traverse the mcts tree without storing it? or my interpretation is correct and the whole mcts tree shall be saved in ram while we perform the search occupying MB of ram?
I'm sorry if my request offended someone, but my actual interest is to understand this info.
thank you and good luck with your mcts effort
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: Nebiyu-MCTS vs TSCP 1-0
Daniel, In place of the piece square tables you would be better served by using two statistics to value the root moves of your shallow search, total number of beta cuts and checkmates for each side. Then return the best material score or in case of materially tied root moves return the score augmented by the statistics.
If you do not believe me then try this simple experiment. With an otherwise material only ab searcher collect only beta cutoffs at the root for the computer. Then play the materially best move and in the case of a material tie play the move with the highest number of beta cutoffs. You will be amazed at the play!
And of course that is just a baseline starting point for a statistical driven search.
If you do not believe me then try this simple experiment. With an otherwise material only ab searcher collect only beta cutoffs at the root for the computer. Then play the materially best move and in the case of a material tie play the move with the highest number of beta cutoffs. You will be amazed at the play!
And of course that is just a baseline starting point for a statistical driven search.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Nebiyu-MCTS vs TSCP 1-0
That is correct, but I think I am suffering in tactics heavily with this approach too. The problem is that when you have a forced move (e.g. a recapture), and you sample the other moves, obviously wrong ones, moves often enough the real score gets smeared out. That was the problem in the playout part of the MCTS before. In Checkers, captures are forced automatically excluding the non-captures so there is no "smearing problem". So I am gonna have to use the shallow search to bias sampling of moves heavily especially when there is a forced line. I need an efficient search that outputs a score and winning probabilities for each move -- just like the NN -- and then i will use it at the leaves AND in the internal nodes.Michel wrote:If I understand Daniel correctly then the 4-ply search is only done in the leaf nodes of the MC-tree as a replacement for the neural network. The move selection is done by the UCB rule.hgm wrote:Have you tried an N.E.G.-like algorithm for move selection, which basically would be to just count number of attackers and protectors of each square, and then play with high probability the moves that are expected to gain material based on that (i.e. LxH captures, or when there are more attackers than protectors)? And suppress the probability of non-captures to squares that are not attacked more than protected?
This seems much cheaper to calculate than a 4-ply search, and should quickly find more complex tactics (like pins or batteries) by MCTS and the high efficiency of generating the refutation.
Daniel
Last edited by Daniel Shawul on Mon Dec 11, 2017 10:30 am, edited 1 time in total.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Nebiyu-MCTS vs TSCP 1-0
Good point H.G. I am gonna try and use something that plays forced moves with high probability. For example, in the following position, it played e2xd4 with the current approach.hgm wrote:Have you tried an N.E.G.-like algorithm for move selection, which basically would be to just count number of attackers and protectors of each square, and then play with high probability the moves that are expected to gain material based on that (i.e. LxH captures, or when there are more attackers than protectors)? And suppress the probability of non-captures to squares that are not attacked more than protected?
This seems much cheaper to calculate than a 4-ply search, and should quickly find more complex tactics (like pins or batteries) by MCTS and the high efficiency of generating the refutation.
[D] rnbqk1nr/pp3ppp/3b4/4p3/3pP3/5N2/PP1PNPPP/R1BQKB1R w KQkq - 0 7
I am gonna have to bias the probability of playing the recapture exd4 with high probability.
The MCTS tree in xml format looks like this after e1xd4 which is played with high probability.
Code: Select all
<node depth="1" move="e2d4 " subtree="0" visits="543" wins="5.695532e-01">
<node depth="2" move="e5d4 " subtree="0" visits="186" wins="6.096836e-01">
<node depth="3" move="a2a3 " subtree="0" visits="3" wins="2.530871e-01">
</node>
<node depth="3" move="a2a4 " subtree="0" visits="3" wins="2.708901e-01">
</node>
<node depth="3" move="g2g3 " subtree="0" visits="3" wins="2.530871e-01">
</node>
<node depth="3" move="g2g4 " subtree="0" visits="3" wins="2.574645e-01">
</node>
<node depth="3" move="b2b3 " subtree="0" visits="3" wins="2.574645e-01">
</node>
<node depth="3" move="b2b4 " subtree="0" visits="2" wins="1.509796e-01">
</node>
<node depth="3" move="h2h3 " subtree="0" visits="3" wins="2.530871e-01">
</node>
<node depth="3" move="h2h4 " subtree="0" visits="3" wins="2.800810e-01">
</node>
<node depth="3" move="d2d3 " subtree="0" visits="3" wins="2.509170e-01">
</node>
<node depth="3" move="e4e5 " subtree="0" visits="3" wins="2.708901e-01">
</node>
<node depth="3" move="f3h4 " subtree="0" visits="3" wins="4.618126e-02">
</node>
<node depth="3" move="f3g5 " subtree="0" visits="2" wins="4.986387e-02">
</node>
<node depth="3" move="f3d4 " subtree="0" visits="6" wins="4.341848e-01">
</node>
<node depth="3" move="f3g1 " subtree="0" visits="3" wins="2.159463e-01">
</node>
<node depth="3" move="f3e5 " subtree="0" visits="2" wins="4.371083e-02">
</node>
<node depth="3" move="f1e2 " subtree="0" visits="3" wins="2.552696e-01">
</node>
<node depth="3" move="f1d3 " subtree="0" visits="3" wins="2.708901e-01">
</node>
<node depth="3" move="f1c4 " subtree="0" visits="3" wins="2.824083e-01">
</node>
<node depth="3" move="f1b5 " subtree="0" visits="9" wins="4.201002e-01">
</node>
<node depth="3" move="f1a6 " subtree="0" visits="4" wins="1.008826e-01">
</node>
<node depth="3" move="h1g1 " subtree="0" visits="2" wins="2.754617e-01">
</node>
<node depth="3" move="a1b1 " subtree="0" visits="3" wins="2.530871e-01">
</node>
<node depth="3" move="d1e2 " subtree="0" visits="2" wins="2.618909e-01">
</node>
<node depth="3" move="d1c2 " subtree="0" visits="66" wins="5.164848e-01">
<node depth="4" move="d4d3 " subtree="0" visits="1" wins="5.000000e-01">
</node>
<node depth="4" move="a7a6 " subtree="0" visits="1" wins="5.287506e-01">
</node>
<node depth="4" move="a7a5 " subtree="0" visits="1" wins="5.258809e-01">
</node>
<node depth="4" move="b7b6 " subtree="0" visits="1" wins="5.028782e-01">
</node>
<node depth="4" move="b7b5 " subtree="0" visits="1" wins="3.014414e-01">
</node>
<node depth="4" move="h7h6 " subtree="0" visits="1" wins="5.201367e-01">
</node>
<node depth="4" move="h7h5 " subtree="0" visits="1" wins="5.344839e-01">
</node>
<node depth="4" move="f7f6 " subtree="0" visits="1" wins="4.741191e-01">
</node>
<node depth="4" move="f7f5 " subtree="0" visits="1" wins="4.942438e-01">
</node>
<node depth="4" move="g7g6 " subtree="0" visits="1" wins="5.201367e-01">
</node>
<node depth="4" move="g7g5 " subtree="0" visits="1" wins="5.201367e-01">
</node>
<node depth="4" move="g8e7 " subtree="0" visits="1" wins="5.658152e-01">
</node>
<node depth="4" move="g8f6 " subtree="0" visits="1" wins="5.258809e-01">
</node>
<node depth="4" move="g8h6 " subtree="0" visits="1" wins="5.201367e-01">
</node>
<node depth="4" move="b8a6 " subtree="0" visits="1" wins="2.800810e-01">
</node>
<node depth="4" move="b8d7 " subtree="0" visits="1" wins="5.172625e-01">
</node>
<node depth="4" move="b8c6 " subtree="0" visits="15" wins="6.905080e-01">
<node depth="5" move="a2a3 " subtree="0" visits="1" wins="2.299033e-01">
</node>
<node depth="5" move="a2a4 " subtree="0" visits="1" wins="2.530871e-01">
</node>
<node depth="5" move="h2h3 " subtree="0" visits="1" wins="2.423608e-01">
</node>
<node depth="5" move="h2h4 " subtree="0" visits="1" wins="2.340053e-01">
</node>
<node depth="5" move="b2b3 " subtree="0" visits="1" wins="2.402531e-01">
</node>
<node depth="5" move="b2b4 " subtree="0" visits="1" wins="1.554605e-01">
</node>
<node depth="5" move="e4e5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="g2g3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="g2g4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="d2d3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3h4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3g5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3d4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3g1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3e5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1e2 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1d3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1c4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1b5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1a6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a1b1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="h1g1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2d3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2b1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2b3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2a4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2d1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2c3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2c4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2c5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="c2c6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="e1e2 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="e1d1 " subtree="0" visits="0" wins="-nan">
</node>
</node>
<node depth="4" move="c8d7 " subtree="0" visits="1" wins="5.402082e-01">
</node>
<node depth="4" move="c8e6 " subtree="0" visits="1" wins="4.913661e-01">
</node>
<node depth="4" move="c8f5 " subtree="0" visits="1" wins="2.509170e-01">
</node>
<node depth="4" move="c8g4 " subtree="0" visits="1" wins="5.770925e-01">
</node>
<node depth="4" move="c8h3 " subtree="0" visits="1" wins="1.509796e-01">
</node>
<node depth="4" move="d6e7 " subtree="0" visits="1" wins="4.971218e-01">
</node>
<node depth="4" move="d6f8 " subtree="0" visits="1" wins="4.398499e-01">
</node>
<node depth="4" move="d6c5 " subtree="0" visits="1" wins="2.026137e-01">
</node>
<node depth="4" move="d6b4 " subtree="0" visits="1" wins="4.884891e-01">
</node>
<node depth="4" move="d6a3 " subtree="0" visits="1" wins="2.140034e-01">
</node>
<node depth="4" move="d6c7 " subtree="0" visits="1" wins="4.856128e-01">
</node>
<node depth="4" move="d6e5 " subtree="0" visits="1" wins="2.044801e-01">
</node>
<node depth="4" move="d6f4 " subtree="0" visits="1" wins="5.086338e-01">
</node>
<node depth="4" move="d6g3 " subtree="0" visits="1" wins="1.952753e-01">
</node>
<node depth="4" move="d6h2 " subtree="0" visits="1" wins="3.313050e-01">
</node>
<node depth="4" move="d8c7 " subtree="0" visits="1" wins="4.884891e-01">
</node>
<node depth="4" move="d8b6 " subtree="0" visits="1" wins="1.188622e-01">
</node>
<node depth="4" move="d8a5 " subtree="0" visits="1" wins="5.560982e-02">
</node>
<node depth="4" move="d8e7 " subtree="0" visits="1" wins="5.560982e-02">
</node>
<node depth="4" move="d8f6 " subtree="0" visits="1" wins="5.560982e-02">
</node>
<node depth="4" move="d8g5 " subtree="0" visits="1" wins="1.215315e-02">
</node>
<node depth="4" move="d8h4 " subtree="0" visits="1" wins="1.377136e-02">
</node>
<node depth="4" move="d8d7 " subtree="0" visits="1" wins="5.316183e-01">
</node>
<node depth="4" move="e8d7 " subtree="0" visits="1" wins="5.316183e-01">
</node>
<node depth="4" move="e8e7 " subtree="0" visits="1" wins="5.258809e-01">
</node>
<node depth="4" move="e8f8 " subtree="0" visits="1" wins="5.115109e-01">
</node>
</node>
<node depth="3" move="d1b3 " subtree="0" visits="3" wins="3.087639e-01">
</node>
<node depth="3" move="d1a4 " subtree="0" visits="26" wins="4.551137e-01">
<node depth="4" move="b7b5 " subtree="0" visits="1" wins="2.918336e-01">
</node>
<node depth="4" move="b8d7 " subtree="0" visits="1" wins="4.769904e-01">
</node>
<node depth="4" move="b8c6 " subtree="0" visits="11" wins="5.934153e-01">
<node depth="5" move="b2b3 " subtree="0" visits="1" wins="2.618909e-01">
</node>
<node depth="5" move="b2b4 " subtree="0" visits="1" wins="1.495097e-01">
</node>
<node depth="5" move="a2a3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="g2g3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="g2g4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="h2h3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="h2h4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="d2d3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="e4e5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3h4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3g5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3d4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3g1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f3e5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1e2 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1d3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1c4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1b5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="f1a6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a1b1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="h1g1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4b5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4c6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4b3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4c2 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4d1 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4a5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4a6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4a7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4a3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4b4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4c4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="a4d4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="e1e2 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="5" move="e1d1 " subtree="0" visits="0" wins="-nan">
</node>
</node>
<node depth="4" move="c8d7 " subtree="0" visits="1" wins="5.028782e-01">
</node>
<node depth="4" move="d8d7 " subtree="0" visits="1" wins="5.201367e-01">
</node>
<node depth="4" move="e8e7 " subtree="0" visits="1" wins="5.115109e-01">
</node>
<node depth="4" move="e8f8 " subtree="0" visits="1" wins="5.000000e-01">
</node>
</node>
<node depth="3" move="e1e2 " subtree="0" visits="8" wins="2.777655e-01">
</node>
</node>
<node depth="2" move="a7a6 " subtree="0" visits="7" wins="2.870979e-01">
</node>
<node depth="2" move="a7a5 " subtree="0" visits="6" wins="2.708901e-01">
</node>
<node depth="2" move="h7h6 " subtree="0" visits="7" wins="2.596716e-01">
</node>
<node depth="2" move="h7h5 " subtree="0" visits="6" wins="2.708901e-01">
</node>
<node depth="2" move="g7g6 " subtree="0" visits="7" wins="2.596716e-01">
</node>
<node depth="2" move="g7g5 " subtree="0" visits="5" wins="2.140034e-01">
</node>
<node depth="2" move="b7b6 " subtree="0" visits="6" wins="2.596716e-01">
</node>
<node depth="2" move="b7b5 " subtree="0" visits="4" wins="1.288522e-01">
</node>
<node depth="2" move="f7f6 " subtree="0" visits="6" wins="2.596716e-01">
</node>
<node depth="2" move="f7f5 " subtree="0" visits="4" wins="1.275654e-01">
</node>
<node depth="2" move="g8e7 " subtree="0" visits="45" wins="4.820281e-01">
<node depth="3" move="b2b3 " subtree="0" visits="1" wins="4.569335e-01">
</node>
<node depth="3" move="b2b4 " subtree="0" visits="1" wins="3.390009e-01">
</node>
<node depth="3" move="g2g3 " subtree="0" visits="1" wins="4.257198e-01">
</node>
<node depth="3" move="g2g4 " subtree="0" visits="1" wins="4.712495e-01">
</node>
<node depth="3" move="d2d3 " subtree="0" visits="1" wins="3.014414e-01">
</node>
<node depth="3" move="a2a3 " subtree="0" visits="1" wins="4.426883e-01">
</node>
<node depth="3" move="a2a4 " subtree="0" visits="1" wins="4.483765e-01">
</node>
<node depth="3" move="h2h3 " subtree="0" visits="1" wins="4.426883e-01">
</node>
<node depth="3" move="h2h4 " subtree="0" visits="1" wins="4.712495e-01">
</node>
<node depth="3" move="d4f5 " subtree="0" visits="1" wins="4.398499e-01">
</node>
<node depth="3" move="d4b3 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="d4e6 " subtree="0" visits="1" wins="2.140034e-01">
</node>
<node depth="3" move="d4c2 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="d4b5 " subtree="0" visits="4" wins="7.033850e-01">
</node>
<node depth="3" move="d4e2 " subtree="0" visits="2" wins="6.532172e-01">
</node>
<node depth="3" move="d4c6 " subtree="0" visits="1" wins="2.140034e-01">
</node>
<node depth="3" move="f3h4 " subtree="0" visits="1" wins="2.299033e-01">
</node>
<node depth="3" move="f3g5 " subtree="0" visits="1" wins="4.398499e-01">
</node>
<node depth="3" move="f3g1 " subtree="0" visits="1" wins="2.159463e-01">
</node>
<node depth="3" move="f3e5 " subtree="0" visits="1" wins="5.143872e-01">
</node>
<node depth="3" move="f1e2 " subtree="0" visits="1" wins="4.626527e-01">
</node>
<node depth="3" move="f1d3 " subtree="0" visits="1" wins="4.257198e-01">
</node>
<node depth="3" move="f1c4 " subtree="0" visits="1" wins="4.569335e-01">
</node>
<node depth="3" move="f1b5 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="f1a6 " subtree="0" visits="1" wins="1.881400e-01">
</node>
<node depth="3" move="a1b1 " subtree="0" visits="1" wins="4.512256e-01">
</node>
<node depth="3" move="h1g1 " subtree="0" visits="1" wins="3.467828e-01">
</node>
<node depth="3" move="d1e2 " subtree="0" visits="1" wins="4.483765e-01">
</node>
<node depth="3" move="d1c2 " subtree="0" visits="1" wins="4.341848e-01">
</node>
<node depth="3" move="d1b3 " subtree="0" visits="1" wins="4.512256e-01">
</node>
<node depth="3" move="d1a4 " subtree="0" visits="1" wins="6.838163e-01">
</node>
<node depth="3" move="e1e2 " subtree="0" visits="1" wins="4.512256e-01">
</node>
</node>
<node depth="2" move="g8f6 " subtree="0" visits="9" wins="3.161837e-01">
</node>
<node depth="2" move="g8h6 " subtree="0" visits="6" wins="2.641225e-01">
</node>
<node depth="2" move="b8a6 " subtree="0" visits="9" wins="2.708901e-01">
</node>
<node depth="2" move="b8d7 " subtree="0" visits="6" wins="2.238454e-01">
</node>
<node depth="2" move="b8c6 " subtree="0" visits="55" wins="4.892551e-01">
<node depth="3" move="b2b3 " subtree="0" visits="1" wins="2.574645e-01">
</node>
<node depth="3" move="b2b4 " subtree="0" visits="1" wins="2.574645e-01">
</node>
<node depth="3" move="g2g3 " subtree="0" visits="1" wins="2.530871e-01">
</node>
<node depth="3" move="g2g4 " subtree="0" visits="1" wins="2.423608e-01">
</node>
<node depth="3" move="a2a3 " subtree="0" visits="1" wins="2.530871e-01">
</node>
<node depth="3" move="a2a4 " subtree="0" visits="1" wins="2.708901e-01">
</node>
<node depth="3" move="h2h3 " subtree="0" visits="1" wins="2.530871e-01">
</node>
<node depth="3" move="h2h4 " subtree="0" visits="1" wins="2.800810e-01">
</node>
<node depth="3" move="d2d3 " subtree="0" visits="1" wins="2.509170e-01">
</node>
<node depth="3" move="d4f5 " subtree="0" visits="1" wins="6.838163e-01">
</node>
<node depth="3" move="d4b3 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="d4e6 " subtree="0" visits="1" wins="2.140034e-01">
</node>
<node depth="3" move="d4c2 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="d4b5 " subtree="0" visits="15" wins="7.225250e-01">
<node depth="4" move="g7g6 " subtree="0" visits="1" wins="2.663663e-01">
</node>
<node depth="4" move="g7g5 " subtree="0" visits="1" wins="1.354530e-01">
</node>
<node depth="4" move="h7h6 " subtree="0" visits="1" wins="2.618909e-01">
</node>
<node depth="4" move="h7h5 " subtree="0" visits="1" wins="2.777655e-01">
</node>
<node depth="4" move="b7b6 " subtree="0" visits="1" wins="2.663663e-01">
</node>
<node depth="4" move="a7a6 " subtree="0" visits="1" wins="2.847472e-01">
</node>
<node depth="4" move="a7a5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="f7f6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="f7f5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c6e7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c6a5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c6b4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c6d4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c6b8 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="g8e7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="g8f6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="g8h6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6e7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6f8 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6c5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6b4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6a3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6c7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d6b8 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c8d7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c8e6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c8f5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c8g4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="c8h3 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="a8b8 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8c7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8b6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8a5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8e7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8f6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8g5 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8h4 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="d8d7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e8d7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e8e7 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e8f8 " subtree="0" visits="0" wins="-nan">
</node>
</node>
<node depth="3" move="d4e2 " subtree="0" visits="1" wins="6.532172e-01">
</node>
<node depth="3" move="d4c6 " subtree="0" visits="1" wins="7.447304e-01">
</node>
<node depth="3" move="f3h4 " subtree="0" visits="1" wins="1.141230e-01">
</node>
<node depth="3" move="f3g5 " subtree="0" visits="1" wins="2.381579e-01">
</node>
<node depth="3" move="f3g1 " subtree="0" visits="1" wins="2.159463e-01">
</node>
<node depth="3" move="f3e5 " subtree="0" visits="1" wins="4.884891e-01">
</node>
<node depth="3" move="f1e2 " subtree="0" visits="1" wins="2.552696e-01">
</node>
<node depth="3" move="f1d3 " subtree="0" visits="1" wins="2.754617e-01">
</node>
<node depth="3" move="f1c4 " subtree="0" visits="1" wins="2.824083e-01">
</node>
<node depth="3" move="f1b5 " subtree="0" visits="1" wins="4.569335e-01">
</node>
<node depth="3" move="f1a6 " subtree="0" visits="1" wins="2.487592e-01">
</node>
<node depth="3" move="a1b1 " subtree="0" visits="1" wins="2.530871e-01">
</node>
<node depth="3" move="h1g1 " subtree="0" visits="1" wins="2.754617e-01">
</node>
<node depth="3" move="d1e2 " subtree="0" visits="1" wins="2.618909e-01">
</node>
<node depth="3" move="d1c2 " subtree="0" visits="1" wins="4.172981e-01">
</node>
<node depth="3" move="d1b3 " subtree="0" visits="1" wins="3.087639e-01">
</node>
<node depth="3" move="d1a4 " subtree="0" visits="1" wins="4.626527e-01">
</node>
<node depth="3" move="e1e2 " subtree="0" visits="1" wins="2.777655e-01">
</node>
</node>
<node depth="2" move="d6e7 " subtree="0" visits="5" wins="2.278713e-01">
</node>
<node depth="2" move="d6f8 " subtree="0" visits="5" wins="2.278713e-01">
</node>
<node depth="2" move="d6c5 " subtree="0" visits="6" wins="2.509170e-01">
</node>
<node depth="2" move="d6b4 " subtree="0" visits="4" wins="8.996207e-02">
</node>
<node depth="2" move="d6a3 " subtree="0" visits="6" wins="1.029904e-01">
</node>
<node depth="2" move="d6c7 " subtree="0" visits="5" wins="2.340053e-01">
</node>
<node depth="2" move="c8d7 " subtree="0" visits="7" wins="2.509170e-01">
</node>
<node depth="2" move="c8e6 " subtree="0" visits="5" wins="1.200733e-01">
</node>
<node depth="2" move="c8f5 " subtree="0" visits="3" wins="2.803189e-02">
</node>
<node depth="2" move="c8g4 " subtree="0" visits="6" wins="2.618909e-01">
</node>
<node depth="2" move="c8h3 " subtree="0" visits="6" wins="1.106775e-01">
</node>
<node depth="2" move="d8c7 " subtree="0" visits="5" wins="2.179020e-01">
</node>
<node depth="2" move="d8b6 " subtree="0" visits="6" wins="2.552696e-01">
</node>
<node depth="2" move="d8a5 " subtree="0" visits="5" wins="2.278713e-01">
</node>
<node depth="2" move="d8e7 " subtree="0" visits="6" wins="2.574645e-01">
</node>
<node depth="2" move="d8f6 " subtree="0" visits="5" wins="2.574645e-01">
</node>
<node depth="2" move="d8g5 " subtree="0" visits="3" wins="5.921364e-03">
</node>
<node depth="2" move="d8h4 " subtree="0" visits="3" wins="6.342173e-03">
</node>
<node depth="2" move="d8d7 " subtree="0" visits="5" wins="2.101558e-01">
</node>
<node depth="2" move="e8d7 " subtree="0" visits="6" wins="2.402531e-01">
</node>
<node depth="2" move="e8e7 " subtree="0" visits="51" wins="4.620264e-01">
<node depth="3" move="a2a3 " subtree="0" visits="1" wins="4.201002e-01">
</node>
<node depth="3" move="a2a4 " subtree="0" visits="1" wins="4.117100e-01">
</node>
<node depth="3" move="b2b3 " subtree="0" visits="1" wins="3.733009e-01">
</node>
<node depth="3" move="b2b4 " subtree="0" visits="1" wins="3.161837e-01">
</node>
<node depth="3" move="g2g3 " subtree="0" visits="1" wins="3.895976e-01">
</node>
<node depth="3" move="g2g4 " subtree="0" visits="1" wins="4.117100e-01">
</node>
<node depth="3" move="h2h3 " subtree="0" visits="1" wins="4.798633e-01">
</node>
<node depth="3" move="h2h4 " subtree="0" visits="1" wins="4.942438e-01">
</node>
<node depth="3" move="d2d3 " subtree="0" visits="1" wins="2.870979e-01">
</node>
<node depth="3" move="d4f5 " subtree="0" visits="11" wins="7.129936e-01">
<node depth="4" move="c8f5 " subtree="0" visits="1" wins="2.754617e-01">
</node>
<node depth="4" move="e7f8 " subtree="0" visits="1" wins="2.120732e-01">
</node>
<node depth="4" move="e7f6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e7e8 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e7e6 " subtree="0" visits="0" wins="-nan">
</node>
<node depth="4" move="e7d7 " subtree="0" visits="0" wins="-nan">
</node>
</node>
<node depth="3" move="d4b3 " subtree="0" visits="1" wins="6.838163e-01">
</node>
<node depth="3" move="d4e6 " subtree="0" visits="1" wins="2.360753e-01">
</node>
<node depth="3" move="d4c2 " subtree="0" visits="1" wins="6.635741e-01">
</node>
<node depth="3" move="d4b5 " subtree="0" visits="1" wins="7.403284e-01">
</node>
<node depth="3" move="d4e2 " subtree="0" visits="1" wins="6.686949e-01">
</node>
<node depth="3" move="d4c6 " subtree="0" visits="1" wins="2.120732e-01">
</node>
<node depth="3" move="f3h4 " subtree="0" visits="1" wins="2.708901e-01">
</node>
<node depth="3" move="f3g5 " subtree="0" visits="1" wins="2.641225e-01">
</node>
<node depth="3" move="f3g1 " subtree="0" visits="1" wins="2.381579e-01">
</node>
<node depth="3" move="f3e5 " subtree="0" visits="1" wins="5.373473e-01">
</node>
<node depth="3" move="f1e2 " subtree="0" visits="1" wins="4.257198e-01">
</node>
<node depth="3" move="f1d3 " subtree="0" visits="1" wins="3.706114e-01">
</node>
<node depth="3" move="f1c4 " subtree="0" visits="1" wins="4.426883e-01">
</node>
<node depth="3" move="f1b5 " subtree="0" visits="1" wins="4.341848e-01">
</node>
<node depth="3" move="f1a6 " subtree="0" visits="1" wins="2.299033e-01">
</node>
<node depth="3" move="h1g1 " subtree="0" visits="1" wins="3.038712e-01">
</node>
<node depth="3" move="a1b1 " subtree="0" visits="1" wins="4.061446e-01">
</node>
<node depth="3" move="d1e2 " subtree="0" visits="1" wins="4.712495e-01">
</node>
<node depth="3" move="d1c2 " subtree="0" visits="1" wins="4.683817e-01">
</node>
<node depth="3" move="d1b3 " subtree="0" visits="1" wins="4.683817e-01">
</node>
<node depth="3" move="d1a4 " subtree="0" visits="1" wins="5.000000e-01">
</node>
<node depth="3" move="e1e2 " subtree="0" visits="1" wins="4.117100e-01">
</node>
</node>
<node depth="2" move="e8f8 " subtree="0" visits="7" wins="2.423608e-01">
</node>
</node>
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Nebiyu-MCTS vs TSCP 1-0
I guess it depends on whether you consider using the knowledge that a Queen is worth more than a Knight, so that you should try N x protected Q with high probablilty, and Q x protected N only with very low probability, 'cheating'. Or the fact that capturing unprotected pieces is a good deal.
A weakness of MCTS is that it considers every position of the tree in isolation. When it finally figures out it is good to capture PxQ in one position close to the root, it will in no way bias it towards PxQ in other positions deep in the tree. For that a neural network controlling the move selection would be helpful. This could learn very quickly from positions close to the root that grabbing unprotected material is good, and that with protection N x Q usually ends much better then Q x N. And then apply that kowledge to get more realistic playouts.
A weakness of MCTS is that it considers every position of the tree in isolation. When it finally figures out it is good to capture PxQ in one position close to the root, it will in no way bias it towards PxQ in other positions deep in the tree. For that a neural network controlling the move selection would be helpful. This could learn very quickly from positions close to the root that grabbing unprotected material is good, and that with protection N x Q usually ends much better then Q x N. And then apply that kowledge to get more realistic playouts.
-
- Posts: 4190
- Joined: Wed Nov 25, 2009 1:47 am
Re: Nebiyu-MCTS vs TSCP 1-0
Try the following. At the leaf node you are expanding, do first just eval for all the moves, select a few best ones and then perform mpv search of a fixed depth with those including QS.Daniel Shawul wrote:That is correct, but I think I am suffering in tactics heavily with this approach too. The problem is that when you have a forced move (e.g. a recapture), and you sample the other moves, obviously wrong ones, moves often enough the real score gets smeared out. That was the problem in the playout part of the MCTS before. In Checkers, captures are forced automatically excluding the non-captures so there is no "smearing problem". So I am gonna have to use the shallow search to bias sampling of moves heavily especially when there is a forced line. I need an efficient search that outputs a score and winning probabilities for each move -- just like the NN -- and then i will use it at the leaves AND in the internal nodes
You convert scores for each move into probabilities using a logistic function.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Nebiyu-MCTS vs TSCP 1-0
I had already something for reading tactics (using qsearch) when children nodes are first created. So what I do now is to do a shallow depth search (depth=4) instead and store that score for computing move probabilities later. I do not want to completely cut out inferior moves from consideration but bias the UCB formula so that a move that wins material is selected with very high probability. Logistic is what I use for converting the eval score to winning prob, but I think something more aggressive is need for the problem at hand, that is avoiding excessive exploration in forced lines. Reducing the exploration coefficient helps a little, so does sorting the moves it seems.Milos wrote:Try the following. At the leaf node you are expanding, do first just eval for all the moves, select a few best ones and then perform mpv search of a fixed depth with those including QS.Daniel Shawul wrote:That is correct, but I think I am suffering in tactics heavily with this approach too. The problem is that when you have a forced move (e.g. a recapture), and you sample the other moves, obviously wrong ones, moves often enough the real score gets smeared out. That was the problem in the playout part of the MCTS before. In Checkers, captures are forced automatically excluding the non-captures so there is no "smearing problem". So I am gonna have to use the shallow search to bias sampling of moves heavily especially when there is a forced line. I need an efficient search that outputs a score and winning probabilities for each move -- just like the NN -- and then i will use it at the leaves AND in the internal nodes
You convert scores for each move into probabilities using a logistic function.
Daniel