The perfect game

[zac]

Hi all,

I'm returning to go after almost two years off; I'm not sure why I stopped playing, but I saw the AlphaGo documentary on Netflix and it got me thinking about the game again. So, a couple of days later, and I'm well and truly hooked again.

I was thinking this morning about computer go, and how it can be trained by playing games against itself. I got to wondering; how far away are we from go being "solved", if that is even possible? Will there come a time where the optimal move in every situation is known, and so the perfect game of go could be played? The thought that a computer would eventually just play the same game again and again, because no further improvement could be made, was quite strange. I wonder what that game would look like? I wonder which side wins? I wonder what it, and the other improvements in computer go, will mean for human players understanding of the game.

As I've been away from the game for a while, can anyone give me an idea of what impact computer go has been having on professional play, if any? Are there certain lessons that have been learned?


Thanks and all the best,

Zac

[Uberdude]

As I've been away from the game for a while, can anyone give me an idea of what impact computer go has been having on professional play, if any? Are there certain lessons that have been learned?

Yes. Most striking is invading early at 3-3 under a 4-4 stone. AG shows the wall isn't so good if you don't make the 2nd line hane connect exchange, and also jump instead of hane when the invader crawls is now most common. Other ideas popularised by AG include:
- big high shimari from 3-4, small low going out of fashion.
- more kicking of low approach to 3-4, corner valuable.
- push through table shape in magic sword ogeima joseki.
- more attachments as first moves against positions like Chinese formations.
- early attachment against shimaris
- high value of press move after low approach to 3-4, knight instead of kosumi response to prevent that has seen surge in popularity.
- liking of early shoulder hits, particularly against 4-4 6-3 enclosure
- dislike of slide after 4-4 knight approach and answer, strong preference instead for attach and hane.

I did start a thread to collect AG inspirations in pro play but it's not been updated in a while as it's so common now. forum/viewtopic.php?f=13&t=12953

[RobertJasiek]

Solved as a 19x19 game under a chosen, given ruleset has different meanings, such as weakly solved (finding some perfect play sequence possibly without understanding why it is one but having proven that it is perfect play) to strongly solved (knowing all perfect play sequences incl. complete explanation why each move is perfect play). Computer or mathematical research has provided nothing, except for very late endgame, whole board semeais or the like. My estimate as a go theory researcher is that we need at least 400 years until go in general might be weakly solved by mathematical proofs. There are two presuppositions: 1) 19x19 go does not turn out to be harder than solvable within reasonable time (similar to NP-complete of nxn go), 2) generalised artificial intelligence does not become faster than researching human mathematicians during the next four centuries.

Which side (Black) wins - or ties - in 0 komi games we proved in the 90s but related proofs date back to On Numbers of Games in the 70s, I think.

The impact of computer go on human play is greatly exaggerated. I might double the impact of mathematical go on human play this year but the overall impact will still be limited to specific types of positions with certain properties (such as late endgame positions without complications). The problem for computer or mathematical impact is, of course, that complications are the norm.

[Uberdude]

I wonder what predictions about the future chaps in 1618 were making! I also wonder how long RJ would have predicted it would be before we had a super-human Go program 5 years ago.

[RobertJasiek]

That I make a prediction on research in mathematical go theory does not mean that I would be able to make good predictions for everything. I make the particular prediction because a) I have researched in mathematical go theory for 22 years, b) there are only a few researchers in mathematical go theory, c) I have got a reasonable impression of the relation between already solved versus still necessary mathematical go theory, d) there are no shorthands from current knowledge in mathematical go theory to the knowledge necessary for perfect play because I have met blocks preventing them even for comparatively simple problems in mathematical go theory.

Approximations to perfect play might be found very much faster, like AlphaGo is an approximation to some next level of non-perfect play. There are mathematical approximations for the middle game but they say essentially nothing about perfect play in the arbitrary position.

[John Fairbairn]

I wonder what predictions about the future chaps in 1618 were making! I also wonder how long RJ would have predicted it would be before we had a super-human Go program 5 years ago.

Well, this was the age of Mother Shipton and her most famous, numerically palindromic prophecy didn't quite come true:

The world to an end shall come
In eighteen hundred and eighty one.

This neatly encapsulates a necessary attribute of the 400 years kind of prophecy: make sure it's only going to happen well after you're dead in the hope no-one can prove you wrong.

But 1618 was also the time Francis Bacon became Lord Chancellor of England. I'm not well up on this sort of thing but I believe he is counted as one of the fathers of the scientific method, so presumably even then there were people who disapproved of rash predictions. And yet 400 years on...

[RobertJasiek]

1618 predictions are a very bad comparison because they refer to the universe and real world with their limitless possibilites. 19x19 go is a finite game (even with ko rules allowing infinite sequences, the possibilities can be described by finite different starts of sequences until possibly repetition).

