5
$\begingroup$

Komi is the additional number of points given to the non-starting player in the game of Go.

For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it was lower, even 2.5 points.

A question arises: what value it should be so that it is a fair game? Draws allowed.

(This handles the unlikely to me case, in which Go is already fair, without komi. Then one would just discover that komi should be 0. So, I'm not assuming that Go without komi is unfair)

The following idea came to my mind:

Let's take e.g. 5x5 board and an agent A. Let it self-play many games, plot the average of points won by the starting player in the end of the game, stop simulations when the value converges.

Do the same for 6x6, 7x7 board and so on up to 19x19 (or further).

So, for a given agent A, we will have a list of mean scores for a starting player on increasing board sizes, e.g. [25, 14.2, 9.6, ...], meaning that on a 5x5 board, on average, the first player wins with 25 points. On 6x6 board, on average, with 14.2 points, and so on. These could be the komi values.

Now, maybe the values in the list will be always decreasing. Maybe they converge to some value as the board size grows. Is it already described somewhere?

The values will probably depend on the agent A. Maybe one could also find a relationship between the strength of the agent A and the values in the list. E.g. maybe the stronger the agent, the values decrease slower.

So, one could start with a weak agent. See what values in the list it produces. Then, improve agent A (using e.g. some reinforcement learning algorithm or giving more time to the search) and produce another list of mean values. And so on.

Maybe the variance of results (or some other function) could be a nice measure of how far the current agent is from the optimal one (because the optimal one vs optimal one will always result in exactly one outcome, variance 0). So e.g. maybe agent who has scores vs himself in [-2; 2] is closer to the optimal one than the agent with scores in [-20; 20].

Say for the weakest agent A the list would be [25, 14.2, 9.6, ..., 6.6] and for the strongest agent A (ideally this agent would play optimally) [25, 18, 14, ... 8.2]. Now one knows that the sensible komi for 19x19 is in the range of 6.6 and 8.2.

My questions are:

1) Have you seen something similar done before? I would be happy to read. I've read Solving Go for Rectangular Boards, which solves Go up to 5x5. If such analysis wasn't described, I could do one out of curiosity.

2) Do you see some problems, refinements or other interesting things to check?

$\endgroup$
  • $\begingroup$ This is roughly how Komi values have been determined, with computer players replaced by human players. $\endgroup$ – Yuval Filmus Sep 19 '17 at 10:24
  • 3
    $\begingroup$ To me, this seems like more of a question about Go than about computer science. For example, it seems much more likely that an answer would be wrong because it contained bad Go rather than bad computer science. $\endgroup$ – David Richerby Sep 19 '17 at 10:47
  • $\begingroup$ @YuvalFilmus Yes, one can take human data, subtract used komis and see what were the average scores for first player. However this seems much more difficult setup to draw any conclusions from. More noisy. Because every agent (human) was different. Humans also learn over time, get tired etc. Also the number of human games is limited. With agents, one can have exactly the same players and let them play as many games as desired. $\endgroup$ – Adam Stelmaszczyk Sep 19 '17 at 11:43
  • $\begingroup$ @DavidRicherby It indeed is a question about Go, I haven't found such tag. In this question I view Go as an abstract strategy game and game theory is under mathematics, which seems to overlap with theoretical computer science domain, e.g. because of the methods used (game trees, neural nets, reinforcement learning etc). I think I see what you mean that an answer would have "bad Go" - as in komi from artificial agents (especially optimal ones) might be bad for humans (make them unhappy). I agree. i just thought about such analysis of abstract game. Doesn't have to do anything with humans play. $\endgroup$ – Adam Stelmaszczyk Sep 19 '17 at 12:01
  • 1
    $\begingroup$ @Evil Related to what I wrote above. I didn't use word "fairness" in my question, since humans are out of that question. It's just like one is given a game as in game theory, strictly defined as a set of states and actions and you have to e.g. find Nash equilibrium. No fairness, if people like to use it etc. So, the board games stack exchange is the opposite where I see this question belonging too. Thanks for the first link. They used optimal agents, that's why size of the boards was so small. I did some googling before, I proposed something a bit different, computationally tractable. $\endgroup$ – Adam Stelmaszczyk Sep 19 '17 at 12:15
2
$\begingroup$

From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (see Tablebases, Fermat, Knights and Knightmares - you might need access to ICGA Journal). Optimal solutions frequently destroy any intuition about a game. I expect that even AlphaGo Zero approach would be not enough even for small boards like 7x7 to approximate the optimal komi value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.