Does Kami No Itte Exist

Page moved here from Scartol/Philosophy of Go.

This page collects many contributions to the discussion of Kami No Itte, a Japanese term meaning something like a “god-like” or “perfect” move and made popular by its dramatic use in Hikaru no Go. Topics include:

• On kami no itte:
  • What does “kami no itte” mean?
    • Is it the same as an optimal play?
    • Must it be brilliant or aesthetically pleasing?
    • Does it involve enlightenment?
  • Can we recognise kami no itte?
  • How can we get closer to kami no itte?
  • Is kami no itte attainable for humans?
  • Is kami no itte attainable for computers?
• On perfect play:
  • How would perfect play by computers affect our appreciation of Go?
  • Is perfect play theoretically possible?
    • It is mathematically proven that optimal play exists (even if some contributors doubt it).
  • What would be the result of a perfectly played game?
    • This depends on komi. If both aim to maximise their score, it is always the same for a given komi, which can be chosen to make it jigo or a win for Black or White.
  • Is perfect play unique (up to symmetry)?
    • Very many endgame positions have more than one optimal move; this is probably true in many much earlier positions, including those that arise from perfect play.

Table of contents How our knowledge approaches kami no itte Proof of the existence of optimal play Introduction Formal proof Brute force algorithm Final comments Footnotes on the proof Objection to proof, due to unstated assumptions about the rules of Go Further discussion Other interpretations, enlightenment Is perfection attainable? More on enlightenment Various reactions, chaos Is perfect play unique? Attainability (2), decidability Can perfect play lead to a tie? Recognising kami no itte Can Black lose with perfect play? Number of games, element of chance Meaning of kami no itte (1) Kami no itte by committee? God v. kami no itte Does perfect play remove the artistic element Comments on the proof above Meaning of kami no itte (2) The search and its impact our appreciation Evolutionary peaks Bots reaching 5 dan See also

How our knowledge approaches kami no itte

Contribution from Scartol that started these discussions

Let's start with the assumption that a set of kami no itte does in fact exist (I'm undecided, but that's irrelevant for the time being). If there is one, let's consider the methods of discovering it since the dawn of Go.

In the game's childhood, players probably found patterns emerging only after many many games (how long would I have to play before I discovered the notion of atari on my own?). Eventually, masters of the game emerged, and they worked long and hard to perfect their art.

Their knowledge could be compounded by study, meditation, what have you — but ultimately could survive only through books and students, each of which could only be developed so much, so fast. And each of which can only develop / sort through / combine so much material so quickly. Add to this the relatively (to today) small numbers of players, and progress toward the kami no itte could be seen as crawling.

As the popularity of Go expanded, so too did the level of study, and the recombinant degree of complexity. As time went on, masters were able to study each others work/art, and critique it and comment on it. All of this was watched intently by the students, who then became the new masters, and so on.

Enter the computer. Vastly more qualified than the human at simple number-crunching, HAL and his cousins began to race through the relative merits of shape elementals and game threads. But even more significantly, they gave us the tools needed to again raise the level of game analysis exponentially. We can save SGF files, review and comment on them, store them, and ask HAL to crunch them. The race toward the kami no itte speeds up incredibly. As microchips become more complex and AI explodes through its confines, we're probably closer to the kami no itte than ever before.

Suppose we then graph the speed of this progress. Wouldn't it look something like this?

Infinitely close, never touching?  

...where the horizontal axis is time and the vertical axis is proximity to the kami no itte...

If so, then the question is: Will we ever reach it? I'm inclined to say "no," for the reasons outlined above, and because I don't really believe it exists..

— Scartol

It does exist, as proven below, although it's unlikely that we will ever approach it closely. I think your words are right on the caption, but the graph should look more like this:

Infinitely close, never touching?  

— Scryer

Proof of the existence of optimal play

Introduction

Hi! I'm a mathematics student, and while this philosophical discourse is intriguing, I must object in the strongest possible terms to the assertion that kami no itte does not exist. Go is a two-player perfect information game, which always terminates in a finite number of moves. Therefore there is no question whether perfect play exists. It must. Before I give the argument for this, let me do some clean-up about details concerning Go. As you may know, the major Go federations use rules which permit situations like triple ko, in which the game could theoretically continue forever, but then there is also a rule which declares a draw upon the third repetition of the same whole board position. Second, I can give no concrete upper bound on the length of a Go game (practically, no pro game has lasted beyond 450, if what I've read is right). But this is irrelevant. All that matters is whether any single run of play terminates, not whether there is a finite bound on the lengths of all possible runs of play (it is not so hard to devise a combinatorial game which can last 1 or 2 or 45 or 5432459854 moves, or any larger number you care to name, but can not go on forever^[1]).

Formal proof