BTW, the relevant discussion is not so much whether 400 is accurate but whether anybody can contribute so well to mathematical go theory that progress is greatly accelerated by incorporating the complexity blocks efficiently (such as applying everything also to kos that previously has excluded kos, or applying everything also globally that previously has only been local). Mathematics, however, is as precise as slow in its creation. Identification of perfect play requires it.

Mathematics since the 20th century has been accelerated hardly by method but mostly by 1000 or 10000 times more manpower.

[Kirby]

Given the gap in ability between computers and humans, does it really matter when go is weakly or strongly solved?

[RobertJasiek]

Strong playing for arbitrary positions as computers or humans has essentially nothing to do with perfect play, which is about weakly or strongly solving go. We need at least a rough idea of how far in time and insight we are from perfect play. (With the exceptions mentioned before.)

[Kirby]

Strong playing for arbitrary positions as computers or humans has essentially nothing to do with perfect play, which is about weakly or strongly solving go. We need at least a rough idea of how far in time and insight we are from perfect play. (With the exceptions mentioned before.)

Agreed that strong playing isn't related to perfect play. Disagree that it matters for anything practical.

[zac]

Yes. Most striking is invading early at 3-3 under a 4-4 stone.

That is surprising. Was it Kageyama that wrote to set up the position on the board and repeat ”blacks influence is superior to whites territory"? I'll check out your thread to see the joseki chosen by AG in place of the "usual" that I see in my games.

It's brought up some interesting thoughts for me. I feel conflicted about whether I should always try and understand perfectly the reason for playing one way or another, or whether I should try and emulate strong players moves without always fully understanding, and let experience over the board tell me why something is good or bad. I can imagine I know Roberts opinion, but I'm not sure I know my own!

I don't think AI is going to give us much direct insight in to the "why's", which I guess is still left up to human players?

As I'm not really up with what has been happening over the last few years, at what level does a commonly found, widely available computer program now play? I can remember years ago the general advice was to avoid playing against bots if wanting to get stronger. I could only dream of having a program of high dan strength on my computer to play whenever I wanted. Does this type of advice still stand? Have improvements been made in the way weaker bots play? I know in the past playing against bots lower than mid-SDK they always felt distinctly un-human, and generally I felt they weren't helpful. Can the methods of the strong AIs be used to make more sensible, "weak" bots, that could benefit human players in becoming stronger? What about in creating tools to help review games, e.g. to show alternative sequences, point out bigger mistakes etc?

Thanks to everyone who has added to the discussion,

Zac

[John Fairbairn]

We can learn from what happens in the chess world. Not even the most hubristic grandmaster denies that computers are much stronger than humans, but few, if any, seem to try to use computers as a direct learning tool. Instead they use them for blunder checking and for opening preparation (which can be seen as form of blunder checking). They do not use them to make strategic decisions. In fact, many grandmasters still seem to mistrust computers' strategic judgements.

As one example, reacting to the news that AlphaGo Zero beat Stockfish, Lev Aronian recently said "Currently I am analysing with a program that is five years old! So I don't care so much, it's more about adopting the programs to suit your playing style rather than have the best computer program. At the end of the day the position you get, you're going to play, not the computer so it has to suit human's taste."

Actually, he is not really analysing with a program - he employs a team to do the computer analysis and feed him the results. That seems common. This may be how go will develop in future, though the different relative value of the phases of the game in go may make such opening preparation much less important.

[Baywa]

Agreed that strong playing isn't related to perfect play. Disagree that it matters for anything practical.

I'm not so sure in both cases. Let me elaborate.

A)"Strong playing isn't related to perfect play". We don't know that. It could be that certain board positions can be judged as lost or won both by a (strong) player and a perfectly playing "oracle". In this sense, practical and perfect overlap. Perfect play might not be so outlandish that it contradicts every aspect of practical play.

B) "Perfect play doesn't matter for anything practical". Of course, looking at the vast amount of possible board positions and playing possiblities, perfect play seems to be a very theoretical concept. But maybe mathematical research could help to find building blocks of perfect play (or perfect board position). The examples uberdude showed could go in this direction, although they come from studying the play of AlphaGo, who certainly is not an "oracle".

[Uberdude]

Kageyama presumably was chanting ”blacks influence is superior to whites territory" about this position? I don't think AG disagrees that generally this is good for black on an open board, and you only want to play it if black already has a double wing which then becomes inefficient if he follows this joseki.

$$B
$$ --------------------+
$$ . . . . . . . . . . |
$$ . . . . . X O O . . |
$$ . . . . X . X O . . |
$$ , . . . . . X O . . |
$$ . . . . . . . X O . |
$$ . . . . . . . X O . |
$$ . . . . . . . X . . |
$$ . . . . . . . . . . |
$$ . . . . . . . . . . |
$$ , . . . . . , . . . |

