Re: [computer-go] How does MC do with ladders?
Forrest, similar multi-level or hierarchical/partitioned search concepts have been suggested by several people here over the years, myself included many times. I first suggested a chunking probability based search concept back in 1998. I have long been an advocate of goal-directed hierarchical search for Go, but haven't yet figured out how to make it work in practice. I tried some things years before MC/UCT popped up without any real success. There could perhaps be some promise in finding ways to combine some of these multi-level ideas with MC/UCT search techniques. I don't understand the follow-up to your post claiming that you can't do this for these kinds of games because they are not forcing move sequences. We're talking about the play-out part of the search used to sample the game tree. Anything goes, right? Of course, whether any particular play-out method helps or not is another question. -Matt Forrest Curo wrote: It's the approach I believe to be more human-like. Not necessarily the playing style. Human beings chunk. What all this fuss suggests to me is a meta-mc program... You include routines that work out good sequences, as a human would--and then you have the random part of the program include the more promising sequences, where applicable, as if they were individual moves. Forrest Curo This message was sent using IMP, the Internet Messaging Program. ___ 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] Congratulations to GNU and to MoGoBot19!
steve uurtamo wrote: i think that maybe you misunderstand how byo yomi is used in practice. you have a giant pile of time that should be enough to account for basically all of the hardest parts of the game. then you have several (more than 1 !) byo-yomi periods, which are like grace periods on top of what would otherwise be sudden death. however, you don't enter byo-yomi until you have used all of your main time. some people don't ever enter byo-yomi. you certainly can't lose on time unless you're in byo-yomi. once you're in byo-yomi, each byo-yomi period is *plenty* of time to make and answer the reasonably unchallenging final moves of the game. if, however, a challenging move does come up, you can go over your grace period. that's pretty friendly from a sudden-death point of view. you're just only allowed to go over some maximum number of times (often 5 or 10). the reality is that if your opponent is playing moves that you can't answer using byo-yomi, then he's perhaps trying to beat you with the clock, but he's definitely better at the game than you are, and maybe you deserve to lose anyway. it's something that he might do if you're in byo-yomi and he isn't. he wouldn't play moves that he didn't know how to answer if he had fewer byo-yomi periods than you did, because he'd just be beating himself with the clock. all of this adds up to: i think that what you're worried about (someone losing on time while having spent less time playing) is unusual, or deserved. here's my thinking. the only way this could happen would be if (correct me if there's a flaw here): both players were into byo-yomi time. player A starts to play moves very, very quickly. player B plays moves more slowly (and presumably more deliberately). at some point, player B plays one or more moves that player A has to think really hard about. player A goes overtime 4 separate times during this stage of the game and is left with a single byo-yomi period left. at this point he can take up to 30 seconds (say) for every single move that he takes if he wants to. player B plays a very challenging move that player A can't answer in a single byo-yomi period and then player A loses on time. now, from my way of thinking, there's a sense in which player A deserves this -- either he should have spent more of his time thinking during the endgame instead of just making quick moves, or player B is better at generating and figuring out complicated fights (in which case, well, no use crying over losing by time, as that's almost the definition of what it means to be good at go). I'm jumping in here, but how about this? Byo-yomi time is complicated. Fischer time is simple. By other factors, I think there are legitimate pros and cons to both systems, but personally would like Fischer time better. Managing your own time whether in chunks or as a whole _is_ a sub-game/task either way. -Matt ___ 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/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Don Dailey wrote: (snip) In my opinion, the insight that Chrilly articulated was that all of sudden we are now all using some type of global search - the very idea was considered blasphemy just 2 or 3 years ago. That may be too strong a statement. It may have not been popular but many people consistently believed global search must be a big part of any strong playing program, myself included. Not searching using the same techniques as used for chess, but IMO certainly searching has not ever been altogether dismissed nor considered blasphemy. Look back at posts around 10 years ago (when I first joined the list) and probably since its inception and you'll find this to be true. I personally wrote about it on several occasions suggesting that to counter the evaluation problem the search needed to go very deep and even talked about sampling the tree. Other probability based searches have been studied and written about in academic papers and on this list as well. The crucial combination of techniques didn't bubble up, but not for lack of trying. But I have to admit that personally, I have many more ideas than time with a full time job. Over the last 10 years all I've really done is play around with various algorithms and ideas, study the game of go, collect and read a lot of published papers, and keep up on this list - occasionally posting. My wife still doesn't understand my putting this much time into it! ;-) This is the kind of thing that could consume a person. I don't know if particular ideas would pay off or not because I haven't been able to put in the proper time to focus. In spare time, on and off over the years I've only done a few experiments and algorithms mostly focused on partitioning, goal directed and hierarchical searching methods. This negligible computer-go work, some plans and a few ideas is the extent of my would-be program KatanaGo. Regardless, it has been great fun watching the progress of computer-go over the years and the current flurry of activity with MC/UCT is quite exciting! As I wrote in a post in early Feb of this year (paraphrasing from memory), I think the main reason MC/UCT works is because it goes deep (nearly always to the end) and tends to find paths with more favorable possibilities and more importantly avoid paths littered with problems. Though I'm still pretty amazed by how well it plays, but that's the power of the law of large numbers at work. Correct? As for the point that different paths may converge on similar methods, I agree that could be very plausible scenario, but there is a very long way to go yet... ___ 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.
Erik van der Werf wrote: On 4/10/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le lundi 9 avril 2007 14:06, Don Dailey a écrit: But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. Is there any proof that heavy player converge toward the same solution as the pure random playout ? With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranted for heavy playout. With infinite resources the MC part won't have to make any move (heavy or light), so it does not matter. OC, this is all just theoretical throughout most of the game for any board of reasonable size. BTW pure random would fill it's own eyes... The benefit that MC/UCT has is that it can be stopped any time and get a reasonable current selected move. The probability that it will find better moves tends to increase with more resources/playouts. But wouldn't a simple brute force search of the game tree be more efficient than MC/UCT at finding the certain best move, given the hypothetical hyper super computer we are talking about? So if ever this hyper computer exists with near infinite speed and resources we can just run a methodical brute force search and be done with it. Why would one bother running a googolplex random simulations to approach perfect play? So to be practical we have to find ways to improve the search beyond pure scalability like the MoGo developers are doing. Does this make sense? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GTPv3
Don Dailey wrote: On Mon, 2007-03-05 at 10:10 +0100, Heikki Levanto wrote: On Sat, Mar 03, 2007 at 04:10:16PM -0500, Don Dailey wrote: And you CAN compare GTP directly to UCI because both are designed for the same purpose and both are simple text based protocols and the similarities are much greater than the differences. GTP has many purposes. One of them is to sit betwene an engine and an UI, but that is not the only one. It is also used for test scripts to validate engines, and to debug them. So, what even asynchronous extensions you are adding to GTP, please keep the simple synchronous mode still available, for it has many uses too! If I were designing the asynchronous extentions I was mandate that the core doesn't change - that you can continue to use GTP as is without any suprises. I'm entering this discussion a bit late, but what about the following idea? Perhaps we could start from scratch and create the protocol we want with no compromises based perhaps on an async event message model - a model everyone probably is quite familiar with. It could move beyond ASCII messages on stdout and be designed for extensibility. Add all the common features we are looking for to really make a modern, robust and complete system. Since something like this would be a superset of GTP, a reference implementation of the new protocol could also include a proxy implementation of GTP using the new protocol. This would allow the best of both worlds - programs can continue to use GTP if they wanted, operating in a more constrained context than programs that implement and use the new protocol. Years into the future we won't have the baggage of GTP still as likely all programs would eventually move to the new standard. Just a thought... -Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
Heikki Levanto wrote: On Wed, Feb 21, 2007 at 07:55:15PM -0600, Matt Gokey wrote: Whether it is a torus or not is irrelevant. The only thing that matters from a go game play perspective is the graph topology. If all points have 4 neighbors the actual physical shape or layout doesn't matter. There can still be subtle differences. In a standard torus, a ladder comes back to its starting point. If you twist the torus enough, it will miss, and fill the whole board... Hardly relevant to random players that don't understand ladders, but anyway... I'm not sure I agree with this. I hypothesize that 2d, 3d, 4d, torus, or any other shape is completely irrelevant with regard to game play. The only thing that matters is the graph topology. A corollary is that on any board that is completely balanced at the beginning with identical number of neighbors for all nodes, any 1st play is equivalent and therefore optimal. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
alain Baeckeroot wrote: Le jeudi 22 février 2007 14:11, Matt Gokey a écrit : The only thing that matters is the graph topology. A corollary is that on any board that is completely balanced at the beginning with identical number of neighbors for all nodes, any 1st play is equivalent and therefore optimal. Yes. But the round board at http://www.youdzone.com/go.html is not isotropic, it is a cylinder. You can build it with a square garden wire netting cut at 45°, and add one wire on each border to have 4 neighbors everywhere. If you start from any point and go straight you end on a border. If you start from a border and go straight you stay on the border. I don't understand. I think everyone is thinking too visually. What does straight mean in the context of go? Only liberties are meaningful. It is isotropic if you stop visualizing the shape and only consider the graph. Here is a thought experiment to test: define the board only logically using a graph (nodes and neighbor nodes). No topological shape and no mesh layout over any shape is needed. If all nodes have exactly four neighbors, there is no method or algorithm that you can run to find an edge. All nodes will look equivalent. If it were a cylinder, there would still be a top and bottom edge indicated by nodes with fewer neighbors. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
Tapani Raiko wrote: Matt Gokey wrote: I'm not sure I agree with this. I hypothesize that 2d, 3d, 4d, torus, or any other shape is completely irrelevant with regard to game play. The only thing that matters is the graph topology. A corollary is that on any board that is completely balanced at the beginning with identical number of neighbors for all nodes, any 1st play is equivalent and therefore optimal. It is true that the graph topology is the thing that matters, but having an identical number of neighbors for all nodes does not mean that the graphs are similar (isomorphic). For instance in the 3D diamond graph, each node (disregarding the edges) has 4 neighbors as usual, but there are 12 neighbor's neighbors, whereas normal Go board has only 8 (4 diagonals and 4 one-point jumps). I'd say there is a huge difference. OK, I see. That is of course a big and very significant difference. -So the graph topology is crucial not really the shape. -And if a board is empty and balanced with equal numbers of neighbors and uniform (e.g. same connectivity properties throughout) then any 1st play should be equivalent and therefore optimal. Right? A toroid board (defined as a normal square board with the top-bottom and left-right edges connected) would fit this condition, however, the round board does not appear to. Therefore they can't be isomorphic or structurally identical. When describing boards as mapped onto different shapes it would be helpful to describe the graph connectivity properties being imagined since so many different boards can be constructed on the same geometries. As for Don's original question about the toroid board, I think it does change the game significantly since it will be harder to make territory without edges and perhaps less interesting, but the first play is easy since any move is optimal and would not require running even one simulation ;-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
Nick Apperson wrote: I considered making a version of go that plays with tetrahedral geometry. It is a 3D arrangment where all nodes have 4 neighbors and the angles between each are 109 degrees. Its connection properties though are very different because of the way it it layed out. Hence, I am going to have to disagree. Now I understand what you were saying here. But if what you mean is that all that matters is the graph representation of the go board, I will agree with you there. Well that _is_ really what I meant, I just wasn't thinking of all other possibilities and implications. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
Matt Gokey wrote: alain Baeckeroot wrote: Le jeudi 22 février 2007 14:11, Matt Gokey a écrit : The only thing that matters is the graph topology. A corollary is that on any board that is completely balanced at the beginning with identical number of neighbors for all nodes, any 1st play is equivalent and therefore optimal. Yes. But the round board at http://www.youdzone.com/go.html is not isotropic, it is a cylinder. You can build it with a square garden wire netting cut at 45°, and add one wire on each border to have 4 neighbors everywhere. If you start from any point and go straight you end on a border. If you start from a border and go straight you stay on the border. I don't understand. I think everyone is thinking too visually. What does straight mean in the context of go? Only liberties are meaningful. It is isotropic if you stop visualizing the shape and only consider the graph. You are right it is not isotropic - sorry - I didn't look at it closely enough. Here is a thought experiment to test: define the board only logically using a graph (nodes and neighbor nodes). No topological shape and no mesh layout over any shape is needed. If all nodes have exactly four neighbors, there is no method or algorithm that you can run to find an edge. All nodes will look equivalent. I was assuming the board was uniform or isotropic I guess when I wrote this. Mea culpa. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big board. Torus ?
Stuart A. Yeates wrote: On 2/21/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le mercredi 21 février 2007 02:10, Antonin Lucas a écrit: No need for those difficulties, you can play along this board : http://www.youdzone.com/go.html I think this is not a torus, even if each vertice has 4 neighbours. I can easily mentally transform this into a cylinder, with an rectangular lattice and additional connection on the borders to have 4 neighbours. I agree If this were a torus, there would be links between the inner ring and the outer ring of vertexes. Whether it is a torus or not is irrelevant. The only thing that matters from a go game play perspective is the graph topology. If all points have 4 neighbors the actual physical shape or layout doesn't matter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Jacques Basaldúa wrote: Very good analysis and I would like to contribute a 4th reason: As Luke Gustafson pointed out, we have to contemplate the simulation as a _stochastic process_. We want to determine the conditional probability of a win given a particular move is made. And that depends on the _length of the simulation_. Dramatically! This is a reason against scalability of global search MC/UCT. If the simulation is 500 moves long (Chinese rules with recaptures, etc.) the observed variance at an early move blurs out everything. Just a simple stochastic process: Count a dollar each time you correctly predict a p=1/2 coin thrown n=500 times. The expected average is (obviously) 250, but the expected variance of that measure is n·p·(1-p) = 125 proportional to n. Good point. This leads to another thought that I have been wondering about. That is I question whether using more time to search more simulations in the opening is the best approach. For the opening, selecting reasonable robust moves that tend to lead to more favorable options is probably a good objective. The lengths of the simulation are perhaps too long to expect anything better. Later towards the pre-middle to middle game it is very critical to play such that the positions tactical potential is exploited such to secure connections and eye space, etc. It would seem to me that focusing the highest concentration of time and number of simulations during this part of the game might be most advantageous. It would be interesting for someone with a decent MC player to do an experiment like this with one version concentrating highest number of simulations in the opening and one concentrating in the middle game, but otherwise equal and see which version wins more often. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
Don Dailey wrote: On Wed, 2007-02-07 at 11:34 +0100, Heikki Levanto wrote: All this could be avoided by a simple rule: Instead of using +1 and -1 as the results, use +1000 and -1000, and add the final score to this. Heikki, I've tried ideas such as this in the past and it's quite frustrating - everything that tries to take territory scoring into account weakens the program. If you just need to see prettier moves, I think it is good enough to priortize the moves using some other algorithm at the root of the tree. If you just cover the case where a program is easily winning or losing it will play nicer but not stronger. Don, do you have any theories or information about why this is the case? I would think either way the algorithm should always prefer higher average win probabilities, but faced with alternatives where the win probabilities are same or nearly the same but the average winning margins are higher for one alternative, wouldn't it be better to take the path with the better margin? I mean it may in fact be wrong about the win/loss classifications so choosing the better scores would seem to make sense within reason as long as it's not greedy. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Magnus Persson wrote: Quoting Matt Gokey [EMAIL PROTECTED]: (snip) Good point. This leads to another thought that I have been wondering about. That is I question whether using more time to search more simulations in the opening is the best approach. For the opening, selecting reasonable robust moves that tend to lead to more favorable options is probably a good objective. The lengths of the simulation are perhaps too long to expect anything better. Later towards the pre-middle to middle game it is very critical to play such that the positions tactical potential is exploited such to secure connections and eye space, etc. It would seem to me that focusing the highest concentration of time and number of simulations during this part of the game might be most advantageous. It would be interesting for someone with a decent MC player to do an experiment like this with one version concentrating highest number of simulations in the opening and one concentrating in the middle game, but otherwise equal and see which version wins more often. My experience with Valkyria is that most time must be allocated towards early moves. If you make a mistake on 9x9 it is very hard to come back. MC/UCT programs such as MoGo are very good at defending a won position. Therefore it is important to get a won position as early as possible. The longer it thinks the better it plays. In the opening it always critical to find the best move - but later on games are often either won or lost so saving time for those positions are not so important. I agree with this last statement for the early end-game / end-game phase. For the pre-middle to middle I'm not sure. This is the critical part of the game where you need to solidify the winning positions. As long as reasonable opening moves that provide robust options are made and it can play into the middle game stronger than the opponent, winning positions should result. I'm not saying not to spend time up front, just less than when in the middle. On 9x9, the stage where this becomes tactically critical is probably much earlier than on 19x19. Even with 9x9 I predict an MC/UCT program that spent X simulations per move for the first 8 moves, and 2X for the next 8 would tend to beat the same player doing the reverse, where X is some reasonably large number of simulations needed to open decently. I could be wrong, but it would be an interesting experiment anyway. However IMO 9x9 is too small to see the real complications come out. Valkyria saves time in the opening by using an opening library, but as soon as it leaves the library it spends a lot of time on the first move. Moves it spends a lot of time on is also stored in the library. And later on I might correct moves that was played in lost hand myself. I am actually rarely satisfied with the opening moves of Valkyria. It needs more time for those moves... I was wondering if anyone was combining an opening library with MC/UCT by running a large number of the simulations and storing the results. This seems like a pretty natural extension to save simulation time in the opening. How strong a player are you? You are probably unfairly evaluating Valkyria based on your strong expert play/perspective. I'm rather amazed that MC simulations find good moves at all given that most of the playouts are nonsense games. That is why I say MC/UCT is finding reasonably robust moves with more favorable options (strategic play) not necessarily great/best moves. Because of mostly meaningless playouts it misses nuances and tactics deeper into the game that would show otherwise. It seems the deeper the simulations the worse this effect would be. -Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Why not forums?
Eduardo Sabbatella wrote: No please. I use my email client, I sort them, I store them I'm happy with it. Personally, I will not be able to read the forum at work. It will be the difference between reading and not reading the list. I want to choose which info will push me, and forget. I don't want to log into a forum every time I remember about Go. (I have a very bad memory) Mailing lists exist on internet since 20+ yrs ago and continues to be used, they are not outdated! I don't care about having an AVATAR. My 2 cents. Eduardo I agree - please don't move to a forum... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)
Upon continuing to learn about the general Monte Carlo field, I've found it seems there is a general consensus in this community about a distinction between Monte Carlo (MC) and what appears to be commonly called Quasi Monte Carlo (QMC). MC is defined as using random/pseudo-random distributions and QMC using more deterministic or designed distributions that fit the problem better. Just do search on google web or scholar and you'll get a wealth of hits. But here are a few links to documents or pages that specifically address this terminology: http://www.arts.cornell.edu/econ/CAE/final.pdf http://www.mas.ncl.ac.uk/~ngl9/docs/MCQMC.pdf http://www.math.hkbu.edu.hk/~gwei/sci3510/ch1.pdf http://mathworld.wolfram.com/MonteCarloMethod.html http://mathworld.wolfram.com/Quasi-MonteCarloIntegration.html It also seems that today quite often Monte Carlo generally is used to describe any kind of statistical sampling using random or other distributions to approximate solutions to problems like David Doshay pointed out. So would it be helpful to distinguish between MC go and QMC go programs - maybe a little. Since I'm just learning about this I might be misunderstanding some concepts. But besides doing obvious things like minimizing memory usage and optimizing code so that you can increase the sample size, there are many well known strategies to decrease the variability of the simulation. These are called variance reduction techniques. Generally Monte Carlo standard error decreases based on the square root of the sample size (quadrupling the sample size cuts the the standard error in half). I would think in part this would depend on the problem, so not sure if this applies to MC go or how to measure. Variance reduction methods are used to improve the distribution improving the results (error) without increasing the simulation size as much. Here is a list of some of them without any explanation (searching on any of these terms with monte carlo should turn up lots of hits): -Common Random Numbers -Antithetic Variates -Control Variates -Importance Sampling -Stratified Sampling -Conditional Sampling -Systematic Sampling Most of the research using MC methods seems to be for numerical integration, finance applications, and physics applications; not applied to game theory. It may be be challenging to understand how to translate these ideas to MC go or whether they would be helpful. -Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)
ivan dubois wrote: I dont understand how you can reduce the variance of monte-carlo sampling, given a simulation can return either 0(loss) or 1(win). Maybe it means trying to have mean values that are closer to 0 or 1 ? Well strictly speaking I agree the standard models don't fit that well - the application of monte carlo to go is much different than traditional applications. However, imagine the whole path of a simulation to the leaf as a meaningful set of points. We are only measuring the end, but the path is very important too. Also, as you mentioned one could target the larger scoped variance of the set of simulations mean value correctly classifying the point as a win or loss. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MC Go Effectiveness
It seems to me, the fundamental reason MC go (regardless of details) works as it does is because it is the only search method (at least that I am aware of) that has found a way to manage the evaluation problem. Evaluation is not as problematic because MC goes to the bitter end where the status is known with certainty. With random distributions it probably tends to find robust moves that leave a lot favorable options open. With MoGo, Sylvain has shown that better simulation policies can achieve much better results. But what are some of the reasons MC is not even better? -Since MC engines don't deal with tactics directly, they're not likely going to play tactical sequences well for low liberty strings, securing eye space, cutting and connecting, ko fights, or ladders, etc. -Also because most of the play-outs are usually nonsense, they may have trouble dealing with meaningful nuances because the positions that will lead to these distinctions just don't arise with enough statistical frequency in the play-outs to affect the result. Yet when very selective moves are used in the play-outs, too many possibilities can be missed. -Finally, with 19x19 anyway, the size of the board and game tree probably limits the practical effectiveness of the sampling and move ordering. I don't try to address this last point any further in this message. So here is an idea for MC research: Incorporate multiple types of distributions in one MC player. Available time resources would be divided between the different distribution methods. Then the results of these could be combined in some kind of sum/rank/vote/etc. For UCT this could be used to direct the search at those most interesting nodes. As an example, distributions such as these could be used: 1. A random or near random distribution 2. A more selective pattern based distribution 3. A simple tactical reader based distribution - this might not be obvious how to implement, but perhaps it could play tactical sequences if such conditions (based on heuristics) existed on the board, otherwise switch to one of the others. With regard to variance reduction techniques, #2 and #3 might be examples of importance sampling and conditional sampling. And the above overall method might fall under the category of stratified sampling. Thoughts? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
David Doshay wrote: I am a physics guy, and my thesis project was a large MC simulation. The clusters that run SlugGo are usually busy doing MC simulations when not playing Go. In general MC needs to sample according to the proper distribution for the problem. For some problems in quantum mechanics and most in statistical mechanics, the distribution cleanly partitions into percentages of the total, and in those simulations it is easy to do things like generate random numbers and then see what range the random number is in. For Go I could easily argue that sampling random points on the board is clearly the wrong distribution, and those programs using some kind of pattern knowledge are really doing something much closer to MC simulations rather than true random playout. So, I do not think that MC is the misnomer. Thinking that pure random playout is the same as MC is the mistake. Got it. I was thinking Monte Carlo (name based on the gambling city) meant it must be random, but looking into it deeper other statistical sampling methods designed specifically for the problem to reduce the number of simulations can and are often used. Looks like there is some level of confusion about this out on the net too. Wikipedia perhaps needs updating for one. Thanks for clarifying that. Go requires a pretty complex simulation to be run and using more selective moves for the play-outs, if not done very carefully, could have an adverse effect by being too restrictive or sampling the wrong distribution. I'm sure random is not the best distribution also, but at least it is not biased. Are there any methods from other MC research areas to help find good sampling distributions and reduce variance or is Go just wildly different than most domains where MC is used? Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
[EMAIL PROTECTED] wrote: -Original Message- From: [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] ... The earliest MC engines were extremely simple and easily described. It seems inevitable that someone new to the field will seize on this description, and then combine it with the success of current Monte-Carlo engines, leading to unnecessary confusion. I am not sure what you mean by that. Do you mean that different people will use the term MC in different ways and cause confusion in the minds of third parties? In other words, some people are using the simplest pure random playout (no consideration ^of distribution at all) and calling that MC while others are trying hard to keep the moves searched Go-like. and thus get different ^results. Or do you mean that naive programmers will try pure random playout and wonder why the MoGo folks are doing so very much better, not realizing the importance of getting a decent distribution for MC to be effective? I mean both. But IMHO the most serious distinction is whether the MC is combined with tree search or not. I'm not embarking on a nomenclature crusade. Just remarking that when people say Monte-Carlo does this or that, it's often ambiguous what algorithm they are actually talking about. This is the condition that led me to first think of and submit the original question. Sometimes you can't tell what people are talking about when they mention MC go. So does anyone have any thoughts on the follow-up comment and question? That selective move playouts could have adverse effects, and that random is probably not very good but not biased. Also, what MC distribution techniques (from general or specific research areas) might be used to help create better sampling distributions and reduce variance, improving overall results? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte-Carlo Go Misnomer?
Is MC Go a misnomer for programs in this genre not using simple random playouts and combining with other techniques like pattern matching? Technically, does the general Monte-Carlo method require random or pseudo-random sampling? If so, should we dub a new name for these non-random deep play-out sampling based go programs? Maybe Quasi-MC or Directed Sampling... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
Don Dailey wrote: I was looking at many of the posts on the threads about how things scale with humans and computers and I'm trying to reconcile many of the various opinions and intuitions. I think there were many legitimate points brought up that I appeared to be brushing off. In computations done by computer, there can usually be a trade-off between time and memory. In the discussions, we rarely talked about memory and how it figures in to the picture. A lot was said about just knowing something (where a strong player looks at a position and instantly knows a weaker player made a mistake for instance) and the feeling expresses by many was that this was a barrier that could not be penetrated by thinking about the position no matter how much time was allowed. Although I consider the evidence pretty strong for rating curve in both humans and computer, the model of a fixed strength increase per doubling is actually a simplification - in the real world it is more complicated than that. It's important to realize that the ELO formula is based on assumptions about human playing strength that are only approximations. One of those assumptions is that playing strength is transitive and can be expressed as a single value - a number that we call a persons rating. Nevertheless, intransitivity is a real thing. The way we sometimes erroneously think about GO is that you have some fixed strength expressed as a kyu or dan number and that every move is a reflection of this level of play. A better model, which is still a simplification, is that a move is either right or wrong and the stronger you are, the more likely you will choose the better move. Some move are easy to find and the weaker players find them, but on average you are faced with moves of every level of difficulty and the difference between stronger and weaker players is how many of these positions they solve - kind of like a big test with a mixture of easy and hard problems and the one that gets the most answers right wins! From a purely theoretical point of view, a move really is either best or not-best but as humans we judge moves on a sliding scale of goodness and refer to some moves as being horrible and others as being brilliant, good, second best, etc. On this group we recently discussed how to define error vs blunder and so on. The intuition behind judging moves like this is that indeed, some moves give you better practical chances in the real world. So if you are slightly losing, a move my be referred to as a good try because it complicates things, or at least requires the opponent to find a refutation that in human terms is difficult to find. Sometimes a good player, or even a computer can instantly find the right move where a weaker player has no clue and is not likely to discover the correct principle even given several hours of meditation. This has been mentioned a number of times recently. This an example of a chunk of knowledge having a profound effect on the quality of a single move. Even with computers it is possible that a good life and death routine can discover things (more or less) instantly that might take a very long time to find with a global brute force search. Because knowledge can be imperfectly and unevenly applied, one player might play some types of positions much better than others. So even among players of roughly equal abilities, one player may see at a glance what another player would have a very difficult time discerning. What this causes in my opinion is instransitivity. It doesn't cause a player to stop improving substantially with time as many experiments have proved. But it's a known phenomenon that because of intransitivity and these knowledge gaps, you might improve much more against a particular opponent (opponents just like yourself for instance) and much less against other kinds of opponents. But this is also about memory scalability. Better players have more knowledge about the game. It's very difficult to measure knowledge quantitatively in humans. How do you have twice as much knowledge in Go? How do you test this? But it's clear that stronger players have much more knowledge, probably much of it in the form of trained intuition about go positions in the form of pattern recognition. Some knowledge is expressed as cute little proverbs of wisdom such as the opponent's vital point is my vital point among others. Because no two players play alike, and especially computers and humans, bits of knowledge and processing power have different scaling characteristics. Even a particular piece of knowledge could help you more against one opponent that another. So let me restate my feelings based on the above considerations: 1. Game playing skill is a function of time. 2. Memory (or knowledge) can proxy for time - saving enormous amounts of time in many cases. 3. Technique is a function of knowledge and how it's organized - which translates to a big time savings indirectly. This
Re: [computer-go] an idea... computer go program's rank vs time
[EMAIL PROTECTED] wrote: Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Yes, this seems obvious and to me it appears you are begging the question - presupposing the conclusion. You said it yourself in the last sentence: _if_ he is right then mathematically it follows for the larger branching factor. Can't argue with that. I was trying to compare a different relationship related to the branching factor and other characteristics of Go to capacity of human logical reasoning and thinking. The idea being to suggest a possible explanation for why Go may be qualitatively different than Chess in this regard. So I'll attempt to put the relationship I was trying to describe with words into a mathematical model and then further describe my thought process. Let b = branching factor Let f = Effective avg. pruning factor(0-1), thus b*f is an effective avg branching factor Let t = length of thinking time Let p = maximum ply or depth under consideration Let n = avg. number of positions a player can effectively evaluate in one unit of time (either explicitly or otherwise using whatever reading/learning/patterns/etc. to his avail) Both f and n can be considered idealized measures of skill and ability of the player. Let r = rough approximation (as this is a simplification/idealization) of the ratio of coverage of the game tree to depth p and defined as: r(b,f,t,p,n) = n*t/(b*f)^p for all n*t=(b*f)^p, otherwise r=1.0 Obviously if you double the time and keep the depth constant the ratio of coverage goes up in a linear relationship for all b. But as time is increased, p is increasing presumably. Now the graph of r is not linear and higher b results in a faster rate of decline. Now I understand that this doesn't necessarily have anything to do with strength ratings. So that is some background for the concept. Bear with me if this borders on the obvious for a while. So we all know that Go evaluation is very hard (for computers, but also for humans). You can't prune if you can't evaluate in some sense however (not with certainty anyway). You can't evaluate without understanding shapes/life and/or reading. In chess these things are arguably quite a bit simpler. So with chess with a much smaller starting branching factor and simpler more left-brain devices for pruning and evaluating the cost/benefit of looking deeper tends to have reasonable payback at relatively large depths. Contrast with Go, starting with a much higher branching factor and lacking left brain (logical/reasoning) methods for pruning and evaluating, depth tends to create more confusion and quickly exceeds the brain's ability to keep track of exploding variations. However, as you learn from experience you can recognize patterns for the different concepts and balance with analysis to effectively prune and evaluate position potential and group interaction and then you can go deeper with some confidence level in your understanding of the status of the game. Learning these skills while thinking about a particular game's next move is not generally practical and even if possible would presumably require enormous extra time. Yet without this ability you are left with a massively rapid expanding game tree to search. Finally this is why I think it may be the case that doubling human thinking time for Go might not produce linear improvements. Back to the model, we could add another variable perhaps: Let c = reliability/certainty factor for the pruning and evaluations done during the search. r*c might have some meaning... And again I am not saying this is black and white. Chess and Go share these same characteristics to different degrees. I believe Chess is more logical/analytical and Go is more balanced analytical - intuitive/holistic (yin-yang thing), thus each yields to both approaches in different situations and ways. But just because a rule of thumb holds for Chess doesn't mean it does for Go. Of course I could be wrong, but I was just trying to introduce reasonable doubt, since Don always seems so sure of himself ;-) Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Vlad Dumitrescu wrote: Hi Matt, On 1/25/07, Matt Gokey [EMAIL PROTECTED] wrote: But just because a rule of thumb holds for Chess doesn't mean it does for Go. Of course I could be wrong, but I was just trying to introduce reasonable doubt, since Don always seems so sure of himself ;-) If I may venture trying to rephrase your arguments, do you mean that since difficulty grows exponentially there may be a qualitative leap between chess and go? Not really. I merely am raising a question about the assertion that human doubling of thinking time results in _linear_ improvements. I am not claiming that there is no improvement - never have. I am not claiming that every turn must produce better results to improve overall play - never have. However I am trying to explain a rationale for the possibility that improvements may not be linear based on the nature of Go. Comparing chess and go is difficult, but I think this effect can be seen between 9x9 and 19x19 go too: the two games are quite different, because in 9x9 there is practically no strategic element and this element brings a whole new dimension to the game. Yes it is difficult to compare. Don ventured into these waters by asserting that a relationship fairly well established and reliable in Chess holds for Go. As for between 9x9 and 19x19 Go, obviously 19x19 is harder and games are much more strategically and tactically interesting, but I think a similar relationship between chess and 9x9 Go probably holds, just differs by degree. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Ray Tayek wrote: ... I can say that I don't feel overwhelmed when playing chess. ... Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed ... yes, i usually feel this way in tournament games. and again more time will help (for some small powers of 2). I'm glad I'm not the only one that feels this way ;-) i think more time works better because go has more battles going on at the same time. Which also makes it harder when there is interplay between them. if you are analyzing one battle, maybe more powers of two. if it's many battles, maybe fewer powers of two as you will hit your mental limit sooner. This seems to support the idea I was trying to express... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Been following this thread pretty closely and thought I would jump in with a thought and try to find some common ground. I think there is truth to be found in both sides of this argument. Of course people improve with time and so do computers with certain algorithms. The question is about the curve and whether there is a significant difference in this curve between chess and go. Don believes there is probably no difference and states a rule: doubling thinking time = linear improvement in play. What if we look at it mathematically by looking at the branching factor? Go’s branching factor is generally considered to be about an order of magnitude greater than chess – perhaps a bit less, right? That means that after each ply go becomes another additional order of magnitude more complex. Now of course, in practice it’s not so simple, as breaking the game into regions and doing local reading and global analysis reduces the complexity somewhat, but in general go explodes a lot faster than chess and this fact is commonly used as one of the reasons methods used for computer chess don’t work on go especially combined with the lack of reliable evaluation. For the sake of argument if we assume that doubling thinking time allows one to double the number of positions and alternatives that can be analyzed, this doubling would seem to have lesser impact in go where the explosion is much quicker than in chess and thus the same relationship may not hold. The improvement may not be linear or it may not hold for very long. The point of diminishing returns for a human due to this could be much earlier in go than in chess. As go players get better they must learn to “sense” the board based on years of experience combined with our evolutionary tuned super parallel visual pattern matcher. This provides the player shortcuts that otherwise would be impossible (for humans) to read out. Assuming enough processing power and memory this problem would not necessarily hold for computer-go. By the way, I think some of this very same thing applies to both chess and go, just a matter of different degrees. From my own experience with chess and go, I can say that I don’t feel overwhelmed when playing chess. That is, I always feel like I can think and reason about the moves fairly deeply and use simple evaluation like piece counts, protection, mobility, etc. to decide between lines of play. I may be entirely wrong but I feel like I can think about it anyway. I’m not a real strong player, but I had a friend in high school and college whose Dad was a Grand Master. His son was pretty good and we would play a lot of chess together. Once in while I would play against his Dad and usually get slaughtered. One time he was doing one of those events where he would play 30 people at once. I played and managed to keep him challenged well into the middle game. I could tell he was worried. On one trip around I still hadn’t made my move and was forced to make the best one I had. It was a blunder but I didn’t see it yet. Immediately he took advantage of it and I didn’t have a chance after that. He confirmed this after the game was over and set the pieces up as they were at that point and showed me what I should have done (I thought an amazing feat given he was playing 30 or more different simultaneous games). Anyway in this situation where I had a lot more time than he did I was able to challenge him and only after making a blunder was I in trouble. So I see where Don is coming from with Chess. Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed without enough tools to understand how to plan and evaluate moves in all but the simplest isolated cases. I know that giving me tons of extra time against a good player would not help. The interactions between areas and the explosion of the game and lack of experience to be able to “sense” good shape and proper balance early enough to lead to life and territory just simply overwhelms me. The feeling is not as severe as it was when I first learned, but it is still there. I wonder whether even for strong amateurs this is still the case, but just happens a bit deeper. Is this the time limit that Ray talks about where any more time is not helpful? It is that point when it becomes so terribly complex and overwhelming that no more thinking can help given your current ability to judge potential in the positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS pairings using Christoph Birk formula
There may be some confusion about what the assumptions and goals are for the CGOS pairing objectives. I am hearing conflicting statements. So I for one am unsure ;-) Don Daily wrote (from Re: [computer-go] A new pairing system idea for CGOS, 10/8/2006): Your basic idea is sound - but it's all in the formula for point 2. I would not base it on the rating, I would base it on the RANKING Why the ranking over the rating? Ranking eliminates the real strength differences. A cluster of 3 players near 1700 and then one at 1300 looks much different than rank 1, 2, 3, 4. Because a cluster of 2 or 3 bots near 2100, all of them Mogo versions, would mean all or mostly mogo vs mogo. One of the design goals of CGOS is variety. I don't want pairing based on rating pockets. In the current thread Don also wrote: [snip] I would prefer that it's a fairly rare event for a 2100 player to play a 500 player unless no other players are available [snip] And I'd have to go back though the messages, but I'm pretty sure I've heard it stated several times that CGOS should prefer pairing players of similar strength more often than those of dissimilar strength (whatever this means). Sometimes ratings are used and sometimes rankings are used, even though the two have different meanings and implications. If there are clusters of ratings in the pool with shelves (which there likely will be) then pairing by ranking will likely result in pairing significantly different strength players more often than you want (because some closely ranked players will be far apart in relative rating strength). In the real world the ratings will not be distributed evenly. Also there may not be drastic drop-offs from the 2100 to 500 range, but there will certainly be clusters and thus drop-offs. Both methods (by rating or by ranking) will tend to favor pairing different but similar strength versions of the same program together (i.e. the Mogo example Don cited), since presumably if all the versions of Mogo have ratings near 2100 then they will be ranked closely together as well. But is this really a big concern? Are there multiple versions of the same program being played at the same time commonly? And if there are and they are of similar strength then why wouldn't one want to pair them, like any others? And how would a rank based method improve this? Don then also wrote: So I'm starting to believe I will use one of Christoph Birk's formulas with best of N selection: N=1+sqrt(NP-npaired-2) With this formula (as well as the others) and pairing from the top-down, I think gives CGOS a nice distribution. The only issues I see with this technique, if I understand it correctly, is that some players can never be paired, and that clusters will be ignored, therefore in some cases pairing weak programs with stronger ones too frequently. IMO we need to be more explicit. Don asked about how he should do pairing on CGOS so I was just offering a suggestion, but without describing the problem explicitly and the objectives it makes it difficult. Here are some key assumptions/requirements I thought of that apply to CGOS and that would create an effective pairing distribution: 1. The pool of players will not be uniformly distributed by rating, there will likely be clusters and isolated points. 2. The pool of available players can change between each round. 3. In any round, it should be possible that any available player can be paired with any other available player. The probability of this happening for any specific pairing depends on the pairing algorithm, but between any two players it should not be zero nor 1 (unless of course there are only two players in the pool). 4. In each round, pairings of players of similar strength are preferred with the probability of the pairings correlated to the relative strength (however defined). How specifically this probability/selection is made depends on the algorithm and its sensitivity to the relative strengths. I don't know if these are the same assumptions and objectives everyone had in mind or not nor if they are even valid or complete, but it would make sense to define/communicate what we want to achieve before we try to devise a method for it. Don? Anyone else? The rating-weighted random pairing method I suggested was meant to handle these assumptions and satisfy these requirements. To test the pairing methods, I suggest something similar to what Don did with N evenly distributed players and N current CGOS players, plus also creating sets of N randomly distributed players; and then run many simulations of sample pairings on these groups for different values of N and plot/analyze the results. When I have some free time and if Don is interested, I may run some simulations for the method I proposed and post some results. Don, please let me know whether your mind is made up already. Matt
