Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Thanks Chrilly. For anyone else interested, it is here: http://www.xilinx.com/publications/xcellonline/xcell_53/xc_pdf/xc_hydra53.pdf But, as you say, the the search tree as an adaptable error filteridea is only mentioned in passing. I guess I'll just have to wait for Ulf Lorenz to translate his Dissertation into English :-). Or you learn German. As I side effect you can than also read Goethe and my chess columns. The chess columns are interesting, but then you have to learn also the Austrian version of German). Ulf has used this model for a project to improve the robustness of airplane-schedules. ... Interesting. It is always motivating to hear about game theory getting applied to the real world. (And having been stuck in Amsterdam airport for 5 hours because KLM forgot to schedule a pilot for my flight, I think the airline industry needs all the help it can get!) The problem is, that there is no economic incentive. A robust solution is usually somewhat worse than the non-robust one. I assume that you did not get any compensation for the 5 hours in Schiphol. Such methods will only become important, if KLM has to pay you. 50 Euro/h. The scheduling was done before by humans. These schedules have been robust. Simply for the fact that it is too complicated for a human to make an optimal schedule. But also because humans have some feeling what can go wrong and they anticipate the most likely delays. To a certain degree computer-optimization was introduced to make the schedules less robust. But you have also choosen a very poor airline. KLM was fine a few years agos, but then they started to save money and now its notorious for being late, loosing baggage. But as the other lines have gone the same way, it makes no big difference. There a few good lines left. I my experience the best one is Emirates from Dubai. You should give it a try the next time. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Noise reduction in alpha-beta search
Ingo Althoeffer has published some time ago a theoretical article about this idea. He called it telescope evaluation. According his theorectical findings is the error propagation not better than the usual approach. K.Chen proposed a similar approach. Use the mean of the last and second-last evaluation. I tried this. It makes the search more stable. With the normal search we have strong odd/even effects. At odd depths Suzie evaluates the position (considerable) higher than at even depths. At odd depths Suzie has 1 move more in the variation than the opponent. This odd/even effect disappears with the K.Chen mean. Also the search depth increases, because move ordering is more stable. But the result in the autoplay-matches was worse. One gets effects like the following: 1 Ply before the horizon the opponent makes a threat. The evaluation goes down considerable, but there is a defense move and at the horizon nothing has happened.. But according the mean the programm is still in some trouble. Or if one reverses the role, Suzie would like to play the threat-move. This scheme increases therefore even the potential of the programm to cheat. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Monday, April 09, 2007 4:48 PM Subject: [computer-go] Noise reduction in alpha-beta search I think following is a way to reduce the noise in alpha-beta search. Instead of using the evaluation values, use the cummulative evaluation values. That is the sum of the evaluation values of each node of the playing path under examination. Daniel Liu -- AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. -- ___ 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] Simplified MC evaluator ?explained?
Weston Markham wrote:
1. Uniform playouts, as used in practice, are not really uniform over
all legal go moves. Generally, pass moves are excluded until
necessary, and moves that fill eyelike points are excluded. So, I
assume that when you use the word legal, you mean admissible within
this sort of playout.
That shouldn't make a difference. If you count the pass as a legal move
you should also count it as a legal moves in the subpaths.
You would have W (subpaths without pass) and W' (subpaths with pass).
Since it is only one of the 255 legal moves (counting the expected value
of # legal moves as 19^2 - 212/2 where 212 = length of a pro game) it
should not be very important even if miscounted.
2. That variance depends on the length of the playout. It is
difficult for me to make sense of this statement, simply because not
all playouts from a given position have the same length.
Of course, but it is reasonable to expect 9x9 playout around 120, 19x19
around 400, etc. That has, at least, two consequences:
1. UCT is stronger for global search studying move 150 than move 5.
2. UCT can also be used for local search on 50-80 empty cells, something
astronomically above what can be done with alfa-beta (assuming we want final
evaluation, not evaluating nodes at some intermediate state.) Of course,
UCT does not talk territory so adding the local subgames is far from
trivial.
The variance of the stochastic process is not to be mixed up
with the distribution of the error of a repeated Bernoulli experiment!
Perhaps I have mixed them up. Can you explain more clearly or precisely
what the variance of the stochastic process is?
Repeated Bernoulli experiments are studied as a stochastic process and,
in our case, _the experiment is a stochastic process itself_.
We have a nested process: A process whose steps are stochastic processes.
Therefore we have the variance of the Bernoulli process which is in the
binomial Bi(n, p) but that p is the result of a stochastic process whose
variance biases p towards 1/2.
I don't don't have a particular mathematical model for that process and
model
it as a noise. No matter how you distribute it, as long as the expected
value is zero
it and has the same consequences. This may be clearer:
Count each move in the playout as adding a random territory difference
in {-3, -2, -1, 0, 1, 2, 3} to the actual territorial value with any
distribution whose expected value is 0. The probability of the result
being 0 (a win) starting with a good move (initial value = +5)
after 10 moves is significantly bigger than starting with a bad move
(initial value = -3). But after a million moves the probability of
a win is the same for both = 1/2. Because the variance of the
experiment is somewhere in k·n the standard deviation is proportional
to the sqrt of n = 1000. With a std deviation around 1000 the initial
values 5 or -3 are way too small to make any difference.
Does this game violate the condition that the number of legal moves
for each side is balanced?
I mean my argument in the big numbers. Of course, if you take it down to
the detail you can find counterexamples. But these counterexamples
should be balanced for black and white. In fact, that's what I pretended
to say if everything is the same for black and white take the same
in an informal sense, there is no reason one of the sides should be
favored and p estimates W. What is more important is that it estimates
W biased towards 1/2 because the playout is a stochastic process.
Even if we can compute W exactly, do we have any reason to think
that its value is a good estimate of the minimax value of the game?
It is *not* a good estimate. I am not trying to advocate in favor of MC
as a panacea. In the beginning I was among the critics and have done
an effort to understand it better. Slowly I am becoming convinced
of the possibilities specially in combination with other methods
and now I have written a UCT engine, mainly for analysis.
W fails to represent the minimax value of the game at least in two
common situations: self-atari moves that would be a good idea if
the opponent was kind enough as to forgive the capture and ladders.
But _that is_ what uniformly random MC evaluates, not my fault ;-)
Jacques.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
Don Dailey wrote: On Sun, 2007-04-08 at 11:24 +0200, Heikki Levanto wrote: In fact this is how beginners think about the game. It doesn't seem to me like a good learning aid to try to get the computers to emulate the losing strategy weaker players use. Weaker players can not estimate the score until very late in the game. Not with enough precision, anyway. Thus, most of the time they have no idea if they are winning or loosing by 0.5 points. But the whole idea is to take you PAST this level of understanding. About 9 years ago, Dave Dyer wrote something in a private message to me that has stuck with me. It has affected my thinking about the game ever since. He wrote that games between strong players are played on the knife-edge between life and death. In fact it was this idea and ideal that inspired the name of my may-never-come-to-be go program KatanaGo, currently nothing more than a pile of half developed ideas and experiments done in spare time over the years. If I ever have the proper time to devote to computer-go, perhaps it will play and in my dreams even play at this delicate balance point. ;-) To defend Heikki's point though, for a computer program to be a good teacher it should be aware of the full game status which the UCT/MC methods make difficult. In teaching mode the program could offer clues and depart knowledge of this type about what is important and not important in the game, LD status, good and bad moves, and the reasons for these. Of course this is an ideal way beyond just playing well. From this perspective, neither a program which plays randomly because the game is already won nor a program which aggressively exploits a won position and destroys its opponent is the ideal teaching opponent. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CALL FOR PAPERS: COMPUTER GAMES WORKSHOP 2007
CALL FOR PAPERS: COMPUTER GAMES WORKSHOP 2007 Amsterdam, The Netherlands 15-17 June 2007 H.J. van den Herik and J.W.H.M. Uiterwijk Maastricht, The Netherlands IBM, SARA (Academic Computer Centre Amsterdam) and NCF (Foundation of National Computing Facilities) are enabling the organization of the Computer Games Workshop 2007 (CGW2007) (15-17 June 2007), the 15th World Computer-Chess Championship (WCCC) (11-18 June) and the 12th Computer Olympiad (CO) (11-18 June) to be held in Amsterdam, The Netherlands. Location: The Turing hall, Science Park Amsterdam, Kruislaan 419, 1098 VA Amsterdam. For information on the 15th WCCC and the 12th CO, see elsewhere. Below we focus on the CGW2007. The organization of the events is to highlight the initiation of the new NWO supercomputer, called HUYGENS. The official date of the start of the computer's operation is June 13. The mayor of Amsterdam Dr. Job Cohen will attend the starting meeting. The workshop commences on June 15 at 8.30 h and will take place on three consecutive days, each day from 8.30 h till 12.30 h. The workshop aims in the first place at providing an international forum for computer-games researchers presenting new results on ongoing work. Hence, we invite contributors to submit papers on all aspects of research related to computers and games. Relevant topics include, but are not limited to: (1) the current state of game-playing programs, (2) new theoretical developments in game-related research, (3) general scientific contributions produced by the study of games, and (4) (adaptive) game AI. Moreover, researchers of topics such as (5) social aspects of computer games, (6) cognitive research of how humans play games, and (7) issues related to networked games are invited to submit their contribution. Important Dates Paper Submission May 15, 2007 Acceptance Notification May 21, 2007 Camera-ready Papers June 1, 2007 Paper Submission Requirements Papers of 8 to 10 pages are preferred. The maximum length is 12 pages. The preferred format for submission is PDF, but Postscript or Word is also acceptable. The paper must be written in the English language. We prefer the Springer Lecture Note Series (LNCS/LNAI) format. Please follow the instructions for authors available at the Springer LNCS/LNAI Web: http://www.springer.de/comp/lncs/authors.html. Refereeing Process Since this announcement is rather late, the usual full refereeing process is impossible to execute. Therefore papers will be refereed in a light way by members of the Programme Committee. In practice, this means that papers are accepted if their topic suits the workshop and their overall quality is acceptable. Accepted papers will be scheduled for presentation during the workshop and will be printed as workshop proceedings. Authors of accepted papers, or their representatives, are expected to present their papers at the workshop. Please submit papers via email to [EMAIL PROTECTED], before May 15, 2007. Notice of acceptance of papers will be sent by May 21, 2007 to the principal author. Camera-ready papers are due by June 1, 2007. The best contributions of the workshop will be published in the ICGA Journal. Moreover, depending on the quality, a submission of material for publication in the LNCS series may be considered. Registration Registration FeeEarly (on or before June 1) Late (after June 1) Participants Euro 50 Euro 70 Students Euro 25 Euro 35 Admission to the workshop and a copy of the workshop proceedings are included in the workshop registration fee. Workshop Proceedings The proceedings will be edited by Professor H.J. van den Herik, dr. J.W.H.M. Uiterwijk, dr. M.H.M. Winands, and M.P.D. Schadd, M.Sc.. Each workshop participant will receive a copy at the start of the workshop. The Programme Committee The relatively short period between the final agreement on the organization and the actual dates of the events has inspired us to work with almost the same programme committee as last year (Turin, 2006, see below), except that three co-chairs are supplied by the scientific staff of our sponsors. Co-chairs: Professor H.J. van den Herik Representative IBM-research to be announced later Dr. A. Osseyran (SARA) Dr. P. Aerts (NCF) For more information on WCCC, CO and CGW 2007: J.W. Hellemons, email: [EMAIL PROTECTED] www.icga.org ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] SGF-Questions
a) If one setups a position. Is there a property for the number of white and black captured stones so far. No. (If you use Chinese scoring, that doesn't matter.) b) There is the property AE. The list of empty points. Is it necessary to setup also the empty points or is it sufficient to setup only the black and white stones with AB and AW? Just use AB and AW. Only use AE when you're actually removing stones. c) if one setup-ups a position and there is no KO-Point. Is it necessary to specifiy a non-existing KO-Point (e.g. as KO[tt] or KO[] ) or has one to setup the KO only if there is a real KO-Point. Only add the KO property if there's a forbidden ko point. Also note that KO is not a standard SGF property, but some programs support it. Anders Kierulf www.smartgo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Noise reduction in alpha-beta search
It can't be. He was probably studying the general game, not Go Ingo Althoefer published his results in the context of chess. Alpha-Beta Search was until recently not a topic in Go (besides its not possible). The score in Go is additive, if the score is territory. But that is not a possible evaluation function. E.g. in the first stages only on small parts of the board is white/black territory defined. The rest is influence/Moyo (or nothing). One needs also some notion of weakness of a group. The All or Nothing (Group is Living or Death) approach does not work. There must be some evaluations/stages in between. If a weak group controls some territory, this territory should also count less... This problem is to be solved by deeper search. Yes. But it is very difficult to find reasonable quiet criterions. One has to stop the search at one point, because otherwise it explodes. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tuesday, April 10, 2007 5:23 PM Subject: Re: [computer-go] Noise reduction in alpha-beta search It can't be. He was probably studying the general game, not Go. The score in Go is additive, if the score is territory. 2-steps approach make some sense, but not in general situation. At each step the pendlum swings to one side is the nature of the game. Nothing wrong with it. One gets the same problem with single step evaluation too. This problem is to be solved by deeper search. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 10 Apr 2007 1:46 AM Subject: Re: [computer-go] Noise reduction in alpha-beta search Ingo Althoeffer has published some time ago a theoretical article about this idea. He called it telescope evaluation. According his theorectical findings is the error propagation not better than the usual approach. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Monday, April 09, 2007 4:48 PM Subject: [computer-go] Noise reduction in alpha-beta search I think following is a way to reduce the noise in alpha-beta search. Instead of using the evaluation values, use the cummulative evaluation values. That is the sum of the evaluation values of each node of the playing path under examination. Daniel Liu AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ 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] The physics of Go playing strength.
According to the report on MoGo (RR-6062), its playout part seems pruning not interesting moves using patterns. -gg Darren Cook: [EMAIL PROTECTED]: With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranteed for heavy playout. As Don pointed out before, the reason it converges to perfect play is because of the UCT part, not because of the playout part. If the playout part prunes some moves, nothing is guaranteed. I believe the point is that UCT never prunes moves. The playouts performed at UCT leaf nodes are just to give an estimate to help UCT decide which part of the tree to explore next. I.e. heavy vs. light playouts are like intelligent vs. random move ordering in alpha-beta. Darren -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] off-topic: Tenured Faculty?
Is there anyone on this list who is a tenured associate or full professor at the college/university level, especially in the United States? If so, please contact me. I have set the Reply To: field accordingly. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Tue, 10 Apr 2007, Hideki Kato wrote: According to the report on MoGo (RR-6062), its playout part seems pruning not interesting moves using patterns. Yes, but the UCT part will (sooner or later) explore EVERY path. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Tue, 10 Apr 2007, Christoph Birk wrote: On Tue, 10 Apr 2007, Hideki Kato wrote: According to the report on MoGo (RR-6062), its playout part seems pruning not interesting moves using patterns. Yes, but the UCT part will (sooner or later) explore EVERY path. But then again, if you had the resources to explore every path MC/UCT would be very inefficient compared to alpha/beta. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] cgos viewer
Just tried to download the latest version. Downloaded, unzipped but didn't work/display. Did I not get it from where I should have?? Thanks... Tris... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos viewer
In message [EMAIL PROTECTED], Don Dailey [EMAIL PROTECTED] writes On Tue, 2007-04-10 at 11:54 -0700, Tris wrote: Just tried to download the latest version. Downloaded, unzipped but didn't work/display. Did I not get it from where I should have?? It's hard to say - I don't know where you got it from. Also, you didn't specify your operating system so I have no idea which one has an issue. Please note there are playing clients for you go program and viewing clients. Which did you try? Did you unzip it first? This arm's-length software support can be a difficult business. My wife once heard me, taking a support call on the telephone, ask have you got a computer?. She told me that such a question was unhelpful and insulting. But as the user's answer had been no, I felt I had saved us both some wasted and confusing questioning. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
-Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 10 Apr 2007 2:43 PM Subject: Re: [computer-go] The physics of Go playing strength. On Tue, 10 Apr 2007, Christoph Birk wrote: On Tue, 10 Apr 2007, Hideki Kato wrote: According to the report on MoGo (RR-6062), its playout part seems pruning not interesting moves using patterns. Yes, but the UCT part will (sooner or later) explore EVERY path. Well, really it could be either way. In the simplest case, UCT builds a tree without skipping any legal nodes. In that case, the playout type doesn't matter and the engine's convergence in the limit is assured. (Of course we'll all be dead by then...) But some implementations do decline to explore some legal nodes in the tree, particularly for larger board sizes. For instance, some versions of Mogo constrained some internal nodes in the tree to those with moves within a local neighborhood of the previous move. IIRC their RR-6062 report touched on this. In the current version of AntIgo, I use patterns learned from the (heavy) playouts to bias the selection of moves in lightly visited internal nodes. And there are a lot of other little tricks that can potentially alter the asymptotic properties of the algorithm. I doubt it matters, because any such trick I can think of, could be massaged into a form where the engine would converge anyway. It all comes down to the terminology we're using being not so precise or universally accepted. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
I doubt it matters, because any such trick I can think of, could be massaged into a form where the engine would converge anyway. It all comes down to the terminology we're using being not so precise or universally accepted. And we can be sure that as the hardware improves, engine writers will do whatever they can to make it perform best on current hardware while still remaining very scalable (even if not provably infinitely scalable). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos viewer
So you got it from the wrong place! Good - we can solve your problem then! Go here: http://cgos.boardspace.net/9x9/index.html and I think you will find a version that works for the new cgos. - Don On Tue, 2007-04-10 at 12:57 -0700, Tris wrote: Got it from: http://www.greencheeks.homelinux.org:8015/~drd/public/ Got the windows version: cgosview-windows.zip Yes, Unzipped first. Earlier version worked fine! Tris At 12:29 PM 4/10/2007, you wrote: On Tue, 2007-04-10 at 11:54 -0700, Tris wrote: Just tried to download the latest version. Downloaded, unzipped but didn't work/display. Did I not get it from where I should have?? It's hard to say - I don't know where you got it from. Also, you didn't specify your operating system so I have no idea which one has an issue. Please note there are playing clients for you go program and viewing clients. Which did you try? Did you unzip it first? - Don Thanks... Tris... ___ 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] cgos viewer
Got it from: http://www.greencheeks.homelinux.org:8015/~drd/public/ Got the windows version: http://www.greencheeks.homelinux.org:8015/%7Edrd/public/cgosview-windows.zipcgosview-windows.zip Yes, Unzipped first. Earlier version worked fine! Tris At 12:29 PM 4/10/2007, you wrote: On Tue, 2007-04-10 at 11:54 -0700, Tris wrote: Just tried to download the latest version. Downloaded, unzipped but didn't work/display. Did I not get it from where I should have?? It's hard to say - I don't know where you got it from. Also, you didn't specify your operating system so I have no idea which one has an issue. Please note there are playing clients for you go program and viewing clients. Which did you try? Did you unzip it first? - Don Thanks... Tris... ___ 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] The dominance of search (Suzie v. GnuGo)
Hello, 2007/4/6, Tom Cooper [EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Here's another way to test this sort of thing that is completely intrinsic to the engine (doesn't require gnugo): Start with and empty board and zero komi. Analyze using UCT until the winning percentage at the root reaches X. Note the number of simulations required (or the amount of time). Repeat for a larger board size. One should probably average N trials at each board size for more reliable numbers. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Here's another way to test this sort of thing that is completely intrinsic to the engine (doesn't require gnugo): Start with and empty board and zero komi. Analyze using UCT until the winning percentage at the root reaches X. Note the number of simulations required (or the amount of time). Repeat for a larger board size. One should probably average N trials at each board size for more reliable numbers. Is that a better measure of playing strength? I don't think so. And if the only advantage is that it does not require gnugo, I don't see the point as gnugo is a marvellous tool, why avoid it? Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos viewer
Sweet program! Was taking a look at one of the games. Very nice interface for linux. -Josh On 4/10/07, Don Dailey [EMAIL PROTECTED] wrote: So you got it from the wrong place! Good - we can solve your problem then! Go here: http://cgos.boardspace.net/9x9/index.html and I think you will find a version that works for the new cgos. - Don On Tue, 2007-04-10 at 12:57 -0700, Tris wrote: Got it from: http://www.greencheeks.homelinux.org:8015/~drd/public/ Got the windows version: cgosview-windows.zip Yes, Unzipped first. Earlier version worked fine! Tris At 12:29 PM 4/10/2007, you wrote: On Tue, 2007-04-10 at 11:54 -0700, Tris wrote: Just tried to download the latest version. Downloaded, unzipped but didn't work/display. Did I not get it from where I should have?? It's hard to say - I don't know where you got it from. Also, you didn't specify your operating system so I have no idea which one has an issue. Please note there are playing clients for you go program and viewing clients. Which did you try? Did you unzip it first? - Don Thanks... Tris... ___ 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] The dominance of search (Suzie v. GnuGo)
I watched MoGo playing with different rank of players. Usually 5d players has no problem winning. Starting from 4d begin to lose games. However, part of it is due to most players are not familar with 9x9 Go. Taking this into consideration I place MoGo at about amateur 2d. For professional players consider 9x9 is solved. This is all my opinion. Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 times, it also need to make up the difference between 4k and 2d. Exponential may not be the case. Just consider this that it could be factorial which is worse than expernential. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 10 Apr 2007 3:12 PM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) Hello, 2007/4/6, Tom Cooper [EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
Christoph Birk: [EMAIL PROTECTED]: On Tue, 10 Apr 2007, Hideki Kato wrote: According to the report on MoGo (RR-6062), its playout part seems pruning not interesting moves using patterns. Yes, but the UCT part will (sooner or later) explore EVERY path. Yes, but the estimated score could be wrong. Then, where to converge? -gg Christoph ___ 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/
