How much stronger can AI be?

So it’s well established that the AI are a lot stronger than any human. However, it is also a fact that the strong AI are trained for winning the game, and not for destroying their opponent.

Now, I was thinking how easy it is for a human who is a lot of ranks better than his opponent to utterly destroy his opponent. A 25k playing against a 5k would probably keep barely any of their groups alive, but equally so, a 5k playing against a vindictive professional would meet a similar fate. However, is it possible for an AI to be so incredibly strong that they will make it difficult for a pro to keep most of their groups alive?

I doubt any pro would be willing to play a game just to be destroyed, so let’s frame it in a different way: is it possible for an AI to beat AlphaGoLee with a difference of score running frequently into the hundreds? (and I don’t mean an AI trained on beating AlphaGoLee, since there is probably an exploit to be found and abuse, I mean a general go playing AI that is trained on winning with a large margin from any player as strong as Lee Sedol)

How big is the gap we have to fill until perfect play?

5 Likes

Well, if you’re defining “perfect play” as “a professional can study the game for several days and find no mistakes” then we’re already there. But then again there are also some human games like that. If you mean “perfect play” as “play that will always win as Black by 0.5 pt against another perfect player” then we can’t test that unless either 1. We know that the opponent is perfect, in which case the test is redundant or 2. We weakly solve Go by finding all winning paths for Black (a job for quantum computers, I wouldn’t be as foolish as to call it impossible ever.)

2 Likes

The objective of the game is not to have as high of a score as possible, but rather just more than your opponent, so I would not define strength by the ability to rack up as high of a score as possible.

These two objectives (securing victory vs maximizing score) are different, since the latter might encourage a riskier and bolder level of play, while the former is about maximizing probability of victory. I think it’s generally believed that the strategy of attempting to kill everything is not the best for maximizing the chance of victory.

For defining strength in this way, I think there might be a ceiling. I doubt that it is possible for even “perfect play” (while aiming to maximize score) to reliably win by a huge margin (like 50+ points) against top pros or the current top robots.

I would measure the gap vs perfect play by how many “ranks” exist between the current top players (which are robots) and the theoretical best. Of course, how to define ranks is a debatable, but maybe we could say that a player is one rank above another if they can win ~65% of the time (or demonstrate some other significant but bounded advantage over the other player, like maintaining ~50% win rate despite giving handicap). Thus, however many levels on the rank ladder that exists between the current best and perfect play could be a definition of the gap. I think the question of how big this gap is will remain unsettled for a long time.

4 Likes

No, I define “perfect play” in the technical sense as in “God’s play” or more precisely, a strategy (that is: a response to every possible move of your opponent) that will let you win the game guaranteed. Note that the opponent does not have to be a perfect player, as a winning strategy will win regardless of how good or bad the opponent is.

I know we can’t test my question (at least not without a breakthrough in either game theory or in computing science), so it’s more a philosophical or intuitive question than a technical one. Of course I would be more interested in an answer to the technical question… :stuck_out_tongue:

2 Likes

If I remember correctly, Shin Jinseo once said that he believed he was three stones away from perfect. In fact, I think the exact wording he used was “I would bet everything I have on a four-stone game against God.”

4 Likes

He wouldn’t say that today though. :stuck_out_tongue_closed_eyes:

4 Likes

You don’t think so? He is in that first generation of post-bot top players, right?

1 Like

I know, but it is a secondary measure of strength. I mean, when a 5k plays against a 15k, a 20k and a 25k, he ought to win all of the games easily. However, it will be difficult to win with a large margin against the 15k player and difficult to win by killing everything against the 20k. Or at least something amongst those bounds.

My premise is that the bot is already easily good enough to beat pro players, so the next best goal would be “by how much?”. It a question that wouldn’t be able to be asked for (for example) chess, as the margin in score is not quantifiable in that game. With Go it is however, and I bet that everybody would be speechless if the news arrived that any top pro from today has lost 5 games in a row where not a single group of them managed to live (highly unlikely that that’s going to happen, but we haven’t proved that it’s impossible, assuming the pro plays more or less conventionally…).

2 Likes

i have no clue apparently. Deepmind claims the 3rd generation of alphago, which is zero(?) is 5 stones stronger than alphago lee.

but don’t be serious on how many stones either handicap or final score. it’s against the spirit of go. the perfect game is to win, not to destroy.

2 Likes

So what about winning and destroying? I mean, winning is basically child’s play for an AI nowadays.

