Random Play

Random as zero Go knowledge

Beside the hand of God, random play is one of the absolute points at strength scale. Nevertheless, there's currently no ranking system based on either of them, because they are so difficult to estimate, let alone measure.

Chris: How do you define random play? The problem is the possibility to pass. Is pass just a move that gets the same probability as all the others or do you apply Go knowledge to determine at what point you should pass? The strength of random play also would seem to be dependent on the rule set that is in use.

blubb: "Random moves" are bound by nothing but the rules. Since passing is just as legal as every other legal move and merely doesn't change anything on the board (except the side to play), the range of random play includes pass. Otherwise the play would differ from random by some Go knowledge. As for the dependency on the particular ruleset in use, we have found significant influence of handicap being set up the japanese way or placed freely. This influence is - beside the non-linearity mentioned below - a reason to make the steps as small as one stone difference each, such that no handicap will be needed. Superko vs. no-result rule might also have slight impact on the rank outcomes, even though we couldn't find any significance yet.

Chris: And I suppose you use area scoring? Territory would be too difficult, I would think, if play can end at a random point in time.

blubb: Yes, we were mostly using area scoring.

aceofspades: One issue is that defining random play runs into the philosophical discussion of the meaning of 'randomness'. Of course, one could simply trust that probabilistic quantum mechanics is a true ultimate description of the universe, and use something like HotBits. Otherwise, though, you have to grapple with stuff like the fact that the 'apparently reasonable' von Mises necessary conditions on random sequences are self-contradictory.

erislover I don't think so, aceofspades, unless you are taking the extremely holistic view that there is some kind of link between physical phenomena like atomic decay and the winning conditions (and hence "good play") of go. I would think that "random" in this context means less "fundamentally unpredictable" as it does "completely without relation to the point of the game." Whether randomness "really" exists seems besides the point. Don't you think?

aceofspades You may be right, but I find "without relation to the point of the game" to be even more vague. It examines strategies from the point of view of explanations of moves and motives behind them, rather than the effect they have in play. What if I gave you a set of numbers that coded for a Turing machine that played go. You would have difficulty finding any way in the machine was thinking about the game with ideas that made sense (e.g., no where would you be able to say, "Oh yes, that part is so that it uses miai"). But what if that machine was a 10k or the Hand of God? Similarly, I could give you some simple formula that looked like it produced random moves but over time it tended to place its stones together in groups, thereby being moderately better. It's not enough to simply characterize random play as not being related to the point of the game.

::People talk about randomness like it was the worse thing ever, but when talking about chess, some program where the only information is the current board situation, and so cant think or look at the future, would be worse than randomness.

Evaluating the rank of random

Velobici: Random play...very difficult to estimate, let alone measure ? I could quickly write a program for pseudorandom play. Given a connection to HotBits (using randomX for instance), it will have truly random play. This is not hard. Once written, let people play the program, if they can endure doing so, it will then be assigned a rating. Writing a program for kami no itte is beyond my skill.

blubb: During last year, Aloril and I have done some research on the rank of random but, given the little computing power available, we could not get to anything better than "random play is likely to be between 100k and 160k". We scaled down GnuGo 3.6 from full strength to random (actually pseudo random, not based on hotbits or the like) in 10 steps (using gtpTuner), and tried to get an estimate ( gtpBalancer) of the appropriate handicap at each step.
Due to the nature of randomized play, the fluctuation was immense. We run a few hundred games at every step, but the resulting accuracy was still very low. For a reasonably small uncertainty similar to the one of what is believed to be perfect play (say, +/- 1 stone), many thousands games per step would be required. Moreover, since rank differences do not translate to stones quite linearily, smaller steps should be evaluated, preferrably by reverse tuning, that is, aiming at adjusting the variable engine to a fixed rank, like exactly one stone above or below the previously measured reference engine. We have tried reverse tuning at bigger steps already with promising results, but alas, we would have needed like one week per step and didn't have the endurance (PC's at home, which should remain usable).
Anyway, provided sufficient computing power, all this seems feasible today already - unlike kami no itte. Hence I agree, the random end is still (by far) the easier one to evaluate. (Yet another issue is the way the particular Go engine deals with deteriorated moves, though. Different engines might result in different estimates.)

AJP: Look at some beginner (or even non-beginner) games: ever see someone make death in gote, or self atari? By comparison, a random move starts to look pretty good.

