Mathematical Bounds of Komi

    Keywords: Go term

Has any upper or lower limit for the 'correct' komi been proven mathematically?

Jared: It seems to me that the discussion of the upper and lower bounds are almost two separate topics.

Jared: Also, is it possible that discussion of the actual correct komi is a separate topic and should occur elsewhere, perhaps in the discussion page for komi?


SAS: It's easy to prove that 0 is a lower bound for the correct komi and 361 an upper bound. It doesn't seem likely that any useful bounds could be proved. But for practical purposes we know the correct komi anyway - as Roger Clegg once said "[ext] it is plain as a pikestaff that it is 7".

Arno: I agree that 361 is an easy to prove upper bound, but how does the easy proof for 0 as lower bound look like? That assumes that having the first move is an advantage. How do you prove that? [1]

SAS: You don't have to prove that being Black is an advantage, only that it isn't a disadvantage. It isn't a disadvantage, because Black is allowed to pass his first move.

For simplicity I will assume that two consecutive passes end the game, but other rules should give the same result. Let's suppose that playing the first move (as opposed to merely passing) leads to an n point loss. First suppose the komi is 0. Then Black will pass and White will pass, and the position on the board is a jigo, and so the game is drawn. Now suppose the komi is -n (reverse komi of n). Then Black will pass. Now, a White pass will lose by the n reverse komi, but a White play will lose by the n reverse komi plus the n point disadvantage of first move. So either way, the -n komi (or any other negative komi) gives a win for Black.

Arno: The proof for the upper bound goes something like this: if Black starts and White plays no move, Black can win by at most 361 points because no captures have occurred. Thus the upper bound for komi is 361, otherwise White would always win.

My guess is that the correct komi is somewhere between 0-12 points. But that I cannot prove.

Miz: After actually thinking about it a bit I see that 0 and 361 are of course obvious bounds. Improving on the 361 might not be too hard though. We'd just have to prove that White can live with some points. :) I agree that komi 7 feels about right for us humans, anyway.

KjeldPetersen What if you play mirror Go, this proves that white can get close to the same points as black. What is the upper bound now ? Black can only get extra points from the center of the board. If the upper bound of komi was close to 361, black has to capture the whole board. Now white has only to divert from mirror-playing ones, and black can't capture the whole board. So the upper bound can newer be 361.

mgoetze: Really? I am very much interested in this proof, please provide it. :)

Anonymous: To prevent manego from winning, wouldn't komi have to be at least 1.5?

unkx80: I think manego is a non-issue. See countering mirror go.

Daniel: well it occurs to me that mirror go does bump the lower bound up to 1 even with the countering strategies manego does provide an initial influence advantage that has to be worth at least 1 point providing the player is not going to let their own stones die.


[1] removed my "thinko" of negative komi. I was thinking along the lines of not being allowed to pass on the first move, which of course is not what go rules are about. -- Arno


Kungfu:

Well, set a lower bound at 0, and an upper bound at 361. So it's somewhere between that.

As I see it, the object of komi is to get the winning percentage down close to 50%. So then as proof I present that komi 12 is surely sufficient to give White more than a 50% winning percentage.

Now considering that White is supposed to be the slightly stronger player, if both players are of equal strength, then Black, starting with sente, should win, due to the proverb that you should give up a stone to get sente. Komi should then be at least 1, so I propose 1 as a new lower bound. Now also considering that you should add a move and then sacrifice, a lower bound for komi should be 2.

To calculate the optimal value of komi, theoretically allow draws in the ruleset, and then choose komi to maximize the possibility of a draw.

You should get a line graph with a point in the middle, and then values of komi indicating percentage along that line. White is on the left, Black on the right. Which side has the greater % of draw based on +-0.5? (I.e. there should be some statistical uncertanity at 50%). Give jigos to that player.

To make it more clear, if you get a value of x for optimal komi based on maximum probability of draw, and a 52% win (for white) at 0.5 but a loss of 47% for -0.5, then there is a 2%-3% discrepancy around x komi. Since it is more difficult for white to win with x komi, then White should win jigos.