Another way to look at winning with a large margin that is perhaps more in the spirit of go, is winning with a ridiculous amount of komi.

1 Like

There definitely is a ceiling, as perfect play exists (a winning strategy exists, go is a perfect information game with finitely many states between two players), even when we shift the focus from winning to winning with a large margin. Hence there is an upper limit. The question is what it is.

Problem with this is that this definition of rank will not work against a perfect player, since there is 0% chance of winning against them…

1 Like

I have no doubt that DDK-level players could find themselves completely destroyed with no living stones after game against a much stronger player that is bent on trying to kill everything. However, I think this phenomenon does not translate as we move up the skill ladder.

Even if there are 100 ranks between perfect play and the current top-level play, I don’t believe it will mean that the perfect player would simply be able to kill every (or even the vast majority) of stones played by our current top players.

Well, it depends on komi I think. For non-integer komi, one player should have an advantage, so if two perfect players alternate between games who gets black or white, they will each have a 50% win rate. If one of them is slightly less than perfect (they occasionally make mistakes and lose the games under the color that they should win), then you could get a ~65% win rate for the perfect player.

2 Likes

It shouldn’t matter, as even with draws it will remain a fact that a perfect strategy cannot be won against, since go does not involve chance. Of course, this winning strategy might be so complicated that it is impossible to describe it with less information than that there are atoms in the universe (based on the number of possible Go games), so practically it will likely have to involve chance.

1 Like

So a perfect player can never lose in tic tac toe? :wink:

1 Like

You are also implicitly assuming that the game is fair.

However, I believe that with non-integer komi and a rules set that avoids “no results”, that go would not be fair, i.e., one color has an advantage that can be forced into a win (even against a perfect player) with perfect play.

If we allow ties by adopting an integer komi, then I would amend my earlier definition with defining a win as worth 1 point, a loss worth 0 points, and a draw as worth 0.5 points, and talk about expected scores instead of win rates.

These expectations and win probabilities are not with respect to any randomness inherent to the game (of course, the game of go is deterministic), but instead with respect to the potentially random performance of the players.

To consider why it is possible for a perfect player to score less than 100%, imagine that they are playing against an almost perfect player that usually plays perfectly, but occasionally makes mistakes with some level of random chance. Further, consider the expected scores over a series of games where they alternate between who gets black and who gets white.

1 Like

Exactly. Good example: I can play tic tac toe against anybody without losing, since the drawing strategy is easy enough to remember.

What do you mean with “fair”? Why do you believe this? If one colour has an advantage over any supposedly perfect strategy, then that would imply that there is no winning strategy for that colour (i.e. no perfect play). If neither player has a winning strategy, then there must be drawing strategies for either player, due to the nature of go it is impossible for such a strategy not to exist.

Compare it with tic-tac-toe. A potentially random player would at random moments make a mistake in their move. Of course this is ridiculous for such a simple game as tic-tac-toe, but there is really no difference with go: randomness in play is only a practical problem, not a theoretical one.

1 Like

Fair means that the game is not biased toward either player (color). Unfair means that one color could always force a victory by playing correctly.

I believe that given a non-integer komi and a rules set that avoid non-results the game of go would be unfair, i.e., that either black or white could theoretically force a win by playing correctly.

For unfair games, where one player (color) could force the win, the other color does not have a winning strategy. However, that does not prevent us from defining the concept of a hypothetical perfect player. The perfect strategy, even from a theoretically losing position, is still definable as the strategy that loses slowest, since that would give the most opportunities for their opponent to make a mistake.

I’m not talking about players that play completely randomly. Imagine a player that plays the best move most of time, but has some non-zero probability of making sub-optimal moves. That player might finish an entire game without making any mistakes, but in some games they might make mistakes.

1 Like

There is nothing new to be discovered in physics now. All that remains is more and more precise measurement. - Lord Kelvin, late 1800s.

7 Likes

A better example would be 5x5 Go (5x5 Go is a solved game after all.) Given perfect play and no Komi, black will always win and will win by 25 points (Chinese scoring.) So, you cannot play 5x5 Go “without loosing”. It depends entirely on which color you are and that is random chance.

But perfect play is not the ceiling. If AI will be able to read mind of opponent, it will be able to exploit mistakes of certain person and win by more points.

Its possible to make simulation of professionals by using base of pro games. Bot may use this simulation to win against any pro by at least 50 points for example. It will not win each time, but when it will, it it will win by more points than perfect play.