Re: [computer-go] Transpostions in UCT search
Reinforcement Learning terminology :-) In Go the state is the board situation (stones, player to move, ko info, etc.), the action is simply the move. Together they form state-action pairs. A standard transposition table typically only has state values; action values can then be inferred from a one ply search. In a full graph representation the state-action values are the values of the edges. Erik On Mon, Oct 27, 2008 at 4:03 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > > On 27-okt-08, at 12:45, Erik van der Werf wrote: > > Using state-action values > > appears to solve the problem. > > What are 'state-action values'? > 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] Transpostions in UCT search
When a child has been sampled often through some other path a naive implementation may initially explore other less frequently visited children first. The new path leading to the transposition may therefore suffer from some initial bias. Using state-action values appears to solve the problem. Erik On Mon, Oct 27, 2008 at 2:21 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > A while ago I implemented what I thought was a fairly straightforward way to > deal with transpositions. But to my surprise it made the program weaker > instead of stronger. Since I couldn't figure out immediately what was wrong > with it, I decided to leave it alone for the time being. > > Just now I decided to do a search on transpostions and UCT in this mailing > list and it seems to have been discussed several times in the past. But from > what I found it's not entirely clear to me what was the conclusion of those > discussions. > > Let me first describe what I did (ar attempted to do): all nodes are stored > in a hash-table using a checksum. Whenever I create a new node in the tree I > add it in the hash-table as well. If two nodes have the same checksum, they > are stored at the same slot in the hashtable in a small list. > > When I add a node to a slot that already contains something, then I use the > playout statistics of the node(s) already there and propagate that up the > tree. When I have done a playout I propagate the result of the single > playout up the tree, but at each step I check in the hashtable to see if > there are multiple paths to update. > > I've seen some posts that expressed concerns about using the existing > statistics of another path. This may be the reason I'm not seeing any > improvement. So I was wondering if there's any consensus about how to deal > with transpositions in a UCT tree. Or if someone could point me to other > sources of information on the subject. > > 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] Ending games by two passes
On Fri, Oct 24, 2008 at 4:57 PM, Robert Jasiek <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>>
>> In my opinion the goal of a ko rule is to prevent games from not ending.
>
> All restriction rules (about suicide, cyclic repetition, successions of
> passes) contribute to that goal. Ko rules do so by restricting cycles,
> succession of pass rules do so to avoid very long encores.
>
>> 1: [1-eye-flaw], 2: [triple-ko,...]
>>
>> Is it mathematically impossible to construct a ko rule that allows 1 and
>
>> avoid 2? [...]
>> superko. It is overly restrictive.
>
> In principle, everything can be expressed by rules. E.g., both 1 and 2 can
> be avoided by the following, not overly restrictive restriction rules
> combination:
>
> - the basic ko rule as the 2 move rule (i.e., passes serve as ko threats)
> - the fixed ko rule ("A play may not leave position A and create position B
> if any earlier play has left position A and created position B.")
> - 3 ending passes
>
> The effect is that 1-eye-flaws can be removed, triple-kos are not fought,
> and triple-kos can be removed (one side is dead!).
>
> Fine in theory but nobody likes my very efficient invention :( Maybe you?
>
I guess more people would like it if triple-kos and other non-abusive
long cycles would lead to a tie.
Erik
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ending games by two passes
On Fri, Oct 24, 2008 at 11:47 AM, <[EMAIL PROTECTED]> wrote: > Please correct me if I'm wrong, but are you saying that white is alive with > TT-rules (=Tromp-Taylor?) or other rulesets with positional superko if black > has not enough eyes left to fill as ko threats? Yes. > If that's true, I would be disgusted if positional superko would ever be > accepted as a rule in human vs. human games. Does it really matter if it is human vs. human games? Why have different (inferior?) standards for computers anyway? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ending games by two passes
Hi Dave, This is a well-known problem with overly simplified rulesets. TT-advocates don't care about the rare anomalies. Did you notice that under positional superko you cannot take back the ko after *any* number of consecutive passes? This is yet another reason why in some cases filling an eye or playing in sure territory may be the best move... In your engine you don't want to use 3 passes unless absolutely necessary because of horizon effects. In my experience it is best to use 3 passes only if there is exactly one basic ko, and in all other cases use 2 passes to end the game. Erik On Fri, Oct 24, 2008 at 10:00 AM, <[EMAIL PROTECTED]> wrote: > Is it correct to end games by 2 consecutive passes? > > When I learned go 20 years ago I was taught that 3 consecutive passes are > required to end a game of go. > In practice 2 passes are sufficient in nearly all cases, but sometimes 2 > passes is not enough. > Suppose we have this position in a 5x5 game with area scoring and 2.5 komi: > > (0 = white, # = black) > > ABCDE > 5 00### > 4 00#+# > 3 +0### > 2 00##+ > 1 0#+## > > Black has just played C4. > > The controller is very simple. It only prohibits simple ko (superko is not > checked) and all stones left on the board when the game ends are considered > alive. > White now at C1. Black has no choice but pass and then white quickly passes > too. What happens now? > > If 2 passes end the game, the controller will award a win to white by the > komi. > If 3 passes are required to end the game, black captures at B1, white has no > choice but pass, then black captures at A3 and will (probably) win the game. > > On could argue that controllers are smarter than the controller in my > example, so 2 passes are usually sufficient in pactice, because the > controller will query the engines for dead stones. > But in my example, wouldn't both engines be justified to declare the white > stones alive because of the 2 pass rule? > > Also, if I am correct, (light) playouts are usually controlled by an > internal "controller" that is very similar to the controller in my example. > Wouldn't they be vulnerable to this type of situation? > > Why not avoid this issue simply by requiring 3 consecutive passes to end the > game? > > Am I missing something here? > > Dave > > > > > > > > > ___ > 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] komi study with CGOS data
Don, thanks for providing these statistics! Overall it suggests that on CGOS White only has a small advantage. I still don't like this, but it is not nearly as bad as I initially suspected. The initially decreasing percentages are somewhat puzzling. One might speculate that up to a certain level Black's strategy to dominate the center is easier, and White needs significant resources to learn how to build two sufficiently large living groups. My guess is that for 5-minute CGOS games the average level of play is still weak enough to keep White's advantage relatively close to 50%. I'm not sure how many programs actually play at peak strength on CGOS, but in the future we may expect to see an increasing group suffering from the large komi. Maybe it would be interesting to compare recent games to older games to see if there is a trend in the top group? Erik On Thu, Oct 9, 2008 at 6:08 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > Ok, I'm doing the komi study. I hope this data formats properly on > your email clients. > > I am not including the first day or two of games because I remember > that I started out with 6.5 komi but I think that only lasted a few > hours. > > I'm including ALL games unless they ended with an illegal move. > > I'm using bayeselo ratings. So each bot has only 1 rating over it's > entire lifetime of games. > > I do not include games where either player played less than 20 games. > 20 games does not give a very accurate rating, but I had to draw the > line somewhere. However it's probably within 100 ELO of being > correct. > > I require opponents to be within 100 ELO of each other. I ran this > many times using different minimum ELO values. > > The data seems to indicate that white's winning percentage at 7.5 komi > DECREASES with the strength of the players in general. > > HOWEVER, the 2500 ELO entry is intriguing. It shows a sudden jump > with a sample of 3400 games. Does anyone have an explanation for > that? Is this just sample error? Or are the programs finally strong > enough to start seeing that white wins at 7.5 komi? > > Another interesting fact is that whites win percentage drops below 50% > with some of these entries (stronger players.) > > > DIFF MIN ELOWHITETOTAL PERCENT > - --- --- --- --- > 100074513 141579 52.630 > 100 10074513 141579 52.630 > 100 20074511 141577 52.629 > 100 30074191 141054 52.598 > 100 40073723 140308 52.544 > 100 50073524 140009 52.514 > 100 60073427 139874 52.495 > 100 70072763 138921 52.377 > 100 80072335 138212 52.336 > 100 90071227 136490 52.185 > 100 100071192 136432 52.181 > 100 110071084 136231 52.179 > 100 120068862 132356 52.028 > 100 130067765 130428 51.956 > 100 140066562 128193 51.923 > 100 150064143 123672 51.865 > 100 160056458 108767 51.907 > 100 170053943 103828 51.954 > 100 18004079078999 51.634 > 100 19001840336247 50.771 > 100 20001685933340 50.567 > 100 21001379327399 50.341 > 100 2200 898618072 49.723 > 100 2300 855517266 49.548 > 100 2400 768615569 49.367 > 100 2500 1801 3400 52.971 > 100 2600 12 28 42.857 > > When I use a window of 200 ELO the data looks very similar. > > Here is the data when I require the difference to be 50 ELO or less: > > DIFF MIN ELOWHITETOTAL PERCENT > - --- --- --- --- > 5004618487556 52.748 > 50 1004618487556 52.748 > 50 2004618387555 52.747 > 50 3004603187326 52.712 > 50 4004589087100 52.687 > 50 5004581586996 52.663 > 50 6004581386993 52.663 > 50 7004537686377 52.533 > 50 8004510885932 52.493 > 50 9004405084302 52.253 > 50 10004403284277 52.247 > 50 11004396984163 52.243 > 50 12004284082193 52.121 > 50 13004236181354 52.070 > 50 14004150379735 52.051 > 50 15004100378853 51.999 > 50 16003795972933 52.046 > 50 17003628069569 52.150 > 50 18002847854845 51.925 > 50 1900 853516668 51.206 > 50 2000 789615433 51.163 > 50 2100 682313349 51.112 > 50 2200 4145 8120 51.047 > 50 2300 3917 7704 50.844 > 50 2400 3627 7166 50.614 > 50 2500 1497 2871 52.142 > 50 2600 12 28 42.857 > > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.o
Re: [computer-go] (early) termination of random playouts?
Anything can exist in a random game :-) Sent-two-return-one may me the biggest practical concern, but I would not be surprised if some day a molasses ko would pop up as well, especially if your playouts are not too stupid. Erik On Thu, Oct 9, 2008 at 5:24 PM, Jason House <[EMAIL PROTECTED]> wrote: > Which multi stone capture case still exists under random games? > > Sent from my iPhone > > On Oct 9, 2008, at 11:12 AM, "Erik van der Werf" <[EMAIL PROTECTED]> > wrote: > >> On Thu, Oct 9, 2008 at 5:03 PM, Jason House <[EMAIL PROTECTED]> >> wrote: >>> >>> On Oct 9, 2008, at 10:41 AM, "Erik van der Werf" >>> <[EMAIL PROTECTED]> >>> wrote: >>>> >>>> Sure, some long cycles have multi-stone captures. >>> >>> Can you provide an example? >> >> http://www.cs.cmu.edu/~wjh/go/rules/bestiary.html >> ___ >> 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] (early) termination of random playouts?
On Thu, Oct 9, 2008 at 5:03 PM, Jason House <[EMAIL PROTECTED]> wrote: > On Oct 9, 2008, at 10:41 AM, "Erik van der Werf" <[EMAIL PROTECTED]> > wrote: >> Sure, some long cycles have multi-stone captures. > > Can you provide an example? http://www.cs.cmu.edu/~wjh/go/rules/bestiary.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] (early) termination of random playouts?
Sure, some long cycles have multi-stone captures. Erik On Thu, Oct 9, 2008 at 4:39 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > You might be right. I have a liberal game length limit on my play-outs > so I didn't notice this. > > Another game limiting rule could be something based on counting the > number of consecutive 1 stone captures and terminating once this goes > beyond some reasonable limit such as 10.Would infinite games still > be possible with this rule? > > - Don > > > > On Thu, 2008-10-09 at 10:25 -0400, Jason House wrote: >> You are incorrect that the following heuristics in random games lead >> to finite game length: >> * no eye filling >> * no suicide >> * no simple ko violations >> >> Consider two eyeless chains with 3 ko's connecting them... Two taken >> by black and it's white's move. Filling the one ko it has is suicide. >> It must take a ko. On black's turn, it can't fill a ko due to suicide >> and must take a ko. The cycle repeats infinitely. >> >> Yes, this is a real bug found in a real CGOS game... I opted for the >> game length limit so my bot could remain online 24/7 >> >> Sent from my iPhone >> >> On Oct 9, 2008, at 9:15 AM, Don Dailey <[EMAIL PROTECTED]> wrote: >> >> > Claus, >> > >> > I think you have summarized things better than I am going to, but >> > here >> > goes anyway: >> > >> > If the play-outs are uniformly random and you have eye rule, it is >> > guaranteed to terminate as long as you use simple ko. It might even >> > be >> > guaranteed to terminate if you don't, I don't know. Although it's >> > guaranteed to terminate, it could be arbitrarily long (millions or >> > billions of moves) but that is not a practical consideration. The >> > odds >> > of it not terminating within a couple of hundred moves at 9x9 is >> > probably extremely low as long as you have eye and simple KO and do >> > not >> > allow suicide. >> > >> > If it's not uniformly random, all bets are off. >> > >> > If you want to be paranoid, you can limit the number of moves but it's >> > not necessary. Something like number of empty points times some >> > constant such as 2 or 3 might be good here. >> > >> > There are several eye rules used, but I believe the vast majority of >> > us >> > use the same one. It is stated like this: >> > >> > 1. An empty point surrounded by friendly stones. >> > 2. If edge, no diagonal enemies allowed. >> > 3. If NOT edge, only 1 diagonal enemy allowed. >> > >> > Some programs do these things in addition to simple ko, no suicide >> > allowed and eye rule: >> > >> > 1. Limit the number of moves. (not needed) >> > 2. Stop game if one side has many more stones than the other. >> > 3. Detect superko (a waste of time) >> > 4. Let pass move be one of the random moves tried. (bad) >> > >> > >> > You asked if people compared the eye rules. This has been discussed >> > on >> > this group before and the short answer seems to be that it probably >> > does >> > not make too much of a difference if it's reasonably sound. You >> > might >> > get different opinions on this. >> > >> > - Don >> > >> > >> > >> > >> > >> > On Thu, 2008-10-09 at 13:31 +0100, Claus Reinke wrote: >> >> Hi again, with yet another question:-) >> >> >> >> Could someone please summarize the state-of-the art wrt the various >> >> ways >> >> of limiting random playouts, and the their consequences? >> >> >> >> There are several variations on the "don't fill your own >> >> eyes" (dfyoe) approach, >> >> but the way this approach is often described tends to confuse me >> >> (eg, when >> >> someone seems to claim that there is exactly one correct way of >> >> implementing >> >> this, or when someone seems to claim that this guarantees >> >> termination, or when >> >> the resulting biases are not even mentioned, let alone discussed or >> >> compared >> >> against biases in alternative implementations, etc.). >> >> >> >> I'll try to summarize my current understanding, in the hope that >> >> others will >> >> fill in the missing pieces or point out misunderstandings: >> >> >> >> - the only thing that guarantees termination of random playouts >> >> (with or >> >>without dfyoe) is the positional superko rule: no whole-board >> >> repetitions >> >>allowed. Waiting for this to kick in without taking other >> >> measures is not >> >>an option: it takes too long and the results don't tell us much >> >> about the >> >>value of the initial position. >> >> >> >> - dfyoe variations share some motivations: >> >>- reduce the likelihood of unnaturally long playouts (but not to >> >> zero) >> >>- try to avoid disastrous endgame-situation mistakes that random >> >> playouts >> >>are otherwise prone to make (and that eliminate the value of >> >> playouts) >> >>- try to be simple (efficiently implementable), with low (but >> >> non-zero) >> >>probability of introducing errors (filling in when not >> >> filling in would be >> >>better, or vice versa) >> >>
Re: [computer-go] 7.5-komi for 9x9 in Beijing
Maybe we could just do a vote? Erik On Wed, Oct 8, 2008 at 11:56 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > On Wed, 2008-10-08 at 22:43 +0200, Erik van der Werf wrote: >> > The only reason I would favor one over the other >> > is if it turned out that in "practical play" the games ended up >> closer. >> > For instance if black won a 53% at 6.5 komi and white wins 51% at >> 7.5 >> > komi, I would favor 7.5 because it kept the scores close. >> >> Last week I was told that, with 7.5 komi against itself, Mogo wins >> over 60% as White. Also against my own program I have much better >> chances when playing White. > > I really don't trust this after doing the Leela experiments. > > Also, I studied this a while back with CGOS data and saw a very tiny > advantage for white, not much. This was even when I filtered the weaker > opponents out. I suppose I could do this again but it doesn't seem to > prove anything. > >> As programs become stronger the advantage for one side with fractional >> komi will inevitably become totally unbalanced. At some point we will >> approach 100% and then I rather have that go to the first player. The >> only fair alternative is to use integer komi. > > I think we have a long time for that to happen.When that day comes, > 9x9 will be like checkers is now, you have to play 10 or 20 draws just > to get 1 or 2 wins. > > - Don > > > > >> > > ___ > 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] 7.5-komi for 9x9 in Beijing
On Wed, Oct 8, 2008 at 9:46 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > On Wed, 2008-10-08 at 11:47 -0700, Christoph Birk wrote: >> On Wed, 8 Oct 2008, Don Dailey wrote: >> > much more common.There were just a few games that used 6.5 komi >> > because when I first started CGOS I had set 6.5 by mistake but I think >> > that was just for a few hours at most. The vast majority of these are >> > 7.5 komi games: >> >> After all this discussion about komi for 9x9 games, wouldn't you >> think that using 7.5 was a mistake and go back to 6.5 ? > > Why? 1) In my opinion the first player should have a chance to win even against the strongest possible opponents. 2) Currently at high levels 7.5 komi appears to give a huge advantage to White. 3) The playable openings for 6.5 komi appear to be more diverse (thus making the game more interesting). 4) Professionals use 6.5 > 5.5 gives black a huge advantage. Actually it should be almost the same as for 6.5 (see my previous email). > The only reason I would favor one over the other > is if it turned out that in "practical play" the games ended up closer. > For instance if black won a 53% at 6.5 komi and white wins 51% at 7.5 > komi, I would favor 7.5 because it kept the scores close. Last week I was told that, with 7.5 komi against itself, Mogo wins over 60% as White. Also against my own program I have much better chances when playing White. As programs become stronger the advantage for one side with fractional komi will inevitably become totally unbalanced. At some point we will approach 100% and then I rather have that go to the first player. The only fair alternative is to use integer komi. > I believe 6.5 would give black a bigger advantage than 7.5 gives white in > "practical play." This may be true for your CGOS games. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another 6x6 analysis.
On Fri, Oct 3, 2008 at 1:23 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > At http://trac.gnugo.org/6x6.sgf you can find an ongoing analysis of > 6x6. Nice! The main line looks correct. It even has an interesting 59-ply deep variation which I don't remember seeing before. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 7.5-komi for 9x9 in Beijing
On Fri, Oct 3, 2008 at 2:33 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > I had heard somewhere that there are some who believe 8.0 is the right > komi for 9x9 Chinese. I personally believed for a long time it was 7.0 > based on statistical data of games.However that can be misleading. Do you understand why even numbers are very unlikely? It's rather trivial, but somehow many people seem to miss it... On 9x9 the board we know that all intersections are either Black (B), White (W), or Neutral (N): B + W + N = 81 Without seki: W = 81 - B (no neutral intersections in the final position, so N = 0) Score = B - (W + komi) = 2B - (81+komi) Consequently: with 5.5 komi Black needs 44 points to win, with 6.0 komi Black needs 44 points to win, with 6.5 komi Black needs 44 points to win, with 7.0 komi Black needs 44 points to tie, with 7.5 komi Black needs 45 points to win, with 8.0 komi Black needs 45 points to win, with 8.5 komi Black needs 45 points to win, with 9.0 komi Black needs 45 points to tie At high levels on 9x9 it appears to be extremely difficult for Black to get 45 points. With seki: N = even For the common type of seki, where the stones living in seki share two liberties, the perfect komi is again an odd number; results are therefore consistent with the numbers above (without seki). N = odd Only if optimal play inevitably leads to a seki with an odd number of neutral intersections the perfect komi becomes an even number (in which case 7.5 might make sense). However, given what is known from professional level 9x9 games this seems unlikely. If there really are persons that believe that the perfect komi on 9x9 should be 8.0 then I would very much like to see a game record of such a game... I'm sure some top 9x9 programs will have fun trying to tear it apart :-) Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another 6x6 analysis.
On Fri, Oct 3, 2008 at 11:31 AM, Markus Enzenberger <[EMAIL PROTECTED]> wrote: > Gunnar Farnebäck wrote: >> >> To do that, just point your regular cgos client to trac.gnugo.org, >> port 6867. > > what rules does GNU Go use in the 6x6 analysis? > > I connected Fuego configured with CGOS rules. After a while it terminated, > because Fuego returned an error response to a play command with a move that > violated the positional superko rule. (By default, Fuego does not accept > illegal moves to avoid that configuration errors in experiments go by > unnoticed.) Makes sense, IIRC in my own analysis some years ago there were some interesting lines containing a long cycle that go up to about 49 ply from the empty board. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 7.5-komi for 9x9 in Beijing
>From all we know so far it is most likely that perfect komi is 7.0. Even numbers lik 6.0 and 8.0 are unlikely because they always require a seki with an odd number of shared liberties (in all optimal lines!). Since IMO the first player should have a chance to win it seems natural to set the komi 0.5 points *below* the perfect komi, which leads to 6.5. Further, I have a suspicion that 6.5 komi allows more diverse opening lines, which makes the game more interesting. Erik On Fri, Oct 3, 2008 at 1:35 AM, "Ingo Althöfer" <[EMAIL PROTECTED]> wrote: > Gian-Carlo Pascutto wrote: >> I'd have some preference for playing the decisive game >> with komi = 6.5, but apparently thats not possible on KGS. > > But that should not be a problem, as long as the operators > do not believe in the final verdict of KGS. > >> I think with komi = 7.5 white >> is scoring very high (too high?) in the top games. > > I made a count for the 9x9-competition in Beijing (komi=7.5: > > Looking only at games among the top 5 rankers > there are 20 games so far (including two tiebreak-games) > with 15 wins for White and 5 Wins for Black. > > Looking at all games among the top 7 rankers > there are 40 games (including two tiebrak-games) > with 27 : 13 for White. > > Taking all 164 games of the tournament (including two > tiebrak games) White is ahead by 93:71. > > It is probably not an accident that the quota decrease > with decreasing playing strength: > > 15/20 > 27/40 > 93/164 or translated to decimals > 0.75 > 0.675 > 0.567. > > However, when B+7 is the correct value on 9x9, > komi=6.5 might lead into similar problems. > > Ingo. > > -- > Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: > http://www.gmx.net/de/go/multimessenger > ___ > 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] On ranks 2 and 3 of 9x9 in Beijing
On Fri, Oct 3, 2008 at 12:13 AM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote: > I'd have some preference for playing the decisive game with komi = 6.5, > but apparently thats not possible on KGS. I think with komi = 7.5 white > is scoring very high (too high?) in the top games. Last year (when the komi was still 6.5) some participants played through kgs with Japanese rules. Of course internally their programs still used Chinese rules, so some final scores had to be corrected manually afterwards. Anyway, I think it would be much nicer if, at least for unrated games, one could simply set the komi to any value. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Wed, Sep 24, 2008 at 6:30 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > I don't know if even size boards are special, but it seems to me that > such small boards should have very high komi's. 4.0 seems pretty low > but then I'm really no expert on komi's and I'm a pretty weak player so > I'm not in any position to really say. The center is the best opening move for all small odd size boards. Small even size boards have a lower komi because there is no center point. I'm quite confident that 4.0 is the correct komi for 6x6. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Mon, Sep 22, 2008 at 7:14 PM, "Ingo Althöfer" <[EMAIL PROTECTED]> wrote: >>> Does someone here know of other (documented) attempts >>> to solve 6x6 Go? >> >> Didn't Erik van der Werf do it under his rules? > > He did it for 5x5-Go, see at > http://erikvanderwerf.tengen.nl/5x5/5x5solved.html > Several 6x6 positions were solved, but not the empty board. E.g., for the following position we could prove a Black win by at least 2 points (which took about 13 days in 2002). . . . . . . . . . # O . . . # O . . . . # O . . . . . # O . . . . . . . Optimal play on 6x6 under Chinese rules is expected to give a Black win by 4 points. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: 9x9 go Principle Variation with perfect play
On Sun, Sep 14, 2008 at 4:29 AM, Hideki Kato <[EMAIL PROTECTED]> wrote: > David Fotland: <[EMAIL PROTECTED]>: >>At this point I think everyone would agree that E5 is the optimal first move >>for black on 9x9. > > Some Japanese professionals say E5 is 1 to 2 points loss, though komi > is 6.5 and with Japanese rules. With a komi of 7.5 it may very well be that all opening moves lead to a loss. Black can only hope for a blunder by White. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Maybe these are the same? http://gobase.org/9x9/ Erik On Wed, Sep 10, 2008 at 4:38 PM, Olivier Teytaud <[EMAIL PROTECTED]> wrote: >> >> - There had been a TV program of professional 9x9 Go for years (some >> member of this list have the records of the games played in this >> program). Takemiya 9p and Yuki 9p were the strongest. > > I'm afraid the answer is no, but: > are these records free and available somewhere ? > > Thanks for your interesting informations around Go and 9x9 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] reminder, there is another possible computer go contest in Taizhou
On Wed, Aug 27, 2008 at 4:57 AM, David Fotland <[EMAIL PROTECTED]> wrote: > > In late september there is a computer go contest in Taizhou, with cash > prizes. They might cancel this contest due to lack of participation, so if > you are thinking of going, please let them know today or tomorrow. > > David > > From: ?? [EMAIL PROTECTED] > > This email is an invitation letter from the Institute of Computer GO at > Beijing University of Posts and Telecommunications, we've got your email > from the submission list of 2008 Conference of Computer Games and World 9*9 > Computer Go Championship. > > We are happy to announce that an international computer GO championship is > to be hosted by Taizhou city government and Beijing University of Posts and > Telecommunications. As 2008 Conference of Computer Games and World World 9*9 > Computer Go Championship will be held in Beijng this year, so we have time > for the game in this tournament before (September 22-26), to facilitate your > itinerary. > > This event does not require registration fee, and your the board and lodging > in Taizhou will be provided freely by the organizing committee, so you only > need to predate your China's trip one-week earlier, and the first > destination to be revised as Taizhou. If there is any problem on how to > reach Taizhou, we can provide some help. If you are willing to participate > in the tournament, only need to reply to this email, we will contact you. > > 2008 TaiZhou Computer Go Championship > > 1. The number of participating countries and regions: 20 countries and > regions, including China and the China Taipei. In accordance with the > relevant provisions of BOCOG, The participating teams and all staff from > China Taiwan use "Chinese Taipei" title. > 2. The number of entries: 50 > 3. Competition schedule: September 22 to September 26 > a. 9/22: receiption > b. 9/23: a round robin preliminaries way > c. 9/24: a round robin preliminaries way > d. 9/25: a round robin preliminaries way > e. 9/26: Final championship matches, and man-machine matches, award > ceremonies 4. Prize competition > 19x19 Go: > First place, 3,000 USD > Second place, 2,000 USD > Third place, 1,000 USD > Fourth place, 500 USD > Fifth place, 250 USD > > 9x9 Go: > First place, 2,000 USD. > Second place, 1,000 USD > Third place, 500 USD > Fourth place, 250 USD > > > -- > Zhiqing Liu, Ph.D. > Professor, School of Software Engineering Director, BUPT-JD Computer GO > Research Institute Beijing University of Posts and Telecommunications > Voice: +86-10-6228-2601 and +86-10-5882-8089 > Fax: +86-10-6228-2601 and +86-10-5882-8005 > Email: [EMAIL PROTECTED] > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > I already booked my flights; Steenvreter will only participate in the official ICGA events. Personally I think it is bad to have 3 competing tournaments so close to each other. I must say that I'm quite puzzled by the behavior of the local organizers in China. In my opinion, instead of running yet another tournament, professor Liu should have tried to supported the ICGA events with sponsorship for the Go competitions just as was done for the Chess tournament. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
On Thu, Aug 14, 2008 at 12:00 AM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote: > Mark Boon wrote: > >> Not an expert on AB-search or UCT search but there's a subtle >> difference I think. In AB search, if some processors have been >> searching in a branch that is subsequently cut off, the work is 100% >> wasted. In UCT there's no such black-and-white cutting. If you do >> sampling in what then turns out not to be the optimal branch, further >> sampling in the optimal branch may cause the UCT-value to drop to a >> point where you'd otherwise start sampling the sub-optimal branch >> again. So in that case you gain back part of the 'wasted' work. >> >> I'm also inclined to think that the 'chunks' of work that are wasted >> tend to be larger for AB-search than for UCT. But I'm not 100% sure. > > The problem is that the optimal settings for UCT appear to be much stronger > on the exploitation side than on the exploration side, making it much more > likely that such work is really wasted. > > It is not so obvious to me any more what the differences are between a state > of the art UCT searcher (i.e. with nearly no exploration) and a state of the > art alpha-beta searcher (i.e. with heavy late move reductions). One might consider heuristics like AMAF, pattern knowledge, etc. to be simply a more effective way to guide exploration. The UCB term has no domain-specific knowledge. It works surprisingly well but it should be no surprise that one can do better with domain-specific knowledge. > They both just hammer out the mainline deeper until the score drops a bit, > or an alternative rises strongly. > > UCT without exploration is just minimax, no? The move/path selection behaves like a best-first minimax, but where are the min/max operators in the updates? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Seki in playouts
On Tue, Aug 12, 2008 at 6:18 PM, Martin Mueller <[EMAIL PROTECTED]> wrote: > >> I >> did not realize that his program, even with a large tree, would not be >> able to recognize the seki. I knew of course that the original Mogo >> playouts had this problem, but I thought all strong programs had >> solved it by now... > > Hello Erik, > > seki in playouts is still an unsolved problem for Fuego as well. I have > tried many times to fix it by disabling selfatari moves. But anything I > tried made the program measurably weaker overall. Hi Martin, The tricky thing is to determine *when* to disable self-atari moves. Forgive me for not going into details now; if you ask me again in Beijing or after the Olympiad I'll say more. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
On Mon, Aug 11, 2008 at 7:58 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > Erik van der Werf wrote: >> For the final position in the game record any strong human player will >> tell you that the game is clearly over. No points are left to be >> gained and the result is obvious. > > Actually there's one point left to gain in the seki, since the game is > played with Chinese rules. ;-) You're right, my reply was sloppy (it seems I'm too much used to Japanese rules). Also I should have read GCP's email more carefully; I did not realize that his program, even with a large tree, would not be able to recognize the seki. I knew of course that the original Mogo playouts had this problem, but I thought all strong programs had solved it by now... Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
On Mon, Aug 11, 2008 at 6:17 PM, Jason House <[EMAIL PROTECTED]> wrote: > On Aug 11, 2008, at 12:02 PM, "Erik van der Werf" <[EMAIL PROTECTED]> > wrote: > >> On Mon, Aug 11, 2008 at 4:54 PM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> >> wrote: >>> >>> >> Some time ago I observed that kgsgtp does not tell my program that the >> opponent has resigned (which is a bit annoying because it then keeps >> pondering when the game is already over). > > > KgsGtp should send kgs-game_over in such cases. Hmm, guess I missed that command. I had solved the issue by setting an upper bound on the ponder time, which also works well for playing manually. Thanks, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
On Mon, Aug 11, 2008 at 4:54 PM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote: > She was also a bit "unlucky" in the sense that Leela did not understand it > was dead lost. > > I use quotes because had it understood better it was losing, it would have > put up more of a fight :-) If Basti is correct that Leela resigned that would suggest that 'she' actually did understand. For the final position in the game record any strong human player will tell you that the game is clearly over. No points are left to be gained and the result is obvious. If Leela had persisted in attempting to push the opponent through the clock, then I guess any EGC referee would have considered that 'unsportsmanlike' behavior (but it would of course be nice to know for sure). >> As time was running out and the robot played obstinate moves, I told >> the operator to kill it. However, it looked to me like he never >> touched the keyboard, so when a dialog appeared, stating that >> LeelaBot had resigned, I asked him if he had killed the robot, and he >> replied he did not. > > The KGS server should have recorded the resignation instantly, but there > is no sign of it in the game record. Some time ago I observed that kgsgtp does not tell my program that the opponent has resigned (which is a bit annoying because it then keeps pondering when the game is already over). It's a long shot but maybe this behavior somehow also goes the other way around? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
On Mon, Aug 11, 2008 at 4:14 PM, Basti Weidemyr <[EMAIL PROTECTED]> wrote: > What would you have done in a case like this? :) Inspect the log file. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
On Fri, Aug 8, 2008 at 11:07 PM, steve uurtamo <[EMAIL PROTECTED]> wrote: > i don't think that it's known to be exptime-complete. http://www.ics.uci.edu/~eppstein/cgt/hard.html E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computer Go tournament at EGC, Leksand, Sweden
On Wed, Jul 23, 2008 at 2:55 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > Erik van der Werf wrote: >> >> On Thu, Jul 17, 2008 at 6:39 PM, Erik van der Werf >> <[EMAIL PROTECTED]> wrote: >> >>> >>> On Thu, Jul 17, 2008 at 6:18 PM, Don Dailey <[EMAIL PROTECTED]> wrote: >>> >>>> >>>> Did you know that you can create your own linux environment without >>>> having >>>> to "touch" the machine you will be using? >>>> >>> >>> I have DSL-N (Damn Small Linux) on a USB stick so I can probably make >>> something that boots. However I'm woried about the hardware support >>> and network configuration (it has to connect to KGS). Also I think I >>> would have to upgrade the kernel, but I don't know how easy that will >>> be with DSL (and if I have time for it). Anyway, simply using an ssh >>> connection to my machine at home would have been *much* easier... >>> >> >> FYI >> >> Installing Ubuntu 8.04 on a USB stick solved the problem on all >> hardware I tested on (6 different Machines, of which 5 are Dell's). >> > > How big is the memory stick? I have a fast 4 gig stick that I want to put > to use but I'm not sure I could get a very comfortable Ubuntu installation > working on it.I guess for this purpose you don't need much software > installed. I used a 4 GB stick. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computer Go tournament at EGC, Leksand, Sweden
On Thu, Jul 17, 2008 at 6:39 PM, Erik van der Werf <[EMAIL PROTECTED]> wrote: > On Thu, Jul 17, 2008 at 6:18 PM, Don Dailey <[EMAIL PROTECTED]> wrote: >> Did you know that you can create your own linux environment without having >> to "touch" the machine you will be using? > > I have DSL-N (Damn Small Linux) on a USB stick so I can probably make > something that boots. However I'm woried about the hardware support > and network configuration (it has to connect to KGS). Also I think I > would have to upgrade the kernel, but I don't know how easy that will > be with DSL (and if I have time for it). Anyway, simply using an ssh > connection to my machine at home would have been *much* easier... FYI Installing Ubuntu 8.04 on a USB stick solved the problem on all hardware I tested on (6 different Machines, of which 5 are Dell's). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computer Go tournament at EGC, Leksand, Sweden
Well, I only wanted to participate in 9x9. My program is strong enough to not need help from amateurs. For 19x19, if anyone really wants to cheat it is still relatively easy, even under the current restrictions. Personally I think strength of the programs should be irrelevant. The organizers should simply require that the 'thinking process' is visible and that log files can be inspected by the tournament director in case of a dispute. Erik On Thu, Jul 17, 2008 at 8:25 PM, David Doshay <[EMAIL PROTECTED]> wrote: > The programs would have to get strong enough that it would be hard > to find some human willing to hide behind the network connection for > the purpose of cheating. We could debate that level, but it would have > to be at least into the pro ranks. > > Until then, I have to build traveling racks to hold my cluster, and it is > a pain. > > Cheers, > David > > > > On 17, Jul 2008, at 10:08 AM, Erik van der Werf wrote: > >> In what way would computer Go need to evolve? >> >> Erik >> >> >> On Thu, Jul 17, 2008 at 6:50 PM, David Doshay <[EMAIL PROTECTED]> wrote: >>> >>> Someday computer Go will evolve enough to have enough trust for >>> remote computing. But not today, unfortunately. >>> >>> Cheers, >>> David >>> >>> >>> >>> On 17, Jul 2008, at 9:39 AM, Erik van der Werf wrote: >>> >>>> ... simply using an ssh >>>> connection to my machine at home would have been *much* easier... >>> >>> ___ >>> 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] Computer Go tournament at EGC, Leksand, Sweden
In what way would computer Go need to evolve? Erik On Thu, Jul 17, 2008 at 6:50 PM, David Doshay <[EMAIL PROTECTED]> wrote: > Someday computer Go will evolve enough to have enough trust for > remote computing. But not today, unfortunately. > > Cheers, > David > > > > On 17, Jul 2008, at 9:39 AM, Erik van der Werf wrote: > >> ... simply using an ssh >> connection to my machine at home would have been *much* easier... > > ___ > 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] Computer Go tournament at EGC, Leksand, Sweden
On Thu, Jul 17, 2008 at 6:18 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > That always irks me when I hear this kind of thing. The world is basically > windows "chauvinistic" and it's common to find little consideration given to > any other platform. > Did you know that you can create your own linux environment without having > to "touch" the machine you will be using? My wife has her own windows > machine that she doesn't want me "touching", but I have a complete linux > install via an external hard drive that leaves her machine "untouched." > Although the install is specific to that machine, it is easy to build > "universal" setups that will boot on any modern PC into Linux, without > touching the hard drive of that machine.This would require that you > bring a memory stick of some kind or perhaps an external USB hard drive. > You can get big ones really cheap now, and they are very compact. You > plug it into the USB port and then boot into Linux. > In my opinion, the tournament organizers should do this for you and the > other potential Linux participants since Linux is becoming more and more > popular and apparently it is already very popular with Go programmers. > There are several possibilities for setting up machines that could use > either Windows or Linux that would not require major effort on their part - > just one good Linux guy helping them. > > I also feel for the Mac people and also people that have built programs that > run on networks of workstations or other potential supercomputer programs > that would not be able to participate. I have DSL-N (Damn Small Linux) on a USB stick so I can probably make something that boots. However I'm woried about the hardware support and network configuration (it has to connect to KGS). Also I think I would have to upgrade the kernel, but I don't know how easy that will be with DSL (and if I have time for it). Anyway, simply using an ssh connection to my machine at home would have been *much* easier... Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computer Go tournament at EGC, Leksand, Sweden
On Thu, Jul 17, 2008 at 3:53 PM, Nick Wedd <[EMAIL PROTECTED]> wrote: > Steenvreter no yes Hi Nick, I never said yes. At this point it is rather unlikely that Steenvreter will participate. Steenvreter only runs on linux. Since the machines in Leksand run windows and remote computation is not allowed (which is funny considering the tournament is on KGS) I pretty much have to be present myself. I did not find cheap flights for a short visit and I probably won't have time to attend the EGC for a full week, also housing seems to be getting difficult. So for now better assume that Steenvreter will *not* participate in Leksand. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 2008 World 9x9 Computer Go Championship in Taiwan
On Tue, Jul 1, 2008 at 10:58 PM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote: > Edward de Grijs wrote: >> >> GCP wrote: >> >> > Given how well the support for Beijing is (essentially refunding the >> > plane tickets, you get more for participating in Beijing than winning >> in >> > Taiwan!), I would be really surprised if many strong programs show up >> > for this. Calling the Taiwan tournament the World Championship is a >> > silly joke. >> >> I did not know that the plane tickets to Beijing are refunded. >> Where can this information be found? > > Sorry to all!!! > > I got confused because I entered multiple games in the Olympiad. The > financial support is only for the chess event. > > This means participating in Taiwan is financially more interesting for the > go players. > That's a pretty good deal!!! http://64.68.157.89/forum/viewtopic.php?topic_view=threads&p=193819&t=21591 Why isn't there any sponsoring like this for the other tournaments? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Participants in the Computer Olympiad
On 6/23/08, Rémi Coulom <[EMAIL PROTECTED]> wrote: > a schedule was posted too: > http://www.grappa.univ-lille3.fr/icga/event_info.php?id=22 Not much details yet in this schedule... I'm interested to participate, but I'd like to know some more details first. I find it strange that the (penalty-free) registration already closed before any schedule was published. The registration page also talks about "events in Amsterdam"; maybe I shouldn't take that date seriously either? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Move prediction studies in Chess/Shogi?
Levente Kocsis did some research on move ordering in chess using neural networks. Apparently even a linear mapping already works surprisingly well. His publications are at: http://aurora.mlhci.sztaki.hu/www/index.pl/kocsis Erik On Wed, May 21, 2008 at 2:29 PM, <[EMAIL PROTECTED]> wrote: > Hi... and sorry for the somewhat off topic subject... but since there > obviously are some (ex)chess people here, I'll ask anyway. > > Are there any articles about move prediction in chess or shogi (in English), > as there are quite a few in go? I've been googling around > ---I'd say quite a lot---recently, but failed pitifully. > > -Esa > ___ > 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] Computer Go Forum
On Sat, May 3, 2008 at 8:49 AM, Joshua Shriver <[EMAIL PROTECTED]> wrote: > Is there a computer go forum? http://www.computer-go.jp/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Yet another question on uct and rave
On Fri, Mar 28, 2008 at 3:10 PM, Jaonary Rabarisoa <[EMAIL PROTECTED]> wrote: > So to sum up we have the following pseudo code : > > at a given node : > - find the child (among the visited child only) that maximizes de UCT-RAVE > value > - if this maximum UCT-RAVE value is less than FPU value and if there still > exisits unvisited nodes : > > choose one unvisited node- continue > > Is this correct ? Maybe, but it depends on how exactly you compute your Upper Confidence Bounds. If you don't add UCB's to the rave values you may either have to compare based on the UCT part alone, or do as GCP suggests (which sort of turns FPU in an UCT prior). However, I would suggest that you first start out with the standard UCT (always explore unvisited nodes) and see how you can improve from that as a baseline. If your branching factor becomes too big maybe try some kind of metabandit. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Yet another question on uct and rave
On Fri, Mar 28, 2008 at 2:36 PM, Jaonary Rabarisoa <[EMAIL PROTECTED]> wrote: > So if I understand, at each node we need to play every possible action once > at first, even many of these actions are surely non optimal. And this may be > slow if the number of the possible action at this node is huge. Well, as discussed in their ICML paper you could also initialize nodes with prior knowledge. > When you talk about FPU, does it mean that you give a kind of default value > for unvisited node and compare this value with (1-beta)*Q_uct + beta*Q_rave > if we can compute it ? Yes, you do the normal UCT-RAVE selection for the moves that have been already been explored at least once, then if the highest upper confidence bound (from the move you would normally select if there are no unexplored nodes) does not exceed the FPU value you select an unexplored node (FPU=infinity gives standard UCT). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Yet another question on uct and rave
On Fri, Mar 28, 2008 at 11:20 AM, Jaonary Rabarisoa <[EMAIL PROTECTED]> wrote: > Hi all, > > After a long search on the computer go mailing list archive and reading and > reading again the paper of Gelly and Silver (ICML 2007) I didn't find > answers to my question. > In this paper they introduce a way to select the next move, at a given > state, using the rave and uct value of its childs. They do this by comparing > > (1-beta)*Q_uct + beta*Q_rave > > > But, by the definition of the rave and uct value, for each child of a given > node we may have the following situation : > > - its rave and uct value are defined ( in this case we can compute the > above score) > - only the rave value is defined (in this situation the n(s,a) = 0 and the > uct value is not defined) Plain UCT always selects unvisited nodes first ( n=0 -> Q=infinite ). > - neiher rave nor uct value is defined This cannot happen if you always select unvisited nodes first (because if you select a move it leads to an update for both Q_rave and Q_uct). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New UCT-RAVE formula (was Re: computer-go Digest, Vol 43, Issue 8)
Hi David, On Sat, Feb 16, 2008 at 7:07 PM, David Silver <[EMAIL PROTECTED]> wrote: > Yes, but why add upper confidence bounds to the rave values at all? If > they really go down that fast, does it make much of a difference? > > According to the recent experiments in MoGo, you are right :-) However, I've > seen slightly different results in other strong UCT-RAVE programs. > > I think you are right that the exploration interacts heavily with the playout > strategy. If the playouts heavily favour a particular response (e.g. black > always connects at d3), then using an UCB on RAVE is one way to ensure that > the opposite result is also tried (e.g. what happens if white cuts at d3?). > > I did of course test this and my program actually became weaker when I > added UCBs to the rave values! > > Interesting! Did you use prior knowledge in your RAVE values? (See below) > > No, this was done without using prior knowledge to intialize the rave values. The way I originally understood it the purpose of rave was to play stronger > when the number of simulations is low. This can already be achieved by > adding a greedy component to emphasize moves that are likely to be winning > based on their rave-value alone. > > Agreed, this is certainly the most important aspect of RAVE. > > The purpose of UCB in UCT is clear (to ensure sufficient exploration when > the tree grows large). UCB in rave does not really do the same. > > Agreed. > > I think its two main effects are: (1) it emphasizes the inverse order in > which the moves where added, > > Not sure what you mean by this. > > I'll try to explain: In my implementation I only have a rave estimate for a particular move in a particular position if this move has been sampled at least once (so the corresponding child node has to be present in the tree). New moves (and corresponding child nodes) are added one at a time (or with tricks like FPU even slower) until all legal moves are present. The order in which (unexplored) legal moves are added to the tree depends on move ordering heuristics (promising moves should be added first). A consequence of this is that the rave-visit counters for moves added early generally receive a lot more hits than the moves that are added later. The invsqrt factor used in computing the upper confidence bounds then causes the moves added last (with low rave-visit counts) to receive a high upper confidence bound, hence emphasizing the inverse order in which the moves were added. With a good move ordering the moves added last are nearly always bad, so emphasizing them reduces playing strength. > and (2) it emphasizes exploration of moves that are infrequently selected > in the playouts. > > Agreed. > > I think neither of them is a good thing. The better the move ordering or > the knowledge in the playouts, the more it hurts... > > Not if you also encode your playout knowledge as prior knowledge for the RAVE > algorithm. This way, you can specify your confidence in the choices made by > the playouts. The UCB is always relative to this confidence level. > > I think the prior knowledge should improve playing strength due to an improved rave-value estimate. However, w.r.t. the UCB's, the larger initial counts associated with the prior knowledge simply bring the added upper confidence bounds closer to zero, which is done even more effectively by not adding them at all. Best, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: computer-go Digest, Vol 43, Issue 8
On Tue, Feb 12, 2008 at 9:03 AM, Darren Cook <[EMAIL PROTECTED]> wrote: > 9.5pt komi is unreasonable. I agree with Don that perfect game value > will probably turn out to be 7pts, though I'm keeping an open mind that > it may be 6pts. I'd be surprised if it was 8pts, though that could just > mean I've been analyzing the wrong openings :-). On 9x9 with Chinese rules even komi values (e.g. 6 or 8) are unlikely because they would require seki in all optimal lines of play. Consequently I'd expect 7, but wouldn't completely rule out 5 and 9 just yet. Under Japanese rules I guess it can be anything from 5 to 10 (and maybe even the full range :-)). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New UCT-RAVE formula (was Re: computer-go Digest, Vol 43, Issue 8)
Hi David, On Fri, Feb 8, 2008 at 6:09 PM, David Silver <[EMAIL PROTECTED]> wrote: > > Note as well that the current implementation of MoGo (not the one at > > the time of the ICML paper) use a different tradeoff between UCT and > > Rave value, thanks to an idea of David Silver, which brought > > improvements in 19x19 (where the Rave values are the most useful), > > while it was marginal (still better) in 9x9. But anyway we here are > > talking about 9x9, so it can't explain what you are talking about. > > > > I think it is time to share this idea with the world :-) > The idea is to estimate bias and variance to calculate the best > combination of UCT and RAVE values. > I have attached a pdf explaining the new formula. Thanks! > >> (2) () Depending on the playout > >> policy, adding an upper confidence bound to the rave values can push > >> some terrible bad moves up (like playing on 1-1). The reason seems to > >> be that such moves are normally sampled very infrequently (so the UCB > >> will be higher), and when they are selected (...) Sylvain snipped the part where I explained why the values will also be higher, so you may have missed that. Essentially what can happen is that the bad move is always rejected unless it serves a clear purpuse, and this purpose may then correlate strongly with winning the game (e.g., big capture). Of course this all depends on knowledge in the playout policy. IIRC Mogo's policy is mostly random when the local patterns don't apply, so I guess the only hard-reject pattern that may cause problems with the rave-values in Mogo are eye-filling moves that win the game. > > That could be an explanation, but there are two points: > > - the prior you put on top of Rave often avoid to first sample 1-1, > > and even when you do, you very often loose just 1 playout because of > > the UCT value you get right away. > > - I never observed a big discrepancy between the number of Rave > > samples for each move. > > Also, the upper confidence bound reduces rapidly with RAVE, because so > many moves are played in each playout. Yes, but why add upper confidence bounds to the rave values at all? If they really go down that fast, does it make much of a difference? I did of course test this and my program actually became weaker when I added UCBs to the rave values! The way I originally understood it the purpose of rave was to play stronger when the number of simulations is low. This can already be achieved by adding a greedy component to emphasize moves that are likely to be winning based on their rave-value alone. The purpose of UCB in UCT is clear (to ensure sufficient exploration when the tree grows large). UCB in rave does not really do the same. I think its two main effects are: (1) it emphasizes the inverse order in which the moves where added, and (2) it emphasizes exploration of moves that are infrequently selected in the playouts. I think neither of them is a good thing. The better the move ordering or the knowledge in the playouts, the more it hurts... > So even without prior > knowledge, moves like the 1-1 point should be observed less when using > RAVE, because they will quickly become associated with losing games. As explained before, this may depend on how you do the playouts. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
Hmm, sounds like I should experiment some more. Thanks! Erik On Thu, Feb 7, 2008 at 1:11 AM, Hideki Kato <[EMAIL PROTECTED]> wrote: > Hi Erik, > > My program is very based on MoGo's report and the paper. Yes, I > used FPU of 1.15. > > -Hideki > > Erik van der Werf: <[EMAIL PROTECTED]>: > > > >Hi Hideki, > > > >Your results look similar to those of Mogo as reported in their icml > >paper. When you ran this experiment, did you use anything like FPU or > >progressive widening, or did you use Levente's original design which > >always selects unvisited moves first? > > > >Regards, > >Erik > > > > > >On Wed, Feb 6, 2008 at 3:42 PM, Hideki Kato <[EMAIL PROTECTED]> wrote: > >> I found some data. GGMC Go v2r6, against GNU Go 3.7.10 level 10, 9x9, > >> komi 7.5, 3000 playouts/move, 2000 games match: > >> > >> Without RAVE: winning rate was 23.1 +- 0.9% (-209 +- 9 ELO) > >> With RAVE: winning rate was 65.3 +- 1.1% (+110 +- 8 ELO) > >> > >> Though this includes some other improvements, most come from RAVE. > >> Unlike MoGo, my best 'K' was 1000. > >> > >> Following is my implementation of RAVE for GGMC v2r6. > >> 1) Each playout returns the score and all moves with colors played. > >> 2) While back-propagating the value (degitized score), computes the > >> mean and the variance according to UCB1 and do the same for RAVE > >> seperatelly. For RAVE, the values of all (legal) moves, except played > >> one, in a node are updated. > >> 3) In the computation of values for RAVE, the point is that there > >> appeares three colors (as someone, I remember GCP, mentioned before). > >> If the players' colors aren't the same then skip. Count the value as > >> is or negate (1 - score, for me), depending on the color of the player > >> at the position and the color for the score. > >> 4) Before back-propagating the value of each playout, I setup a color > >> table for all intersections of the board for speed-up, in fact > >> (initialized with EMPTY). That is, fill the board (table[move] = > >> color) by tracing the moves and the colors returned by the playout > >> forward (from leaf node to end of the game). Then, by tracing the > >> path from root to the leaf node, clear the table[move] (table[move] = > >> EMPTY), in order to avoid duplicate counting with UCB1. > >> 5) While descending the tree, merge the values come from UCB1 and > >> RAVE with 'K' according to the formula in the paper. > >> > >> #Though I'm writing this by reading my source code, this description > >> may include some errors. > >> > >> Hope this helps, > >> > >> Hideki > >> > >> Gian-Carlo Pascutto: <[EMAIL PROTECTED]>: > >> > >> >> I also implemented RAVE in Mango. There was a few points of > improvements > >> >> (around 60 Elo points with gnugo as reference), but as much as in the > >> >> paper of Gelly and Silver :( (around 250 Elo points if I remember > well) > >> >> > >> >> It might be that the effect of RAVE depends a lot on the simulation > >> >> strategy. Indeed, sometimes my RAVE was playing very good moves but > also > >> >> very bad ones. > >> > > >> >I don't think the simulation strategy is the key. > >> > > >> >I suspect the improvement is largest when you don't do progressive > widening. > >> > > >> >Nevertheless it would be quite interesting to see the implementation > >> >details of ggmc's RAVE. RAVE performance is quite dependent on exact > >> >implementation and parameters. > >> -- > >> > >> [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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
Hi Hideki, Your results look similar to those of Mogo as reported in their icml paper. When you ran this experiment, did you use anything like FPU or progressive widening, or did you use Levente's original design which always selects unvisited moves first? Regards, Erik On Wed, Feb 6, 2008 at 3:42 PM, Hideki Kato <[EMAIL PROTECTED]> wrote: > I found some data. GGMC Go v2r6, against GNU Go 3.7.10 level 10, 9x9, > komi 7.5, 3000 playouts/move, 2000 games match: > > Without RAVE: winning rate was 23.1 +- 0.9% (-209 +- 9 ELO) > With RAVE: winning rate was 65.3 +- 1.1% (+110 +- 8 ELO) > > Though this includes some other improvements, most come from RAVE. > Unlike MoGo, my best 'K' was 1000. > > Following is my implementation of RAVE for GGMC v2r6. > 1) Each playout returns the score and all moves with colors played. > 2) While back-propagating the value (degitized score), computes the > mean and the variance according to UCB1 and do the same for RAVE > seperatelly. For RAVE, the values of all (legal) moves, except played > one, in a node are updated. > 3) In the computation of values for RAVE, the point is that there > appeares three colors (as someone, I remember GCP, mentioned before). > If the players' colors aren't the same then skip. Count the value as > is or negate (1 - score, for me), depending on the color of the player > at the position and the color for the score. > 4) Before back-propagating the value of each playout, I setup a color > table for all intersections of the board for speed-up, in fact > (initialized with EMPTY). That is, fill the board (table[move] = > color) by tracing the moves and the colors returned by the playout > forward (from leaf node to end of the game). Then, by tracing the > path from root to the leaf node, clear the table[move] (table[move] = > EMPTY), in order to avoid duplicate counting with UCB1. > 5) While descending the tree, merge the values come from UCB1 and > RAVE with 'K' according to the formula in the paper. > > #Though I'm writing this by reading my source code, this description > may include some errors. > > Hope this helps, > > Hideki > > Gian-Carlo Pascutto: <[EMAIL PROTECTED]>: > > >> I also implemented RAVE in Mango. There was a few points of improvements > >> (around 60 Elo points with gnugo as reference), but as much as in the > >> paper of Gelly and Silver :( (around 250 Elo points if I remember well) > >> > >> It might be that the effect of RAVE depends a lot on the simulation > >> strategy. Indeed, sometimes my RAVE was playing very good moves but also > >> very bad ones. > > > >I don't think the simulation strategy is the key. > > > >I suspect the improvement is largest when you don't do progressive widening. > > > >Nevertheless it would be quite interesting to see the implementation > >details of ggmc's RAVE. RAVE performance is quite dependent on exact > >implementation and parameters. > -- > > [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] More UCT / Monte-Carlo questions (Effect of rave)
Hi Sylvain, On Wed, Feb 6, 2008 at 4:41 PM, Sylvain Gelly <[EMAIL PROTECTED]> wrote: > Do you want to come? ;) Well, I have a nice job, but one can always try to make me an offer I can't refuse ;-) > I just can't do too many things at the same time. Sounds familiar... > > Well, since you say the improvement is marginal on 9x9 then I think we > > are actually in agreement. I also get an improvement, but it's just > > not that much. When I wrote 'spectacular' I meant the reported jump > > from 25% to over 55% winrate against gnugo. > > I am sorry, I was unclear. When I said marginal in 9x9, I was talking > of the differences between the current MoGo (well, at least when I > left it 6 months ago :)) and the algorithm described in the ICML > paper. The change is only on how to balance the two values you get > (UCT and Rave). > Rave in 9x9, as described in the paper, gives a big jump in > performance, and the numbers reported in the paper are accurate: those > are computed with many thousands games against gnugo and I carefully > did the experiments multiple times. > In addition, Hideki for example report the same order of improvements. > I have to point out that it is really easy to make a mistake in the > updates making Rave much less interesting. I am definitely not saying > that you or anyone else made a mistake, but it can just happen, > sometimes :). In the ICML version of UCT without RAVE, you did not use your First Play Urgency, right? I think that using FPU has an effect similar to what others reported with their progressive widening. From what I've seen it looks like plain UCT, without FPU or progressive widening, has more to gain from RAVE. Am I wrong to assume that the strongest version of Mogo before you introduced RAVE used something like FPU or progressive widening? Best, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
Hi Sylvain, Thanks for your reply! How do you like your new job? Do you miss CompGo? ;-) On Wed, Feb 6, 2008 at 2:20 PM, Sylvain Gelly <[EMAIL PROTECTED]> wrote: > > (1) They compared Rave to plain UCT. If they would have compared it to > > a more sophisticated implementation (like the best Mogo before Rave) > > they probably could not have shown a spectacular improvement. > > The best Mogo before Rave was very close to plain UCT with the > sequence-like simulations. And indeed we exactly compared the best > Mogo before and after Rave. There is a table (I don't remember which > number), which show the incremental improvements from plain UCT, to > Rave, passing by plain UCT with sequence-like simulations. All > experiments have been done with MoGo's code, all other parts of the > code staying constant. There were not "secret part" of MoGo disabled > to make the improvement of Rave more interesting. > > One discrepancy between our results and the one some of you observe, > as Gian-Carlo stated, is likely to come from the parameters and detail > of implementation. We heavily tuned those parameters and details > against gnugo, and that makes quite a big difference. I chatted more > closely with some of you about details and it did make a difference. > Maybe some of you can share what made a change, if you want. > > Note as well that the current implementation of MoGo (not the one at > the time of the ICML paper) use a different tradeoff between UCT and > Rave value, thanks to an idea of David Silver, which brought > improvements in 19x19 (where the Rave values are the most useful), > while it was marginal (still better) in 9x9. But anyway we here are > talking about 9x9, so it can't explain what you are talking about. Well, since you say the improvement is marginal on 9x9 then I think we are actually in agreement. I also get an improvement, but it's just not that much. When I wrote 'spectacular' I meant the reported jump from 25% to over 55% winrate against gnugo. I only got such an improvement when I first dumbed down my implementation to a plain UCT without a good move-ordering (and always expanding all unvisited nodes first). > > (2) () Depending on the playout > > > policy, adding an upper confidence bound to the rave values can push > > some terrible bad moves up (like playing on 1-1). The reason seems to > > be that such moves are normally sampled very infrequently (so the UCB > > will be higher), and when they are selected (...) > > That could be an explanation, but there are two points: > - the prior you put on top of Rave often avoid to first sample 1-1, > and even when you do, you very often loose just 1 playout because of > the UCT value you get right away. Yes, using more prior knowledge will probably reduce the problem. > - I never observed a big discrepancy between the number of Rave > samples for each move. I guess this is because your playout policy is more uniform than mine? The problem tends to disappear with uniform random playouts. My program has some hard-reject patterns to discard moves that are strictly inferior to adjacent alternatives, so in some situations I can easily get a large difference between the number of Rave samples for each move. Best, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
Hi Guillaume, I think we talked about this before, but others may be interested as well. In my opinion the ICML paper on Rave has several weaknesses. It's been a while since I read the paper, but here are some I remember: (1) They compared Rave to plain UCT. If they would have compared it to a more sophisticated implementation (like the best Mogo before Rave) they probably could not have shown a spectacular improvement. (2) The paper suggest that you should add an upper confidence bound to the rave values. Although they didn't actually make this explicit, because IIRC the paper failed to provide an actual value for the constant c, I guess most people naturally assume it to be positive. However, Rave is already a greedy heuristic, so if anything you should probably subtract the confidence bound. Depending on the playout policy, adding an upper confidence bound to the rave values can push some terrible bad moves up (like playing on 1-1). The reason seems to be that such moves are normally sampled very infrequently (so the UCB will be higher), and when they are selected (e.g. for a big capture deep in the playout) they correlate more with winning (so the value will also be higher) without generalizing to earlier positions. Best, Erik On Wed, Feb 6, 2008 at 10:47 AM, Chaslot G (MICC) <[EMAIL PROTECTED]> wrote: > I also implemented RAVE in Mango. There was a few points of improvements > (around 60 Elo points with gnugo as reference), but as much as in the paper > of Gelly and Silver :( (around 250 Elo points if I remember well) > > It might be that the effect of RAVE depends a lot on the simulation > strategy. Indeed, sometimes my RAVE was playing very good moves but also very > bad ones. > > Guillaume > > -Original Message- > From: [EMAIL PROTECTED] on behalf of Magnus Persson > Sent: Wed 06/02/2008 00:42 > To: computer-go@computer-go.org > Subject: Re: [computer-go] More UCT / Monte-Carlo questions > > Quoting Gunnar Farnebäck <[EMAIL PROTECTED]>: > > > I have never managed to implement RAVE successfully. It made my > > program significantly slower but no stronger even at a fixed number of > > simulations. > > I get a small effect from RAVE, My rationalisation is that if the > program is rich with other features to improve performance RAVE may > not add that much. > > -Magnus > > > ___ > 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: Re : [computer-go] Is MC-UCT really scalable ... is a troll
On Jan 23, 2008 2:45 PM, ivan dubois <[EMAIL PROTECTED]> wrote: > When I say a minimax solver, I mean a program witch returns a random move > UNTIL it has completed its search, as I explained in a previous post. A plain minimax solver (without enhancements like iterative deepening) doesn't return anything until it has completed its search. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] mathematical morphology
On Jan 23, 2008 1:47 PM, Jacques Basaldúa <[EMAIL PROTECTED]> wrote: > Erik van der Werf wrote: > > > You may also be interested in my > > article on estimating potential territory > > I am. Can you post a link, please. sure, it's all at: http://erikvanderwerf.tengen.nl/publications.html My thesis contains the latest version (see chapter 10); the original article is mostly the same, and can be downloaded from: http://erikvanderwerf.tengen.nl/pubdown/predicting_territory.pdf Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable against humans?
:-) I do not know what the long-term effects on the game of Go would be of an entity with super-human playing strength. Humans tend to have funny reactions when it comes to computers performing tasks formerly believed to have required intelligence... In any case, I know some people already play on larger boards and it seemed like a possible reaction to a successful brute-force approach. Erik On Jan 22, 2008 6:03 PM, David Fotland <[EMAIL PROTECTED]> wrote: > This is an odd idea. When computers started beating people in chess, humans > did not abandon the game and change to some other similar game. Why do you > think go players would stop playing go when computers get strong? > > David > > > > > In the future, when humans are consistently defeated by computers on > > 19x19 and the remaining players move up to a more 'interesting' size, > > will you be claiming that 19x19 isn't Go either? > > > > E. > > > > ___ > 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] Is MC-UCT really scalable against humans?
On Jan 22, 2008 5:54 PM, David Fotland <[EMAIL PROTECTED]> wrote: > I'll admit that I was skeptical that monte carlo would scale to 19x19, and > clearly I was wrong. Maybe I misremember the early debates, but I think the > argument from the UCT/MC side was that fast pure-random playouts were > scalable and would do well on 19x19. > The pure random playouts got quite > strong at 9x9, and there was much discussion about how to make playouts > faster, how to implement fast pseudo-liberties, etc. When I was skeptical > that this pure random approach would scale to 19x19, I was correct. Hi David, I don't think any of the pure random playouts ever provided really strong play on 9x9, but still definitely stronger than I initially believed possible. The topics that you mention as being imortant for 19x19 (heavy playouts, patterns, L&D knowledge) are all implemented in my 9x9 program (and obviously they did provide some advantages). Consequently, I don't view them as relevant in distinguishing 9x9 from 19x19. The differences are in my opinion much subtle than some people appear willing to believe. BTW Historically, MC alone was never very impressive. I think the primary wattershed was the discovery of UCT. With UCT even the random playouts seem to scale, though probably still several orders of magnitude worse than the knowledge-rich approaches. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable against humans?
On Jan 22, 2008 4:08 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > What irritated me was what I referred > to as 'putting words in someone elses mouth'. It feels like Erik is > purposefully trying to offend, both in his answer to Petri and in his later > answer to me. I think there's no need to try to offend people. Hi Mark, I just try to be concise. If I've hurt your feelings then I apologize. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable against humans?
On Jan 22, 2008 2:50 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > > On 22-jan-08, at 11:21, Don Dailey wrote: > > > Hi Mark, > > > > I think it's Petri who was the condescending one. > > > > Well, you could see it as condescending if someone pooh-poohs 9x9 Go. > But then one should argue that if you'd want to. But to pretend by > deduction he also claims 17x17 or 19x19 are not interesting, like > Erik did, is putting words into his mouth and then go say "look what > silly things he's saying". I really don't like that. > Pretend?? So where lies the fundamental divide between 19x19 and 9x9? If anything, in the last couple of years most of the progress in Computer Go came from 9x9. Some dinosaurs claimed it wouldn't scale up because it was a completely different game... The problems Petri sketched are well known and solutions already exist. The fact that most programs have not implemented those solutions yet does not mean a fundamentally different approach is needed for 19x19. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] mathematical morphology
IIRC Ken Chen did something similar with the number of stones on boundaries. I'm not sure, but there may be something in the extended articles originating from JCIS 2003. You may also be interested in my article on estimating potential territory (which shows that if you want to apply influence functions, such as Bouzy's algorithm, it helps to incorporate life-and-death knowledge). Erik On Jan 22, 2008 1:18 PM, Nick Knol <[EMAIL PROTECTED]> wrote: > Hi all, > > This is my first post to the list, and I'm pretty new to this, so sorry if I > break from etiquette. > > I'm currently working on my senior undergrad thesis project. My idea is to > use Bouzy's dilation algorithm ( > http://www.gnu.org/software/gnugo/gnugo_14.html ) to find areas of the board > that form boundaries of influence between different groups and then > concentrate move searches in those areas. After analyzing about 70 > dan-level games on KGS I've found a very strong correlation to the number of > moves made in these boundary areas. I define these boundaries (somewhat > naively perhaps) as areas of the board that have an absolute value of less > than 4 after performing an arbitrarily large number of dilations on the > board (>=30 or so). > > I've looked around and haven't found any literature on this specific use of > Bouzy's algorithm, so this gives me hope that my idea has some original > merit. Possible applications could include: > > -weighting pre-selected moves based on whether they happen to be in a > boundary region > -limiting the branching factor for game tree searches (averages out to be > about 78 over the course of the game, still too many but a big improvement > from 250) > -move ordering for game tree searches > -possible weighting of move distributions for MC-based AI > > I was hoping someone more experienced than me could comment on this and > possibly let me know if I'm reinventing the wheel and if any of these > applications seem plausible. Thank you. > > -Nick > > p.s. if anyone is interested in my data i have some matlab files and graphs > i could post > > ___ > 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] Is MC-UCT really scalable against humans?
On Jan 22, 2008 11:14 AM, Petri Pitkanen <[EMAIL PROTECTED]> wrote: > 9x9 is not Go At some point in history the common board size was 17x17. Are you suggesting that 17x17 wasn't Go either? In the future, when humans are consistently defeated by computers on 19x19 and the remaining players move up to a more 'interesting' size, will you be claiming that 19x19 isn't Go either? E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
On Jan 16, 2008 10:42 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote: > I can not think of any situation where filling a one-point eye would be a > correct move (provided that it is a "real" eye and not a "false" one). > > > Can anyone come with concrete examples? Sure, for example with the following shape filling the eye makes a bulky five nakade in the corner _ |. # # |# # Under cgos rules you may in rare cases even have to fill eyes of pass-alive groups. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
On Jan 2, 2008 5:54 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > Erik van der Werf wrote: > > I'd propose something simpler: > > > > No time is deducted for pass. > > > > With this rule your program will only loose time when it absolutely > > has to respond to the opponents move. In most games the winning > > program can simply play until it has a sufficient number of > > unconditionally alive stones on the board and then pass forever > > without ever risking a loss on time. > > > This is not manageable and is also subject to manipulation.The > server could wait forever to see if a move might be pass. The only > reasonable way to implement this is to allow a liberal time margin for a > pass move. For instance if your bot passes, up to 5 seconds is > "forgiven." Yes, it's probably a good idea to set some kind of upper limit. > I'm somewhat opposed to this idea. The decision to pass is still a > "considered decision" and I don't see why pass should be treated > differently. Normally, for rules using area-counting, pass is at best a worthless move. Your rules shouldn't encourage pass-fights. > Better would be some kind of victory declaration.The program claims > victory - which means that it agrees that every move from now on (for > itself) is a pass move. It would be the counterpart to resignation - > with the provision that you give up all rights to defend yourself if you > are wrong. Won positions may still have forcing moves for the opponent (e.g., atari-connect, etc.). I don't see a need for a separate victory declaration. If pass (and resign) are good enough for humans why would bots need more? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
On Jan 2, 2008 5:46 PM, Eric Boesch <[EMAIL PROTECTED]> wrote: >... > Finally, I'm still not aware of any go programs that keep playing > after they have obtained a dead lost position because the programmer > wants them to do it. It's just easier to write a program that doesn't > know when to resign than to write a program that does. > > On this point, I disagree with Erik. We get enough stupid games by > accident that we don't need programs that play asinine games on > purpose. Well, actually I agree with you (hence the smiley), but in my opinion this should be solved in the rules. The rules should not encourage undesired behaviour. For this particular problem Byo-yomi is one solution, not counting time for pass is another. For the latter, of course, passing should still be done within a reasonable time but what is reasonable may still be quite long because (1) it provides an immediate opportunity to end the game and (2) if it is (ab)used before the actual game is over it gives a big advantage to the opponent (because he gets to move twice). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
On Jan 2, 2008 4:18 PM, Jason House <[EMAIL PROTECTED]> wrote: > I've also considered the exact opposite strategy... When losing a game, aim > to stress the opponent's time management (since it's the highest probability > of victory). That would include underhanded tricks like filling my own > eyes. I probably won't implement that, but it was an interesting thought. Why not? If you bots logically applies CGOS rules it should only pass in a losing position if it has absolutely no other legal move. Any other way your bot will be playing sub-optimal ;-) BTW filling an eye is not necessarily a bad move. It can, e.g., be optimal in capturing races, and under superko it can be the tesuji even when it sacrifices an unconditionally alive group. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
I'd propose something simpler: No time is deducted for pass. With this rule your program will only loose time when it absolutely has to respond to the opponents move. In most games the winning program can simply play until it has a sufficient number of unconditionally alive stones on the board and then pass forever without ever risking a loss on time. Erik On Jan 2, 2008 3:02 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > Of course it's also possible to implement the Fischer clock on CGOS. > Fischer clock is where you have a fixed time component (such as 5 > minutes) but you also are given an increment - another fixed time > component that is added to your clock EACH MOVE. > > So it might be expressed as "2 minutes + 5 seconds" which means you > are given 2 minutes initially, but you are also awarded 5 seconds per > move - whether you use it or not.It is simply added to your clock. > > I've always liked this kind of time control. It prevents games lost > due to mad time control scrambles. It makes the games feel more > traditional (like the old days when clocks were not used) because the > pressure of the clock has been reduced (although not eliminated.) > > There are some problems with this on CGOS: > >1. I don't think GTP has Fischer time mode. >2. Not traditional in GO. >3. Programs do not currently implement it. >4. It doesn't really solve your problem. > > The fact that it's not traditional isn't a factor from my point of > view, I am progressive about positive change. > > It doesn't solve your problem because you would still be cheated out of > 2 seconds per move - although it might be much easier for you to deal with. > > It would be simple to handle the GTP issues. If your program could not > handle Fischer time some modes could be added to the client to help you > manage it.In the simplest case it would just report time remaining > and there could be modes that factor in the next N moves to this. > > - Don > > > > > > Peter Christopher wrote: > > I realize there are some legitimate reasons to have your bot play out > > the games on cgos until the bitter end. Here I would like to present > > one reason why you may want to have your bot resign instead. I live > > in the Philippines. My ping from my computers here is usualy about > > .3-.4 seconds. I do often put some bots on cgos from here, tend to be > > rated around 1600-1700. Because of the long ping & the tromp-taylor > > rules, my bots often lose won games on time. Playing from my computer > > here, I typically set a buffer around 45 seconds when the bot assumes > > the game is a won game & almost immediately plays filler moves. > > Nevertheless, with this buffer or even a larger buffer, the bot often > > captures massive groups, and at 2 moves per second (all network lag), > > the bot can't fill the whole board again & again, and if my bot passes > > & yours doesn't, that's also slow to fill the board. The end result > > is that in your records, you may be testing your bot's new features > > and want to have an accurate elo rating to know whether it is working. > > If your bot is playing my bot, and your bot doesn't resign lost > > games, you won't have an accurate rating of its new features. Sorry > > for the inconvenience. This is happening today quite a lot vs. > > challenger. Some other days it's a different bot. Just something to > > keep in mind. > > Peter > > ___ > > 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] rotate board
This should help: http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653 Erik On Dec 19, 2007 5:58 PM, Rémi Coulom <[EMAIL PROTECTED]> wrote: > Hi, > > I have not had time to study it in details, but I found this: > http://fragrieu.free.fr/zobrist.pdf > > A Group-Theoretic Zobrist Hash Function > Antti Huima > September 19, 2000 > Abstract > Zobrist hash functions are hash functions that hash go positions to > fixed-length bit strings. They work so that every intersection i on a go > board is associated with two values Bi and Wi. To hash a position, all > those values of Bi are XORed together that correspond to an intersec- > tion with black stone on it. Similarly, all Wi's are XORed together for > those intersections that have a white stone. Then the results are XORed > together. > We present a Zobrist hash function with the extra property that if z is > the hash value of a position p, then the values z′ for the positions p′ that > are obtained from p by exchanging the colors, by rotating the position > and my mirroring can be efficiently calculated from z alone. Still, z and > z′ are different. > > Rémi > > ___ > 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] A thought about Bot-server communications
On Dec 11, 2007 2:18 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > > >> There is some > >> question about how you define a position (a board state, or a board > >> configuration i.e. SSK or PSK) but you can nitpick if you want and say > >> that superko has nothing to do with positions repeating but I think when > >> a position repeats it's superko. > >> > > > > And when you say it's superko my first thought is that the game is > > over because one player just made an illegal move... > > > > > > > >> Are you just trying to nitpick semantics? > >> > > > > In a loose informal context this would certainly be nitpicking (e.g. > > the difference between 'ko' and 'ko-rule'). However when it is about > > formalizing rules it really helps to be precise and minimize ambiguity > > (I would think TT-proponents should at least agree with me on this). I > > really do think it is important to distinguish clearly between > > conditions (what constitutes a repetition) and consequences (direct > > loss / continued analysis / no result, etc.). > > > Ok, let's get into semantics. Is superko an illegal move? Again, I regard superko as a concept that refers to a special class of rules for dealing with repetition. So no, it is not an illegal move. >Is it > simply forbidden or is it part of the rules that you lose immediately if > you play it? In card games that is called an irregularity and there > are separate rules to deal with these. > > If you make some other illegal move what happens?For instance if you > take one the opponents stones and place it on the board?Do you lose > immediately or do you get your hand slapped with the objection that "you > can't make that move, play something real!" OC we have general tournament rules and rules for dealing with unsportsmanships behavior... However, slapping you on the hand and giving you the option to alter your move does not fundamentally change anything to the assumed illegality of a particular move. For optimal play you still had to play elsewhere, hence for a sufficiently informed player the effect is the same. Traditional rules (without superko) can have fundamentally different game outcomes. Social etiquette alone does not suffice to remove these differences. The fundamental problem with superko is failure to distinguish between balanced and unbalanced cycles. In an unbalanced cycle, such as send-2-return-1, your suggestion "you can't make that move, play something real!" is fine. In a balanced cycle, such as triple-ko, this is not the obvious thing to say. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
On Dec 11, 2007 4:00 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > Erik van der Werf wrote: > > On Dec 10, 2007 6:48 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > >> In Go however, even if the fundamental game is unchanged you may be > >> playing illegal moves if you are not aware of the superko situation. > >> > > > > And you think superko is part of the fundamental game??? > > > Well, I seem to be saying here that it is NOT part of the fundamental > game. I'm sorry, then I misunderstood what you were trying to say. > > BTW Several authors here use the words repetition and superko as > > synonyms; I believe this is misleading. > > > They are essentially synonyms - I don't see your point. I think you've just proven my point ;-) In my opinion repetition is a more neutral word. It avoids mixing conditions with consequences. > There is some > question about how you define a position (a board state, or a board > configuration i.e. SSK or PSK) but you can nitpick if you want and say > that superko has nothing to do with positions repeating but I think when > a position repeats it's superko. And when you say it's superko my first thought is that the game is over because one player just made an illegal move... > Are you just trying to nitpick semantics? In a loose informal context this would certainly be nitpicking (e.g. the difference between 'ko' and 'ko-rule'). However when it is about formalizing rules it really helps to be precise and minimize ambiguity (I would think TT-proponents should at least agree with me on this). I really do think it is important to distinguish clearly between conditions (what constitutes a repetition) and consequences (direct loss / continued analysis / no result, etc.). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
On Dec 10, 2007 6:48 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > In Go however, even if the fundamental game is unchanged you may be > playing illegal moves if you are not aware of the superko situation. And you think superko is part of the fundamental game??? In my terminology *repetition*, and having some rules to prevent infinite games, is a fundamental aspect of the game. Superko is not fundamental. BTW Several authors here use the words repetition and superko as synonyms; I believe this is misleading. Superko refers to a special class of rules for dealing with repetition (to avoid infinite games). Superko rules share the property that they declare moves that create repetition illegal. (They differ only in how they define a repetition.) Superko rules always do what they are supposed to do (prevent infinite games), but sometimes they do a bit more... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
On Dec 10, 2007 6:07 PM, Álvaro Begué <[EMAIL PROTECTED]> wrote: > It looks like even under non-superko rules, something special happens if a > position is repeated, which means that a program should know the entire > history of the game, or it may accidentally repeat a previous position, even > if it is winning the game by a large margin. Yes, but my point was that this special thing does not necessarily have to happen directly. If both sides have played the full cycle at least once then they have had every opportunity needed for analysis and for playing elsewhere. If neither side chooses to abandon the cycle (and look-ahead can show there is a cycle anywhere in the cycle!) then there is no need to play forever and the server (referee) can simply decide the result based on a long-cycle analysis. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
On Dec 10, 2007 5:23 PM, Álvaro Begué <[EMAIL PROTECTED]> wrote: > On Dec 10, 2007 11:05 AM, Erik van der Werf <[EMAIL PROTECTED]> > > Or simply don't use superko. Normal rules work fine with only some > > minimal knowledge of the last move. Long cycles are not an issue > > because they may repeat multiple times without altering the inevitable > > outcome (which, e.g., can be decided on the server side after n-fold > > repetition). > I am not sure what you mean by "normal rules". Most human players I know use informal Japanese rules (so this is what is normal for me, and probably most players in the Netherlands). OC formalizing them is non-trivial, but certainly not impossible. In practice w.r.t. long-cycles these rules are in pretty good agreement with traditional Asian rules (Chinese/Japanese). > Are three kos a draw? What > about other long cycles? To formalize this in the following I assume repetitions are always on even plies (so the player to move must be the same). For long cycles (anything greater than two moves) you need to distinguish between the following 3 types: 1) Winning cycle: Each cycle you gain prisoners. (or equivalently, you pass more, underlining your intent not to continue the cycle) 2) Balanced cycle: both sides capture the same number of opponent stones. 3) Losing cycle: Each cycle you loose prisoners. (or equivalently, you pass less, underlining your malicious intent to prevent a normal game-end) The outcome, to be determined after one or possibly more than one cycle, is (1) win, (2) draw, or (3) loss. > It is not my intention to sound confrontational. I really don't know how > other rule sets deal with tricky situations. No problem. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
On Dec 10, 2007 4:35 PM, Álvaro Begué <[EMAIL PROTECTED]> wrote: > > In GO, this is probably a more serious problem. > Yes, there is no such thing as an irreversible move in go. Well there is the opening move... (unless suicide is legal you can never recreate the empty board). > I think we are > stuck with sending the whole list of moves every time we want to describe > the current state of the game. Or simply don't use superko. Normal rules work fine with only some minimal knowledge of the last move. Long cycles are not an issue because they may repeat multiple times without altering the inevitable outcome (which, e.g., can be decided on the server side after n-fold repetition). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The global search myth
On Dec 5, 2007 5:01 PM, Álvaro Begué <[EMAIL PROTECTED]> wrote: > On Dec 5, 2007 9:33 AM, Erik van der Werf <[EMAIL PROTECTED]> wrote: > > > > Look for Realization Probability Search. > > Oh, thanks! I knew it was too natural to be original. Well, I actually > thought about it around 1998, so it might have been new back then. Maybe, but the closely related idea of adding fractional plies for search extensions has been around quite long. I would not be surprised if some Chess engines already used it in the 90's (but of course nobody would talk about it). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The global search myth
On Dec 5, 2007 3:03 PM, Álvaro Begué <[EMAIL PROTECTED]> wrote: > A long time ago I thought of how to organize what to prune The Right Way > (tm). I initially thought about it in the context of computer chess, but I > think it is even more relevant for computer go. Instead of doing global > search where you say "a node will be considered a leaf if it is n moves away > from the root", you can say "a node will be considered a leaf if the > probability of the game actually going through it is less than p". Now you > need a model for the probability distribution of moves at any given node > (maybe in the style Remi did it, maybe using prior search results...). If > you are 4 moves away from the root, you can multiply the probabilities of > those moves to get the probability of the branch. > > If you want to recover an additive notion of "depth", so you start with a > fixed quantity and you subtract something until you get to 0 and your code > looks more like traditional alpha-beta, you can use > -log2(probability_of_the_move), and then your depths are measured in bits > (see http://en.wikipedia.org/wiki/Information_content ). > > I would prefer to not take logs and work with probabilities because then > transposition can be dealt with correctly by adding the probabilities of the > converging branches. This may or may not be important. > > Probably other people have thought of this, but I have never seen the idea > expressed concisely before. I hope it gives people something to think about. Look for Realization Probability Search. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] euler numbers
On Nov 27, 2007 1:58 PM, Stuart A. Yeates <[EMAIL PROTECTED]> wrote: > Could you give us a quick reference for exactly _which_ Euler numbers > you're using? Wikipedia has three separate ones and the MathWorld site > a similiar number. I cannot speak for Don, but in the work on solving Go I calculated the zeros-joined Euler number from independent bitmaps for Black and White with the border set to zero. IIRC half-joined and ones-joined performed worse (in the sense that the tree got bigger). An interesting alternative may be to combine colours so that the quad-counts directly use all the local information (that way, e.g., the diagonal miai-connection can be distinguished from one where the opponent is interfering). Back in 2002 I did not use this because the binary version has a smaller lookup table. The ICGA article contains a bit less information than my thesis. E.g., an explanation of the Euler numbers can be found on page 28 of the thesis. Here's a link: http://erikvanderwerf.tengen.nl/publications.html Erik > On 26/11/2007, Don Dailey <[EMAIL PROTECTED]> wrote: > > > > After reading the paper on solving go on small boards, I am curious > > about the use of euler numbers as a simple evaluation element. > > > > I implemented a little euler number test program and it works correctly > > from a sample of about 50 positions of various types. I'm using the > > fast version where you scan 2 lines at a time with a lookup table. > > > > However, it calculates holes inside of groups and this does not detect > > eyes or "holes" on the edges of the board.It's not clear how to deal > > with this. > > > > I'm experimenting with a version that wraps a border around the whole > > board so that even the empty position looks like a 1 group with one big > > hole.This causes a lot of silly anomalies - for instance if you > > surround a big chunk of safe opponent stones it looks like a big > > hole.If you own half the board and the opponent owns the other > > half, his half contributes favorably to your euler number (it looks > > like a big hole of yours.) > > > > Of course I realize that this is just a quick and dirty calculation but > > I was curious about any tricks that others use to deal with it. > > > > - Don > > > > ___ > > 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] Language
On Nov 13, 2007 6:40 PM, Chris Fant <[EMAIL PROTECTED]> wrote: > > No need to get turned off on that. In most cases you don't need to > > shake that much. Remember you only need to get the new stone and its > > direct opponent neighbours connected to a liberty. There's plenty of > > tricks for early termination. Last time I tested it I got ~75k uniform > > random playouts on 9x9 (IIRC libego got ~100k on the same machine). > > > > Erik > > That's pretty good. And I'm guessing your code wasn't optimized to > the extent that libego has been. Maybe not as much as libego, but I did put some effort into the optimization. I'm sure it can still be optimized further, but for that I would consider some specialized assembler instructions (I believe others here have already done that). > Is it fair to say that heavy playouts are a better use of MC execution time? If you have to choose, yes, but in principle one does not exclude the other. It really depends on the kind of features you want from your representation. If, e.g., you frequently need exact liberty counts then a pure bit-board representation may not suffice. > And does a bitboard > approach make it more difficult to incorporate heavier concepts into > the playouts? For some concepts bitboards are actually quite nice, but for others you may want something else. My latest program has a mixed representation with bitboards and other data structures. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Nov 13, 2007 5:35 PM, Jason House <[EMAIL PROTECTED]> wrote: > On Nov 13, 2007 11:23 AM, Heikki Levanto <[EMAIL PROTECTED]> wrote: > > There are pathological cases where this has to loop many times, flood > filling > > the one liberty to a long chain of stones, but those should be rare. > > > > This was my big turn-off. I would expect the average case in mid-game to > require several shakes (maybe 4?). Even with 64 bit numbers, 9x9 bit boards > don't fit... requiring lots of operations per shake. With aspirations of > 19x19, I figured the overhead would be too much. > > I never did any formal proof or disproof of that. > No need to get turned off on that. In most cases you don't need to shake that much. Remember you only need to get the new stone and its direct opponent neighbours connected to a liberty. There's plenty of tricks for early termination. Last time I tested it I got ~75k uniform random playouts on 9x9 (IIRC libego got ~100k on the same machine). Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] XML alternatives to SGF
On 10/23/07, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > But I can provide a hint for something I would find useful. If it's > something I'm missing in today's sgf viewers it's a good way to dump and > inspect a transposition table. It's possible to expand the > transpositions into a big tree with duplicate subtrees but that makes it > very difficult to traverse it efficiently. Alternatively the tree is cut > off when the same position is reached again but then there's no easy way > to find where the position was first reached, which is needed to follow > the continuations. Finally a useful idea! I remember trying something like that a couple of years ago. I then did it the ugly way, simply by numbering each node with a comment. It can probably be done much nicer by having the option to tag a node and then provide some kind of symbolic link to refer to a tagged node (the transposition). Maybe reserve something like properties TaG and LinK for a future FF? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
On 10/11/07, terry mcintyre <[EMAIL PROTECTED]> wrote: > It would be great to see Steenvreter on the 9x9 cgos server. It is still on my to do list... > BTW, can you translate "Steenvreter" for us English speakers? Thanks! It is a combination of the Dutch words "Steen" and "vreter". (Dutch has the nice property that we can glue words together to create new ones.) The translation of "steen" is "Stone". "Vreter" is more difficult. "vreten" is a kind of rude form of eating, like an animal. I don't really know an accurate translation, maybe something like "devourer"? On 10/12/07, Chris Fant <[EMAIL PROTECTED]> wrote: > Someone already did: Stone eater. Phonetically this may be the best option, but the meaning is bit different. It would have been accurate for "Steeneter", but coming from "Steenvreter" the implied lack of etiquette is lost in translation. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Yes I'm here :-) Sorry to have to disappoint you though, I have not yet found enough time to work on 19x19. For now the throne rightfully belongs to Mogo. Erik On 10/11/07, Chris Fant <[EMAIL PROTECTED]> wrote: > Can we also count on Steenvreter for this 19x19 smack-down? You out > there, Erik? > > > On 10/11/07, Eric Boesch <[EMAIL PROTECTED]> wrote: > > On 10/11/07, David Fotland <[EMAIL PROTECTED]> wrote: > > > But the only way to settle this is to do some experiments. I could > > > certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and > > > we also have them play for ratings against people on kgs, it would settle > > > it. > > > > Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS. > > CrazyStone is rated 2k. All of these numbers are with moderate time > > controls (not the 15 minute sudden death time controls that became a > > subject of controversy). > > > > There was also KCConGui, running KCC Igo, that played for a while on > > KGS. I don't know whether it was an official bot, or whether its > > departure had anything to do with its lopsided losing record against > > CrazyStone. The KCConGui page notes that KCC Igo won the Gifu > > Challenge four years in a row, most recently against sparse > > competition, but the best claim to the computer go throne belongs to > > Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA > > tournament. > > ___ > > 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] Former Deep Blue Research working on Go
On 10/10/07, Don Dailey <[EMAIL PROTECTED]> wrote: > In GO, threats tend to be very indirect and distant, at least from the > point of view of a naive search algorithm and this is a real killer to > the idea - my feeling is that null move in GO is not workable. I have the same feeling. Some years ago in Magog I did quite a lot of experiments with tricks like (recursive) null move pruning. Although it provided significant reductions in the search tree it consistently made the program play weaker. The only trick that (almost) seemed to work was Multi-Cut. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OT: median of a data stream
On 8/16/07, Darren Cook <[EMAIL PROTECTED]> wrote: > Calculating the mean of a stream of numbers [1] is easy: just keep track > of the sum and the count, and divide at the end. But what about the > median? > I think I always need to buffer at least half the numbers A counter for each unique value should always suffice and may be less than half the numbers in the stream. If you don't require huge precision you can save a lot by increasing the bin-size (just maintain a histogram). > , but does anyone know for sure, or know a clever algorithm [2]? Not sure, but I guess you could look for an incremental update of any probability density approximation that has sufficient complexity for your purposes. An even more simplistic approach might be to compare incoming samples to the current estimate and increment/decrement by a small constant depending on whether it's higher or lower (but that may be too crude for your purposes). Best, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] EGC2007
On 8/10/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > I organized side event "Predict Professinal Moves" at > European Go Congress 2007. I made a brief and shallow > summary (without any analysis) of the results and decided > to post it here---in case someone is actually interested ;). > > The side event: >http://users.tkk.fi/eseurane/EGC2007/experiment.pdf > The summary: >http://users.tkk.fi/eseurane/EGC2007/summary.pdf > > -Esa It might be interesting to see how Rémi Coulom's move predictor does on these positions. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Abstract analysis of Monte Carlo playout
Hi Antti, I had a quick look at your numbers. Maybe I misunderstood something, but at first glance there appears to be a parity effect (an even number of 100% blunder moves always get it right). How do the statistics look if the game length is odd? If it matters, maybe you should sample over a reasonable distribution of game lengths or otherwise just average odd and even. Erik On 7/28/07, Antti Huima <[EMAIL PROTECTED]> wrote: > > Hi, > > there was some time ago discussion about whether it pays off to improve the > quality of an MC play-out agent or not, and how important it is to keep it > "balanced", so I performed the following abstract experiment: > > Assume that we start from a position that is game-theoretic win for Black. > If we play out moves from this position--say for instance 100--then every > move can either switch the game-theoretic value of the present position > (blunder) or not (in general a correct move). Of course the only way to > switch the game-theoretic value by a player is by blundering in a position > that is won for the player and ending up in a position that is lost for the > same player: there is no way to "blunder" a lost position into a won one. > > I implemented a simple C program that calculates the probability of ending > up with correct game-theoretic value at the end of the simulation when the > probability of blundering, when possible, is given as a function of the move > number. Here are some results (explanations below): > > Game length 100, simulations 100 > 0% flat | 100.00% > 1% flat | 99.01% > 2% flat | 98.04% > 5% flat | 95.27% >10% flat | 90.97% >20% flat | 83.28% >50% flat | 66.74% >80% flat | 55.59% >90% flat | 52.65% >95% flat | 51.58% >98% flat | 57.02% >99% flat | 68.53% > 99.5% flat | 80.37% > 99.8% flat | 90.97% > 99.9% flat | 95.21% > 100% flat | 100.00% > Linear ramp up | 50.17% >Linear ramp down | 99.03% > Squared ramp up | 50.17% > Squared ramp down | 99.99% > Squared ramp up, inverted | 98.09% > Squared ramp down, inverted | 49.97% > Spike | 0.00% >Spike with 10%/10% noise | 52.30% > Spike with 10%/0% noise | 9.95% > Spike with 0%/10% noise | 52.34% > > Each row represents one million play-outs. The left column is the > probability function (how probable it is to blunder) and the right column is > the probability that we get the "correct" result at the end of a play-out. > Here are the descriptions of the functions: > > - N% flat means that the move is correct with probability N% and a blunder > with probability (1-N%), when possible (you can't blunder if you are in a > lost position) > - Linear ramp up means that the probability is 100% * (k/N) where k is the > move number, i.e. moves tend to get better and better by the end of the game > - Linear ramp down is 100% * (1-k/N), i.e. inverted > - Squared ramp up is 100% * (k/N)^2 > - Squared ramp down is 100% * (1 - (k/N)^2) > - Squared ramp up and down inverted are obtained by 100% - X where X is the > squared ramp > - Spike means that black makes one blunder in the middle but all other > moves are correct > - Spike 10%/10% noise is 10% correct move in the middle move and 90% > elsewhere > - Spike 10%/0% noise is 10% correct move in the middle and 100% elsewhere > - Spike 0%/10% noise is 0% correct move in the middle and 90% elsewhere > > And here some analysis: > > - Obviously a move generated that blunders always with probability 1/2 when > possible is a great basis for MC analysis because it ends up with correct > game-theoretic value with 67% probability > > - It is also obvious that of the ones sampled above, the worst probability > patterns are rising ramps, i.e. playout agents that play badly in the > beginning but get better and better towards the end of the game. For these > agents the end result is basically just random noise. The reason is, I > believe, that first both players blunder all the time and the game-theoretic > value remains always won for Black (two blunders --> Black still winning), > but when the blunder probability starts to drop, first the result becomes > more or less random, and then the dropping probability "locks" the > game-theoretic value to the random value. > > Finally, to those who question these numbers, here some intuitive > explanation of the mechanics behind: > > Suppose you play correctly with probability 50% and you start with Black's > move from a position that is win for Black. > > With probability 50% you play correct, White answers whateve
Re: [computer-go] The Problem With Random Playouts
On 7/26/07, Darren Cook <[EMAIL PROTECTED]> wrote: A couple of months back I wrote an article on why I believe UCT with random playouts (as opposed to heavy playouts) will never give a strong computer go program. I've finally got it finished, edited and published: http://dcook.org/compgo/article_the_problem_with_random_playouts.html I'd be surprised if the UCT experts on this list will find much new there, but I hope some people will find it of value. Thanks to Magnus Persson for reviewing an earlier version. Darren One remark; when you write: "What I am calling random playouts for the purposes of this article give all legal moves equal weight and randomly chooses one of them, and this process is used for both players all the way to the end of the game." I get the impression that this also includes filling single point eyes. Is this your intention? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hint for good Bayes book wanted
On 7/23/07, chrilly <[EMAIL PROTECTED]> wrote: I have a Phd in statistics. But Bayesian methods were at that time a non-topic. I know the general principles, but I want to learn a little bit more about the latest developments in the field. Bayes is now chic, there are many books about it. I assume also a lot of bad ones. Can anyone recommend me a good state of the art book about Bayesian inference. Should be somewhat in the applied direction, but also with a sound mathematical background. Chrilly You could try something like: Information Theory, Inference & Learning Algorithms by David MacKay or maybe Data Analysis: A Bayesian Tutorial by Devinderjit Sivia & John Skilling Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
On 7/23/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: No. Erik is wrong even in theory. An arguement can fault in two aspects:assumption and logic. His arguement faults on the former, even his logic is iron clad. He assumed the existence of an Oracle, which we all know is incorrect. 'We' seem to be drifting away a bit here... Adaptation is something that is easily observed with relatively stupid entities. To some extend I agree that such an observation probably indicates some kind of intelligence, but on the other hand, the world is full of adaptive systems which for some reason several of the earlier posters here would not consider to be intelligent. Once the level of intelligence of some artificial system would move far beyond the level of the observer he may no longer be able to observe the adaptation or learning (and with human observers in complex domains we probably don't even need to go to oracle-level for that). However, does that mean the system would now be considered unintelligent, or stupid, just because adaptation stopped or because we simply can't detect it? I don't think so! I guess most ordinary humans might even consider this system to be incredibly intelligent. But how do they get to that conclusion without observing any adaptation or learning? E. BTW Oracles are a useful tool for theory. Moreover, in practice they can be constructed for sufficiently small well defined finite domains such as small board Go, six-men chess (end)games, etc. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
On 7/22/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: Can this oracle explain logically how he become one? :) :-) That depends on the domain. If the domain is Go-world you would not even be able to phrase that question. If the domain would be the world in which you live, the correct answer would probably be something like "You are too young for this boy." ;-) E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
On 7/22/07, Jim O'Flaherty, Jr. <[EMAIL PROTECTED]> wrote: In theory, there is a perfect girlfriend for me. In practicality, there is my adapting to make the current girlfriend good enough and better, with perfection never really obtainable. Interesting example. Intelligence may be like beauty; very difficult, if not impossible, to define objectively. But then, you seem to know pretty well what she should be like ;-) Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
On 7/22/07, Weimin Xiao <[EMAIL PROTECTED]> wrote: "A hypothetical almighty oracle that already knows the correct answer to every question and the right response in every situation would never have to adapt." For a moran without a goal, the ability to adapt or to learn is where he shows his intelligence. I suppose you mean moron ;-) But yes, as long as we make fallible AI systems, adaptivity or learning will probably be an important feature to distinguish between the various shades of stupidity. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
On 7/21/07, Weimin Xiao <[EMAIL PROTECTED]> wrote: Intelligence is the ability to adapt or learn. A hypothetical almighty oracle that already knows the correct answer to every question and the right response in every situation would never have to adapt. Hence evidence of intelligence according to your definition would not be observed. IMO the adaptation is just a means to an end. The end (Intelligence, whatever it is) does not necessarily require adaptation. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Why are different rule sets?
On 7/12/07, Nick Wedd <[EMAIL PROTECTED]> wrote: >For computers special cases matter. Especially for a search based >programm. A search based programm finds every possible special case and >plays into this case, because the opponent does not prevent it. >Are there something as Universal accepted computer-Go rules? There is - >at least on paper - a computer FIDE. The IGGA. Is there something as >the IGGA computer-Go ruleset? According to the game records from the recent ICGA events in Amsterdam, the 19x19 events used Japanese rules with 6.5 komi, and the 9x9 games used Chinese rules, but with 6.5 komi. So I suspect not. Don't trust the rule specification (or timing information for that matter) in the raw game records, they may have been set differently to circumvent difficulties by those who played using a remote system. All Go events in Amsterdam used Chinese rules. IIRC the last time the Olympiad used Japanese rules was in 2002, after that it was always Chinese rules. BTW I have no idea what IGGA means, "International Guild Of Glass Artists", "International Grooving and Grinding Association", "International Gomputer Games Association", is it a typo??? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Interesting Test Position (for UCT)
On 7/11/07, chrilly <[EMAIL PROTECTED]> wrote: Attached is an interesting testposition which occured in UCT-Suzie against Peter-Woitke. If black plays 37 c4 the game is lost by 0.5 points. If Black passes, white gets a lot of threats. Black can choose between a safe loss, or some risk and a win. UCT-Suzie and the public domain version of Crazy-Stone played the save loss. Seems like you're mixing up Territory and Area scoring. Under area scoring rules the programs can strengthen their (final) position by playing in their own territory. (Crazystone as Black would win under Chinese rules) The example illustrates why Japanese rules provide a slightly more interesting endgame. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Explanation to MoGo paper wanted.
On 7/11/07, Richard Brown <[EMAIL PROTECTED]> wrote: On 7/11/07, Don Dailey <[EMAIL PROTECTED]> wrote: > The dirty hack I'm referring to is the robotic way this is implemented > in programs, not how it's done in humans. With a pattern based program > you essentially specify everything and the program is not a participant > in the process. It comes down to a list of do's and dont's and if we > can claim that knowledge was imparted it might be true, but no wisdom or > understanding was. I'm compelled to point out that neural nets, _trained_ on patterns, which patterns themselves are then discarded, have the ability to "recognize" novel patterns, ones which have never been previously seen, let alone stored. The list of do's and dont's has been discarded, and what to do or not do, in a situation that may never have been seen before, is inferred, not looked-up in a library of rules. So, it is not true that with a pattern-based program "you essentially specify everything". At least, not if you have thrown the patterns away, and have substituted multilayer feedforward networks for that _training_data_. > UCT simulates understanding and wisdom, patterns just simulates > knowledge. This is a very strong assertion. We eagerly await the proof. :-) I can just as easily assert: Trained neural nets simulate understanding and wisdom. (A static pattern library merely simulates knowledge, I agree.) > Again, this is largely philosophical because even UCT programs are > robots just following instructions. It's all about what you are trying > to simulate and why it's called AI.I think UCT tries to simulate > understanding to a much greater extent than raw patterns in a > conventional program. Than raw patterns, yes. Trained neural nets, too, try to simulate understanding to a much greater extent than do raw patterns. Of course Don is right, it boils down to philosophy. And while we're on that topic, ... I regret some of the terms that have come into use with regard to AI, due to the (misguided, in my humble opinion) philosophy of some. The very name "artificial intelligence" bothers me; AI programs are neither. When humans run certain computer programs, the programs may seem "intelligent" enough to perform other tasks. By the implied reasoning, taken to its logical conclusion, a hammer is "intelligent" enough to drive a nail. The military has their so-called "smart bombs" but in truth, machines and algorithms are no more intelligent than hammers. By a similar token, "pattern recognition" bothers me. Machines and algorithms don't "recognize" anything, ever. That's anthropomorphism. A somewhat better term is "pattern classification", but machines don't really classify anything, either. It is we humans who classify, _using_ the machines. It's like saying that the hammer drives the nail, when in fact it is the human who does so, _using_ the hammer. And there is nothing particularly "neural" about "neural networks", other than their origins. (True, they were first invented -- discovered, really -- by someone who was trying to simulate a neuron, but they are much more general than that.) I prefer the term "multilayer feedforward network" for the type of "neural net" commonly used in many domains. (And now in go!) This sort of semantic nitpicking may seem too severe. However, it keeps me from falling into the camp of those who believe that machines will one day literally become intelligent, develop self-awareness, and achieve consciousness. Ain't gonna happen. -- Rich P.S. -- I hated the movie "AI". So how would you define intelligence? E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Who else uses Hashtables in UCT?
On 7/10/07, chrilly <[EMAIL PROTECTED]> wrote: I have no finished a plain vanilla 9x9 Suzie-UCT Version. The UCT-tree is stored in a Hashtable. I am interested who else uses this approach. Steenvreter has a hashtable. The reason for using a hashtable was: I was too lazy to implement an explicit tree. At least at 9x9 I have no problem with memory size. In fact there are 2 hashtables, one for the Alpha-Beta and one for the UCT-Version. With the default parameters each version uses 160 MB. A chessprogrammer in Go-Land, part X: I interpreted SuperKo as repetition of position (which seems to be correct, although Stefan Mertin told me, there are numerous versions of SuperKo). I used the Nimzo/Hydra code to detect this. But there is a - not a very subtle - difference between Go and Chess. A move which generates a repetition of position is in Chess legal, in Go it is'nt. That actually depends on the rules; there is no world-wide consensus on how to deal with long cycles. Traditional rules allow some long cycles, unpolished western rules declare any repetition illegal. But I assumed its legal and had quite complicated and buggy code to handle this case. I did not know how to evaluate it. It came not to my mind, that its just an illegal move and one only has to generate the nextbest one. Stefan Mertin told me the difference several times, but it did not help, only the advice of Peter Woitke, just delete this stupid code, was the right instruction level. :-) Steenvreter recognizes the following 3 types of long cycles (all situational): (1) winning cycles (the player that completes the cycle gains in each round because he captures more stones or equivalently passes more), (2) losing cycles (opposite of winning cycles), and (3) balanced cycles (both sides capture the same number of stones). In the tree, when a long cycle is detected the corresponding result (win/loss/jigo) is directly used instead of the normal MC-playout result. Losing cycle results are only used locally (they are not propagated down to the root because any other move should be considered better than a direct loss); for updating the other nodes the search simply continues on another move. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: Erik wrote: > Sure, but that does not necessarily matter because there are many more > end- than middle-game positions. The reason I brought it up is that I > remembered a statement by someone (sorry forgot the source, maybe John > or Gunnar remembers) that from all legal positions nearly all can be > considered final. Of course one could argue about what makes a > position final, obviously not all borders will be nicely closed and > generally there will still be some points to be gained, but I think > the main idea was that at that point the winner is relatively easy to > determine (so one side would normally resign). This also makes sense > if you simply look at the expected number of stones on the board. I don't remember that statement. My guess, without trying it out, is that most legal positions are rather unsettled and that the number of positions that are final in any strong sense is a tiny fraction of the legal positions. Ok, then probably I'm mistaken and read it in a different context. In any case, my statement should be relatively easy to falsify; just generate some positions and count the fraction that is easily solved. If correct, a decent uct search, or maybe even a traditional solver, would in most cases quickly converge to an extreme probability of winning. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: On 7/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: > > On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: > > I think this is what I want. Thanks! So I might have to repeat this > > a few hundred times to actually get a legal position? > > Are you aware that nearly all of these positions will be final positions? > > So I'll repeat my question: why do you need any of this? If you only > need final positions it's probably much better to take them from real > games, and if you actually need middle game positions you will have to > use a different procedure... > > E. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > Won't the final positions be much more likely to be rejected since they are much more likely to be illegal? Sure, but that does not necessarily matter because there are many more end- than middle-game positions. The reason I brought it up is that I remembered a statement by someone (sorry forgot the source, maybe John or Gunnar remembers) that from all legal positions nearly all can be considered final. Of course one could argue about what makes a position final, obviously not all borders will be nicely closed and generally there will still be some points to be gained, but I think the main idea was that at that point the winner is relatively easy to determine (so one side would normally resign). This also makes sense if you simply look at the expected number of stones on the board. What is your claim about the distribution of the number of stones on the board with this scheme? Simply that for most interesting purposes you will have too many of them on the board. Further, depending on the purpose, one might argue that there are more interesting distributions to sample from (e.g., you could sample from all positions ever played by strong players on KGS). I am hoping to use this method to help generate training data for a learning system that learns certain graph properties of the board that can also be computed deterministically from the board position. I know that might sound crazy, Not to me ;-) but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. Well, I'm not sure whether this way you will be able to beat hand coded algorithms, but it's certainly interesting to try. In any case I would still think that, to make a strong program, it's better to sample from real games, or maybe do both to see if it makes much difference. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: I think this is what I want. Thanks! So I might have to repeat this a few hundred times to actually get a legal position? Are you aware that nearly all of these positions will be final positions? So I'll repeat my question: why do you need any of this? If you only need final positions it's probably much better to take them from real games, and if you actually need middle game positions you will have to use a different procedure... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/8/07, George Dahl <[EMAIL PROTECTED]> wrote: How would one go about creating a random board position with a uniform distribution over all legal positions? Is this even possible? I am not quite sure what I mean by uniform. If one flipped a three sided coin to determine if each vertex was white,black or empty, then one would have to deal with stones with no liberties somehow. Could those just removed? - George All legal positions can be enumerated, so just create a database containing all legal positions and then select one at random. If this does not work for you, e.g., due to insufficient storage, just keep generating random positions (using your special coin) until you hit one that's legal. OC, once you start 'correcting' illegal positions it probably won't be uniform over all legal positions any more, that's why, unless you come up with something clever, you should regenerate the entire position. May I ask why you need any of this? E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] results of computer olympiad 9x9
On 6/16/07, Peter Drake <[EMAIL PROTECTED]> wrote: It's still a long way off, but I hope to organize a computer Go tournament at the 2008 Congress here in Portland, Oregon. Would that be in August? It might not fit well with the events in Beijing. see: http://www.grappa.univ-lille3.fr/icga/event.php?id=37 Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] results of computer olympiad 9x9
On 6/16/07, Don Dailey <[EMAIL PROTECTED]> wrote: On Fri, 2007-06-15 at 23:54 +0200, Erik van der Werf wrote: > So far, Steenvreter has never played on CGOS. I'm very busy with work, > so it will take a while before I have time to put it up for some > games. Also to be honest, I'm not really that interested. I guess CGOS > is nice if you have no other way to evaluate the strength of your > program, but I really like it much more to play in a tournament like > the Computer Olympiad where I can meet other programmers face to face. It sounds almost like you are afraid to play on CGOS. After winning a tournament you may feel that you have a reputation to protect. I understand it may look that way, but really the primary problem is lack of time. Coming week I have to be in Sweden, then a conference in Germany, and further a lot of other small things to do in between. These things were much easier when I was working full time at university... I personally feel the results of hundreds of games on CGOS are more valid than 10 games no matter how much importance or prestige is attached to a particular tournament. 10 games just isn't statistically significant. The tournament was double round robin, so that's 18 games. On the first day I lost one game because of a stupid bug, and won 2 because I was lucky to meet a weak opponent. I was only able to recover from the unnecessary loss against Go Intellect because Crazy Stone managed to crush Mogo twice in the normal rounds. Also Mango could probably have done much better if it hadn't suffered from some weird bugs, so clearly the outcome could have been quite different... Having said that, I agree with you 100 percent about your preference. There is nothing that compares to a real face to face tournament for the pure excitement of it. The stress of each move is powerful motivator for improving your program. I am also a strong supporter of ICGA having been a member off and on since it was ICCA in the early days. I really loved the experiences of playing in the Computer Chess tournaments they organized and the people I got to know. Your result was excellent, but the results were close, only a 1 game difference between the top 3 finishers doesn't "evaluate" a program. If you played that same tournament over and over you would very likely see Mogo and CrazyStone winning many of them too. There is no way to say who is better especially since the hardware isn't even equal, Steenvreter running on the most powerful of the 3 top finishers. You're completely right. I think Mogo and Crazystone play stronger in the beginning of the game, and my program has to be a bit lucky to get them into a difficult fight. This is not something that can't be solved, I know exactly what I have to do, but I just need time. Steenvreter was really a rush job, hacking things together until the last day before the tournament and no time to test properly. I was hoping to be able to catch up with the stronger programs, but never expected it to win the tournament. When I played in the ICCA organized tournaments we used to privately laugh (even though we absolutely loved those well organized tournaments) that people actually believed it was about "proving who was the best computer player in the world."In 1993 my program won the International Computer Chess Championship and we privately joked about that too - we knew that we had played 2 programs that were at least a little better and one that was MUCH better. We "lucked out" by getting a draw against the program that was much better and wining against the 2 that we believed had a statistically better chance of beating us. We knew we were not the best, but we prepared the program to win. We knew it was about being good enough that we had a chance to win. A weak program has almost no chance, but to have a "reasonable" chance of winning a tournament you must be good enough to consistently beat the weaker players and not so weak that you have little chance of beating 1 or 2 strong players. In a 5 round tournament which was typically what we played in, you may only have to face 1 strong program and if you have a chance of beating it, you can win a tournament - or someone else may knock it out so that you don't have to. Winning a 10 round tournament of course if much more impressive. But it's still not a very valid indicator of who is the better player. We were in Hong Kong one year and I think Murray Campbell, one of the Deep Blue authors told me that they estimated their chances of winning to be about 50%. At first that sounded ludicrous because they were the heavy favorites and everyone knew their program was far better than any other program. But there calculations were roughly correct. Being best doesn't mean you will win. The problem is that you usually have to win almost ever
Re: [computer-go] results of computer olympiad 9x9
On 6/16/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: If Mogo had played B8 instead of C9 it probably would have won the game. Oops, that should of course be B8 instead of A7. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] results of computer olympiad 9x9
On 6/14/07, Sylvain Gelly <[EMAIL PROTECTED]> wrote: Hi Magnus, Congratulations to Steenvreeter. Thank you for your analysis. Did you looked at the first game Steenvreeter-MoGo (MoGo was white)? I wonder, because MoGo was really happy, estimation always increased, up to 81%, then in one move dropped to less 50%, and MoGo eventually lost. I wonder if MoGo did a blunder, or simply that it evaluated badly the position for some reason. In the second game, it increased exactly in the same way, but continued to increase to a win this time ;-). Cheers, Sylvain I did some analysis with Steenvreter. The game seems to be one of the most difficult from the tournament. It's hard to say for sure, but according to Steenvreter Mogo was ahead until move 50. If Mogo had played B8 instead of C9 it probably would have won the game. I think the main reason why Mogo lost is that it had already used too much time, and simply could not search deep enough to find the solution. Best, Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
