I actually don’t think the incompleteness theorem applies here. Since there are a finite number of game states, you could theoretically compute the perfect game, we just don’t have the hardware to do it.
2 Likes
Recursive definitions need a base case (as the minimal algorithm does)
I think that the incompleteness theorem is not a problem for proving that a perfect player can exist (the minimax algorithm is already sufficient for that).
But for a perfect player that maximizes the handicap that it can give to all go playing entities that could possibly exist (strong and weak), I think that it needs to perfectly predict all moves of all possible go playing entities (so it can prune good moves that those entities miss and then minimax its way to the highest handicap). Proving that this prediction ability is possible is a much bigger problem, I think (and it may run into the incompleteness theorem and possibly other problems).
1 Like
Godels theorem is about formal systems (any sufficiently powerful formalized system will still have unprovable theorems). The problem with the “best vs anyone” problem is that the constraints aren’t really formalized. And even if they were, I sense that it would still be a somewhat finite state-space.
2 Likes
I thought it would also apply to things like self-simulating systems.
1 Like
Indeed any position has a perfect komi, and the reasonable way to make a perfect player play handicap is to have them play towards the best result they can guatantee. For instance, with 2 handicap stones, no komi, maybe a game between perfect players would end with B+21. When a perfect player plays against a non-perfect player, it simply chooses some perfect move (a move that doesn’t change the perfect komi). This guarantees it to lose by at most 21 points, but of course everytime the other player makes a mistake they catch up some number of points.
Having a player take into account the opponents strength (to make overplays which it knows can pay off), is a different sort of idea. In a certain sense such a player is stronger, but objectively it is making some mistakes. And it anyways gets a bit hard to talk about. We could model an arbitrary player as a deterministic AI which always plays the same move in a given position, or perhaps it plays each move with some probability. In that setting there is a player which maximizes winrate (or alternatively tries to win by as large a margin as possible), against a particular player. But that’s not how humans work, so pretending that there is some entity that can predict all your moves, is somewhat of an unrealistic thought experiment 
(but of course it may still be useful, even if it’s unrealistic)
6 Likes
You’re probably right. Even a random player in a finite universe may be predictable when you can run a sufficiently good simulation of the universe.
3 Likes
Yeah I guess it depends if we consider the universe deterministic or not. But more of a physics problem I think than a math one!
2 Likes
I would call this a perfect “god” player: a perfect player that assumes you play as strong as it does itself (even after seeing evidence of the contrary).
I would call this an imperfect “devil” player: a semi-perfect player that assumes its opponent will make specific mistakes (based on some knowledge about the opponent acquired before or during the game) and it plays moves to exploit those likely mistakes (but the opponent could play some unexpectedly strong moves, so it is a somewhat risky strategy). I expect that this imperfect “devil” player can give more handicap than a perfect “god” player could, but it will crash and burn in some of those handicap games.
I would argue that a perfect “devil” player is much stronger: it doesn’t make assumptions about which move its opponent will play. It can simulate its opponents (including itself) perfectly, so it knows with 100% certainty which mistakes its opponent will make and it can exploit that maximally. It cannot beat a perfect “god” player, but it should be able to give (much) more handicap than both a perfect “god” player and an imperfect “devil” player.
3 Likes
Not a problem here, Go is a finite two-person perfect information game, thus is determined (which is a theorem by Zermelo). You’ll need to run into infinite length games to get into statements that are not generally provable with ordinary mathematics.
In fact, that’s a good rule of thumb for anything related to incompleteness, halting, undefinability, you need at least an infinite number of possibilities to run into trouble.
To describe what a perfect player is, you first need to describe what a strategy is. A strategy is not much more than a function that takes a board state where it is your turn, and provides you with a move. A strategy is winning for, let’s say, Black at a certain position, if Black will win the game by following their strategy regardless of the strategy that White uses (so anything White does is being considered by Black, and countered).
So, since Go has a finite number of different board states, there are only a finite number of possible moves at each position. Then, the number of strategies is finite as well, as this is just a combination of a possible move for each position.
The moral of the story, is that perfect play has nothing to do with predicting your opponent’s strategy: it counters every possible strategy.
Note that this would then still constitute a perfect player: its strategy only differs from a perfect player when it is in a losing position. When in a winning position, it could just switch to the strategy of the perfect player.
5 Likes
Also in human games, one can observe both proper “god”-like playing styles and tricky “devil”-like playing styles.
This is somewhat relevant to rank spacing and my “Only Kyus” suggestion, because a “devil”-like white player can probably give more handicap than a “god”-like white player of the same rank. So which of those handicaps should a weaker player use to estimate his own rank?
1 Like
Before you determine komi first you have to make the Universe…
11 Likes
The way I interpret the devil player is that it will maximize score against an opponent, so it will continue to play trick moves even if it is ahead!
1 Like
I wonder if building a ranking system around trick players even makes sense. It seems (and this is purely speculation) like a league of devil’s players may never stabilize haha.
3 Likes
Indeed this seems the reasonable choice for the “devil”. But even if you consider a god-devil hybrid, which plays like god when ahead and like the devil when behind, I wouldn’t call that perfect. To me, perfect play does not depend on komi. It is making one of the score-maximizing moves in any position. So let’s say that you’re losing by 10 points, and there is a tricky moves which may let you win if the opponent missplays, but if they respond correctly you will lose by 20 points. I would not call such a move “perfect”. (clearly this is just a question of definitions, but I personally think this particular definition of perfect is the most useful - we need another new word for “winrate-maximizing play against a particular player”)
5 Likes
I see it as giving maximum (komi) handicap, but perhaps that’s basically the same thing.
1 Like
This feels closely related to the fact that small handicaps are much more reliable than large handicaps. To win in a 9-stone handicap game (where the rank difference is actually 9 stones, and not 20 stones or whatever), you probably have to make some “trick plays”. In other words, our handicap system is actually built around players that are at least slightly devilish (because we are… 
).
But for theoretical analysis, it’s sort of nicer to pretend like everyone is trying to play like an angel instead 
And I believe we can basically do this at small handicaps of say 1-2 stones. In a 2-stone handicap game, you can just play normally, and slowly catch up during the game, no trick plays necessary.
(well, of course you may still fall behind throughout the game, and may have to complicate things… so the effect is always there, even in even games. But trick plays are certainly less important the less handicap there is)
4 Likes
But, how is this different from an actual “bad” player? There is no reason why this would be a strong player: they tend to lose to whomever can read out their trick moves.
It’s possible to maximise score while simultaneously playing perfectly. In fact, maximising score should lead to a perfect play.
The general idea I have about this, is that it is not the devil player that decides the score lead, it’s the opponent that makes the mistakes that decides the score lead. Any and every point that the devil receives above what is possible through perfect play, is due to the opponent granting it to them.
I also do not see how to formulate a strategy that encapsulates the idea of playing for a bigger lead on the cost of needing your opponent to make a mistake. How to determine that a move is “difficult to read”? The devil would need information outside the game of Go to be able to formulate such a strategy, such as information about the strategy of the opponent (i.e. common mistakes). It cannot be a universal strategy therefore.
3 Likes
I think the devil has mind-reading/predictive capabilities as well. Doesn’t give it an edge against a perfect player, but definitely gives an edge against an imperfect player. (And it won’t always play the same moves as a perfect player)
1 Like
In this case, how would the devil player play against itself?
1 Like