Now as promised, I will show why any perfect information game must have a winning strategy for one of the two players^[2]. To make argument shorter, we assume there are no draws, though it's trivial to extend the reasoning to cover these cases. We will call the players Black and White, with the convention that Black goes first (it is not necessary to assume that any particular one of the players goes first, or that the possible moves at every point are in any sense symmetric. However, then it becomes not a matter of proving a winning strategy exists for Black or for White, but rather for Black, White, the first player (whoever that may be) or the second player (whoever that may be)).

So here we go: consider the set of all possible positions in the game. The most primitive relation between position X and position Y is: Y is an option of X; that is, one of the moves available to the player whose turn it is to move in X, turns X into Y. We assume the concept of position includes information about whose turn it is to move.

Consider the initial position P1. Suppose by way of contradiction there is no winning strategy for Black or for White. This means there must be some option P2 of P1, in which there is also no winning strategy for either player. To see why, suppose for the sake of finding a contradiction, that each option of P1 was determined (there was a winning strategy for Black of for White). If one such option was a won position for Black, then Black could simply use his first move to go to that position. If all the options were winners for White, then Black would have no choice but to pick the means of his execution, and White's would just have to wait patiently, and then apply his surefire strategy at whatever option Black chose. So we have shown that the supposedly undetermined initial position P1, begets another undetermined position P2 as one of its options.

Likewise, since there is no winning strategy for either side at P2, there must be an option P3 of P2, in which there is no winning strategy for either player. Continuing this way, we generate an infinite run of play P1, P2, P3, P4, ... all of whose positions share the quality of lacking a winning strategy. Consider this carefully!!! I just said we have an infinite run of play such that ... well, it doesn't matter. An infinite run of play is a contradiction in terms, because we know the game must terminate in a finite number of moves (notice how we need not have any idea what this finite number is).

To review, we assumed that there is no winning strategy for our two player finite perfect information game, and then we showed that the game must not really be finite after all.

Brute force algorithm

How would a thinking galaxy find the kami no itte? It would first consider all possible terminal positions in Go (one is which both players have passed, or otherwise agreed the game is over, or in which one player is forced to concede he has no legal move left). For each such position, the thinking galaxy would note who won, and put it in the huge DONE pile in its memory banks (former red supergiant stars, which have been cleverly re-engineered so that each electron's spin records a bit of information). The DONE pile at any point, consists of all the positions for which the galaxy (or Enlightened Zen master, if you prefer) has already determined who is the winner and what his strategy is. Then the galaxy would work its way backwards, placing in its TO DO pile every possible position whose options are all already in the DONE pile. Suppose it were Black's turn to move in some such position X. Then if one of the options in the DONE pile was a won position for Black, then X would be won for Black as well. But if all the options were won positions for White, then X would be won for White too (extend this reasoning to cover draws and drawing strategies if you like). Either way, the galaxy could move X into the DONE pile. Now there would be a new updated DONE pile, so the TO DO pile would no longer be current, and the galaxy would have to form it again. This process would go on and on and on, with an ever growing DONE pile, perhaps making a new DONE pile every day. Now we make use of the fact that Go is one of those games which is finite in the strong sense that we can pick a specific finite number N ahead of time such that every game of Go must terminate in N moves. Certainly the a game can last no longer than twice the number of possible arrangements of black stones, white stones, and liberties on the board, which in turn is no larger than 3^361. For concreteness, let's just say that the longest game possible lasts a zillion moves. Then, it must be true that on the zillionth day, the galaxy finally finds the initial position itself, and following its usual procedure, evaluates it, and places it in the DONE pile. At this moment the galaxy is enlightened.

Final comments

I might point out again, that when we merely wanted to show that perfect play exists (without identifying a method to find it), we did not have to know there is any particular finite upper bound to how long a game of Go could last, so long as any one game could only go on finitely long. The sequence P1, P2, P3, ... of undetermined positions was like a ladder in Go, with each step in the reasoning like an atari by Black and the response to it by White. If the board were infinite, Black could keep running forever, but so long as the edge is out there somewhere, White's fate is sealed from the beginning (here Black is someone who insists there is no perfect play and White is someone who knows better).

Footnotes on the proof

[1] If all games terminate and the players only have a finite number of possible moves on each term, as in Go, then there is a time before which all games terminate. For otherwise one of the finitely many choices of the first player must permit infinitely many different lengths of continuation, as must one of the second player's responses to that choice, and so on: in this line of play the game doesn't end. "Another mathematician"

But this is Konig's lemma, which is not constructive. It might not be possible to find the alleged line of play, even in principle. Instead, just stick to the idea that the goban is finite, so that sets an upper bound, and we can skip all that talk of infinity. "Constructive mathematician"

[2] So far as I know, the first proof of this was given generally, but using chess as an example, nearly 100 years ago: Zermelo, Ernst. [1912] "Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels," Proceedings of the Fifth International Congress of Mathematics, Cambridge, Vol. 2: 501. The title translates to "Regarding an application of set theory to the theory of chess". —Scryer

Objection to proof, due to unstated assumptions about the rules of Go

I doubt that optimal play exists for traditional Go in any reasonable sense. I even have my doubts for modern Go.

There are many closely-related rulesets for Go. Not all of them are clear in all situations, and not all of them are always finite.

Yes, there are some modern rulesets that "clean": they are mathematically unambiguous and have a (very very very large) limit on the length of a game. It is true that each clean ruleset must have its own optimal plays. But there is no guarantee that there is any play which is simultaneously optimal for all current clean rulesets.

Imagine if the "optimal" players must behave completely differently, depending on an obscure ruling about a superko situation for which there is no current consensus. --Fool

Further discussion

Other interpretations, enlightenment

The mathematician again ...

In the above, I assumed the concept of kami no itte refers to perfect play, that is, play that assures victory. But if the literal sense of "God's move" is right then maybe the argument is wrong. God might be a moyo player, like Takemiya Masaki, and perhaps His opponent could find ways to refute His strategy, forcing God to either resign Himself to defeat, or to taking real territory on the sides. Either way God, or Takemiya, might not be happy with the result.

__

Since the subject of Zen Enlightenment has been brought up, I was hoping my efforts at teaching some basic combinatorial game theory might be reciprocated with an explanation of this concept. In the West, there was of course a period known as the Enlightenment which consisted largely in the resurgence of rationality as an ideal, and scepticism about established religious and secular authority. But that is a different way of using the word. So, what is the nature of Enlightenment in the Zen sense? In science, we have somewhat vague but workable criteria of success: expanding the explanatory power and predictive scope of our theories, improving man's control over nature through the development of technology. In Go, a good player is one who often wins or gives a strong challenge to players of high rank, or at least one who creates good positions for himself (certainly there would be something to be said for someone who opens like a shodan, but frequently makes beginner mistakes in middle game and end game, though I gather this isn't common). In art, one can speak of a work being beautiful or expressive. In Zen, there is Enlightenment? But what does this word refer to?