The same statistical analysis can be used to determine the value of x handicap stones, for x-handicap-stone games only. Just analyze x stone handicap games and recalculate the komi based on maximizing the probability of a draw.

Does this sound reasonable? Why doesen't someone do it? It might be PhD material. Get a grant to run a Go club/server? I'm there ;)

But to prove it mathematically, using bounds, you might want to come up with an equation for a limit. How you structure it would be the key.

-- Kungfu

SAS: Yes, you can examine statistics for games using various komi, preferably between very strong players (as they are less erratic). The statistics that I've seen indicate that the correct komi is 7. (See, for example, the link that I've added for the Roger Clegg quote at the top of the page.) But this is just statistics. However convincing it may be, it is not a mathematical proof of anything. As I said above, it doesn't seem likely that any useful bounds could be proved.

lavalyn: You assume that the rulesets can always end the game in a scoring position - and thus ignore situations such as triple ko or eternal life. By some odd fluke, there could be White perfect play leading to eternal life or can force a void position optimal (i.e. to avoid it is to let White win). Komi can actually be zero without logical fault under standard Japanese or Chinese rulesets (superko notwithstanding).

SAS: But in order to prove things about Go, we need a logically consistent and complete ruleset. No such ruleset that I know of allows a game to end in no result. (Japanese rules are not complete and consistent. I don't know about Chinese rules - see my question on the Chinese Rules page.)


RobertJasiek: Although Japanese rules are incomplete and equivocal, they will be explained completely and unequivocally by the Japanese 2003 Rules. I.e. they will explain professional Japanese rules. Verbal Japanese rules of amateurs need some modifications so that their explanation becomes sufficiently incomplete and illogical...


Wedge: Excuse me for expanding the discussion a bit, but I am a mathematically minded person who is new to Go and I am trying to understand Komi from a slightly different perspective. First, I use the definition of Komi as the integer to add to White's score that will always bring the game to Jigo if both players play perfectly. As the previous discussion highlights, it is hard to say much about a 19x19 game, so I thought I would consider NxN games starting N=1 and see how far I can get.

Here are some interesting questions to consider along the way. How does Komi change as N varies from odd to even? As N -> Infinity, the amount of territory near the boundaries grows like N but the amount of territory in the middle grows like N*N, so what is the N at which the best strategy changes from controlling the boundary to controlling the middle? Is it anywhere near N=19? What is the N -> Infinity value for Komi?

Here's my thinking so far. For 1 <= N <= 5, if I assume that I understand the rules accurately (I am a novice after all), perfect komi should be trivial:

     Japanese scoring (jp)    Chinese scoring (cn)
  N=1     Komi= 0                Komi= 0
  N=2     Komi= 3                Komi= 1
  N=3     Komi= 8                Komi= 9
  N=4     Komi=15                Komi= 16(?)
  N=5     Komi=24                Komi= 25

The basic game goes Black first plays as close to the center as possible and then White then Black passes. If White plays then White loses and if Black plays a second stone, Black loses. So, this saturates the N*N-1 (jp) (or N*N (cn), respectively) bound discussed above.

blubb: I dared to supplement your komi list with the appropriate values according to chinese rules. Hope that's ok. For N=4, I don't see if white can get a seki due to superko. (I haven't really thought about that yet.)
Eli Dupree: At N=2, if white plays in the corner across from Black's first stone, then whoever would play next would get captured. With superko, they'd lose; without superko, they could get into the same position (black in one corner, white in the opposite) a few moves later. Either way, it's even, so komi should be 0.

At N=6, something interesting happens. The playing area is now big enough that Black can no longer control the entire board with the first stone, so the upper bound is no longer saturated. Now, after lots of fooling around with games on N=6,7,8 using combinations of GNU Go (sort of assuming that if you let a program like GNU Go run long enough, it can completely determine a game of this size) and my brain to cross check that the computer isn't doing something stupid, here's my current guesses for komi:

  N=6  Komi~ 3
  N=7  Komi~ 8
  N=8  Komi~17

No guarantee that these results are true, but it looks like the Komi for N=8 is much larger than the current estimates for N=9, so what is different between N=8 and N=9? Doesn't look like there is much hope for a smooth extrapolation to N=19. There is more info on the Small Board Go page, where you can eventually find a 6x6 game with Komi=4, so maybe I'm in the right ballpark.

I'd be interested in hearing about anyone else's exploration in this direction.


Bill Spight: Of the square boards, the even boards have low komi, and the odd boards seem to peak at 24 for the 5x5. Ted Drange and I did some small board research ([ext] http://www.mathpuzzle.com/go.html) in the 1970s, he more than I.

I conjectured that the proper komi for an even square board for N >= 2 was less than or equal to the proper komi for any such odd square board and greater than or equal to the proper komi for an smaller square even board. In other words, the proper komis for even square boards of size 2x2 or larger form a monotonic increasing sequence approaching an Ultimate Komi. In like fashion, the proper komis for odd square boards of size 5x5 or larger form a monotonic decreasing sequence approaching the same Ultimate Komi.

Japanese komi for the 2x2 and 4x4 is 0. I do not know about the 8x8, but I would guess that it is around 5.


Ben Axelrod: I mean no offense, but I think that coming up with the trivial bounds on komi of 0 and 361 is rather pointless. Surely, we are not approaching the problem correctly. I propose two novel methods:

For the first method, I will use a slightly different definition of komi than the one above. Here, komi is an integer to add to white's score that will bring the game to jigo about 50% of the time, in a game between two players of exact equal strength. This doesn’t help us much because there are no two people with the exact same strength… However, a computer program will always play at the same strength. (Granted that programs do not play like humans and are nowhere near Dan level, but I think I read somewhere that Komi should be board size and player rank independent.) So I think an interesting and meaningful experiment would be to have a good program play against itself many times and record the score difference. The average of that score difference should be close to a mathematically accurate value for komi. Well, it will at least be in a standard deviation of it…

Squint: The "correct" value for komi should be that for two perfect players, presumably, which Gnu Go is not. I suspect the value of komi for a _good_ game will be different for weaker players. Imparticular, between two 30kyu (complete beginners), I think a komi of 0 will probably give the best results, the first stone becomming quickly lost in the noise. I'd also extrapolate from there to suggest that higher ranks derive a greater advantage from the opening sente, and that komi should increase as a function of ability. Of course, since different Go communities have different ranks for like abilities amongst their members it would be rather hard to specify what this should be, although it opens the interesting thought that a players rank could be expressed in terms of the komi which is appropriate at their level of play, and so become independent of location or club. (Impractical, yes, but an intriguing principle).

The second method is less anylitical. I propose a shift in thinking. Maybe we should not think about komi as the amount black will win by at the end of the game, but rather how much advantage black gets by playing first. It seems to me that the advantage black gets by playing first is the influence of that first stone on the board.

[Diagram]
Blacks first stone influence  

From this analysis, it looks like 5 is a reasonable amount. I am not sure if either of these methods will work, I am still rather new to Go. I just thought I would post a new perspective.

Evand: Neither of these methods quite gets to anything mathematically rigorous, but the first is what is basically done in practice. Analysis of profesional games would suggest that with komi 7, black and white each win about half the time. So, we play go with komi ~= 7. That's a little bit simplified; there are better explanations elsewhere on the site.

Second, computer programs produce consistently different results than humans. For example, Gnugo has very distinct play styles; I believe someone determined at some point that it needs a larger komi than people when playing itself.

As for the advantage gained by the first stone -- the easiest way to define that is in terms of correct komi, instead of vice versa. That is, the advantage of the first move is, by definition, the amount you can win by if you play first. Your method of looking at the area around the stone is far too local -- it doesn't take into account the fact that different plays are different in terms of how good they are.

There are a large number of ways to think about komi; the question posed by this page is a rigorous mathematical one, which isn't all that practically useful, imho. Proving 0 and 361 is fairly trivial; proving something better than 0 for a lower bound would (I'm guessing) be on par with solving the game in difficulty. Proving something better than 361 amounts to proving white can live; that's actually a non-trivial problem, and would probably require a lot of work on a computer program to find a solution.

HandOfPaper: As far as rigorous mathematical proofs are concerned, what if we just try to prove what we can about go and then see when we're in a position to prove upper bounds on perfect komi that are better than 361? We already have things like the Two Eyes Theorem, which gives a rather simple sufficient condition for the life of a stone formation. (here I am excluding wide eyes from the notion of an eye--- obviously this can be extended much further, but I feel lazy now) I suggest trying to prove something like:

Optimal play will never involve filling in a one-point eye which is enclosed by a single group of stones.

Here, of course, "group" is used in the strict sense of the word: If we look at the 361-vertex graph which is the go board and see moves as coloring vertices a certain color, then a group is a monochromatic connected component of the graph.

Tim Hunt: Your conjecture is false:

[Diagram]
corner  

Optimal local play for X is to fill the eye, killing white without a ko. It would be easy to make this into a full-board position.

HandOfPaper: Thanks for the counterexample. How about this amended version? :

Optimal play will never involve filling an eye that is surrounded by a single group of stones unless that eye is in the corner.

Is getting too off-topic? Should this move to another page? Is there another page better suited to this kind of discussion?

DougRidgway How about Holigor fills his own eye?

[Diagram]
White to play  

unkx80: A picture says a thousand words... so here goes, an eye at the side.


HandOfPaper: I thought of a counterexample, based on the way Rectangular Six In The Corner leads to ko:

[Diagram]
White to Play  

This just needs to be extended to a whole-board position where white wins the corner because white has more ko threats than black does.

unkx80: Unfortunately this is not a counterexample.


Rakshasa: IMO i think it's pointless to try finding the mathematical bounds of komi since if you can find the bounds you can find the optimal play. You can't find any bounds unless you can rigorously prove that there is no moves that would give a score above or below the bounds.

Kungfu made the suggestions for equations with limits, this won't work at all. We arn't dealing with calculus here. Each possible move has an interesting value that is the score if both sides play optimally the rest of the game. This value is not predictable except for the optimal play, which is constant. If you can't predict it you can't make an equation to take the limit of. (If you have a way to predict it... then you can find the optimal play anyway)

It is like having a great pile of numbers and no +,-,/,* operators. We can increment and decrement but there's no theories to get there quickly. Everything is empirical, and only in localized situations can we make theories that hold.

ilan: But au contraire, one can certainly imagine a situation in which the exact value of the komi is rigorously computed yet without having any idea about the exact sequence which achieves this. One can even imagine that this last fact can be proved rigorously without knowing a single specific example.

Rakshasa: As i said, you may be able to compute the exact value of a move if you have the right theorems. But my point is that you can't predict any bounds unless you can rigorously compute the possible values of the moves. (Except for certain situations)

togo: As ilan said, it is possible that we do not need an optimal play. And it is possible that we do not need the value of any special move. Indeed that would be a very, very normal thing to happen. And this applies to the exact Komi. We already know, that we do not need an optimal play for finding bounds (0 and 361).

There is a very easy way to lower the upper bound, Evand already presented it: Prove the possibilty of a living group for White. Contrary to his belive it is very easy: Just make a brute force attack for the first n moves. And here I present the second idea: Place White's stones in the vicinity. Third idea: Look for a second group in another region of the board (and so on). Fourth idea: If you found a living group, extend it in simple ways. My guess is that we would arrive well below 100 even with a simple PC.

Spensar: How do you define "Optimal Play"? Is it playing to maximize the minimum of the difference between your score and your opponents, assuming that your opponent will always move to do the same, and that both players are fully aware of all possible move trees?

Bill: See Optimal Play. :)

Batavia?: What a lot of people seem to be forgetting here is that komi is not the value of the first move. It's the difference of the sum of the value of all black moves and the sum of the values of all white moves. Also you can't use specific corner examples and talk about optimal play unless you can show that you will ever arive at that corner using some kind of optimal play. Otherwise you might very well talk about situations that would never occur in real games.

axd: I'm wondering if it is possible to find the limit komi is tending towards when the board size increases to "very large" (I'm avoiding the word "infinity").

Malcolm: The question of correct komi on an NxN board is linked to the second open question on the list of open mathematical questions.


Mathematical Bounds of Komi last edited by 50.23.115.116 on January 26, 2015 - 07:58
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library