Othello Is Solved?
arxiv.org
arxiv.org
But no elaboration? Sounds to me like the game is not solved, instead the author looked pretty hard for a winning line, and didn't find one.
There are other proofs like this - the 4 color theorem one, which was also reduced to a finite number of configurations which were manually colored.
Also curious: in the end of the paper they talk about having "weakly solve" Othello... the paper overall reads really strangely.
But given the overall state of that paper I think this is a side concern at best anyway.
It's the default for all reasonable games - statespace is huge (i.e. tic-tac-toe is childsplay) and simple strategies don't exist (that'd make bad human game). You can't even iterate all positions - even less prove them all for one outcome.
It is the default and all that matters.
This is one of the dangers of reading papers as a non-expert. You can dismiss or be wowed by something that is totally irrelevant.
They wrote the paper very much like the Checkers paper from Science 2007.
- the game is obviously known to be a draw
- but we don't have computational power to enumerate that
- so test a bunch of game states
- and confirm that none of them are wins
- ???
- it's solved! Trust me!
The process used generates a statistical approximation and tells you how close it is to correct, in theory a perfect solution would beat this by that amount, in practice of course Poker is a game of chance, and so over any realistic game it wouldn't matter because the deviation from correctness they've computed is tiny. Could they make an even smaller deviation with more compute used? Sure, but why bother.
https://en.wikipedia.org/wiki/Cepheus_(poker_bot)
Cepheus is instructive also because some humans have played against this and believed they were outplaying it, which indicates there are real human poker players who misunderstand their own variance so much (and/or discount real variance from others so much) that they're completely unable to successfully rate their abilities.
If you lose 12Bb over 100 hands you are not, in fact, "winning except that it sometimes gets lucky". You're just losing, of course it sometimes gets lucky, that's how luck works, it's a game of chance.
You have a ~10% chance over 100k hands to be <0 dollars earned. Likewise, 10% of time time you'll make twice that. Poker is fascinating in that there are a ton of people who never actually hit the true law of big numbers hands and walk around thinking "I'll never be good enough to play at X level" or "I'm a poker god with big winnings" not knowing how good they really are.
Professional players do actually get in statistically significant sample sizes, but for amateur players, most don't get enough hands to really understand their skill level.
The next sentence:
> Although there are numerous ways to select subsets that would prove the initial position results in a draw, we used algorithm 1 to obtain a small subset.
Algorithm 1:
> We developed an algorithm that requires predictive scores for all positions with 50 empty squares and returns a subset such that if the all positions belonging to that subset are solved, and the all solutions match the predictions, the initial position is consequently solved. It was described as Algorithm 1.
(The algorithm is also printed out)
From start of game to 50 squares left is enumerable.
From 36 moves left to end-of-game is apparently solvable.
The middle is the combinatorial explosion, and he avoids explaining how he navigates it.
A nitpick, but I don't think you meant to say "enumerable" here
"enumerable" means "able to be enumerated, or counted"
https://webstersdictionary1828.com/Dictionary/Enumerate
"innumerable" means "unable to be numbered, or counted"
The beginning and end of the game have less possibilities to consider. The midgame has the most possible moves = hardest to calculate.
If you read carefully, the midgame is the bit the author avoids explaining how to solve ;)
It's possible the author is correct, I'd need to really sit down and try to work out their reasoning but at first pass I'm skeptical.
The script at https://github.com/eukaryo/reversi-scripts/blob/main/reversi... plays perfectly (assuming the whole thing is correct) a bunch of data computed by other scripts in the repository using the 36-empty-squares solutions, for which a regular machine is presumably suitable.
It seems that what it does is essentially look up a <=300GB table with all positions with 37-64 empty squares reachable from the weak solution, and runs edax with "-solve" for positions with <=36 empty squares.
I don’t see a lot of people saying this (not parent either), but I know that many hope for closed-form solutions to things, even secretly.
It just dang doesn’t look that way anymore. Weird when a finite set is sufficient to prove subproblems that cover a perplexingly different or larger domain.
Whether a proof is accepted or not, we’ll still kinda wonder on the structure of special cases in computational complexity. They seem to work unreasonably well, and we rarely find them by hand/brainmeat.
There are certain squares that you should avoid placing pebble on as the game develops - equally there are squares that you should definitely try and place a pebble on if you can.
Implementing these rules can give you a fairly decent opponent and it's interesting to see how quickly people will ascribe "intelligence" to something that is very simple.
The heuristic algorithm won by a landslide -- 60 to 4 or worse (I don't remember exactly).
https://vintageapple.org/byte/pdf/198107_Byte_Magazine_Vol_0...
Who is actually "ascribing intelligence" to this? Othello has been on $10 LCD games that take double AA batteries.
I haphazardly ascribe intelligence to too many things.
Someone had to come up with the heuristics and then baked it into rigid rules. For the outside observer it's impossible to tell if it's baked or if it's being intelligently decided on the fly.
So you mean AAAA?
Is Othello like checkers, where there were mostly draws in high level games?
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.
From the computer point of view, it's more possible states to explore, so I think it makes things much harder
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.
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.)
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).
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?"
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
That's the easiest part.
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.
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
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.
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.
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""
Chess and Go and Checkers competitions have not disappeared after humans stopped being the best players of them.
https://www.dicebreaker.com/series/wizstone/news/go-player-d...
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.
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.
This depends on whether the solution can be "memorized" so to speak. For games where it can, it makes playing meaningless.
"Solved" doesn't mean "beats humans."
I see your point about what "solved" would mean for humans, though.
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.
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?
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.
I solved a simpler game about 15 years ago that my brother and I used to play: an African game with about 10 pits on each side of the board that hold stones. I coded up an alpha-beta engine for it, and discovered crazy always win strategies to match how my brother and I played. Suddenly I would win all the games, and then he never wanted to play again. This was a classic match up of a computer scientist vs. an optometrist.
There’s a joke in here about perspective
... I'll see myself out.
https://en.wikipedia.org/wiki/Mancala if you want more info
And it is indeed mentioned under the Names and Variants section. Seems likely that there's a historical connection somewhere.
..cringe...
Doesn't that sentence sound bizarre to you? Is that why people bowl? And isn't the implication that American males need help learning social skills?
They played the game for the same reasons that all humans have played games for millennia.
It’s instructive to see old Africans playing Mankala. They play very fast. It can become more like poker, where deceit is a part of the game. If you spam down your stones fast enough sometimes you can skip a bowl, or drop an extra stone, in order to gain advantage.
I’m not facile enough to play this way, and I play with family and so don’t cheat. It’s a very different thing, though. Like the difference between British ladies playing slow Mahjong over tea, versus people playing for money in a gambling room in China.
What you describe is just a talent at cheating, and I assume against the rules of the game. In poker, bluffing is an explicit part of the game allowed by the rules. I wouldn't even call it "deceit" in that context. At the very least, these are highly distinct categories of deceit.
The rules state that property owners can ask for the rent until the next player rolls the dice.
Even when you adjust for population and CD key pricing.
I wouldn't equate skipping a bowl with bluffing. Maybe, palming a chip as you put your bet in: which certainly isn't "part of the game".
Sports have a lot of things that are in some sense against the rules, but standard penalties are applied if caught, and it's just a part of the game, like fouling a player in basketball. Nobody considers it cheating, it's a part of the game because the penalty is standardized. Of course you still try not to get caught.
Fouls are conserved and used throughout the game. They're usually somewhere between intentional and accidental - you'd rather get your hand on the ball and not foul if you can. But you'd often rather foul than they get the 2 points if those are your only options. And how many fouls you have left against their best shooters is a major consideration throughout the game.
There's an anecdote about some Kobe Bryant trash talk that I think demonstrates both that fouls are valued for stopping 2 points, but ALSO the per-player foul limit is an additional consideration and separate strategic consideration.
> So we were playing, and you know it was like a two-on-one break. And, Caron Butler fouls and stops the break. So everybody was like, "Good job! That stop stops two points."
> So, Kobe comes out... and we’re all like, "Good, Good. You saved two points."
> Kobe walks over to him and says, "Hey, who are you guarding?", and Butler responds, "You!", and he goes, "Huh... How many fouls you got?". And Caron says, "I got one!" and Kobe says, "So you only got five left? Well, you need all six fouls to guard me, and you just wasted one... on him! It’s a stupid... stupid play!"
> And you had to think about it like... "God, he’s right!"
computer scientist vs. an optometrist.
What does being an optometrist have to do with anything?
"classic" here is tongue-in-cheek
I imagine generally the upper limit on always winning is higher. As in, usually the person consistently losing wants to stop playing before the player consistently winning.
I’ve found that I can really enjoy myself without crushing my 6yo or it feeling like it’s just a luck-based game.
In theory there is no luck. But in practice you can't calculate that far ahead, due to the chain reactions.
You can easily make your own board.
(The ‘AI’ player is very weak)
(Nice job BTW)
Original author’s website: http://radagast.se/othello/
A github source: https://github.com/hoshir/zebra
https://mame.github.io/6x6-reversi-oracle/
via: https://twitter.com/mametter/status/1476379841004183556
I didn't know 8x8 was unsolved until now.
But what if someone plays imperfect Othello? I heard Magnus Carlson will start his games with completely unorthodox opening moves to throw his opponents off kilter because they're always used to playing well-known moves. Will this AI work against that tactic as well?
Basically in games with no hidden information (chess, go, othello, etc) how you got into a game state does not matter. If your AI can play perfectly then it can make the perfect move from any state.
You actually used to be able to. That’s part of how Kasparov beat Deep Blue in ‘96 IIRC - by forcing the game into unusual situations where the computer would have fewer prior games to pattern match off. But by the rematch heuristics for “off book” situations had improved, and the same strategies failed (or even backfired).
In Othello the number of pieces go up and down in weird patters, so a draw is very surprising for me.
Has anyone checked the proof?
Edit: Is Othello solved for smaller boards? Can this proof be aplied to smaller boards?
And especially: https://archive.org/details/byte-magazine-1980-07/page/n57/m...
That Byte article is about implementing practical heuristics to create a human like player as opposed to completely exhaustive play which was most definitely impossible on early 80s machines.
I happened to implement a version myself at https://luduxia.com/reversi/
https://en.wikipedia.org/wiki/Reversi
By the way - in the general case (NxN board, arbitrary position) - determining whether there's a winning strategy is a PSPACE-complete problem.
"Othello is now solved, computationally proved that perfect play by both players lead to a draw."
I could never win against my creation :-)
After a while, that got dull so I wrote a little program that would randomly POKE into the game's memory space. The usual result was a crash, or a program that didn't know how to play, or would only put pieces on the lines instead of the empty cells, that kind of thing. Every so often, though ... it would just play a little differently against me. No crashes, no weirdness. I always wondered what exactly had gone on with my random mutation there: was there some table of position evaluations whose weightings I had tweaked? A rule jumped over in the code?
On a related note, are there any Wikipedia list articles which are empty lists?
Rest assured that no computer will ever dominate a human opponent at Candyland.
For the spinner version of the game, the computer could use a physical or statistical spinner model to gain an edge.
https://en.wikipedia.org/wiki/Solved_game#Solved_games
Not being on that list doesn’t necessarily make a game harder; it may just be less popular with computer scientists.
Did not see that coming. That just makes the game more interesting I think.
We had an expert Othello player in our class who helped with fleshing out strategies for scoring the boards, in the end it was pretty difficult to beat.
Used alpha-beta if memory serves.
Note that professional players are far from mastering 9x9, and regularly play 9x9 tournaments.
Solving the full 19x19 game is utterly out of the question.
[1] https://forums.online-go.com/t/katago-attempts-to-solve-7x7/...
https://en.m.wikipedia.org/wiki/Solved_game
That would point to there being no advantage in perfect play. However, in imperfect play, the first or second player could still have a measured advantage.
Imagine having the hubris to describe your own paper like this.
I wish that the superconductor debacle (and many others) had taught people critical thinking and skepticism. And yet this is the #1 post on HN right now.
In contrast, this is not spouting a revolution in physics, but a mathematical puzzle that is mostly trivia. I suspect that the best computer Othello algorithm can already trounce a human.
"Solving" a game is not "trivia" or a "puzzle". It's an actual mathematical problem that requires nontrivial proofs for nontrivial games. Think about it: a game as "simple" as checkers was only solved in 2007.
> I suspect that the best computer Othello algorithm can already trounce a human.
That's a completely different problem. Chess computers are much, much better than humans, but chess is far from being solved.
How hard a game is to "solve" at least using traditional algorithmic techniques is related to its search space. That is a combination of the length of the game and the number of possible moves in each position (ply and branching factor). Chess has more possible positions than exist atoms in the universe by some estimates. Checkers has a tractable, for modern supercomputers, 500 billion possible positions with about a ~6 branching factor over an average of ~50 ply games.
Othello is several orders of magnitude more complex than checkers but not quite at the level of chess. So, this is a big claim. It's by no means trivial.
I don't think anyone was saying it's easy, just that they didn't think it was very useful to know.
> It's not obvious to me that othello is much more complicated than checkers.
How is that not saying it's trivial when the context is a thread mentioning that Checkers has already been solved.
They then went on to qualify their statement with the information that they don't specifically remember the rules of Othello. In a discussion held in good faith, this should be assumed to be an invitation to add additional insight as to why Othello might be more complicated.
You either know the reason why and didn't state it, or believe it's more complicated based on authorities you trust and didn't relate that and instead stated it authoritatively, or don't know it at all and misrepresented it. None of those are very useful for discussion. The former two are easy to rectify by explaining, qualifying, or referring someone to additional info though, and would have been a more useful way to respond.
Ultimately though, it sort of feels like you're reaching for an additional interpretation that makes an earlier misinterpretation still valid, when you could just say "oops. Most of my comment still stands as accurate, but I guess I misinterpreted your point."
Edit: from looking at you profile, it appears you are a CS professor. Perhaps part of the issue is context. This is a public forum, not a classroom, and while in a classroom your statements can be taken with an assumed authority, nobody necessarily knows that about you here when you post, so some additional qualification of your statements or background may be warranted.
I guess you're either in a frame of mind you can accept it as it was meant or you aren't.
I think the OP was saying that since Checkers is solved and they "think" Othello is similar it would be easy to solve, implying that since we can do one we can do the other. I was disputing that notion.
Ok, so, do you trust everything posted on the Internet until you verify it?
I really think "distrust but verify" is a heck of a better rule, unless your source has a really solid track record.
Given that most papers don't replicate, and most hype ends up BS, "don't trust until it's verified" is a much better rule.
Doesn't it make sense to give some visibility to such claims so they can be verified? I would think a lot of people on HN are equipped to take part in this informally.
But I agree with you that the title is too categorical and should be updated.
No one has said you’re not allowed to be excited if you want. Just like GP is allowed to be a wet blanket if they want.
Speaking of “get over yourself.” I’m so tired of this “if you don’t completely validate and elevate my feelings then you’re bad/mean and preventing me from feeling what I want” crap. God forbid anyone ever disagree with you.
Some people are looking for facts and science, and some are looking for enthusiasm and excitement. Can't discount either one, I suppose.
People getting each other excited by pretending fiction is reality is called religion. That's fine if people are honest about it.
My admonition "get over yourself" is a response to this ridiculous idea that science should be a joyless affair. It isn't, and must not be. Historically, fuddy-duddy downers don't make the big discovaries.
To conclude something about P ?= NP, they would have to have solved the NxN board for all N.
Against who? You were playing against beginners?