I'd also like to ask some questions about the thought processes other players undergo when playing a game. I wasn't sure where else to put this, so go to MentalProcess using this link if you'd like to respond to my questions.

Is perfection attainable?

Scartol: I feel like Jeff Goldblum in Jurassic Park. I understand that — mathematically — the kami no itte must (does) exist. And yet, in examining the balance between chaos and order (in science, in math, in literature, in societies, in ecology), I grow more skeptical by the day that we humans will ever be able to impose the pure order that we seek, on the goban as everywhere else.

To put it another way: A computer may some day be able to determine the kami no itte and use it to defeat all human players. On that day, Go will cease to be a game, and will be seen only historically as a puzzle that had to be solved by machines (see Manuel de Landa's War in the Age of Intelligent Machines for a synopsis of this line of discussion). 'Players' of the future will simply memorize this pattern and play accordingly. 'Skill' will consist merely of knowing the perfect responses to play that deviates from the pattern of white's that comes closest to challenging the kami no itte.

Meanwhile, what does that mean for humans? It means that — until Deep Blue comes up with the ultimate DONE pile — we have to find the balance between chaos and order. Thus, no kami no itte.

More on enlightenment

(still Scartol)
Now, about Zen enlightenment. In Zen, enlightenment does not refer to pure rationality, as it was used in Europe. Rather, Zen enlightenment is about understanding the way — the way of the Buddha, the way of the universe, the path, whatever you want to call it. It is neither pure rationality or pure non-rationality. It's about balance and self-awareness.

I will let the ancient masters speak for themselves. Here is a story from Paul Reps' compilation Zen Flesh, Zen Bones that does a better job than I ever could:

Everyday Life is the Path

Joshu asked Nansen "What is the path?"

Nansen said "Everyday life is the path."

Joshu asked "Can it be studied?"

Nansen said "If you try to study, you will be far away from it."

Joshu asked "If I do not study, how can I know it is the path?"

Nansen said "The path does not belong to the perception world, neither does it belong to the nonperception world. Cognition is a delusion and noncognition is senseless. If you want to reach the true path beyond doubt, place yourself in the same freedom as sky. You name it neither good nor not-good."

At these words Joshu was enlightened.

Various reactions, chaos

I will have to take a look at this "Zen Flesh, Zen Bones" sometime. In the meanwhile, I hope people do appreciate the proof I gave above. It could of course be made much more succinct, if one used mathematical notations and way of expression. At any rate, I think it is a really beautiful proof of something which is not entirely obvious (when I first learned the idea of a combinatorial game and heard this theorem, I felt like I would have tried to refute it if it were phrased as a conjecture. As it was, I nodded my head and proceeded to construct the proof by myself. Now it seems painfully obvious but that's because I've already thought about it so much).

And yes, the brute-force methods described above, will probably never be amenable to implementation. That's why I used the metaphor of a thinking galaxy with memory banks made of supergiant stars. I can't really claim to know whether with the number of particles in the universe, it's thermodynamically possible to construct a perfect player for Go (even if one gave it the age of the Universe to compute). I suspect the answer is no, but for now, I don't really have the calculations to back it up. Certainly, there is a disparity of many orders of magnitude between the number of possible Go games and the number of particles in the world. Then again, it is possible to add really huge numbers on an abacus with nowhere near that many discrete moving parts, so maybe there is some way around this.

The idea of order and chaos in Go appeals to me. Chess seems like a more orderly game than Go, in that it's not so hard to evaluate a position once you've mapped out the move tree as far as you can. Just look at material, king safety (possibly backed up by a little bit more move-by-move analysis directed specifically at this one parameter), pawn structure, potential for pawn promotion, strength on open files, and a few other parameters. Yet even there, I believe Deep Blue's programmers had trouble developing anything like a mid-game library to complement the database of opening and endgame patterns. I believe one said that chess is just "too chaotic" with small differences in a position disabling any meaningful analogy making (to a known position in a library) in the mid-game. Or at least analogy making that could be implemented using know algorithms. By the way, see Douglas Hofstadter's "Fluid Concepts and Creative Analogies" for a discussion of an interesting architecture for computer analogy making. The idea in that book is to go beyond

1. implementations inspired by mathematical notions like homomorphism and isomorphism, where the underlying conceptual structure (a group structure, a metric, a topology, etc.) is already given,

to

2. analogy making where the conceptual structure is constructed from primitive ingredients together with the mapping between the two analogous situations.

But Hofstadter's goal is to take the first baby steps towards an understanding of how the human mind works, not to create an expert system that can outperform a human at any particular task. At any rate, Go is even more frustrating than chess for a programmer because the move tree branches much faster, and positional evaluation is much more difficult. Hundreds of points may hinge on whether a group is alive or dead, and in real play, this may be depend both on its own independent potential for life, its potential for connecting to other groups (themselves of doubtful status), similar questions regarding surrounding enemy stones as well as faraway shapes, and the whole complex interplay of threats and counter-threats based on these considerations. Attempts are being made to remedy the unsatisfactory state of life and death algorithms with goal-directed reasoning. This strikes me as a good idea, true to the spirit of Go. I am reminded of how Davies begins his work "Tesuji"

The first principle in reading is to start with a definite purpose. There is no better way to waste time than to say to yourself "I wonder what happens if I play here" and start tracing out sequences aimlessly. Tactics must serve strategy. Start by asking yourself what you would like to accomplish in the position in question, then start hunting around for the sequence that accomplishes it. Once you have your goal clearly in mind the right move, it if exists, will be much easier to find.

I think Go is very interesting for the fact that it involves concepts on multiple levels generated from a very simple base, and allowing both formal, numerical and informal, intuitive versions. At the lowest level, we have black, white, liberty, and adjacency. Then we get concepts like capture and connection, as well as life and ko. Then we have sente and gote, strength, good and bad shape, aji, influence, and so on. The excellent player perceives both incisive tactical sequences and grand strategic issues. He is able to leap from one level of abstraction and precision to another. This movement between different levels of thinking and the ability to see their mutual relevance seem to be essential to much of rational thought, but not something which has been implemented very well by machines yet.

Is perfect play unique?

Kami no itte does exist, as proven above. However, it may be interesting to note that it has not been proven to be unique. That is, there may be more than one way to play perfectly. (Even not taking symmetries into account.) As far as I know, there could be millions of equally 'perfect' games.

Does this change anything? Maybe not. Still, it's a nice thought. Maybe tengen is just as good as hoshi. Perhaps those perfect games would even be widely different in style, more so than current professional games?

In any case, I feel that perfect game should be jigo. If komi is needed to achieve that, it must be an integer. It's sort of mystery to me why fractional komi is used so often. We know it can't be mathematically correct, after all. ;) And preventing ties feels philosophically wrong to me.

