On Sat, 2006-12-30 at 13:52 +0000, Jacques Basaldúa wrote: > Aloril wrote: > > > Actually given *enough* games "fully random including > > eye filling and passing moves" will win against a pro player. > > That is "true", at least as it is true that a monkey would > write Hamlet typing at random long enough. > > That probability is in the range of 1 to (x·100)^(y·100) > where x and y are > 1. x represents the number of available > moves in hundreds (more than 100 typically) and y represents > the number of consecutive moves the random player has to > "guess". (The whole game and, therefore, also more than > hundred.) This number is below the probability of breaking > any type of cryptographic system (private key or public key) > by a fluke in the first guess. For practical reasons that > number is called zero. ;-)
Your odds of finding a "winning move against a pro player" is different from finding one of the "best move(s)" in the position, you can get away with making some non-optimal moves, otherwise there would be no need for pro ranks. If a 4 dan pro needs 2 stones to get equal chances against a 6 dan pro, then there is a bit of wiggle room. It's easier to think in terms of a random player beating the ultimate player. I have no idea how many moves are playable in the ultimate sense from the opening position - but I can imagine that even surviving after playing 4 or 5 random moves will be most unlikely. But I imagine that the ultimate player can take a few random plays and still beat a strong pro, after all a strong pro can give 3 or 4 stones away for free against a weaker pro and still win! But a few randomly placed stones is better than nothing at all! Imagine if those stones were not placed completely random but had just a little bit of common sense added to them. The odds can be improved significantly with minor improvements, such as biases against certain moves. "Don't move in the corner" for the first N moves, for instance, will increase your odds of playing a complete game perfectly by orders of magnitude! But still not enough to make it likely in this universes lifetime. Many searching algorithms are based on this principle. Simulated annealing plays the odds like this with minor biases added to random searches which can actually produce reasonable moves a high percentage of the time. One of the first MC style programs used simulated annealing. All these types of algorithms are based on the principle that a random search given even the most minor help improves enormously, and random search even by itself is a reasonable way to explore a very large space and get useful information very quickly. Many people equate "random" search with "meaningless" search and I believe it is why there is much resistance to the idea. But random search can be directed quite nicely. A very early MC program of mine tried to "evolve" a strategy using a random search (PBIL) which is similar to simulated annealing and genetic algorithms. It was quite effective at this strategy, however there were serious limitations to the way I represented knowledge of the game, which put a low ceiling on what it could achieve. I think this is a very promising approach except that it's almost impossible to represent a strategy in a way that is compact, specific enough and fast enough to lend itself to a huge number of simulations. The way I represented a playing strategy was as a single list of moves, very much like Goggle, a go program that uses simulated annealing to find a move. What was being optimized was the ordering of the move list and the strategy was to play the first legal move in the list. This plays reasonable looking moves but is a very limited strategy. The ideal kind of knowledge is admissibly correct knowledge. Unfortunately, it's hard to come by in GO. Even the 1 point eye avoidance rule that seems so safe is not admissible. The rule, "don't move to the corners" for the first N moves is another one of these rules. Can it be proved that this is NEVER the best move in the first N plays of the game? Of course I expect N to be a reasonable number. I think it's clear that a corner move is not the best FIRST move, but I doubt this can actually be proved! Or maybe it can? If it can actually be taken advantage of or shown that a pass move is better than a corner move, that might be close to a proof, close enough that I would accept it. Of course I am already convinced it is not the best first move. Or can it at least be proved that in a perfectly played game, a corner move would never happen in the first N moves where N is a reasonable number? I could see how positions might be constructed early in the game where it IS the best move, but could it ever be the best move in a perfectly played game? Of course I don't expect an answer. The point is that admissible heuristics would go a LONG way in a random search - just a few simple ones used to reduce the search space would increase the chances of playing a perfect game enormously. Of course I realize that by itself this doesn't make it "likely" by any reasonable definition, so please don't send your flames! - Don > The problem of "towards infinite shift" of Elo rating of > programs vs random is a different one. It is caused because > the probability formula never returns zero (except for > infinite difference), but it does return very small values > (not as small as those of my previous argument). > > One possible solution would be to force this value to zero > (statisticians do that for problems related with goodness > of fit) when the number of expected wins is below 5 in n. > Where n a reasonable guess for the number of games > the bot can play. Using this, there would be a maximum > Elo difference above which nothing should be computed > or, even better, the game should not be played at all. > > But there is, of course, the possibility of a win due > to an Internet fail, a bug, the operator resigned to > power off the computer .. and the this probability is > equal for both. So probably doing nothing is also an > wise option. ;-) > > Jacques. > > > _______________________________________________ > 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/
