Hacker News Reader

Comment by bediger4000 | Hacker News Reader

Does this paper render the championship moot? Is any software based on the paper entered?

Is Othello like checkers, where there were mostly draws in high level games?

This paper "weakly solves" Othello. That means that we know for the initial board state both 1) the final win/lose/draw outcome (it's a draw), and 2) the sequence of moves that should be taken by perfect players to get there (Figure 1, right).

In particular, the paper does not "strongly solve" Othello. If you have an arbitrary board state, 1) and 2) are are not necessarily known for it. That means it's still possible to win a game by intentionally deviating from the perfect sequence and betting on the fact that your opponent doesn't know how to recover.

>That means it's still possible to win a game by intentionally deviating from the perfect sequence

Someone with perfect strategy would have an answer for any deviation. Playing imperfectly would likely get you into a losing position. There is no way to go from a game being drawn if played perfectly to being winning if the then loser were to be using perfect strategy.

I agree. As a nuance, (and I'm not an Othello player, but a chess player) in many positions in chess, there are many moves that, while not the best, are just slightly worse. Finding the 'refutation' for a weaker move is the measure of the strength of a player, and playing a few slightly weaker moves in a row will almost certainly take even high level players out of 'book' (the memorized sequence of best moves). At that point, the strength of the players becomes important, as opposed to how much they have memorized. The strategy, then, is to have a _slightly_ worse position from which one can recover and go on to win. Obviously, if the opponent plays perfectly, it is either a win for him or a draw. Typically the 'slightly weaker' move still keeps the game a draw. The advantage is not a game-winning sized advantage. I wonder if in Othello there are positions where there are multiple possible moves which 'preserve' the draw.

No, the paper only "weakly solves", so it doesn't give a perfect strategy of the type you talk about.

Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess. Armed with it, you will still lose easily to Magnus Carlsen. He will deviate fro| the sequence and you won't know the perfect responses to his moves.

> Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess

How would you go to prove that this is the perfect game of chess, if you didn't explore all of it's possible sequences? If they did solve the game, there's no way around knowing all possible outcomes - starting from a fixed given position.

You don't, you trust that God has proved.

I don't get then, how the paper "solves Othello": how does it determine the perfect game (why is it perfect)?

The claim (see other threads, it is not clear if the paper really shows this) is that you can follow their plan or any deviation from it known results. That is no matter what I play if you understand their paper you can ensure you don't lose. If I also know their paper I can force a draw, but I won't win.

Not the perfect game, a perfect game. There will be a huge number of them, many of them very boring and unremarkable

"Weakly solved" does actually imply that perfect strategy. I think you're referring to "ultra-weakly solved", which seems to be what the paper did.

A "weak solution" demonstrates perfect play from the initial state and merely implies the existence of a perfect strategy for the entire tree of game states, but, crucially, need not actually produce said strategy. Doing so would be a "strong solution."

An "ultra-weak solution" is even less. It gives the win/lose/draw outcome of the perfect strategy, without producing that strategy, nor even producing the game of perfect play from the initial state.

This is all covered in the second paragraph of the paper's introduction.

So are the definitions in the Wikipedia article then wrong?

https://en.wikipedia.org/wiki/Solved_game

And if a strategy for perfect play only from the initial position is a strong solution, then what do you call the even more strongly solved case of a strategy for perfect play from any position?

The second paragraph of the paper isn't super specific about its definition for "weakly solved", but I read it as agreeing with my statement. It also calls checkers "weakly solved", a game for which a strategy to beat any possible move is known.

>He will deviate fro| the sequence and you won't know the perfect responses to his moves.

Even if you don't know the moves you will know that you are in a winning / drawn position. Magnus can not find a way to get to a winning position unless you make a mistake.

That'll be very little help if the perfect game you have starts with 1.e4, but Magnus plays 1.d4. Yes, you're not losing, congratulations. You're still on your own against Carlsen now.

You can just evaluate whether or not a given move will change from a +1 or 0 position to a 0 or -1 position and play it from there.

Perfect play in a perfect game means that the objective won't change - in optimal control theory this is called Pontryagin's Maximum Principle or the Bellman optimality criteria. A "value to go" function is enough to find the optimal solution.

Yes, but we were talking about a scenario where someone was just given the moves of a single perfect game. Not an oracle that gives you the -1/0/+1 of any position.

Weakly solving a game requires a proof of optimality, which means an evaluation of all variations to prove their value. A sequence of moves in one perfect game isn't weakly solving a game.

> unless you make a mistake.

That's the easiest part.

> Someone with perfect strategy would have an answer for any deviation.

Someone verified there is a perfect strategy, using tons of computational resources and lots of time. The game tree they explored may have millions of billions of nodes, of which only the top layers could be saved.

To use a perfect strategy in an actual game, you need to have it stored in some format that allows near-real time lookups.

Such is the difference between weakly and strongly solving.

EDIT: Strongly solving goes beyond the latter, requiring real-time best play from arbitrary positions.

> Such is the difference between weakly and strongly solving.

no, you described difference between storing the result and not storing it

strongly solving means allowing arbitrary amount of mistakes from either player before giving to the solver

The author isnt claiming it's possible to win against a perfect opponent, but rather, all perfect play scenarios end in a draw. If both players either can't play perfectly, or choose to play imperfectly, then it moves into unknown territory and either side can force a win.

This does have to be mutual though, if only one side plays imperfectly, then the other can always force at least a draw.

So if you know the other side is incapable of playing perfectly, it could be rational to deviate.

>That means it's still possible to win a game by intentionally deviating from the perfect sequence

This part is not correct. If the arbitrary board state you start from is reachable from the fixed opening state given that the other player plays perfectly, then weak-solvedness means the other player can force whatever (a draw, in this case). If not, then the question is open. I don't know Othello, but an example of a chess position that is not reachable from the standard opening position is one where White has 8 pawns (so none have been promoted) but two bishops on white squares -- such a position can never arise through a legal sequence of moves. If we pretend for a moment that chess has been weakly solved as a draw, another example would be a position where White has only its king left, while Black has two rooks -- in this situation, Black can force a win, which implies that this is not a position that could ever arise under perfect play from the standard opening position, since that has already been proven to always result in a draw.

I found it helpful to (re-)derive what "forcing a draw" actually means, maybe you will too: Player 1 can force a draw from board position B in k moves or less iff, on their turn, (1) it is already a draw or a win for them, or (2) k >= 1 and they can play a move that draws or wins immediately, or (3, the inductive case) k >= 2 and they can play a move such that, for every legal move that player 2 could then play, player 1 can force a draw or win from the resulting board position in k-2 moves or less.

This is a misunderstanding. To give an example. A perfect 1.e4 player needs a response to every possible move including 1.. f6. But he doesn't need to know how to respond to 1. d4 d5 because he avoids ever ending up in that position.

Why would it render human games moot? Why would a software participate in a championship?

The draw percentage in checkers/draught and in chess are roughly similar, (anywhere between 50% and 60% at high-level play), despite checkers being solved and chess not.

Now that Othello is solved, there exist a set of rules a player can follow to guarantee a win or draw every game. It's possible (if unlikely) that a computer could sufficiently compress those rules to be memorizable (and then applicable) by a human.

Checkers have been solved 16 years ago and still see competition. A game being solved is not exactly the same as "apply this memorizable algorithm and you'll win", especially if the solution implies scanning 10^n positions for each move.

I recall hearing that competition checkers has a randomization element at the start, to keep it more interesting. I believe checkers is strongly solved anyway, but it at least keeps people from memorizing all of the major lines.

In case you wondering like me, checkers here means American checkers, played on a smaller 8x8 board. International checkers played on 10x10 board is a much bigger space to explore of course.

Does the board size matter here? Wouldn't the strategy from 8x8 board somehow generalize to bigger boards? The one issue that I can possibly see is even vs odd board sizes, e.g. play on 9x9 board can be a bit different than 8x8 or 10x10.

Solve a 2x2 Rubik's cube and see if that helps solving a 4x4 ^^

From the computer point of view, it's more possible states to explore, so I think it makes things much harder

I meant: after you've analyzed the whole solution space for a smaller board, can't you come up with some heuristics, which will be applicable regardless of the board size? Checkers is a very simple game, all pieces are identical, unlike chess.

That would be a fun way to define computer opponent: introduce an arbitrary amount of allowed compute power.

Say, allowing a purpose designed device, but limited to 1W of power consumption. Or some fixed energy budget (J) per move. Too strong? Take it down to 0.1W, 10mW or whatever.

That would degrade brute forcing as a viable approach, and bring it back to smart algorithms, clever ways to reduce the search space, etc.

They are moot because the solution is known. When a human makes a mistake the intrigue is discovering the fix to become better. In solo copetition solved games are highly fascinating because the person is racing the TAS or the solved route. In human versus human games, we can simply look up what the human did wrong. There is no cognitive challenge in answer lookup. Its just oh, he sucks he missed the move. Since its two humans competing it becomes "who sucks less" but its two losers that both suck competing. Thats the problem with competitive play of solved games, it must be solo competition against the solution.

> Since its two humans competing it becomes "who sucks less" but its two losers that both suck competing.

Yeah, this is my problem with bowling and golf. If you're a professional bowler, literally your only job is to knock down the pins. Why do anything else? If you miss one, you're bad at your job. Ditto with golf -- the hole is right there, just get the ball in it!

(Honestly not sure how sarcastic vs sincere I am in this comment.)

Foot races are also solved - these losers should just get a car!

Cars are not allowed in the rules of the game "foot race", therefore your solution is not valid and therefore your argument has no evidence to support your claim.

You used this word, evidence. I don't think it means what you think it means.

Parent made an argument by analogy, no evidence needs to enter the picture. At best you can say his analogy is flawed.

It's not even flawed, anyway. If cars not being allowed is supposed to refute the analogy, then an obvious answer would be that Othello playing programs could also banned in Othello competitions (given that the solution can't just be internalized by a human player).