-Miz

SAS: Professional tournaments are often knockouts or other formats where drawn games would be a problem, so fractional komi is pretty much inevitable there. Amateurs have a tendency to follow professional practice (on the grounds that professionals must know what they're doing), so we end up with fractional komi in McMahon Pairing tournaments, where it clearly isn't useful.

(Part of the discussion here has been moved to Mathematical Bounds of Komi.)

TheNNown?: Indeed, we have not yet proved that kami no itte is unique, but rest assured: I promise you it can be proved that it is, and what's more — it can be proven that in a no-komi game, white (the second player) cannot win, meaning either black wins or the game ends in jigo, or, if the ruleset allows (for example, the Japanese ruleset which has only the "normal" ko rule), the game continues infinitely (if the ruleset doesn't allow an infinite game, then either black wins or the game ends with a tie).

Tas: Nonsense, kami no itte is in no way unique. In the yose it is clear that we might have multiple moves which is worth the same, and leads to the same result in terms of points. The same, I am sure, is even more common (though harder to see) in the middle game and opening. I am quite convinced that it is not enough to count the number of perfect games in millions.
On the other hand I fully agree that perfect play will ensure a black win in a no komi game. It is not proven that the initial temperature is not negative, that the empty board is not some kind of seki, but I'm sure its not.

