RE: [computer-go] Life and Death
I just looked at this position and it looks like a win for black in the first position. Many Faces evaluates it as a win for black, and plays c1 to save the lower left black group with almost no thinking time. Mogo is correct because the lower left black group is not dead. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Matthew Woodcraft > Sent: Sunday, March 09, 2008 11:49 AM > To: computer-go > Subject: [computer-go] Life and Death > > I've included two 13x13 positions below. In both positions it is > Black's > move. > > The first position is simplified from a real game. Black has two > enclosed dead groups, and White has a small but easy win. > > The second position is a modified version of the first in which the > dead > groups are more obviously dead. > > If I try MogoRelease3 playing as Black on position 2, it shows a 20% > score and resigns either immediately or after a couple of moves. > > If I try it on position 1, it shows a score of 70%+ for Black, and > continues to play until White takes steps to remove the dead groups > from > the board. I've tested with up to 2^24 playouts. > > I have tried increasing --collectorLimitTreeSize and --limitTreeSize > (like bigMogo in the scalability study), but I can't set them much > higher than the default on this machine without running out of memory. > > I'd be interested to see if someone with a bigger computer can find out > what resources it needs to judge this position well, and to see how > other engines do. > > Position 1 > > (;GM[1]FF[4] > CA[UTF-8] > SZ[13] > HA[0] > KM[0.5] > AB[jb:kb][cb:cc][kc][bd:cd][jd:ld][be][he][cf:df][bg][gb:gh] > [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][lk][al][ck:cl][ji:jl] > [dm][im] > AW[ia:ja][ib][hc:jc][db:dd][hd:id][ce:de][ie][ke:le][bf][hf:jf] > [lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk][hk:ik] > [dl][il][bm][fl:fm][hm] > ) > > Position 2 > > (;GM[1]FF[4] > CA[UTF-8] > SZ[13] > HA[0] > KM[0.5] > AB[jb:mb][cb:cc][kc][bd:cd][jd:md][be][he][cf:df][bg][gb:gh] > [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][bk:ck][lk][al][cl] > [ji:jl][im] > AW[ia:la][ib][hc:jc][mc][db:dd][hd:id][ce:de][ie][ke:le][bf] > [hf:jf][lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk] > [hk:ik][dl][fl][il][bm:cm][em:fm][hm] > ) > > -M- > ___ > 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] Life and Death
David Fotland: <[EMAIL PROTECTED]>: >I just looked at this position and it looks like a win for black in the >first position. Many Faces evaluates it as a win for black, and plays c1 to >save the lower left black group with almost no thinking time. > >Mogo is correct because the lower left black group is not dead. I'm sorry if wrong but the black seems dead by B5 after C1, isn't it? -Hideki >David > >> -Original Message- >> From: [EMAIL PROTECTED] [mailto:computer-go- >> [EMAIL PROTECTED] On Behalf Of Matthew Woodcraft >> Sent: Sunday, March 09, 2008 11:49 AM >> To: computer-go >> Subject: [computer-go] Life and Death >> >> I've included two 13x13 positions below. In both positions it is >> Black's >> move. >> >> The first position is simplified from a real game. Black has two >> enclosed dead groups, and White has a small but easy win. >> >> The second position is a modified version of the first in which the >> dead >> groups are more obviously dead. >> >> If I try MogoRelease3 playing as Black on position 2, it shows a 20% >> score and resigns either immediately or after a couple of moves. >> >> If I try it on position 1, it shows a score of 70%+ for Black, and >> continues to play until White takes steps to remove the dead groups >> from >> the board. I've tested with up to 2^24 playouts. >> >> I have tried increasing --collectorLimitTreeSize and --limitTreeSize >> (like bigMogo in the scalability study), but I can't set them much >> higher than the default on this machine without running out of memory. >> >> I'd be interested to see if someone with a bigger computer can find out >> what resources it needs to judge this position well, and to see how >> other engines do. >> >> Position 1 >> >> (;GM[1]FF[4] >> CA[UTF-8] >> SZ[13] >> HA[0] >> KM[0.5] >> AB[jb:kb][cb:cc][kc][bd:cd][jd:ld][be][he][cf:df][bg][gb:gh] >> [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][lk][al][ck:cl][ji:jl] >> [dm][im] >> AW[ia:ja][ib][hc:jc][db:dd][hd:id][ce:de][ie][ke:le][bf][hf:jf] >> [lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk][hk:ik] >> [dl][il][bm][fl:fm][hm] >> ) >> >> Position 2 >> >> (;GM[1]FF[4] >> CA[UTF-8] >> SZ[13] >> HA[0] >> KM[0.5] >> AB[jb:mb][cb:cc][kc][bd:cd][jd:md][be][he][cf:df][bg][gb:gh] >> [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][bk:ck][lk][al][cl] >> [ji:jl][im] >> AW[ia:la][ib][hc:jc][mc][db:dd][hd:id][ce:de][ie][ke:le][bf] >> [hf:jf][lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk] >> [hk:ik][dl][fl][il][bm:cm][em:fm][hm] >> ) >> >> -M- >> ___ >> computer-go mailing list >> computer-go@computer-go.org >> http://www.computer-go.org/mailman/listinfo/computer-go/ > >___ >computer-go mailing list >computer-go@computer-go.org >http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Life and Death
I think that the original description of the position should have said 'killable' rather than 'dead', and that David missed the fact that it is White to move. At 08:06 27/03/2008, Hideki wrote: David Fotland: <[EMAIL PROTECTED]>: >I just looked at this position and it looks like a win for black in the >first position. Many Faces evaluates it as a win for black, and plays c1 to >save the lower left black group with almost no thinking time. > >Mogo is correct because the lower left black group is not dead. I'm sorry if wrong but the black seems dead by B5 after C1, isn't it? -Hideki >David > >> -Original Message- >> From: [EMAIL PROTECTED] [mailto:computer-go- >> [EMAIL PROTECTED] On Behalf Of Matthew Woodcraft >> Sent: Sunday, March 09, 2008 11:49 AM >> To: computer-go >> Subject: [computer-go] Life and Death >> >> I've included two 13x13 positions below. In both positions it is >> Black's >> move. >> >> The first position is simplified from a real game. Black has two >> enclosed dead groups, and White has a small but easy win. >> >> The second position is a modified version of the first in which the >> dead >> groups are more obviously dead. >> >> If I try MogoRelease3 playing as Black on position 2, it shows a 20% >> score and resigns either immediately or after a couple of moves. >> >> If I try it on position 1, it shows a score of 70%+ for Black, and >> continues to play until White takes steps to remove the dead groups >> from >> the board. I've tested with up to 2^24 playouts. >> >> I have tried increasing --collectorLimitTreeSize and --limitTreeSize >> (like bigMogo in the scalability study), but I can't set them much >> higher than the default on this machine without running out of memory. >> >> I'd be interested to see if someone with a bigger computer can find out >> what resources it needs to judge this position well, and to see how >> other engines do. >> >> Position 1 >> >> (;GM[1]FF[4] >> CA[UTF-8] >> SZ[13] >> HA[0] >> KM[0.5] >> AB[jb:kb][cb:cc][kc][bd:cd][jd:ld][be][he][cf:df][bg][gb:gh] >> [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][lk][al][ck:cl][ji:jl] >> [dm][im] >> AW[ia:ja][ib][hc:jc][db:dd][hd:id][ce:de][ie][ke:le][bf][hf:jf] >> [lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk][hk:ik] >> [dl][il][bm][fl:fm][hm] >> ) >> >> Position 2 >> >> (;GM[1]FF[4] >> CA[UTF-8] >> SZ[13] >> HA[0] >> KM[0.5] >> AB[jb:mb][cb:cc][kc][bd:cd][jd:md][be][he][cf:df][bg][gb:gh] >> [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][bk:ck][lk][al][cl] >> [ji:jl][im] >> AW[ia:la][ib][hc:jc][mc][db:dd][hd:id][ce:de][ie][ke:le][bf] >> [hf:jf][lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk] >> [hk:ik][dl][fl][il][bm:cm][em:fm][hm] >> ) >> >> -M- >> ___ >> 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/ -- This email has been verified as Virus free. Virus Protection and more available at http://www.plus.net ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
Quoting Petr Baudis <[EMAIL PROTECTED]>: Please note that pachi1 had a rather embarassing bug of starting the random playouts with wrong color (so if the last tree node was black, the playout would start with black as well). pachi2 has this bug fixed; the ELO rating is still not settled, but so far it seems that the impact of this has been about 20-30 ELO in the 110k playouts area, which seems surprisingly little to me. It just shows that MC evaluation is robust, and this is because it is relative between moves and not an absolute evaluation. As long as the same bug applies to all moves it should not be that important. If the playouts are light i guess it matters even less. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
Magnus Persson wrote: > Quoting Petr Baudis <[EMAIL PROTECTED]>: > >> Please note that pachi1 had a rather embarassing bug of starting the >> random playouts with wrong color (so if the last tree node was black, >> the playout would start with black as well). pachi2 has this bug fixed; >> the ELO rating is still not settled, but so far it seems that the impact >> of this has been about 20-30 ELO in the 110k playouts area, which seems >> surprisingly little to me. > > It just shows that MC evaluation is robust, and this is because it is > relative between moves and not an absolute evaluation. As long as the > same bug applies to all moves it should not be that important. If the > playouts are light i guess it matters even less. Yes, I agree. With light playouts I would expect starting with the wrong move to only be a slight weakening of the program. - Don > > -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/
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: What I have now takes 10-15 microseconds on a 2Ghz Intel computer to find all the patterns on a board (on average for 9x9, for 19x19 it's more like 15-20 usec) From your difference between 9x9 and 19x19 I assume that you are updating the patterns of the cells after a stone was placed, (else the difference should be 361/81 times) not a computation from scratch. I make this sure so that we compare apples to apples. As far as the patterns computing is concerned, (i.e. excluding the board part verifying captures, etc.) for a pattern of 40 neighbors I get times easily below 500 nanoseconds (even on an old P4 3.4 GHz) for updating 40 hashes. I explained that about June last year, when I wrote it. Since it passed my tests (June 07) I have never changed a character in the code that writes the 67090 asm lines. It is just a black box, that works 100%. Each board cell has an updating function that knows where the board limits are, the resulting code (for hash 32 bit mode) is something like an endless: lea ebx, [edx + ecx*2 - SizeOf_bccCell] mov eax, 0967f6762h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax lea ebx, [edx + ecx*2] mov eax, 0d83b6518h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax lea ebx, [edx + ecx*2 + SizeOf_bccCell] mov eax, 0121001f7h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax The longest of these functions has 206 lines, the typical about 120. There is not a single conditional jump, no vars in RAM, etc. It's written in Java so making it in C would possibly give a two-fold speedup. I hate the Java war but, when I said that it is taking a 10 year handicap, at least for patterns that is true with no doubt. My code running on 1998 hardware (it is compatible) outperforms Java code for updating patterns. Somehow smaller sets don't go much faster, but larger sets do slow down, every ten-fold increase in number of patterns seems to double the time. What I wrote above updates the hashes (or the masks, because the board has many modes) but does not search the hash to get urgency. For searching in a sorted list, I use the second best language after automated asm .. .. manually written asm, of course ;-) ;; One iteration: ;; -- CompStepMACRO name mov eax, ebx add eax, ecx shr eax, 1 and al, 0fch ;; Align to a valid pointer cmp edx, [eax] jz &name&out cmovc ecx, eax;; This is true if [eax] > value cmovnc ebx, eax;; This is true if the previous is false ENDM Also (almost) without conditional jumps. The only conditional jump is selected once when the hash is found and exits. 10 steps of that can search in a 1024 long list, 20 steps in 1024^2. A doubling in table size is just adding one step, (8 instructions, say 64 clock cycles). I hope this helps. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching (Oops)
"Santiago" wrote: ... Oops, wrong name ... (Santiago is my official name, because I was born in a dictatorship that did not allow foreign names. After that, I was too lazy to change it. Jacques, like my French grandfather, is my real name.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ing Challenge
On Wed, Mar 26, 2008 at 08:50:28PM -0700, David Fotland wrote: > > You are right. > > Well, I did compete for this prize about 15 times, so I hope so :) Are there any current prized computer tournaments or does anyone know about Ing foundation or anyone else planning to resume the challenge? What was the reason that it got interrupted, lack of fast enough progress or simple reallocation of funds within the foundation? -- Petr "Pasky" Baudis Whatever you can do, or dream you can, begin it. Boldness has genius, power, and magic in it.-- J. W. von Goethe ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: > Thanks for the pointer Don, that might be worth looking into at some > point. > > When you say 'amazing accuracy despite this speed and simplicity' I > still have to ask: "how fast?". I think 10usec is actually pretty > fast. But when talking about using it during MC playouts for example, > it's still rather slow. This is due to the pile-up of numbers. A > (relatively) big area to look for, and a large number of occasions to > do the lookup. > > The patterns don't necessarily need to be hand-crafted. But throwing a > million generated patterns at it also has its price in terms of > performance. Pattern lookup has nothing to do with the number of patterns it was trained on of course. Think of this as a kind of neural net.The data produced is compact, and is a function of the number of attributes, and the number of classes (this is a classifier) and not the amount of patterns used for training. Therefore 10 million training patterns would take the same storage as 1 million or even just one.I generate 16 versions of each pattern for each possible color and orientation and the training time, I'm guessing, is dominated by the time it takes to read the training file (a text file) into memory, parse the fields, and rotate the patterns. Of course I don't really care about the training time itself since this is a one time operation but it's fast nevertheless, not like training a neural net or running a genetic algorithm. All it is, is parsing data and collecting it into a data structure to be able to calculate probabilities from. If you are just interested in patterns generated the old fashion way, hand crafted without learning or generalization (other than wild cards), then this has nothing to offer for you.The techniques for doing this have been around for decades and you are an expert in them and there is nothing new in this. David Fotland, and many of the top GO people have very fast pattern matchers that work well and are super-optimized to do what they do very quickly. I definitely agree with you, when it comes to pure state of the art pattern matching (the old fashioned way) that variable pattern shapes with wild-card matching is very important. This is all fine for a programmer who is also an expert GO player, but for someone like myself there is no other choice (other than taking a few years to become a GO expert) but to explore this in a machine learning context. Naive Bayes is called "naive" for a reason. It makes assumptions about the independence of observations that are not true, however it has been shown both empirically and formally that it can very often perform surprisingly well despite these limitations even in domains where attributes are highly correlated.In GO, patterns attributes of course are highly correlated probably to an absurd degree, but there are many simple enhancements that correct the shortcomings while maintaining most of the simplicity. But it is a whole different thing from what you are doing. - Don > > Mark > > > On 26-mrt-08, at 16:17, Don Dailey wrote: > >> Mark, >> >> I am doing some experimentation with something similar to patterns, but >> based on Naive Bayes classifiers. The idea is to use Naive Bayes >> classifiers to generalize patterns. The classifiers would still be >> focused on some constrained area of the board, such as the 5x5 matrix or >> something, but they would be extremely compact compared to patterns and >> very good at generalizing. I'm convinced they would have to be enhanced >> with additional attributes concerning the points being considered, but >> one of their strengths is that you can pile on huge numbers of >> attributes without killing the speed or memory consumption very >> significantly. >> >> Recently there has been a huge surge of interest in Naive Bayes >> Classifiers due to their simplicity and speed, and yet amazing accuracy >> despite this speed and simplicity.Nothing has been found that >> improves all that much on Naive Bayes for many applications, and some >> simple improvements to Naive Bayes has put it in the same league as >> other far more complex and computationally expensive methods such as >> neural networks and decision trees. >> >> I have no idea whether I'm barking up the wrong tree - but I think it's >> definitely worth taking a look at. I don't think GO programs can be >> improved much more by simply adding more hand crafted patterns - we need >> to find ways to generalize knowledge in powerful ways. >> >> Naive Bayes is trained by example and it's trivial, basically a single >> pass statistics gathering. So you must basically show it a gazillion >> sample patterns with "known" classifications.You could build these >> from games of strong players for instance. >> >> - Don >> >> >> >> >> Mark Boon wrote: >>> Lately I have been putting some effort into pattern-matching. Although >>> I have made progress, the result wa
Re: [computer-go] State of the art of pattern matching
Jacques, Yes, I do an incremental update so the board-size should be almost irrelevant. I'm not sure why I see any difference between 9x9 and 19x19 but it may have to do with the fact that the edge cuts a lot of pattern seach short. On 27-mrt-08, at 10:13, Santiago Basaldúa wrote: Mark Boon wrote: What I have now takes 10-15 microseconds on a 2Ghz Intel computer to find all the patterns on a board (on average for 9x9, for 19x19 it's more like 15-20 usec) From your difference between 9x9 and 19x19 I assume that you are updating the patterns of the cells after a stone was placed, (else the difference should be 361/81 times) not a computation from scratch. I make this sure so that we compare apples to apples. As far as the patterns computing is concerned, (i.e. excluding the board part verifying captures, etc.) for a pattern of 40 neighbors I get times easily below 500 nanoseconds (even on an old P4 3.4 GHz) for updating 40 hashes. I explained that about June last year, when I wrote it. Since it passed my tests (June 07) I have never changed a character in the code that writes the 67090 asm lines. It is just a black box, that works 100%. Each board cell has an updating function that knows where the board limits are, the resulting code (for hash 32 bit mode) is something like an endless: lea ebx, [edx + ecx*2 - SizeOf_bccCell] mov eax, 0967f6762h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax lea ebx, [edx + ecx*2] mov eax, 0d83b6518h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax lea ebx, [edx + ecx*2 + SizeOf_bccCell] mov eax, 0121001f7h bt dword ptr [ebx], bidx_StoneBit cmovc eax, esi xor [ebx + 4], eax Sorry, without a bit more explanation, the assembler code is very hard to understand. What exactly does it do? Does it relate to a pattern? Did you write a paper or post explaining this in more detail? Do I understand correctly that you generate this code automatically? I believe David Fotland does something similiarly. I have thought about that but I wasn't sure if that was really much faster. You are talking about updating 40 hashes. Does it mean your patterns have fixed size? In the 500 nanoseconds, how many patterns do you compare? One? A thousand? A million? How about rotations and color inversions? To make it really an apples to apples comparison I'd like to make sure we're talking about the same thing. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Life and Death
--- David Fotland <[EMAIL PROTECTED]> wrote: > I just looked at this position and it looks like a > win for black in the > first position. Many Faces evaluates it as a win > for black, and plays c1 to > save the lower left black group with almost no > thinking time. > > Mogo is correct because the lower left black group > is not dead. That's interesting -- did Mogo know in some sense that the group could be defended, yet fail to actually play the necessary move(s)? I wonder if enough information is available in the playouts to determine that certain moves will dramatically tilt the outcome? Can that information indicate a sense of the urgency of certain moves compared to others? > > -Original Message- > > From: [EMAIL PROTECTED] > [mailto:computer-go- > > [EMAIL PROTECTED] On Behalf Of Matthew > Woodcraft > > Sent: Sunday, March 09, 2008 11:49 AM > > To: computer-go > > Subject: [computer-go] Life and Death > > > > I've included two 13x13 positions below. In both > positions it is > > Black's > > move. > > > > The first position is simplified from a real game. > Black has two > > enclosed dead groups, and White has a small but > easy win. > > > > The second position is a modified version of the > first in which the > > dead > > groups are more obviously dead. > > > > If I try MogoRelease3 playing as Black on position > 2, it shows a 20% > > score and resigns either immediately or after a > couple of moves. > > > > If I try it on position 1, it shows a score of > 70%+ for Black, and > > continues to play until White takes steps to > remove the dead groups > > from > > the board. I've tested with up to 2^24 playouts. > > > > I have tried increasing --collectorLimitTreeSize > and --limitTreeSize > > (like bigMogo in the scalability study), but I > can't set them much > > higher than the default on this machine without > running out of memory. > > > > I'd be interested to see if someone with a bigger > computer can find out > > what resources it needs to judge this position > well, and to see how > > other engines do. > > > > Position 1 > > > > (;GM[1]FF[4] > > CA[UTF-8] > > SZ[13] > > HA[0] > > KM[0.5] > > > AB[jb:kb][cb:cc][kc][bd:cd][jd:ld][be][he][cf:df][bg][gb:gh] > > > [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][lk][al][ck:cl][ji:jl] > > [dm][im] > > > AW[ia:ja][ib][hc:jc][db:dd][hd:id][ce:de][ie][ke:le][bf][hf:jf] > > > [lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk][hk:ik] > > [dl][il][bm][fl:fm][hm] > > ) > > > > Position 2 > > > > (;GM[1]FF[4] > > CA[UTF-8] > > SZ[13] > > HA[0] > > KM[0.5] > > > AB[jb:mb][cb:cc][kc][bd:cd][jd:md][be][he][cf:df][bg][gb:gh] > > > [ig:ih][jh:kh][eg:ei][li][aj:bj][hi:hj][bk:ck][lk][al][cl] > > [ji:jl][im] > > > AW[ia:la][ib][hc:jc][mc][db:dd][hd:id][ce:de][ie][ke:le][bf] > > > [hf:jf][lf][jg:kg][mg][lh][ai:di][gi][mi][cj][ej:gj][ij][dk:fk] > > [hk:ik][dl][fl][il][bm:cm][em:fm][hm] > > ) > > > > -M- > > ___ > > 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/ > Terry McIntyre <[EMAIL PROTECTED]> Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
I've been thinking a bit about the collection of patterns from games, whether of professionals or of programs. It is possible to get some remarkably high correlation between the moves played by pros and a predictor - yet still not have a good program. Why? One possible answer is that many moves are considered but never played; this information is not captured by looking at game records alone. Ordinarily, both players analyze parts of the game - life-and-death situations, for example - and know exactly what outcome to expect. For instance, "the L group is dead" - therefore, one would not create such a provably dead shape. The game record will show the results of decisions made by pros, but not the process of rejecting bad shapes. A tree search based only on game records is unlikely to have enough information to weed out situations which are almost right - "just a little bit dead." Suppose a group can be defended - four liberties in a row, for example. If the opponent plays inside those four liberties, you play to divide the area into two eyes - unless the situation is such that the group has a second eye elsewhere. Game records won't show such frivolous plays, but it is essential to know how to respond to programs which do make such plays. It might be worthwhile for tree search to include patterns which have been generated by life-and-death solvers, determining the status of groups using moves which seldom appear in game records, but which are essential to gather tactical information about the status of groups, used to make top-level strategic decisions. To summarize, the tree search needs to know about patterns which are unlikely to ever be expressed in the game record itself. Terry McIntyre <[EMAIL PROTECTED]> Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
On Thu, Mar 27, 2008 at 12:14:06PM -0700, terry mcintyre wrote: > Suppose a group can be defended - four liberties in a > row, for example. If the opponent plays inside those > four liberties, you play to divide the area into two > eyes - unless the situation is such that the group has > a second eye elsewhere. Game records won't show such > frivolous plays, but it is essential to know how to > respond to programs which do make such plays. Such plays that "almost work" are often played as ko threats. I'm not sure if you get enough samples of these patterns though; and the opponent might tenuki from the play often to connect the ko, I'm not sure if that helps you either. I think this is one reason why people seem to often include some sample of lower-level games during pattern learning. -- Petr "Pasky" Baudis Whatever you can do, or dream you can, begin it. Boldness has genius, power, and magic in it.-- J. W. von Goethe ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Life and Death
David Fotland wrote: > I just looked at this position and it looks like a win for black in the > first position. Many Faces evaluates it as a win for black, and plays c1 to > save the lower left black group with almost no thinking time. > Mogo is correct because the lower left black group is not dead. Doesn't B3 kill in response to C1? -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
terry mcintyre wrote: > I've been thinking a bit about the collection of > patterns from games, whether of professionals or of > programs. > > It is possible to get some remarkably high correlation > between the moves played by pros and a predictor - yet > still not have a good program. Why? > In my opinion it's because playing go is more about the quality of your weakest moves, it's not the average quality of the moves. You pretty much have to play every move at a given level to actually be playing at that level. Of course that's a simplification but gets the point across. Some moves can be found by relatively weak players and the difference between good and great players is in a small percentage of the moves. > One possible answer is that many moves are considered > but never played; this information is not captured by > looking at game records alone. Ordinarily, both > players analyze parts of the game - life-and-death > situations, for example - and know exactly what > outcome to expect. For instance, "the L group is dead" > - therefore, one would not create such a provably dead > shape. > > The game record will show the results of decisions > made by pros, but not the process of rejecting bad > shapes. > > A tree search based only on game records is unlikely > to have enough information to weed out situations > which are almost right - "just a little bit dead." > > Suppose a group can be defended - four liberties in a > row, for example. If the opponent plays inside those > four liberties, you play to divide the area into two > eyes - unless the situation is such that the group has > a second eye elsewhere. Game records won't show such > frivolous plays, but it is essential to know how to > respond to programs which do make such plays. > > It might be worthwhile for tree search to include > patterns which have been generated by life-and-death > solvers, determining the status of groups using moves > which seldom appear in game records, but which are > essential to gather tactical information about the > status of groups, used to make top-level strategic > decisions. > > To summarize, the tree search needs to know about > patterns which are unlikely to ever be expressed in > the game record itself. > > I remember we did talk about this is a group. We came to the conclusion that relevant patterns and positions rarely or never occur on the actual playing board, but are just understood.In a trivial way I discovered this when I was looking for king and pawn endings in a huge grandmaster database. I found very few. And yet these are pretty much fundamental to understanding the game of chess and even influence the openings you play and the goals of the game.It turns out that Grandmasters usually know the outcome of any king and pawn ending that is threatened over the board, and so they basically work around them. And yet they are of fundamental importance in the outcome. In some of my pattern learning experiments, I discovered that only a very small subset of possible patterns occur on the real board, and yet for a game tree searcher it would be pretty important to understand those patterns that are "constantly avoided" in order to understand why they are being avoided. That's why I believe that patterns culled from games are pretty much useless.That probably extends to most learning based on observing games. Nevertheless, I got a pretty good improvement using patterns that Lazarus "never" plays as a form of selectivity in Lazarus.So that is evidence that refutes my idea to a certain extent. I figured if Lazarus would never (or almost never given many opportunities) play to create a certain pattern, it was reasonable evidence that it is not a good move. - Don > > Terry McIntyre <[EMAIL PROTECTED]> > > “Wherever is found what is called a paternal government, there is found state > education. It has been discovered that the best way to insure implicit > obedience is to commence tyranny in the nursery.” > > Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] > > > > > Be a better friend, newshound, and > know-it-all with Yahoo! Mobile. Try it now. > http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ > ___ > 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] State of the art of pattern matching
Actually, a better way to put this: King and Pawn positions are generally understand so well by Grandmasters that they know what the outcome of the game will be once it appears on the board. Therefore, at least 1 player is actively trying to avoid this ending, because the game is essentially over once it appears! And yet you can never be a good chess player without an intimate understanding of this ending which rarely occurs! So how could we expect a machine learning algorithm to "learn" this ending by showing it hundreds of thousands of example games? - Don > It turns out that > Grandmasters usually know the outcome of any king and pawn ending that > is threatened over the board, and so they basically work around them. > And yet they are of fundamental importance in the outcome. > > In some of my pattern learning experiments, I discovered that only a > very small subset of possible patterns occur on the real board, and yet > for a game tree searcher it would be pretty important to understand > those patterns that are "constantly avoided" in order to understand why > they are being avoided. > > That's why I believe that patterns culled from games are pretty much > useless.That probably extends to most learning based on observing > games. > > Nevertheless, I got a pretty good improvement using patterns that > Lazarus "never" plays as a form of selectivity in Lazarus.So that is > evidence that refutes my idea to a certain extent. I figured if > Lazarus would never (or almost never given many opportunities) play to > create a certain pattern, it was reasonable evidence that it is not a > good move. > > > - Don > > > > >> Terry McIntyre <[EMAIL PROTECTED]> >> >> “Wherever is found what is called a paternal government, there is found >> state education. It has been discovered that the best way to insure implicit >> obedience is to commence tyranny in the nursery.” >> >> Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] >> >> >> >> >> Be a better friend, newshound, and >> know-it-all with Yahoo! Mobile. Try it now. >> http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ >> ___ >> 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] State of the art of pattern matching
--- Don Dailey <[EMAIL PROTECTED]> wrote: > terry mcintyre wrote: > > I've been thinking a bit about the collection of > > patterns from games, whether of professionals or > of > > programs. > > > > It is possible to get some remarkably high > correlation > > between the moves played by pros and a predictor - > yet > > still not have a good program. Why? > > > > In my opinion it's because playing go is more about > the quality of your weakest moves, it's not the > average quality of the moves. You pretty much have > to play every move at a given level to actually be > playing at > that level. Of course that's a simplification but > gets the point across. Some moves can be found by > relatively weak players and the difference between > good and great players is in a small percentage of > the moves. Very true! I have the very good fortune to play against a pro from time to time. ( He gives me 9 stones and I try to minimize my losses after that point. ) Many of my moves look very like those of a a pro player, but I'm still somewhere around 5 kyu on KGS. It's one thing to play the first three moves of the Chinese Opening; it's another to correctly handle the umpty-seven variations which follow - especially variants which would never appear in pro games. I've watched a pro patiently wait for one mistake, after which the game unravels. It's like breaking the weakest link of a chain. We lower-level players usually have many such weaknesses, not obvious when we play against people or programs at a similar level. Terry McIntyre <[EMAIL PROTECTED]> Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Life and Death
Oops, yes you are right. I shouldn't try to look at a position when I'm half asleep. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Matthew Woodcraft > Sent: Thursday, March 27, 2008 12:34 PM > To: computer-go > Subject: Re: [computer-go] Life and Death > > David Fotland wrote: > > I just looked at this position and it looks like a win for black in > the > > first position. Many Faces evaluates it as a win for black, and > plays c1 to > > save the lower left black group with almost no thinking time. > > > Mogo is correct because the lower left black group is not dead. > > Doesn't B3 kill in response to C1? > > -M- > ___ > 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] Life and Death
> > David Fotland wrote: > > > I just looked at this position and it looks like > a win for black in the > > > first position. Many Faces evaluates it as a > win for black, and plays c1 to > > > save the lower left black group with almost no > thinking time. > > > > > Mogo is correct because the lower left black > group is not dead. Somebody replied: > > Doesn't B3 kill in response to C1? --- David Fotland <[EMAIL PROTECTED]> wrote: > Oops, yes you are right. I shouldn't try to look at > a position when I'm half asleep. So we are back to the original theory: Mogo incorrectly believed that the position was 70% in favor of a black win, until white made the situation more blatantly obvious. Three questions: a) does the new version of Mogo, with the nakade improvements, handle this situation any better? b) how do other programs fare? c) what strategies would provide a general improvement? Terry McIntyre <[EMAIL PROTECTED]> Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Ing Challenge
The Ing prize stopped when Mr Ing died. He was very interested in computer go. His foundation still funds many go tournaments, but none for computers. The current computer go tournaments I know of are: European go congress (Late July) US go congress (August, small prize this year) Gifu Challenge in Japan (usually September or October, usually moderate prize) - http://www.computer-go.jp/gifu2005/English/outline/index.html Computer Olympiad (Beijing this October, usually no prize, pay to enter) UEC Cup, Japan, first one in 2007. I don't know much about it. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Petr Baudis > Sent: Thursday, March 27, 2008 6:56 AM > To: computer-go > Subject: Re: [computer-go] Ing Challenge > > On Wed, Mar 26, 2008 at 08:50:28PM -0700, David Fotland wrote: > > > You are right. > > > > Well, I did compete for this prize about 15 times, so I hope so :) > > Are there any current prized computer tournaments or does anyone know > about Ing foundation or anyone else planning to resume the challenge? > What was the reason that it got interrupted, lack of fast enough > progress or simple reallocation of funds within the foundation? > > -- > Petr "Pasky" Baudis > Whatever you can do, or dream you can, begin it. > Boldness has genius, power, and magic in it. -- J. W. von Goethe > ___ > 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] Ing Challenge
David Fotland: <[EMAIL PROTECTED]>: >The Ing prize stopped when Mr Ing died. He was very interested in computer >go. His foundation still funds many go tournaments, but none for computers. > >The current computer go tournaments I know of are: > >European go congress (Late July) >US go congress (August, small prize this year) >Gifu Challenge in Japan (usually September or October, usually moderate >prize) - http://www.computer-go.jp/gifu2005/English/outline/index.html >Computer Olympiad (Beijing this October, usually no prize, pay to enter) >UEC Cup, Japan, first one in 2007. I don't know much about it. 2nd UEC Cup is planned at December 6 and 7, 2008. I guess no prize. -Hideki >David > > >> -Original Message- >> From: [EMAIL PROTECTED] [mailto:computer-go- >> [EMAIL PROTECTED] On Behalf Of Petr Baudis >> Sent: Thursday, March 27, 2008 6:56 AM >> To: computer-go >> Subject: Re: [computer-go] Ing Challenge >> >> On Wed, Mar 26, 2008 at 08:50:28PM -0700, David Fotland wrote: >> > > You are right. >> > >> > Well, I did compete for this prize about 15 times, so I hope so :) >> >> Are there any current prized computer tournaments or does anyone know >> about Ing foundation or anyone else planning to resume the challenge? >> What was the reason that it got interrupted, lack of fast enough >> progress or simple reallocation of funds within the foundation? >> >> -- >> Petr "Pasky" Baudis >> Whatever you can do, or dream you can, begin it. >> Boldness has genius, power, and magic in it. -- J. W. von Goethe >> ___ >> 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] Money for computer Go (was: Ing Challenge)
On 27, Mar 2008, at 3:39 PM, David Fotland wrote: US go congress (August, small prize this year) Since I announced that HSRF will supply $1,000 total of prize money for computer Go at the US Congress this year, another person contacted me and has agreed to add a minimum of $250. The offer is also to match other contributions, with that person offering a maximum of $1,000. I need to get back to them to finalize the details of their offer and the matching conditions, but I have been busy trying to move. More details, and perhaps more money, soon. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
On undefined, Don Dailey <[EMAIL PROTECTED]> wrote: > > In some of my pattern learning experiments, I discovered that only a > very small subset of possible patterns occur on the real board, and yet > for a game tree searcher it would be pretty important to understand > those patterns that are "constantly avoided" in order to understand why > they are being avoided. > > That's why I believe that patterns culled from games are pretty much > useless.That probably extends to most learning based on observing > games. I agree wholeheartedly with your observation, but not with your conclusion. It is undoubtedly true that dan level players foresee, understand and avoid many patterns, but it is also true that many players develop those abilities largely through playing many games of go, as well as studying books and problems. Given that there are collections of tens of thousands of games played by kyu level players as they improve to dan level; given that there are collections of thousands of life and death problems studied by those players to the same end; I see no rational explanation why the lessons leant by humans as they improve (or equivalent lessons expressed computationally) can't be inferred. cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