Click Here To Show Diagram Code

[go]$$B
$$ --------------------+
$$ . . . . . . . . . . |
$$ . . . . . X O O . . |
$$ . . . . X . X O . . |
$$ , . . . . . X O . . |
$$ . . . . . . . X O . |
$$ . . . . . . . X O . |
$$ . . . . . . . X . . |
$$ . . . . . . . . . . |
$$ . . . . . . . . . . |
$$ , . . . . . , . . . |[/go]

What AG did which was new is saying this position and tenuki is quite ok for white, and often playing this invasion very early (in fact it seems to think it may be slightly better for white so black usually plays the marked move as jump instead of hane). The rationale in the joseki for making the 2nd line hane connect exchange was white didn't like black a being sente, but AG says answering with b-d is ok for white and nothing to cry about. White doesn't want to make the 2nd line hane connect because it makes black's wall strong and have eyes. AG seems to view the wall here as not particularly strong/thick, and it can later come under attack, the peep at e being a key move.

$$B
$$ --------------------+
$$ . . . . . . . . . . |
$$ . . . . . . a d . . |
$$ . . . . . . X O . . |
$$ , . . . . . X O . . |
$$ . . . . . e . B O . |
$$ . . . . . . . X O . |
$$ . . . . . . . X b . |
$$ . . . . . . . c . . |
$$ . . . . . . . . . . |
$$ , . . . . . , . . . |

Click Here To Show Diagram Code

[go]$$B
$$ --------------------+
$$ . . . . . . . . . . |
$$ . . . . . . a d . . |
$$ . . . . . . X O . . |
$$ , . . . . . X O . . |
$$ . . . . . e . B O . |
$$ . . . . . . . X O . |
$$ . . . . . . . X b . |
$$ . . . . . . . c . . |
$$ . . . . . . . . . . |
$$ , . . . . . , . . . |[/go]

I don't think there's actually anything about these 3-3s in my thread as that was about the Lee Sedol version of AlphaGo, which didn't do these early 3-3 invasions. That really only become visible in the AG Master self-play games (didn't do much in the 60 online games vs pros) and later in AG Zero.

I don't think AI is going to give us much direct insight in to the "why's", which I guess is still left up to human players?

Indeed, it doesn't give any wordy explanations*, but does give variations and so-called win % which humans can than interpret, rationalise, explain etc. *Yet, this is an active area of AI research.

at what level does a commonly found, widely available computer program now play?

Leela is free and high dan amateur if not low pro on home hardware. It beats pros online, but still has some mistakes about life and death a kyu player would get right. Zen is commercial and probably stronger. The non-commercial version on beefy hardware smashes Japanese pros in their training games, and has a good record against top pros on tygem/fox. I don't think the "don't play bots because they have an easily exploitable style (e.g. GnuGo)" advice still stands, and they are plenty strong now. Still I wouldn't suggest avoiding humans.

Can the methods of the strong AIs be used to make more sensible, "weak" bots, that could benefit human players in becoming stronger?

CrazyStone also has some weaker versions whose neural networks were trained on weak human players to make a more realistic weak play style. I've heard it's decent.

What about in creating tools to help review games, e.g. to show alternative sequences, point out bigger mistakes etc?

- https://www.crazy-sensei.com/?lang=en
- GoReviewPartner: forum/viewtopic.php?f=9&t=14050

[Kirby]

Agreed that strong playing isn't related to perfect play. Disagree that it matters for anything practical.

I'm not so sure in both cases. Let me elaborate.

A)"Strong playing isn't related to perfect play". We don't know that. It could be that certain board positions can be judged as lost or won both by a (strong) player and a perfectly playing "oracle". In this sense, practical and perfect overlap. Perfect play might not be so outlandish that it contradicts every aspect of practical play.

B) "Perfect play doesn't matter for anything practical". Of course, looking at the vast amount of possible board positions and playing possiblities, perfect play seems to be a very theoretical concept. But maybe mathematical research could help to find building blocks of perfect play (or perfect board position). The examples uberdude showed could go in this direction, although they come from studying the play of AlphaGo, who certainly is not an "oracle".

A) “related”, I guess, is a flexible word. Of course it may be possible to find connections (relations?) between strong and perfect play. Maybe I should have just acknowledged that they are not the same thing.

B) I suppose it’s possible that insights could come from research into perfect play, but like you say, we already have this from alphago. You might get more from strongly solving the game, but at human skill level, it’s unlikely to make much difference. If you are a 5k watching games from a 5d and also a 7d, maybe the 7d plays better, but it’s pretty indistinguishable to you.

My point is more related to B than to A.