Attainability (2), decidability

Scartol: As a rational individual, I must admit that I can't find a reason to doubt that we will eventually "find" the Kami No Itte. And yet, let us not forget that at one point we believed that we could eventually find a way to predict weather with 100% accuracy — an idea that chaos theory has more or less voided.

Irving: Here's a partial resolution to this argument. Just consider n by n boards. Instead of thinking in terms of perfect moves, think in terms of the perfect general strategy. Then even though the perfect moves clearly exist, it may be provably impossible to find or understand them efficiently.

Of course, it could be even more interesting than that. The existence of an efficient solution to Go could be unprovable either way given the current axioms of mathematics, in which case we're back to philosophy...

Andre Engels: In theory it's possible. From a position play out all possible games until either they end or they get into a cycle. This will be an enormous but finite number. Because the number is finite, one can calculate the minimax values, and ready. It's all very simple in theory, the only problem is that in practice it takes more than the age of the universe.

Migeru: Assume that we knew, for each position, which moves result in the largest margin of victory or the smallest margin of defeat. One cannot assume that there is a unique such move for each position, so even "kami no itte" will be a branching tree, and not necessarily a single "perfect" game. However, for each line there must be a point where the tree stops branching or where all branching amounts just to transposition of yose sequences. There should be such a thing as perfect yose from a sufficiently advanced position.

Also, Irving's point is very good, and seems to have escaped most contributors to this page: just knowing the optimal moves doesn't mean that you understand them. This is related to joseki, where "knowing joseki" means not only knowing the optimal sequences, but also how to punish deviations from joseki. Just like people can lose to opponents just because they didn't play joseki, it might be possible for someone who knows the entire "optimal subtree" to be stomped by a player who deviates from kami no itte early.

TheDude? So what Irving is suggesting is that the problem of finding the optimal strategy for Go for arbitrary board sizes may lie outside of P. Even if it lies in P it might practically impossible anyway. For instance the recent solution of Primes in polynomial time was mitigated by the fact that the polynomial time algorithm runs slower than known exponential time algorithms until extremely large numbers are involved . . . making the algorithm unlikely to be useful.

Thats a fascinating Turing test, though. Perhaps the ultimate one is the game of Go. — Alex Baxter

Can perfect play lead to a tie?

Neil: Who's to say perfect play can't end in a tie?

Hikaru79: Komi does, which is why they were arguing it's merit. On the TW forum, it was suggested that the kami no itte is a giant, whole-board seki?

Patrick Traill Let two perfect players play a game, each trying to maximise their score. If you take the final score as komi, then perfect play leads to jigo; otherwise you can add or subtract ½ to make perfect play lead to a win for White or Black respectively.

Recognising kami no itte

