Re: [computer-go] Ladders and UCT again
One is not so effective but simple. Trace all adjacent four intersections of all stones of a string with marking to avoid duplicate. The other is the combination of two dimensional shift, logical or, and logical and operations on bitboards using 128 bit (or wider) registers. -Hideki Łukasz Lew: <[EMAIL PROTECTED]>: >Can you describe your algorithms? > >Cheers, >Lukasz > >On Sat, Aug 2, 2008 at 19:36, Hideki Kato <[EMAIL PROTECTED]> wrote: >> David Fotland: <[EMAIL PROTECTED]>: >>>I keep liberty counts. >> >> Me too. Also is Hiroshi. >> >> -Hideki >> >>>David >>> >>>> -Original Message- >>>> From: [EMAIL PROTECTED] [mailto:computer-go- >>>> [EMAIL PROTECTED] On Behalf Of Jason House >>>> Sent: Saturday, August 02, 2008 6:43 AM >>>> To: computer-go >>>> Subject: Re: [computer-go] Ladders and UCT again >>>> >>>> On Aug 2, 2008, at 4:31 AM, Gunnar Farneb ck <[EMAIL PROTECTED]> >>>> wrote: >>>> >>>> > It's often a good idea to bias capturing moves in the playouts, >>>> > regardless whether it's a ladder or not. This would result in those >>>> > stones being captured in most simulations. >>>> >>>> What method do people use for finding capture moves in playouts? >>>> Pseudo liberties can miss simple stuff like open triangles and one- >>>> eyed groups. Additionally, some literature discusses captures to add >>>> group liberties. What's the preferred method to detect >>>> that?___ >>>> 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/ >> -- >> [EMAIL PROTECTED] (Kato) >> ___ >> 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/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Ladders and UCT again
I keep a count of the number of liberties for each string of stones. It's updated incrementally when each stone is placed. I only use it for finding captures. I don't read ladders during playouts. Keeping liberty counts is not expensive. I was getting 50k playouts per second on a 2.3 GHz Core2 Duo (1 CPU) just running random playouts without UCT. With UCT, 3x3 patterns, simple local tactical responses, superko test at uct nodes, etc, it slowed down to 30k playouts/second. Incorporating Many Faces and RAVE into the UCT search slowed it down to 12K playouts/second, but made it much stronger. All of these numbers are for 9x9. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Lukasz Lew > Sent: Saturday, August 02, 2008 3:50 PM > To: computer-go > Subject: Re: [computer-go] Ladders and UCT again > > Can you describe your algorithms? > > Cheers, > Lukasz > > On Sat, Aug 2, 2008 at 19:36, Hideki Kato <[EMAIL PROTECTED]> > wrote: > > David Fotland: <[EMAIL PROTECTED]>: > >>I keep liberty counts. > > > > Me too. Also is Hiroshi. > > > > -Hideki > > > >>David > >> > >>> -Original Message- > >>> From: [EMAIL PROTECTED] [mailto:computer-go- > >>> [EMAIL PROTECTED] On Behalf Of Jason House > >>> Sent: Saturday, August 02, 2008 6:43 AM > >>> To: computer-go > >>> Subject: Re: [computer-go] Ladders and UCT again > >>> > >>> On Aug 2, 2008, at 4:31 AM, Gunnar Farneb ck > <[EMAIL PROTECTED]> > >>> wrote: > >>> > >>> > It's often a good idea to bias capturing moves in the playouts, > >>> > regardless whether it's a ladder or not. This would result in > those > >>> > stones being captured in most simulations. > >>> > >>> What method do people use for finding capture moves in playouts? > >>> Pseudo liberties can miss simple stuff like open triangles and one- > >>> eyed groups. Additionally, some literature discusses captures to > add > >>> group liberties. What's the preferred method to detect > >>> that?___ > >>> 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/ > > -- > > [EMAIL PROTECTED] (Kato) > > ___ > > 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] Ladders and UCT again
Can you describe your algorithms? Cheers, Lukasz On Sat, Aug 2, 2008 at 19:36, Hideki Kato <[EMAIL PROTECTED]> wrote: > David Fotland: <[EMAIL PROTECTED]>: >>I keep liberty counts. > > Me too. Also is Hiroshi. > > -Hideki > >>David >> >>> -Original Message- >>> From: [EMAIL PROTECTED] [mailto:computer-go- >>> [EMAIL PROTECTED] On Behalf Of Jason House >>> Sent: Saturday, August 02, 2008 6:43 AM >>> To: computer-go >>> Subject: Re: [computer-go] Ladders and UCT again >>> >>> On Aug 2, 2008, at 4:31 AM, Gunnar Farneb ck <[EMAIL PROTECTED]> >>> wrote: >>> >>> > It's often a good idea to bias capturing moves in the playouts, >>> > regardless whether it's a ladder or not. This would result in those >>> > stones being captured in most simulations. >>> >>> What method do people use for finding capture moves in playouts? >>> Pseudo liberties can miss simple stuff like open triangles and one- >>> eyed groups. Additionally, some literature discusses captures to add >>> group liberties. What's the preferred method to detect >>> that?___ >>> 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/ > -- > [EMAIL PROTECTED] (Kato) > ___ > 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] Ladders and UCT again
On Sat, Aug 2, 2008 at 16:06, Álvaro Begué <[EMAIL PROTECTED]> wrote: > On Sat, Aug 2, 2008 at 9:43 AM, Jason House <[EMAIL PROTECTED]> wrote: >> On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: >> >>> It's often a good idea to bias capturing moves in the playouts, >>> regardless whether it's a ladder or not. This would result in those >>> stones being captured in most simulations. >> >> What method do people use for finding capture moves in playouts? Pseudo >> liberties can miss simple stuff like open triangles and one-eyed groups. >> Additionally, some literature discusses captures to add group liberties. >> What's the preferred method to detect >> that?___ > > When we wrote dimwit, John Tromp found a fast method that I described > here: http://computer-go.org/pipermail/computer-go/2007-November/012342.html > > However, my current thinking is that it's probably best to just keep a > real liberty count and a list of liberties for each chain. This way > you can also find atari moves, which would be very hard to do if you > only keep pseudo-liberties. Do you have any proposal how to find true number of liberties? Cheers, Lukasz > ___ > 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] Ladders and UCT again
David Fotland: <[EMAIL PROTECTED]>: >I keep liberty counts. Me too. Also is Hiroshi. -Hideki >David > >> -Original Message- >> From: [EMAIL PROTECTED] [mailto:computer-go- >> [EMAIL PROTECTED] On Behalf Of Jason House >> Sent: Saturday, August 02, 2008 6:43 AM >> To: computer-go >> Subject: Re: [computer-go] Ladders and UCT again >> >> On Aug 2, 2008, at 4:31 AM, Gunnar Farnebck <[EMAIL PROTECTED]> >> wrote: >> >> > It's often a good idea to bias capturing moves in the playouts, >> > regardless whether it's a ladder or not. This would result in those >> > stones being captured in most simulations. >> >> What method do people use for finding capture moves in playouts? >> Pseudo liberties can miss simple stuff like open triangles and one- >> eyed groups. Additionally, some literature discusses captures to add >> group liberties. What's the preferred method to detect >> that?___ >> 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/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Ladders and UCT again
I keep liberty counts. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Jason House > Sent: Saturday, August 02, 2008 6:43 AM > To: computer-go > Subject: Re: [computer-go] Ladders and UCT again > > On Aug 2, 2008, at 4:31 AM, Gunnar Farneb�ck <[EMAIL PROTECTED]> > wrote: > > > It's often a good idea to bias capturing moves in the playouts, > > regardless whether it's a ladder or not. This would result in those > > stones being captured in most simulations. > > What method do people use for finding capture moves in playouts? > Pseudo liberties can miss simple stuff like open triangles and one- > eyed groups. Additionally, some literature discusses captures to add > group liberties. What's the preferred method to detect > that?___ > 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] Ladders and UCT again
Depending on your implementation, it may be faster to re-derive the liberty list when you need it. For example, if your playout move suggester only suggests capturing the last stone played, you don't need to do all of the work to update liberty counts for any other chains. Thanks a lot for everyone's help here. I think I have my ladder- reader working, although my program was still playing out ladders. The solution turned out to be something completely different: turn up the "exploration" coefficient in the UCT formula. If it's too low, the program commits to a particular move too early, builds up a lot of playouts through that move, and keeps playing the move even though it has read a sequence of follow-ups that lead to a bad result. Peter Drake http://www.lclark.edu/~drake/ On Aug 2, 2008, at 7:06 AM, Álvaro Begué wrote: On Sat, Aug 2, 2008 at 9:43 AM, Jason House <[EMAIL PROTECTED]> wrote: On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: It's often a good idea to bias capturing moves in the playouts, regardless whether it's a ladder or not. This would result in those stones being captured in most simulations. What method do people use for finding capture moves in playouts? Pseudo liberties can miss simple stuff like open triangles and one-eyed groups. Additionally, some literature discusses captures to add group liberties. What's the preferred method to detect that?___ When we wrote dimwit, John Tromp found a fast method that I described here: http://computer-go.org/pipermail/computer-go/2007-November/ 012342.html However, my current thinking is that it's probably best to just keep a real liberty count and a list of liberties for each chain. This way you can also find atari moves, which would be very hard to do if you only keep pseudo-liberties. ___ 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] Ladders and UCT again
On Sat, Aug 2, 2008 at 9:43 AM, Jason House <[EMAIL PROTECTED]> wrote: > On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > >> It's often a good idea to bias capturing moves in the playouts, >> regardless whether it's a ladder or not. This would result in those >> stones being captured in most simulations. > > What method do people use for finding capture moves in playouts? Pseudo > liberties can miss simple stuff like open triangles and one-eyed groups. > Additionally, some literature discusses captures to add group liberties. > What's the preferred method to detect > that?___ When we wrote dimwit, John Tromp found a fast method that I described here: http://computer-go.org/pipermail/computer-go/2007-November/012342.html However, my current thinking is that it's probably best to just keep a real liberty count and a list of liberties for each chain. This way you can also find atari moves, which would be very hard to do if you only keep pseudo-liberties. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: It's often a good idea to bias capturing moves in the playouts, regardless whether it's a ladder or not. This would result in those stones being captured in most simulations. What method do people use for finding capture moves in playouts? Pseudo liberties can miss simple stuff like open triangles and one- eyed groups. Additionally, some literature discusses captures to add group liberties. What's the preferred method to detect that?___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
Peter Drake wrote: > On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: > >> The neighbours of the last move come in the picture because usually >> it's only the last stone played that can be escaping a ladder and it's >> the neighbours of the last move that could have been put into atari. >> Nothing to do with the additional complexities Don mentioned. > > Let me give a specific example. Suppose that, during a playout, the tree > leads us to this position, with O to play: > > *.* > *...OO* > *..O##a...* > *...Ob* > *c* > *.* > *.* > *.* > *.* > > Having reached the frontier of the tree, we now finish the game using > Monte Carlo with a ladder reader. The last stone played, to the left of > a, is trapped in a ladder, but can escape if not chased. Our ladder > reader therefore suggests O play at a. > > For the next move in the playout, if # only reads ladders from the last > move played, it will see that the O stone at a is not in a ladder, so > move is suggested. The playout now turns completely random, and it's a > coin toss as to whether the group will escape. It's often a good idea to bias capturing moves in the playouts, regardless whether it's a ladder or not. This would result in those stones being captured in most simulations. > If we also search stones next to the last stone played, things only get > slightly better. # sees that its stones are in a ladder from which they > cannot escape, so it doesn't suggest b. If we tell it to play a ladder > breaker in such situations, it might play c, which is fine. However, on > O's next turn, c is not in a ladder, nor is any stone next to c, so no > move is suggested. Specifically, O does not make the vital capture at b. > > It seems too expensive to search every point on the board for ladders. > What to do? Don't bother with ladder breakers in playouts. If the tree part of the search has started to run a ladder, the best thing the playout can do is to keep running it until the bitter end. This way the losing player in the ladder will be rightfully punished and discouraged from trying that line of play. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
Ladder read should be helpful in the open space. But when the surrounding area is not full of space, the ladder play could hurt the eyes. for example below in the corner. b is better than a. By ladder reading, it would play at a, and the defender answer at b, leaves the attacker no eye in the corner. *|.#.* *|b..* *|.##aO..* *---* On Fri, Aug 1, 2008 at 1:37 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > > On 1-aug-08, at 14:15, Peter Drake wrote: > > On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: > > The neighbours of the last move come in the picture because usually it's > only the last stone played that can be escaping a ladder and it's the > neighbours of the last move that could have been put into atari. Nothing to > do with the additional complexities Don mentioned. > > > Let me give a specific example. Suppose that, during a playout, the tree > leads us to this position, with O to play: > *.* > *...OO* > *..O##a...* > *...Ob* > *c* > *.* > *.* > *.* > *.* > > Having reached the frontier of the tree, we now finish the game using Monte > Carlo with a ladder reader. The last stone played, to the left of a, is > trapped in a ladder, but can escape if not chased. Our ladder reader > therefore suggests O play at a. > > For the next move in the playout, if # only reads ladders from the last > move played, it will see that the O stone at a is not in a ladder, so move > is suggested. The playout now turns completely random, and it's a coin toss > as to whether the group will escape. > > > That's it. That's all there's to it. (Assuming you meant to write "so no > move is suggested".) > > If we also search stones next to the last stone played, things only get > slightly better. # sees that its stones are in a ladder from which they > cannot escape, so it doesn't suggest b. > > > Exactly. This is the neighbour part. In case 'a' was played by accident and > # can escape it will suggest 'b'. > > If we tell it to play a ladder breaker in such situations, it might play c, > which is fine. However, on O's next turn, c is not in a ladder, nor is any > stone next to c, so no move is suggested. Specifically, O does not make the > vital capture at b. > > > I don't bother with ladder-breakers. > > > It seems too expensive to search every point on the board for ladders. What > to do? > > > What you could do is keep track of stones with one or two liberties and > keep them in a list. But I found it's still too expensive for relatively > little gain in strength, although I'd have to admit not yet having exhausted > all possibilities here. > > What was the question again? ;-) > > Mark > > > ___ > 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] Ladders and UCT again
On 1-aug-08, at 14:15, Peter Drake wrote: On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: The neighbours of the last move come in the picture because usually it's only the last stone played that can be escaping a ladder and it's the neighbours of the last move that could have been put into atari. Nothing to do with the additional complexities Don mentioned. Let me give a specific example. Suppose that, during a playout, the tree leads us to this position, with O to play: . ...OO ..O##a... ...Ob c . . . . Having reached the frontier of the tree, we now finish the game using Monte Carlo with a ladder reader. The last stone played, to the left of a, is trapped in a ladder, but can escape if not chased. Our ladder reader therefore suggests O play at a. For the next move in the playout, if # only reads ladders from the last move played, it will see that the O stone at a is not in a ladder, so move is suggested. The playout now turns completely random, and it's a coin toss as to whether the group will escape. That's it. That's all there's to it. (Assuming you meant to write "so no move is suggested".) If we also search stones next to the last stone played, things only get slightly better. # sees that its stones are in a ladder from which they cannot escape, so it doesn't suggest b. Exactly. This is the neighbour part. In case 'a' was played by accident and # can escape it will suggest 'b'. If we tell it to play a ladder breaker in such situations, it might play c, which is fine. However, on O's next turn, c is not in a ladder, nor is any stone next to c, so no move is suggested. Specifically, O does not make the vital capture at b. I don't bother with ladder-breakers. It seems too expensive to search every point on the board for ladders. What to do? What you could do is keep track of stones with one or two liberties and keep them in a list. But I found it's still too expensive for relatively little gain in strength, although I'd have to admit not yet having exhausted all possibilities here. What was the question again? ;-) Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
From: Peter Drake <[EMAIL PROTECTED]> > It seems too expensive to search every point on the board for ladders. What > to do? Perhaps it would be worthwhile to preserve state from board to board - there are unlikely to be more than 2 or 3 ladders on any given board. When a stone is played, determine whether a new ladder has been created, or the status of an existing ladder has changed. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: The neighbours of the last move come in the picture because usually it's only the last stone played that can be escaping a ladder and it's the neighbours of the last move that could have been put into atari. Nothing to do with the additional complexities Don mentioned. Let me give a specific example. Suppose that, during a playout, the tree leads us to this position, with O to play: . ...OO ..O##a... ...Ob c . . . . Having reached the frontier of the tree, we now finish the game using Monte Carlo with a ladder reader. The last stone played, to the left of a, is trapped in a ladder, but can escape if not chased. Our ladder reader therefore suggests O play at a. For the next move in the playout, if # only reads ladders from the last move played, it will see that the O stone at a is not in a ladder, so move is suggested. The playout now turns completely random, and it's a coin toss as to whether the group will escape. If we also search stones next to the last stone played, things only get slightly better. # sees that its stones are in a ladder from which they cannot escape, so it doesn't suggest b. If we tell it to play a ladder breaker in such situations, it might play c, which is fine. However, on O's next turn, c is not in a ladder, nor is any stone next to c, so no move is suggested. Specifically, O does not make the vital capture at b. It seems too expensive to search every point on the board for ladders. What to do? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
On 31-jul-08, at 21:00, Peter Drake wrote: What you're missing (or so it seems to me) is that it's not to prevent from running a ladder that is caught. Really? My motivation has been to prevent my program from embarrassingly running in just those situations. Is there something other than a ladder reader used for this? The embarassing escape from a ladder that doesn't work is a side- effect resulting from the horizon problem. It's not isolated to ladders but a general problem of which ladders are the most easily recognised form. What happens is that a losing position is made to look better by playing forcing moves that push the moves that make it see the position is bad over the horizon. Using a ladder reader does help in this case, as at least it prevents the ladder from escaping during playout when it shouldn't. So the ladder reader makes the MC evaluation more accurate but does not prevent the horizon problem entirely. It is to ensure to escape when you can or capture when necessary to prevent an escape. And not only the last stone played of course, it could be the neighbour of the last stone played as well. The neighbor point is useful. Of course, as Don pointed out in another message, there are always additional complexities to add -- what if one of the attacking groups is in atari, or can be put in atari? I'm more interested in the bigger issue: exactly what question is the ladder reader trying to answer? When does it suggest a move and when doesn't it? It's simple really. If a big chain is put into atari and it can easily escape, the MC playouts will still only give it a 50-50% chance of escaping. This distorts the MC evaluation from what it should be ideally. So instead of leaving the escape up to chance, the ladder-reader makes sure that the escaping-move is always tried when it has been read out it can indeed escape. Whenever a chain is put into atari, the ladder reader checks if it can escape and suggest the escaping move instead of a random one. In case a (random) move is played where a chain was previously in atari but now has two liberties, the ladder-reader will see if the chain can be captured and suggest the capturing move instead of a random one. The neighbours of the last move come in the picture because usually it's only the last stone played that can be escaping a ladder and it's the neighbours of the last move that could have been put into atari. Nothing to do with the additional complexities Don mentioned. Hope this helps. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
Okay, let me see if I can sum this all up. Let <2, capture, attacker> stand for "defending chain has 2 liberties, it will be captured if the ladder is played out, and it is the attacker's turn". Use the following rules to suggest moves: <1, capture, defender> => defender plays ladder breaker, then attacker captures <1, capture, attacker> => no suggestion <1, escape, defender> => run (play out ladder), no suggestion for attacker's follow-up <1, escape, attacker> => capture <2, capture, defender> => run (to gain a 3rd liberty, escaping the ladder) <2, capture, attacker> => chase (play out ladder), no suggestion for defender's follow-up <2, escape, defender> => no suggestion <2, escape, attacker> => ladder breaker Which chains are considered? All of them with few enough liberties? If we only consider the last stone and its neighbors, moves elsewhere on the board will look disproportionately bad because they "disable" the ladder searcher. Peter Drake http://www.lclark.edu/~drake/ On Jul 31, 2008, at 5:06 PM, terry mcintyre wrote: From: Peter Drake <[EMAIL PROTECTED]> Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. A human player would not play "a random move;" the likelihood of a playing a ladder-breaker would be high. The opponent would then have to consider whether to capture the ladder or respond to the ladder-breaker in some other way. Higher-level players and those with experience programming Go can surely offer improvements. ___ 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] Ladders and UCT again
From: Peter Drake <[EMAIL PROTECTED]> >Our approach was to read out ladders involving the last stone played. >In the playout (beyond the tree), if the attacker can capture by >continuing a ladder, the attacker plays that move. If the defender can >escape by running, the defender plays that move. Otherwise, a random >move is played. A human player would not play "a random move;" the likelihood of a playing a ladder-breaker would be high. The opponent would then have to consider whether to capture the ladder or respond to the ladder-breaker in some other way. Higher-level players and those with experience programming Go can surely offer improvements. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
On Jul 31, 2008, at 4:24 PM, Mark Boon wrote: On 31-jul-08, at 19:50, Peter Drake wrote: I know we had this conversation recently, but I just can't seem to get my head around writing a ladder reader. What, exactly, does the ladder reader do? Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. The trouble seems to be that, once the attacker plays, there's nothing more for the ladder reader to say. At this point, it's 50-50 whether the attacker or defender will play on the defender's last liberty. Thus, the ladder reader doesn't give any pressure to stop running when caught in a ladder. What am I missing? What you're missing (or so it seems to me) is that it's not to prevent from running a ladder that is caught. Really? My motivation has been to prevent my program from embarrassingly running in just those situations. Is there something other than a ladder reader used for this? It is to ensure to escape when you can or capture when necessary to prevent an escape. And not only the last stone played of course, it could be the neighbour of the last stone played as well. The neighbor point is useful. Of course, as Don pointed out in another message, there are always additional complexities to add -- what if one of the attacking groups is in atari, or can be put in atari? I'm more interested in the bigger issue: exactly what question is the ladder reader trying to answer? When does it suggest a move and when doesn't it? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
I did a ladder reader once. Basically it's an alpha beta search where you focus on one group only, and that group has limited liberties. If it's strictly ladder reading, you only consider attacks that reduce the liberty count of a specific string to 1 (atari moves in other words) and defenses that bring up the count to 2.You stop the search when the liberty count can be increased to 3 or there are no moves that fit your criteria. Another trickier class of moves to consider for defenses are captures of stones that are attacking the target group. That is more complicated than just moving to liberty points. There are many optimizations possible and I think many sophisticated programs also consider target chains that have more than 2 liberties and you can also prune based on patterns and so on. What I've given you is pretty much the limit of my knowledge of ladder reading but I know it can get a lot more sophisticated than what I describe depending on how you want to use it. - Don On Thu, 2008-07-31 at 15:50 -0700, Peter Drake wrote: > I know we had this conversation recently, but I just can't seem to get > my head around writing a ladder reader. What, exactly, does the ladder > reader do? > > Our approach was to read out ladders involving the last stone played. > In the playout (beyond the tree), if the attacker can capture by > continuing a ladder, the attacker plays that move. If the defender can > escape by running, the defender plays that move. Otherwise, a random > move is played. > > The trouble seems to be that, once the attacker plays, there's nothing > more for the ladder reader to say. At this point, it's 50-50 whether > the attacker or defender will play on the defender's last liberty. > Thus, the ladder reader doesn't give any pressure to stop running when > caught in a ladder. > > What am I missing? > > Peter Drake > http://www.lclark.edu/~drake/ > > > > ___ > 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] Ladders and UCT again
On 31-jul-08, at 19:50, Peter Drake wrote: I know we had this conversation recently, but I just can't seem to get my head around writing a ladder reader. What, exactly, does the ladder reader do? Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. The trouble seems to be that, once the attacker plays, there's nothing more for the ladder reader to say. At this point, it's 50-50 whether the attacker or defender will play on the defender's last liberty. Thus, the ladder reader doesn't give any pressure to stop running when caught in a ladder. What am I missing? What you're missing (or so it seems to me) is that it's not to prevent from running a ladder that is caught. It is to ensure to escape when you can or capture when necessary to prevent an escape. And not only the last stone played of course, it could be the neighbour of the last stone played as well. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
On Thu, 2008-07-31 at 15:50 -0700, Peter Drake wrote: > I know we had this conversation recently, but I just can't seem to get > my head around writing a ladder reader. What, exactly, does the ladder > reader do? > > Our approach was to read out ladders involving the last stone played. > In the playout (beyond the tree), if the attacker can capture by > continuing a ladder, the attacker plays that move. If the defender can > escape by running, the defender plays that move. Otherwise, a random > move is played. > > The trouble seems to be that, once the attacker plays, there's nothing > more for the ladder reader to say. At this point, it's 50-50 whether > the attacker or defender will play on the defender's last liberty. > Thus, the ladder reader doesn't give any pressure to stop running when > caught in a ladder. > > What am I missing? I haven't implemented this yet, but... I'd have the ladder reader output one of two values: working ladders and broken ladders. An attacker should (only) continue a working ladder and a defender should (only) continue a broken ladder. It's important to detect if the status of a ladder changes. I know an early mogobot had a bias in the random playouts to capture stones in atari. > > Peter Drake > http://www.lclark.edu/~drake/ > > > > ___ > 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/