...is this satire?

In bowling and golf the mistake is athletic. You moved your body wrong, also there are variables such as the wind and humidity of the air in golf, and a in bowling the ball and other micro variables effect play. It's possible to improve physical condition with training, but there is no "perfect". In a fully abstracted competitive game where all variables are eliminated except for mental choices, it becomes about memorization of the solutions if the game is solved.

>In human versus human games, we can simply look up what the human did wrong. There is no cognitive challenge in answer lookup. Its just oh, he sucks he missed the move. Since its two humans competing it becomes "who sucks less" but its two losers that both suck competing. Thats the problem with competitive play of solved games, it must be solo competition against the solution.

I don't think you understand the purpose of games.

This is like saying since we have cars, why do people still race?

Or "why even do shooting competitions, when a robot or a person with a laser scope can easily win them?"

And honestly I think the draw percentage in chess is influenced just as much by sociological processes as it is by game theoretic concerns. The very top chess players are extremely risk averse. Chess is way too complex for humans to ever be able to play perfectly in sufficiently complex positions, honestly. The top players today obsessively avoid positions like that unless they can find a forced drawing line as a backup.

In other words, not losing is heavily prioritised over winning in top chess, currently.

There are many possible ways to change this. My favourite is to make a win worth 3 points, and a draw 1 point. Both in tournament scoring and rating calculation.

