At a birds-eye layman's level, the chess move tree has on average 20 legal moves; the go tree has over 100; it is much bushier. Chess offers a fairly simple evaluation: if you are down on material, you are either dead lost, or you sacrificed material to obtain a mate-in-n moves.
With Go, evaluation is not so simple; you need to be able to determine the life-and-death status of numerous groups, the value of ko threats, and other fairly subtle factors. Hence, the approach of MCTS, which essentially samples a bunch of fairly-random continuations. The original poster was more interested in political/economic implications; he would find The Protracted Game of interest, perhaps. Terry McIntyre <[email protected]> Linux Systems Administration Taking time to do it right saves having to do it twice. ----- Original Message ---- > From: Scott Christensen <[email protected]> > To: [email protected] > Sent: Thu, June 3, 2010 6:25:26 AM > Subject: Re: [Computer-go] Chess vs Go // AI vs IA > > I agree that the human brain is better wired to play Go than Chess. Humans > can remember hundreds of thousands of visual images and their significance, > but we only have a working memory of 6-7 steps in a temporal sequence. > There are fewer possible moves in chess and its easier to assign point values > to positions, so a computer can make moves based on expected consequences > beyond 6-7 moves in the future. In Go there are too many possible future > combinations for even computer systems to deal with. Humans rely on pattern > recognition for effective game play. Computers are extremely poor at > pattern recognition of salient features and almost totally lacking > in intermediate goal setting which are extremely important to human > play. Computers are not really 'thinking' but are merely sorting data > to come up with a 'simulation' of a proper game move. There are > many board scenarios that can be presented to game systems that > demonstrate they have absolutely no concept of the games. The newly > popular technique of Monte Carlo Tree Search does go a step closer to a human > thought process of predicting the consequences of moves to a distant future > outcome rather than just calculating point values a few moves ahead which is > perhaps why this technique has had such fantastic success > lately. On Thu, Jun 3, 2010 at 5:45 PM, < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > wrote: > Send Computer-go mailing list submissions to > > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > > > To subscribe or unsubscribe via the World Wide Web, visit > > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > or, via email, > send a message with subject or body 'help' to > > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > > > You can reach the person managing the list at > > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > > > When replying, please edit your Subject line so it is more specific > than > "Re: Contents of Computer-go digest..." > > > Today's > Topics: > > 1. Re: Chess vs Go // AI vs IA (Michael > Williams) > 2. Re: Chess vs Go // AI vs IA (Mark Boon) > 3. Re: > Chess vs Go // AI vs IA (Don Dailey) > 4. Re: Chess vs Go // AI vs IA > (David Fotland) > 5. Re: Dynamic komi revisited (Petr Baudis) > > 6. Re: Dynamic komi revisited (Petr Baudis) > 7. Re: Dynamic komi > revisited (Darren Cook) > 8. Re: Dynamic komi revisited (Petr > Baudis) > 9. Re: Dynamic komi revisited (Petr > Baudis) > > > > ---------------------------------------------------------------------- > > > Message: 1 > Date: Wed, 02 Jun 2010 18:38:12 -0400 > From: Michael > Williams < > href="mailto:[email protected]";>[email protected]> > > To: > href="mailto:[email protected]";>[email protected] > > Subject: Re: [Computer-go] Chess vs Go // AI vs IA > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=windows-1252; format=flowed > > > One thing that never seems to get mentioned in this periodic debate is the > relationship, within the brain, of sight, patterns and memory. A go board > looks > very > similar 10 or even 20 moves in the future. The same is not true > for chess. It looks vastly different, and in many cases would be over by > that > time. I > postulate that humans are able to read more situations more > deeply in Go than Chess because of the fact that much of the board is > unchanged, > visually and > therefor easier to remember. In chess, things move around > and become harder to remember. Computers have excellent memories and don't > care > about how things > "look". This gives them an advantage over humans in > games that are visually "fast". See also: reversi/othello. I'm sure there > are > counter-examples. It's > just something else to > consider. > > > > > > ------------------------------ > > Message: 2 > Date: Wed, 2 > Jun 2010 13:01:26 -1000 > From: Mark Boon < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > To: > href="mailto:[email protected]";>[email protected] > > Subject: Re: [Computer-go] Chess vs Go // AI vs IA > Message-ID: > > < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=ISO-8859-1 > > On Wed, Jun 2, 2010 > at 12:37 PM, Don Dailey < > href="mailto:[email protected]";>[email protected]> > wrote: >> I don't require anything to be that precise, ? but I want > statements to have >> a bit of substance. ? Phrases such as, "he is > good" depends on a frame of >> reference. >> The best players > in the world are not a good frame of reference either, >> ?they > certainly do not represent humanity in general. ? ?And how good > humans >> play is based on their culture and education too. >> > So when we compare programs to humans, we usually mean some very > well >> trained human, ?someone in the 95th percentile or something > like that, ?not >> really a representative of human-kind. ? ?So which > measuring stick do you >> consider to be "accurate" for comparing how > computers (not humans) play >> completely different games? >> > If you compare the average player, we have probably already succeeded - > the >> best computer go programs are much better than the average go > player. >> ?So now all we have to do is make progress and move up the > ranks, ?just like >> humans have to do - and stop calling it hard. ? > ?That is a given and is why >> we do it. ? ?I do computer chess for the > same reason, ?it is very hard. > > I feel you are beating around the > bush. Go is harder to program to > match a human expert than chess. Yes, > no or you don't want to answer. > > We can probably define 'hard' in > terms of time spent by humans trying, > but I hope we don't need to get > that petty. > > I agree with Michael that the static nature of the > go-board probably > helps humans to make things easier. But it's at least > interesting that > that feature has not been equally exploited > successfully by computers > or their programmers. > > > Mark > > > ------------------------------ > > > Message: 3 > Date: Wed, 2 Jun 2010 21:34:04 -0400 > From: Don Dailey > < > href="mailto:[email protected]";>[email protected]> > To: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > > Subject: Re: [Computer-go] Chess vs Go // AI vs IA > Message-ID: > > < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset="iso-8859-1" > > I agree with you. > Our brains are wired to play go better than chess. > > > Don > > > On Wed, Jun 2, 2010 at 6:38 PM, Michael Williams > < > > href="mailto:[email protected]";>[email protected]> > wrote: > >> One thing that never seems to get mentioned in this > periodic debate is the >> relationship, within the brain, of sight, > patterns and memory. A go board >> looks very similar 10 or even 20 > moves in the future. The same is not true >> for chess. It looks > vastly different, and in many cases would be over by >> that time. I > postulate that humans are able to read more situations more >> deeply > in Go than Chess because of the fact that much of the board is >> > unchanged, visually and therefor easier to remember. In chess, things > move >> around and become harder to remember. Computers have excellent > memories and >> don't care about how things "look". This gives them an > advantage over >> humans in games that are visually "fast". See also: > reversi/othello. I'm >> sure there are counter-examples. It's just > something else to consider. >> >> >> >> > _______________________________________________ >> Computer-go mailing > list >> > href="mailto:[email protected]";>[email protected] >> > href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go"; target=_blank > >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > -------------- next part -------------- > An HTML attachment was > scrubbed... > URL: > <http://dvandva.org/pipermail/computer-go/attachments/20100602/d543756c/attachment-0001.html> > > > ------------------------------ > > Message: 4 > Date: Wed, 2 > Jun 2010 22:52:45 -0700 > From: "David Fotland" < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > To: < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Chess vs Go // AI vs IA > Message-ID: > <0a6c01cb02e0$fdae9cc0$f90bd6...@com> > Content-Type: text/plain; > charset="us-ascii" > > I spent about six months writing such a > program, about 8 years ago, to learn > alpha beta for use in my go > program, and I doubt it's very strong. It > crushes me, but I'm really > weak, maybe 1500. If someone wants to try some > games against it I can > make the executable available. It uses iterative > deepening, partial ply > extensions, killer heuristic, piece-square tables, > very simple pawn > structure and king safety terms, etc. > > > David > >> >> Out of interest, can you put a number on > that? How strong would a >> program be, running on a modern fast > desktop and using only alpha-beta >> and a static evaluation function > based on, say, piece-square tables plus >> "a little consideration to > position"? >> >> -M- >> > _______________________________________________ >> Computer-go mailing > list >> > href="mailto:[email protected]";>[email protected] >> > href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go"; target=_blank > >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > > > > ------------------------------ > > Message: 5 > Date: Thu, 3 > Jun 2010 11:23:58 +0200 > From: Petr Baudis < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > Cc: > Computer Go < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Dynamic komi revisited > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=us-ascii > > On Wed, Jun 02, 2010 > at 03:27:11PM -0700, Peter Drake wrote: >> Okay, next question: on the > previous thread ("Dynamic komi's >> basics"), there were several > comments to the effect of, "I found an >> improvement from doing this > and will describe it in an upcoming >> paper". Have any of these papers > yet been produced or published? > > I'm still in the process of > writing one up, but I'm not sure yet > if I will seek publishing it in any > more formal venue, since the overall > results are rather disappointing. I > still need to write it up for my > thesis anyway, though - I expect to > have a draft ready in few weeks. > > In handicap games, the > improvement is significant, but in even games, > the best method I have > found gives only tiny statistically significant > improvement - about 54% > winrate in self-play after very intensive > parameter tuning, with the > effect being smaller in fast games and > somewhat more pronounced with > large simulation counts. I was not able > to reproduce Hiroshi Yamashi's > results with his (different) algorithm > either in my > program. > > -- > Petr "Pasky" > Baudis > The true meaning of life is to plant a tree under whose > shade > you will never sit. > > > > ------------------------------ > > Message: 6 > Date: Thu, 3 > Jun 2010 11:23:58 +0200 > From: Petr Baudis < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > Cc: > Computer Go < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Dynamic komi revisited > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=us-ascii > > On Wed, Jun 02, 2010 > at 03:27:11PM -0700, Peter Drake wrote: >> Okay, next question: on the > previous thread ("Dynamic komi's >> basics"), there were several > comments to the effect of, "I found an >> improvement from doing this > and will describe it in an upcoming >> paper". Have any of these papers > yet been produced or published? > > I'm still in the process of > writing one up, but I'm not sure yet > if I will seek publishing it in any > more formal venue, since the overall > results are rather disappointing. I > still need to write it up for my > thesis anyway, though - I expect to > have a draft ready in few weeks. > > In handicap games, the > improvement is significant, but in even games, > the best method I have > found gives only tiny statistically significant > improvement - about 54% > winrate in self-play after very intensive > parameter tuning, with the > effect being smaller in fast games and > somewhat more pronounced with > large simulation counts. I was not able > to reproduce Hiroshi Yamashi's > results with his (different) algorithm > either in my > program. > > -- > Petr "Pasky" > Baudis > The true meaning of life is to plant a tree under whose > shade > you will never sit. > > > > ------------------------------ > > Message: 7 > Date: Thu, 03 > Jun 2010 18:36:38 +0900 > From: Darren Cook < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: Computer Go > < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Dynamic komi revisited > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=ISO-8859-1 > >>... results are > rather disappointing. ... >> >> In handicap games, the > improvement is significant, but in even games, >> the best method I > have found gives only tiny statistically significant >> improvement - > about 54% winrate in self-play... > > As the idea (at least, as I > understood it) is for when the player > strength is unbalanced (i.e. > handicap games, or playing an opponent who > is stronger in the opening > but weaker in the endgame (or vice versa)) > that you'd get 54% from > self-play in even games is intriguing. I look > forward to reading your > draft paper. > > Darren > > > > -- > > Darren Cook, Software Researcher/Developer > > > http://dcook.org/gobet/ (Shodan Go Bet - who will win?) > > http://dcook.org/work/ (About me and my work) > > http://dcook.org/blogs.html (My blogs and articles) > > > > ------------------------------ > > Message: 8 > Date: Thu, 3 > Jun 2010 11:45:45 +0200 > From: Petr Baudis < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > Cc: > Computer Go < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Dynamic komi revisited > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=us-ascii > > On Thu, Jun 03, 2010 > at 06:36:38PM +0900, Darren Cook wrote: >> >... results are rather > disappointing. ... >> > >> > In handicap games, the > improvement is significant, but in even games, >> > the best method > I have found gives only tiny statistically significant >> > > improvement - about 54% winrate in self-play... >> >> As the > idea (at least, as I understood it) is for when the player >> strength > is unbalanced (i.e. handicap games, or playing an opponent who >> is > stronger in the opening but weaker in the endgame (or vice versa)) >> > that you'd get 54% from self-play in even games is intriguing. I > look >> forward to reading your draft paper. > > My idea is > rather to better deal with "extreme situations" - when most > differences > between various moves in a situation are so small that they > are lost in > the noise (precise definition of when we consider the > situation extreme > can vary, I explore multiple approaches). Then the > opening in handicap > game would be a special case of this, but also any > other situation in > the game where the program wins/loses by a lot. > > -- > > Petr "Pasky" Baudis > The true meaning of life is > to plant a tree under whose shade > you will never > sit. > > > ------------------------------ > > > Message: 9 > Date: Thu, 3 Jun 2010 11:45:45 +0200 > From: Petr > Baudis < > href="mailto:[email protected]";>[email protected]> > To: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > Cc: > Computer Go < > href="mailto:[email protected]";>[email protected]> > > Subject: Re: [Computer-go] Dynamic komi revisited > Message-ID: < > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > > Content-Type: text/plain; charset=us-ascii > > On Thu, Jun 03, 2010 > at 06:36:38PM +0900, Darren Cook wrote: >> >... results are rather > disappointing. ... >> > >> > In handicap games, the > improvement is significant, but in even games, >> > the best method > I have found gives only tiny statistically significant >> > > improvement - about 54% winrate in self-play... >> >> As the > idea (at least, as I understood it) is for when the player >> strength > is unbalanced (i.e. handicap games, or playing an opponent who >> is > stronger in the opening but weaker in the endgame (or vice versa)) >> > that you'd get 54% from self-play in even games is intriguing. I > look >> forward to reading your draft paper. > > My idea is > rather to better deal with "extreme situations" - when most > differences > between various moves in a situation are so small that they > are lost in > the noise (precise definition of when we consider the > situation extreme > can vary, I explore multiple approaches). Then the > opening in handicap > game would be a special case of this, but also any > other situation in > the game where the program wins/loses by a lot. > > -- > > Petr "Pasky" Baudis > The true meaning of life is > to plant a tree under whose shade > you will never > sit. > > > ------------------------------ > > > _______________________________________________ > Computer-go mailing > list > > href="mailto:[email protected]";>[email protected] > > href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go"; target=_blank > >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > End > of Computer-go Digest, Vol 5, Issue 7 > > ***************************************** > _______________________________________________ Computer-go > mailing list > href="mailto:[email protected]";>[email protected] > href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go"; target=_blank > >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