Andreasteckentrup: Even the worst beginners moves are better than random play, if the beginner wants to win. If a beginner plays self-atari, the chance the random player would capture the next move are still quite low, while the beginner would still capture a stone every 4 or 5 moves.

blubb: Comparing the worst moves of a typical beginner with average random moves isn't fair, is it? Experiments with weakened bots at kgs suggest that very beginners who have just understood the rules may be around 90k ... 50k, but that's hard to measure for they improve so fast, like several stones in a single 9x9 game.

Anti-Go - worse than random play

AJP: Random play is at the bottom of the scale? I bet I can play such that random play wins every time. (I play A1, then A2, A3 etc.)

blubb: Well yeah - sorry to have omitted this - here I am considering the positive half-axis only, with random being zero. Of course, worse is possible. Worst play however, is a rather obscure thing, and might not suit well as absolute reference. The entire negative range behaves very different from what we usually treat as Go.

aceofspades: I firmly believe that the worst possible player is passing every time. Many players object because this is a passively bad strategy, but what these people perceive as 'actively' bad play is merely using your stones to destroy a previously built-up advantage which never would have existed in the first place without somewhat sensible play. This is somewhat like the proof that the first player always wins in Hex: besides the first player imitating any perfect strategy for the second player, his first move can only help him. In Go the situation is not exactly the same because a stone of yours can sometimes be harmful to you, but passing would allow the other player to do that harm himself anyway.

Alex: Well, if you define "worst" as "leading to a loss by the largest possible margin," and you're using territory scoring, then passing isn't it, since then your opponent could win by at most 360 points, assuming that a single stone on the board would be necessary and sufficient to count the rest of the board as his territory under that ruleset. To lose by the largest possible margin, you would have to fill and refill the board with your stones as many times as possible, letting (or forcing!) your opponent to capture them all each time.

tb: Alex, that depends on which area scoring rules you are using. If you are using AGA rules, then each pass transfers a prisoner, and it ends up coming out equal.

Alex: Even if the average random move is better than the worst move near the beginning or in the middle of the game, the play will eventually degrade to that level. Suppose the random player is black, and has an equal probability of playing any open point and passing. If white simply continues to pass and let black play every point on the board (playing only when black passes), evenually black will fill the whole board and put himself in self-atari. The cycle is then free to repeat. How can we even conceptualize random play as Go if the game is unbounded, never-ending?

Chris: Although you may have a point, you example does not seem to be right. At the point where Black only has one-point eyes White cannot respond to a pass by making a move. If Black has ten one-point eyes the probability that he will put himself atari instead of passing before it is too late is only 2/11, so quite small.

GoJaC: Also, in truly random play, you can't predict when black will pass. Your previous move will be a pass by the above method... two passes in succession. You can never pass if you want the game to continue, because black may pass at any move.

excession: would the probablility of passing be the same as making any particular move, or 50% say? Seems like you'd need to decide...

Phelan: As has already been said, the probability of a given move, at any time, is equal to 1 divided by all legal moves, including passing (probability = 1/(LegalMoves+1)). So the probability of passing is the same as making any particular move. It has already been discussed.

Worst possible player is NOT passing every time. Consider a slightly modified version of <random play>, that passes only if it has no legal move. Facing <always pass> with black, this algorithm will fill the board until there's only one square left. In territory scoring, <always pass> wins by one point least than the komi. Furthermore, <random play + consider capture as an illegal move + pass only if no legal move> is even worse : it won't make any capture point and will hardly make more than one territory point. If suicide is allowed, it will loose by an infinite margin against any of random play, always pass, or a normal player.

Kay?: Speaking from a cryptographic background, a worse-than-random player would actually not be ranked worse than random, because they have more go knowledge than the random player. In particular, I can trivially construct a go player from the "worse-than-random" player that asks our "worse-than-random" player what move to make, then makes a random move that is not that move. So random is in fact the worst possible, in terms of go knowledge. If you're not measuring by go knowledge and instead measuring by games lost, then this new game of losing is likely just as hard as real go.

Phelan: You are assuming that rank is a measure of Go knowledge, instead of a measure of a win-loss record against other ranked players. Other than that assumption, I agree with you. A random player has zero go knowledge, but is not the worst possible player. To actually determine what the worst move is at any moment, the more go knowledge one has, the better.

RJHacker? There is an interesting (in my eyes) discussion of Kays knowledge problem, including Alexs cycle problem at MostIgnorantBotImaginable