I think this would incentivise more aggressive play, and disincentivise the constant slog of the same 15 top players playing mostly draws against eachother, and barely playing in more open tournaments with a bigger rating interval.

German soccer league followed the English and Italian league in 1994 with a three points rule. It seems to favor the better teams (with more expensive players) even more, stabilizing the championship. https://www.fiaa.at/theories/die-3-punkte-regel-und-ihre-pro...

Great chess players often pull out a draw from what looks like an obviously lost position. Mostly great players start playing for a win, but somewhere in the middle they realize winning is hopeless and switch to looking for a draw.

> In other words, not losing is heavily prioritised over winning in top chess, currently.

It's more that once you are in a losing position, winning is extremely difficult, and a draw is often the best thing you can achieve.

From there on, the losing side cares about not losing (because winning is almost impossible), but the winning side stills tries to win. Great chess players are the ones who can turn a losing position into a draw, or prevent draws from a winning position.

Then why do we see superGMs constantly bail out for a draw when they're not losing, sometimes even in a better position? And consistently play quiet, safe openings, instead of sharper, if more dubious stuff. Sometimes the position is completely equal with plenty of play left and they instead manufacture a draw via repetition for no reason.

Yet occasionally we see players throw out unsound openings and they work out just fine because they're so complex and sharp they're hard to refute.