I, for one, think that even if kami no itte was found, nobody would realize it. First, nobody is entirely clear as to what it is! If it is a game that is won by every point on the board (certainly could be some people's perception of perfection), then I have seen kami no itte used against me in my n00b days. If it is a draw, then kami no itte is played out every single day. If it is some move that seems to solve every problem a player has on the board simultaneously and turn the game around 360°, then it is purely a matter of personal taste... my kami no itte may not be yours. Because I'm not entirely clear on this, I think back to Hikaru no Go. Sai wanted to obtain kami no itte. Obviously, he was not looking to obtain a god-like knowledge of the perfect response to any move that would allow for a perfect response to every other possible subsequent move. In fact, it is highly suggested (although never said outright), that kami no itte is a MOVE, not a game or a system of equations. Which is what leads me to my theory, which I am sure I am not the first to imagine. I believe Kami no Itte is enlightenment in the Go sense. It is when you FEEL you have made the perfect move, that you have advanced to your limit. Besides being the only plausible definition, it also seems something that a 1000-year-old ghost would be seeking. =P

While I am not denying all the calculations previously made that prove that Go can someday be solved, I am sincerely hoping that this is not what is meant by kami no itte. Isn't kami no itte supposed to be something worth striving for? Turning go into tic-tac-toe is not my idea of unfinished business.

HelcioAlexandre: This is a little bit off-topic since its not about Go, but it's related to the discussion. Check this article about Perfection in Checkers

Velobici: If kami no itte is perfect play, then its easy to understand what it means. To take a very simple example, most folks learn perfect play in tic-tac-toe during childhood. Perfect play means that you can not lose when you have the first move. In the case of tic-tac-toe, perfect play by the second player as well as the first always results in a draw. This is why adults don't play tic-tac-toe, except to teach children the game.

Regarding perfect play in Go, we have to extrapolate forward from the current situation. Given the size of the goban and the abilities of human beings, I dont believe that humans will ever develop perfect play in Go. Computers, in time, may be programmed well enough to beat all humans and even give handicap stones to the most successful human players. At that point, computer programs, particularly ones that can change over time (neural nets are a currently available example, genetic programming another) may continue to increase in strength. Whether they will ever reach a level of play that makes go like tic-tac-toe, I have no idea. It really doesn't matter. Because Go is simple enough and difficult enough to fascinate humans, even if computers are much better.

Can Black lose with perfect play?

arturhonzawa: can't it be that with perfect play from both sides (and komi) results in black losing? Everybody seems to be assuming the opposite, but maybe perfect play by black would be to resign before placing the first stone ... IMHO it's not proven that kami no itte exists (if that means that black can win by making the right moves), what's proven is that perfect play exists, which results in making the difference "black's points — white's points" as large as possible, which doesn't have to be positive. Please some mathematician give his opinion on my view ... I'm just an engineering student

Rich: If it were the case that the second player must win with kame no itte, black should pass. In which case, white passes; kame no itte is thus to not play Go at all.

See Mathematical Bounds Of Komi to refute this argument.

Suppose that go ends with a win for black, with perfect play on both sides. In this situation, perfect play for white is different depending on who is playing black. If white knows that black is a perfect player, then _all_ moves are equally perfect and equally imperfect. Otherwise, perfect play for white is to exploit black's imperfections.

This is true for other games too, such as rock, paper, scissors. You cannot say that some move is perfect play, unless you know who the opponent or opponents are. Against humans it might be one move, against computers a second, against God a third,

malweth Rock paper scissors is at best a psychological game and at worst a game of chance. Although Go has some psychological aspects, there are no random ones other than the identity of your opponent.

spazdor Malweth, have a look at RoShamBot?. ( http://chappie.stanford.edu/cgi-bin/roshambot ) The psychological element of Rock Paper Scissors is surprisingly important.

Number of games, element of chance

It also wasn't mentioned that the total number of Go games (not those resulting from perfect play, which is unknown) is on the order of 10^90 (give or take 10^89 ;). The estimated number of H atoms in the universe is 10^79. Where does this leave Kami no itte? /malweth

Patrick Traill According to Number of possible Go Games#tco3 (the section Number of legal positions), this has been calculated as ``~2.082 × 10^170`` for a ``19×19`` board.

Ellbur: For us humans, there really is a significant element of chance. We play imperfectly. We don't know the best move in every situation. For this reason, we may need to take risks, to plan for an uncertain future, or to judge our opponent, none of which can be done perfectly.

Meaning of kami no itte (1)

Kiryoku: I believe that having the kame no itte means that you know the perfect response to every move any of your opponents can make. If two players who both have the kame no itte play against eachother, komi should cancel out the fact that black got the first move and it ends in a tie, meaning white wins.

Of course, it's pretty much impossible for a human being or even a computer to ever achieve this.

Kami no itte by committee?

Gotjen?: Kami no Itte... in my opinion, you have the hand of god when you cannot be defeated, and making the hand of god, or near-hand of god at least, appear in a game, isn't all that hard.

Just take the best players in the world and put them together in two teams. Then have the teams play a game of Go, where each team decides together where the next move will be played, and they can take as long as they want. (for the sake of the argument, let's assume they don't get into a stupid argument because they're stubborn or something)

The logical result seems to me that neither black nor white will overlook anything, and that they will know a reply to every move. This will result in a tie. If it's not a tie, the komi used was either too high or too low, because then apparently black's first move was worth more than the komi.

(this would also be a good way to decide what komi should be used officially)

comments?

Bob Myers: It's not even clear that this would result in play that is stronger than that of a single strong player. It sounds sort of like a three-legged race, where two Olympic sprinters have their legs tied together. It ignores the fact that there are different styles of go, and the style needs to applied consistently throughout the game. Even assuming that the teams come up with better moves than individuals, it seems unlikely that the improvement would be anything more than incremental — due to the elimination of mistakes (overlooking things) that you mention. But if there is a God who is four stones stronger than Cho U, due to reading and strategizing ability far beyond our imagination, putting a few pros in a room is certainly not going to be able to reach His level.

Gotjen?: About the style thing, I thought about that too. But to me, it makes sense that the team would, while playing, automatically develop a style of its own. They'd use moves of different styles depending on what the situation calls for.

Why would the improvement be nothing more than incremental when there are less mistakes? As far as I can tell, not making any mistakes is the same thing as playing a perfect game.

God v. kami no itte

(Gotjen? continued)
And if we assume the kami no itte means playing at the level of God, then I'd have to agree with those who say it doesn't exist. God knows everything, He knows which moves you will play in reply to His moves, and can thus simply at the beginning of the game decide on a chain of moves which ends in Him winning.

Phelan: Agree with you on the style, but about kami no itte not existing...if you played a perfect game too, with no mistakes, it would be as if you had known which moves god would play in reply to yours. Since there is some probability that this can happen, though it would be very very small, then in that case the game could either result in a tie or, if there really is a problem with who plays first, in a win for either player, depending on who's black.

Gotjen?: No, it's impossible. Let me explain it differently.

Before the game, God knows how His opponent is going to react to all His moves. Therefore, He can come up with a plan that will let Him win. Even if His opponent would play perfectly, with no mistakes, He has already chosen the plan that will let Him win, before the game even started. Since there is always a way to win a game, He always wins.

It's impossible to win against God, since His power and knowledge and all that are infinite. Even if we assume His opponent could get ahead, He could pull a Mitani and create some more prisoners out of thin air ;) but I doubt that would be necessary

Phelan: Since Go is a perfect information game, prisoners would not appear out of thin air. You also state that there always is a way to win a game, which is not true. For some board situations, there is no way to play that would win you the game, unless your opponent would play to lose instead of winning. So, unless you are saying that god would influence us to play worse than that perfect move so he could win, I don't think you can dismiss it that easily.

Let me put an example before you: god plays himself. Who wins? Since god knows exactly what he is going to play in reply to any of his moves, he can play the best moves there are. And in reply to those, he can also play the best moves there are. So, given that, does god win playing black, or white? or is there a tie? One way or the other, those perfect moves would be Kami No Itte, the best move possible, given some situation.

Gotjen?: There are board situations were you cannot win... But God knows how His opponent plays, and can thus predict precisely how he could prevent that situation. When I said 'there's always a way to win' I meant at the time the goban is still empty.

And well, yes, if God played Himself it'd probably be a tie, and yes, God 'probably' has the hand of god. But I thought the discussion was about a human (or a computer, I guess) getting the hand of god. There really isn't any discussion whether God has it, right?

Phelan: I thought you were saying that Kami no Itte did not exist... You believe that god playing himself( the perfect game) would probably be a tie. Me, I'm personally inclined towards a black win, but I think no one can know for sure right now. Nevertheless, to me, that is Kami no Itte, the perfect way to play.

For a 5x5 Board, all the possible moves have been considered, and the best moves have supposedly been found. All the knowledge about that game is known. So, unless god could play moves that hadn't been considered (illegal moves, or moves only allowed on other rulesets), I don't think he could do better than anyone who could remember all the moves possible, and the best responses against those (or had a record of the complete game tree).

I believe no human or machine is currently able to play Kami no Itte on a 19x19 board, but a hundred years ago nobody thought it would be possible for a machine to play chess, much less beat a human champion. Who knows what computers will be like in a century's time? And who knows what humans will be like in a millennium or two?

Like I said before, I don't think you can dismiss it that easily.

Gotjen?: It's true that on a 5x5 goban, much like in tic-tac-toe, once you know the correct reply to all moves, even God would not be able to defeat you. However, a 19x19 goban is much bigger and thus offers much more freedom. In my opinion, it's impossible for even a computer to know the reply to 'all' moves. I can't prove that that's true, of course.

On another note, komi is there to even out the fact that black goes first, so if black has an advantage the komi should be higher.

nachtrabe: If there is an appropriate komi, who wins depends on which way the fractional value of komi goes (if there is fractional komi), assuming that the standard definition of komi actually applies when dealing with perfect games (i.e., the value of the first move is so great for perfect play that it would lend a huge advantage given even slightly less than optimal play).

As others have pointed out though, Go is a 2 player, zero-sum game with perfect information and alternating turns. It has perfect play. Whether a computer will ever achieve that is another question.

Does perfect play remove the artistic element

Quiet Purple? : Mathematics — the art of turning art into number crunching.

YujiSato? : Mathematics ~ Art, Understanding ~ Feeling. If you ever want to know why you feel what you feel at the most basic level, seek for a bit of mathematics. Your perception of beauty is greatly based on mathematical notions such as symmetry, proportions and patterns, besides social standards which are also influenced by mathematical motifs. Emotionally you may not notice that, but your brain knows better than you.

Comments on the proof above

YujiSato? : I'm no mathematician or philosopher, but I do take great interest in this subject and liked some of the earlier comments.

If I understand it right, the first mathematician tried to offer a 'proof' that a winning path must exist. But simple draws, huge sekis and superko situations could possibly complicate the simplification he made. I agree there must be a perfect game, but that could lead to no victory. Those two whole-board seki games serve to illustrate the possibility of "reasonable" full board-sekis:

• http://gogameguru.com/seki-go-game-1/
• http://gogameguru.com/seki-go-game-2/

Another thing that is relevant, not on the existence of a kami no itte, but on its accessibility, is the absurd number of plays possible in go. There must be better estimates than that accessible, but if we assume a 361 factorial number of plays or a 3^361 number of board states; we get respectively 10^768 plays and 10^172 states.

The universe has approximately 10^80 particles. Even in a scheme of a thinking universe (compound of trillions of galaxies); the computation of the best gameplay path would not be attainable through sheer computational power in an algorithm like the one proposed, even in trillions or quadrillions of years, which goes far beyond the age the universe is expected to exist exist in most models.

As an upper bound for universe's computational capacity, assuming that every particle (10^80) in the universe were to generate 1.000.000 calculations per second, for the age of the universe (10^23 s), we would get some 10^109 computations, which would be far off the required calculations to solve the game in a full game tree effort.

• http://en.wikipedia.org/wiki/Observable_universe#Matter_content
• http://en.wikipedia.org/wiki/Timeline_of_the_Big_Bang

Although I think mathematicians and computer scientists could somehow develop methods to access the draw-victory-black-white answers, the kind of solution available for checkers would be impossible in go.

Meaning of kami no itte (2)

(YujiSato? continued)
What is the kami no Itte is also a question in itself. As someone also pointed, a Kami no Itte could come for many given situations, even as the best and brilliant play available in a defined situation. Also, the insight of getting a brilliant play could not necessarily be followed by equally brilliant plays. So, there are many ways in which a Kami no Itte could be seen. As the best play possible at a given time, as a momentary sequence of plays or for the whole game.

Another thing to be thought about is that best gameplay sequences could change among rules and Komis, since there are some..

On the Zen-Artistic line of thought, I think they raise quite interesting points. One of the aspects that I've found fascinating about Go is its intuitive, abstract, beautiful quality. As someone has pointed, it could be debatable if Kami no Itte could be simplified as a gameplay sequence that leads to victory.

Just as a painting that represents quite well a landscape can be less inspiring than an abstract one, perhaps the same could apply to a Go game. Sheer computation capacity may be quite different from insightful gameplay. Even, different paths leading to the same score could be seen as more or less interesting.

The perfect game could be a mirror go with minimal conflict, ending in a tie. That would sure not fit the Kami no Itte definition at all in my opinion. Also, a computer that can beat any game of Go can be as good as a computer that takes beautiful photos of landscapes or makes good music. Would that really imply in beauty or understanding? One can give a computer a huge variety of joseki trees for a computer and it can play excellent fusekis, without any quality of strategy.

On the impossibility of computation of Go games, one could apply rather well the beautiful saying Scartol placed. If we can't know what the best play is, as it is not accessible, the Kami no Itte could possibly be thought of as the best we're capable of doing or perceiving. Losing too much time into thinking what would be perfect could drive us further from the path, instead of closer.

The search and its impact our appreciation

(YujiSato? continued)
On how Kamite no Itte may be sought, I see some possibilities. Maybe one path would be getting josekis and trying to get them bigger, until they combine and take over the board. I suppose professionals are quite good in that already. Another path could be understanding a variety of whole-board sekis and checking for any generality that proves or disproves their applicability under perfect play conditions. Another quite interesting thing could be employing statistical analysis in professional games and checking success rates for different lines of play, as openings.

Anyway, if anyone is too worried about Go losing its beauty with some supercomputer unravelling its mysteries, forget it. We would always start playing in a uncomputable 29x29 board, or a tridimensional board with 2 plays/turn and I'd bet much of go concepts would still apply. And much of go beauty and abstraction and even insightful advantage of humans x computers would still be around.

Evolutionary peaks

YujiSato? A concept in biology that is somewhat relevant to efforts to get better lines of play and the history/sociology of styles is that of evolutionary peaks ( http://en.wikipedia.org/wiki/Fitness_landscape). As one will most likely derive gameplay improvements from existing good gameplay, we might miss other styles that may get to better results, but that aren't tried at all, just because they aren't part of mainstream practice and are therefore underdeveloped.

In this line, Shinfuseki shows quite well that we may go for long periods of development missing important insight, and may need sometimes breaking our standards to advance. Fortunately, differently from biological evolution, cultural evolution is more flexible and allows for that.

Bots reaching 5 dan

One thing that is also relevant right now is the ascent of bots to 4-5d ranks. ( http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+gogameguru+%28Go+Game+Guru%29) They seem to bring a sheer new gameplay style. It may have implications for overall human gameplay in two directions:

• a) it may show that we oversaw potential good gameplay due to historical/psychological limitations and lead us to directly learn from their style.
• b) it may show that we oversaw potential flaws in gameplay that humans didn't consider, but computers do; and that can lead to improvements correcting our own style.

and even

• c) it may show convergence of styles from huge computational capacity and state evaluation, compared to human experience and history. That could hint validation of lines of play.

Even more, something that could be added above as a potential way for developing better gameplay.. Put several 5d bots to play tirelessly against each other, using no game libraries. Analyse their games for statistically convergent styles or solutions..

See also

• Baka No Itte (pessimal play)
• Sightings Of The Kami-No-Itte (humorous)
• Neural networks:
  • Training a Neural Net to Play TTT (page not found)
  • Reinforcement Learning (server not found)