Re: [computer-go] KO in Hashtable-UCT?
Alternatively, I wonder if there is some theoretical way to work it out? What is the most extreme example of being behind (either by X stones, or by some percentage, such as Heikki's 50% above) I think the bias comes as MCGO needs to finish the game up to the last stone/point... Killing a lot of stupid stones... Also, as MC doesn't know anything about Go except basic rules. Some very huge obvious moves aren't obvious for the engine. (potentially creating huge number of dead stones in the way to 'proof' it to itself) My 2 cents __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
In my experience adding a captured stoned limit per game biases the results. strongly. The limit was a constant number. Perhaps it could be good to define it as a function of current move number. In UCT-Suzie I stop also when one side has a big material advantage (captured much more stones). The length limit is related with this, because when a big group is captured the empty points are afterwards filled up again. __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On Wed, May 23, 2007 at 06:47:58AM -0300, Eduardo Sabbatella wrote: In my experience adding a captured stoned limit per game biases the results. strongly. In which direction? The limit was a constant number. Perhaps it could be good to define it as a function of current move number. I don't make any tests for the first 20 moves. Thereafter, I resign if - I have no stones left on board - I have less than half the number of stones my opponent has I also pass if my opponent has no stones left on board. I should do these in the MC simulations too, but so far I have been using Lew's libego unmodified. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
game biases the results. strongly. In which direction? I was comparing my engine with GNUGO 3.6 level 1. It looses more frequently. I don't make any tests for the first 20 moves. Thereafter, I resign if - I have no stones left on board - I have less than half the number of stones my opponent has I also pass if my opponent has no stones left on board. My cut logic was: dead stone difference X. stop the game, wins the player with less dead stones. I'm sure it was a very basic logic, using a more complex one, as you describe, could make sense. Cheers Eduardo __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
-Original Message- From: Eduardo Sabbatella [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wed, 23 May 2007 8:20 am Subject: Re: [computer-go] KO in Hashtable-UCT? game biases the results. strongly. In which direction? I was comparing my engine with GNUGO 3.6 level 1. It looses more frequently. I don't make any tests for the first 20 moves. Thereafter, I resign if - I have no stones left on board - I have less than half the number of stones my opponent has I also pass if my opponent has no stones left on board. My cut logic was: dead stone difference X. stop the game, wins the player with less dead stones. I'm sure it was a very basic logic, using a more complex one, as you describe, could make sense. Cheers Eduardo My guess is that you might just have the wrong threshold. If you only want to measure the winning percentage from a sequence of playout games, then, for a sufficiently high threshold 'X', you should get the correct value and still obtain a speedup worth having. Keep increasing the threshold until it stops making mistakes. If you are doing something else as well (e.g. keeping track of the percentage of games where each intersection winds up as white or black territory), then stopping playout games early can certainly cause problems. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
Heikki Levanto wrote: I don't make any tests for the first 20 moves. Thereafter, I resign if - I have no stones left on board - I have less than half the number of stones my opponent has I also pass if my opponent has no stones left on board. Eduardo Sabbatella wrote: My cut logic was: dead stone difference X. stop the game, wins the player with less dead stones. Dave Hillis wrote: ..., for a sufficiently high threshold 'X', you should get the correct value and still obtain a speedup worth having. Keep increasing the threshold until it stops making mistakes. Alternatively, I wonder if there is some theoretical way to work it out? What is the most extreme example of being behind (either by X stones, or by some percentage, such as Heikki's 50% above) where the losing player can make a comeback and win the game (assume perfect play by both players from that point)? It sounds like a puzzle the people who come up with the go bestiary [1] or huge nakade [2] would enjoy. (Of course, the nice thing about playouts is we don't need to be perfect, just right most of the time; but, still, a theoretical basis is always nice if one is available.) Darren [1]: http://www.goban.demon.co.uk/go/bestiary/rule_challenge.html [2]: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
What is the most extreme example of being behind (either by X stones, or by some percentage, such as Heikki's 50% above) where the losing player can make a comeback and win the game (assume perfect play by both players from that point)? I realized this is quite trivial: a board position where N black stones are in atari, and N white stones are in atari, (where those two chains are not touching). White captures black, then black captures white. You need something for the chains around the stones in atari, so I'd estimate on a 9x9 board N is roughly 30, and on a 19x19 board N is roughly 160. The point being that N is high. Going back to the original issue, how about not stopping a playout early while there are multi-stone-chains in atari. This still leaves a few exceptions (e.g. when the N white stones have 2 liberties but cannot do anything to save themselves) but should take care of most situations. Or, similarly, require one side to have been more than X (e.g. X=15) points ahead for the last 3 or 4 moves. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On Sat, 2007-05-19 at 12:32 +0200, chrilly wrote: In the play-outs, I'm pretty sure infinite play-outs due to not using superko are possible - even with the randomness.But I have a limit on the length of the play-out games because when you use heavy play-outs the games can occasionally last for hundreds of moves. How do you evaluate a game which is stopped by reaching the length-limit? In UCT-Suzie I stop also when one side has a big material advantage (captured much more stones). The length limit is related with this, because when a big group is captured the empty points are afterwards filled up again. It's a rare occurrence that I have to stop a game early - but when I do I simply score the board assuming all stones are alive. Another thing you could do (if you're the anal type) is to finish the game after a certain point with the superko rule turned back on. You would start having to track the keys again. But this almost seems silly because a random game is only a guess anyway. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
The first option is what we do, too. Peter Drake http://www.lclark.edu/~drake/ On May 19, 2007, at 5:30 AM, Don Dailey wrote: On Sat, 2007-05-19 at 12:32 +0200, chrilly wrote: In the play-outs, I'm pretty sure infinite play-outs due to not using superko are possible - even with the randomness.But I have a limit on the length of the play-out games because when you use heavy play-outs the games can occasionally last for hundreds of moves. How do you evaluate a game which is stopped by reaching the length- limit? In UCT-Suzie I stop also when one side has a big material advantage (captured much more stones). The length limit is related with this, because when a big group is captured the empty points are afterwards filled up again. It's a rare occurrence that I have to stop a game early - but when I do I simply score the board assuming all stones are alive. Another thing you could do (if you're the anal type) is to finish the game after a certain point with the superko rule turned back on. You would start having to track the keys again. But this almost seems silly because a random game is only a guess anyway. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly So does your hash function consider all previous board states (for superKo)? If so, how? I can think of one way, but I don't use it since I have a tree that handles the allowable moves independent of the hashtable. When going down a variation the Hash and other Board-State Information like e.g. the KO-Point are stored on a stack. Starting from the current Top of Stack the detection goes down and search for the same hash-key and Ko-Point. Its the Repeated Position Detection method of chess. The Gamestack-Pointer is decremented by 2, one can stop, when a non-capturing move is done (in chess its the other way round). One can start 4 Plies from the top of stack. Due to the stoping criterion one has to check only a few entries (most of the time none). If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. Probably a better way is to ignore the result. But I assumed that SuperKO is a rare event and the result has no significant impact on the search-tree. Maybe there is something wrong with this approach and the Ko-Problems I have a related to this simple SuperKO handling. I noticed several times that a direct transformation of chess methods has some subtle flaws. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On 5/18/07, Chrilly [EMAIL PROTECTED] wrote: When going down a variation the Hash and other Board-State Information like e.g. the KO-Point are stored on a stack. Starting from the current Top of Stack the detection goes down and search for the same hash-key and Ko-Point. Its the Repeated Position Detection method of chess. The Gamestack-Pointer is decremented by 2, one can stop, when a non-capturing move is done (in chess its the other way round). Non-capturing moves can create repetition (but there will of course be captures elsewhere in the cycle). Fortunately, there are other simple criteria. E.g., you can stop whenever a move is played on an intersection for the first time. If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. I guess you mean the *change* in material balance after one cycle. I don't see why komi should be used here. Probably a better way is to ignore the result. Only for balanced cycles. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
Non-capturing moves can create repetition (but there will of course be captures elsewhere in the cycle). So far the SuperKOs I have found where a round-trip of KOs. Fortunately, there are other simple criteria. E.g., you can stop whenever a move is played on an intersection for the first time. Okay. If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. I guess you mean the *change* in material balance after one cycle. I don't see why komi should be used here. No. I assume the game is over. As there is usually no reliable method for counting territory I use the difference of the captured stones as a - first approximation - for the evaluation. If e.g. both sides have captured - in the whole game - the same amount of stones, the eval is 0, but white wins due to Komi. At least for significant differences in captures this is true. MC-Runs are also stopped, when one sides leads in Capture by a large margin. Depending on the margin it produces only a negible bias. Only for balanced cycles. The cycles I have found so far are balanced. Each side captures in turn 1 stone. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On 5/18/07, chrilly [EMAIL PROTECTED] wrote: Non-capturing moves can create repetition (but there will of course be captures elsewhere in the cycle). So far the SuperKOs I have found where a round-trip of KOs. Maybe the others are just hiding from you ;-) Fortunately, there are other simple criteria. E.g., you can stop whenever a move is played on an intersection for the first time. Okay. If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. I guess you mean the *change* in material balance after one cycle. I don't see why komi should be used here. No. I assume the game is over. As there is usually no reliable method for counting territory I use the difference of the captured stones as a - first approximation - for the evaluation. If e.g. both sides have captured - in the whole game - the same amount of stones, the eval is 0, but white wins due to Komi. At least for significant differences in captures this is true. MC-Runs are also stopped, when one sides leads in Capture by a large margin. Depending on the margin it produces only a negible bias. Hmm... To me it seems more natural that the evaluation primarily depends on the nature of the cycle. Your program may choose to play a cycle because of some arbitrary material balance value, which will be meaningless if you can't break out of that cycle. IMO you should simply treat balanced cycles as draws. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. Orego's current approach is: During search, just maintain a single ko point and ignore superko. (There is a maximum number of moves per game to prevent infinitely long games.) After search, when actually making a move: 1) Make a copy of the board 2) Compute the Zobrist hash of the current position from scratch 3) Check for superko violations (against a stack of previous Zobrist hashes for positions in the real game,) 4) If there is a violation, go back to the copy and try the next best move Thanks, Peter Drake http://www.lclark.edu/~drake/ On May 17, 2007, at 11:00 PM, Chrilly wrote: I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly So does your hash function consider all previous board states (for superKo)? If so, how? I can think of one way, but I don't use it since I have a tree that handles the allowable moves independent of the hashtable. When going down a variation the Hash and other Board-State Information like e.g. the KO-Point are stored on a stack. Starting from the current Top of Stack the detection goes down and search for the same hash-key and Ko-Point. Its the Repeated Position Detection method of chess. The Gamestack-Pointer is decremented by 2, one can stop, when a non-capturing move is done (in chess its the other way round). One can start 4 Plies from the top of stack. Due to the stoping criterion one has to check only a few entries (most of the time none). If a SuperKO occurs, the position is evaluated by the Material- Balance. BlackCaptures - WhiteCaptures + Komi. Probably a better way is to ignore the result. But I assumed that SuperKO is a rare event and the result has no significant impact on the search-tree. Maybe there is something wrong with this approach and the Ko- Problems I have a related to this simple SuperKO handling. I noticed several times that a direct transformation of chess methods has some subtle flaws. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On 5/18/07, Peter Drake [EMAIL PROTECTED] wrote: It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. In dimwit, we check for superko while descending the UCT tree, and only check basic ko in the MC playouts. Our check involves a single lookup (of the current, incrementally computed Zobrist key) in a hash_map of previous Zobrist keys, which is not all that expensive. I agree that doing superko checks in MC playouts would cause an unnecesary slowdown. regards, -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
After search, when actually making a move: 1) Make a copy of the board 2) Compute the Zobrist hash of the current position from scratch 3) Check for superko violations (against a stack of previous Zobrist hashes for positions in the real game,) 4) If there is a violation, go back to the copy and try the next best move But then you have an engine which does not converge to perfect play given infinite resources. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Keep the common case fast (was Re: [computer-go] KO in Hashtable-UCT?)
Yes, that sounds reasonable too. In thinking about optimization, the rule as always is keep the common case fast. The cases in UCT Go, in decreasing order of commonness, are: 1) Play a move in an MC playout 2) Play a UCT tree move 3) Start (or finish) a playout 4) Make (or accept) a move in the actual game 5) Initialize data structures and the beginning of the game 1 has to be blazingly fast. 2-3 have to be relatively fast. 4-5 don't matter much unless you're spending an outrageous amount of time on them. Also note that almost all UCT moves are played from nodes with very few children (often 0 or 1). Peter Drake http://www.lclark.edu/~drake/ On May 18, 2007, at 9:15 AM, John Tromp wrote: On 5/18/07, Peter Drake [EMAIL PROTECTED] wrote: It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. In dimwit, we check for superko while descending the UCT tree, and only check basic ko in the MC playouts. Our check involves a single lookup (of the current, incrementally computed Zobrist key) in a hash_map of previous Zobrist keys, which is not all that expensive. I agree that doing superko checks in MC playouts would cause an unnecesary slowdown. regards, -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
True... My experience has been that (largely) ignoring the extremely rare case of superko is a better use of the finite resources we have. Have others found the same thing? Peter Drake http://www.lclark.edu/~drake/ On May 18, 2007, at 9:19 AM, Chris Fant wrote: After search, when actually making a move: 1) Make a copy of the board 2) Compute the Zobrist hash of the current position from scratch 3) Check for superko violations (against a stack of previous Zobrist hashes for positions in the real game,) 4) If there is a violation, go back to the copy and try the next best move But then you have an engine which does not converge to perfect play given infinite resources. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
Peter Drake said: It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. Depending on how a program works, you may well need to check for repetitions other than straight ko, ie black white a2--pass b2--pass b1--a1 a2... Forrest Curo - This email was sent using AIS WebMail. http://www.americanis.net/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
I don't think you can ignore superko in the UCT search - you will lose games. You will also lose games even if you only check the move you will actually play in the game. But in the play-outs, it has almost no value whatsoever, even if it was free. (It probably has SOME value, but miniscule and clearly would weaken the program because you would do less play-outs in a given amount of time.) If you keep superko tests in the UCT tree, you have a scalable program. - Don On Fri, 2007-05-18 at 09:33 -0700, Peter Drake wrote: True... My experience has been that (largely) ignoring the extremely rare case of superko is a better use of the finite resources we have. Have others found the same thing? Peter Drake http://www.lclark.edu/~drake/ On May 18, 2007, at 9:19 AM, Chris Fant wrote: After search, when actually making a move: 1) Make a copy of the board 2) Compute the Zobrist hash of the current position from scratch 3) Check for superko violations (against a stack of previous Zobrist hashes for positions in the real game,) 4) If there is a violation, go back to the copy and try the next best move But then you have an engine which does not converge to perfect play given infinite resources. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
John's post is almost identical to mine! Sorry about that. I could have just said ditto for Lazarus. - Don On Fri, 2007-05-18 at 12:15 -0400, John Tromp wrote: On 5/18/07, Peter Drake [EMAIL PROTECTED] wrote: It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. In dimwit, we check for superko while descending the UCT tree, and only check basic ko in the MC playouts. Our check involves a single lookup (of the current, incrementally computed Zobrist key) in a hash_map of previous Zobrist keys, which is not all that expensive. I agree that doing superko checks in MC playouts would cause an unnecesary slowdown. regards, -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
Lazarus does full superko in the UCT search - but the play-out only look at simple KO. In the play-outs, I'm pretty sure infinite play-outs due to not using superko are possible - even with the randomness.But I have a limit on the length of the play-out games because when you use heavy play-outs the games can occasionally last for hundreds of moves.The more randomness you take out of the play-outs the more likely you will get ridiculously long loops. Superko would solve this, but it would also slow down the play-outs significantly.I see no reason to have the refinement of superko in a random play-out. - Don On Fri, 2007-05-18 at 09:01 -0700, Peter Drake wrote: It took me a long time to get around my mental block and accept the advice of everyone here, but your intuition is correct: superko is so rare, and so expensive to detect, that you should NOT check for it on every move. Orego's current approach is: During search, just maintain a single ko point and ignore superko. (There is a maximum number of moves per game to prevent infinitely long games.) After search, when actually making a move: 1) Make a copy of the board 2) Compute the Zobrist hash of the current position from scratch 3) Check for superko violations (against a stack of previous Zobrist hashes for positions in the real game,) 4) If there is a violation, go back to the copy and try the next best move Thanks, Peter Drake http://www.lclark.edu/~drake/ On May 17, 2007, at 11:00 PM, Chrilly wrote: I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly So does your hash function consider all previous board states (for superKo)? If so, how? I can think of one way, but I don't use it since I have a tree that handles the allowable moves independent of the hashtable. When going down a variation the Hash and other Board-State Information like e.g. the KO-Point are stored on a stack. Starting from the current Top of Stack the detection goes down and search for the same hash-key and Ko-Point. Its the Repeated Position Detection method of chess. The Gamestack-Pointer is decremented by 2, one can stop, when a non-capturing move is done (in chess its the other way round). One can start 4 Plies from the top of stack. Due to the stoping criterion one has to check only a few entries (most of the time none). If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. Probably a better way is to ignore the result. But I assumed that SuperKO is a rare event and the result has no significant impact on the search-tree. Maybe there is something wrong with this approach and the Ko-Problems I have a related to this simple SuperKO handling. I noticed several times that a direct transformation of chess methods has some subtle flaws. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
But then you have an engine which does not converge to perfect play given infinite resources. I assume that you're joking, given: a) a current lack of infinite resources, and b) a current lack of convergence of any kind. No, but I can rephrase for those spooked by the concept of infinity: But then you have an engine that stops scaling at an unknown point. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
I have now also finished a first version of UCT-Suzie (in parallel the Peter Woitke works on the Alpha-Beta Version). UCT-Suzie uses a hashtable, mainly because I found the programming of the tree too complicated. The Monte-Carlo part uses some simple patterns according the MoGo article. Progress is rather slow, because I am working (more than) full-time on FPGA-projects in Computer-Tomography. Here are the problems with hash tables as a tree: 1. Time - it is more expensive - you must gather the children together when making decisions about which node to expand (which generally involves re-generating the keys by making all the legal moves.) There are ways around this that trade space for time but in either case it is more expensive. I do not understand this. In UCT-Suzie the moves are generated, when a new leaf-node is reached. The Hashtable has a link to the move-list. When the node is reached the next time, the moves must not be generated again. Just the calculation of the UCT-Urgency value (WinRate + sqrt() ) has to be done. I assume that this calculation has to be done also in a tree representation. I see no difference in this respect with Gunnars Gnu-GO UCT code. Memory is at least for 9x9 no problem. The number of Monte-Carlo runs/sec. is about 17K (9x9). This can be improved, because the UCT-Player uses the Alpha-Beta DoMove/UndoMove functions which are overkill for UCT. 2. GHI - you must take special care to deal with Graph History Interaction - primarly recognizing that ko situations are different. You can get by with relatively simple solutions that don't fully address this issue but it's still imperfect. I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On 5/17/07, Chrilly [EMAIL PROTECTED] wrote: I have now also finished a first version of UCT-Suzie (in parallel the Peter Woitke works on the Alpha-Beta Version). UCT-Suzie uses a hashtable, mainly because I found the programming of the tree too complicated. The Monte-Carlo part uses some simple patterns according the MoGo article. Progress is rather slow, because I am working (more than) full-time on FPGA-projects in Computer-Tomography. Here are the problems with hash tables as a tree: 1. Time - it is more expensive - you must gather the children together when making decisions about which node to expand (which generally involves re-generating the keys by making all the legal moves.) There are ways around this that trade space for time but in either case it is more expensive. I do not understand this. In UCT-Suzie the moves are generated, when a new leaf-node is reached. The Hashtable has a link to the move-list. When the node is reached the next time, the moves must not be generated again. Just the calculation of the UCT-Urgency value (WinRate + sqrt() ) has to be done. I assume that this calculation has to be done also in a tree representation. I see no difference in this respect with Gunnars Gnu-GO UCT code. Memory is at least for 9x9 no problem. The number of Monte-Carlo runs/sec. is about 17K (9x9). This can be improved, because the UCT-Player uses the Alpha-Beta DoMove/UndoMove functions which are overkill for UCT. 2. GHI - you must take special care to deal with Graph History Interaction - primarly recognizing that ko situations are different. You can get by with relatively simple solutions that don't fully address this issue but it's still imperfect. I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly So does your hash function consider all previous board states (for superKo)? If so, how? I can think of one way, but I don't use it since I have a tree that handles the allowable moves independent of the hashtable. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