I understand how chess play works, being a tournament player myself. My point is not on the mechanics of chess, but the psychology of these players as a result of being brought up in a chess world where risk averse play is strongly awarded.

Ultimately, the core problem here is that these players choose to play in a way that leads to more draws, not that they're so unbelievably strong that it's almost impossible for them to beat eachother.

Just look at computer chess. They're way beyond human capability, and yet they still don't play perfectly. That should tell you how large the gulf is between current human play and perfect or even close to perfect play.

Chess is weakly solved for all practical purposes (it's not proven but no one is able to show a winning sequence for white even with weeks to prepare vs a top engine playing with something like 30 minutes per move) and it doesn't affect the competition at all. It's impossible to remember it all anyway.

Once/if chess is formally weakly solved it will change exactly nothing for human chess players. If your plan is to remember the solution you may just as well start learning top engine lines today.

Weakly solved is a computational notion that has nothing to do with how well humans and computers play. We are far from proving the game theoretic value of Chess. Even for proving that White has a draw; i.e. that White is not in zugzwang in the starting position. We may feel very strongly that the notion is absurd, but I doubt we'll see a proof in my lifetime.

"Solved" in TFA sense is about a class of proofs being discovered, not about merely digital chess software playing better (even if they win every game).

Yeah but this is not very useful concept in practical play and that was the context of my comment. Chess is at different stage today than it was a few years ago. The difference is that no matter what resources and how much time your opponent have they will not beat you as long as you remember the line shown by your home PC.

I call it "weakly solved in practice" because it's exactly that: our (chess players) reality today is exactly the same as if chess was actually weakly solved.

>Yeah but this is not very useful concept in practical play and that was the context of my comment.

This depends on whether the solution can be "memorized" so to speak. For games where it can, it makes playing meaningless.

Obviously. The point is that in interesting games (for example chess) the solution can't be memorized but parts of it can. The point is that in chess we have a solution as good as the mathematical one today (for all practical purposes). It's an interesting point because it matters for practical players - you're no longer afraid your opponent or their team can find "holes" (that is weak moves) in your preparation. You're now only afraid they will play moves you didn't expect.

Chess isn't remotely solved. AlphaZero trounced StockFish, playing moves that StockFish never thought possible. Meanwhile, some say that StockFish has since caught up. But regardless, if cheese engines keep getting better and bearing previous ones, then in no way can you say that any current engine has "solved" chess because a different version will beat it next year.

"Solved" doesn't mean "beats humans."

I see your point about what "solved" would mean for humans, though.

I am sorry but this is completely wrong. It's true old Stockfish lost to Alpha Zero with specific rules, most notably no opening book which classical engines weren't supposed to be used at in competitive play (which is the reason SF doesn't ship with even a basic one - the user is supposed to use their own) and only one minute per move.

People were able to beat "Stockfish with one minute per move with no opening book" back then given enough time and strong hardware. It's no longer the case. Chess from starting position is completely dead in computer/centaur play/correspondence play. No one is able to win a single game vs an engine running on a home PC even if they can use arbitrary amount of computing power to help.

As to engines getting better: they don't get better anymore at playing chess from starting position. They get better at playing chess starting from set of unbalanced positions (chosen to be on the edge of winning/drawn) which would never occur from engine play from starting position.

My point wasn't about humans but about chess in fact being weakly solved. We just don't have a mathematical proof yet.

What? The idea that chess engines have stopped improving is ridiculous. StockFish is continuously improving. And is not just better hardware. For instance, just a couple of years ago StockFish added NNUE. This actually decreased the number of nodes it could look at per second, but the improved algorithm was so much better it bumped it's ELO by another 80 points.

It would be hubris to say "Ok, it kept improving up until last month or so, but now it's perfect."

If it's still improving, that means the current version can be beaten. If it can be beaten, that means we haven't solved it yet.

> No one is able to win a single game vs an engine running on a home PC even if they can use arbitrary amount of computing power to help.

I'm not quite sure I understand what you're suggesting, because it's not clear what "arbitrary computing power" means -- are they also running StockFish? If so, we already know that StockFish in better hardware runs better, so this is meaningless in a normal game, but I am guessing you mean with no time limits.

Is your suggestion that StockFish of 2020 will always draw against StockFish of 2023 if they have "unlimited time?"

If so, this seems slightly tautological. Chess is finite, so we have always known that "given enough time" anyone could enumerate all the possibilities. But if we restrict the time to, say, an hour per move, perhaps you'd say that's not "unlimited" enough.

But I'm actually interested. Has anyone tried 2020 StockFish vs 2023 StockFish with huge time allowances?

I have written that chess engines stopped improving at chess played from starting position - it's a draw every time (well, unless you really push them to play very fast on limited hardware). The reason we assess current Stockfish as stronger engine than Stockfish from 2 years ago is that it is better at playing chess starting from different positions than a standard starting one.

In terms of weakly and strongly solved you could say that modern Stockfish is a step closer to strongly solving chess than previous one (it is able to win more winning positions and find draws in more difficult drawn positions). It is however not able to win from standard starting position (what we call chess).

It seems to me you're not familiar with how chess engines are tested and compared and your misunderstanding of the state of the affairs stems from that.

>>Is your suggestion that StockFish of 2020 will always draw against StockFish of 2023 if they have "unlimited time?"

You don't need unlimited time. You need less than 30 minutes per move on modern top of the line consumer CPU. Probably much less but I want to be safe. You also need an opening book if using Stockfish before NNUE. It had a very well known weakness in the openings and wasn't designed to be used without an opening book. If the goal was to ship a strongest engine in as-is state the programmers would add a few megabytes of book moves - resulting in still smaller executable than modern NNUE version. They didn't because everyone used their own book anyway.

If NN engine "contains" an opening book is a philosophical question heavily debated by chess programmers. It didn't matter for a long time until Alpha Zero team exploited it to make their engine look much better than it really was.

>>But I'm actually interested. Has anyone tried 2020 StockFish vs 2023 StockFish with huge time allowances?

It's pointless from starting position (with caveats above). That's also the reason correspondence chess is dead. Rare wins come from mistakes in move entry or failure to run an engine for 30 seconds for whatever reason. Top correspondence players - guys who used to run multiple huge machines for days or weeks to find any tiny edge with often custom software to guide the engine can't win vs bare unattended Stockfish running on a Threadripper for 30 minutes or less per move anymore.

> Is Othello like checkers, where there were mostly draws in high level games?

Othello tends to have huge score swings in the end game. I think it’s even hard to get a draw from a typical mid game position if both players were to aim for it.

This result may change that, of course.

Depends if you like 'solved' games. Are chess tournaments useless if computers are better? https://www.chess.com/forum/view/general/chess-will-never-be...

I don't understand this comment. Computers are not allowed to play in the championship.

I confess to being dumb and not understanding it's a human championship. My bad!

chess engines are good enough to be effectively solved compared to human play, so not really more than chess tournaments.

Probably

See: Le Sedol [1] after AlphaGo:

"On 19 November 2019, Lee announced his retirement from professional play, stating that he could never be the top overall player of Go due to the increasing dominance of AI. Lee referred to them as being "an entity that cannot be defeated""

[1]https://en.wikipedia.org/wiki/Lee_Sedol

That is one player's choice, but not even close to a majority one.

Chess and Go and Checkers competitions have not disappeared after humans stopped being the best players of them.

IN what could be interpreted as irony, Lee Seedol went on to invent more board games.

https://www.dicebreaker.com/series/wizstone/news/go-player-d...

Someone should probably let Shin Jinseo know that the Go world championships are now "moot", because he appears to still spend a lot of time training and practicing for them.

Reply on news.ycombinator.com