For those interested in the game (it's popular among computer science and AI scholars), the Othello world championship is currently underway in Rome, Italy with games live streamed on liveothello.com and Youtube @WorldOthello
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.
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.)
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).
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.
> 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 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.
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.
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.
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.
> 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.
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.
"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""
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.
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.
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.
Othello is one of those games that works really well for playing with young kids. The rules are simple. There’s patterning to learn. It’s fun to cause massive flips. And best of all, it’s just as fun for the adult as it is the kid.
I’ve found that I can really enjoy myself without crushing my 6yo or it feeling like it’s just a luck-based game.
> Next, we selected 2,587 positions out of the aforementioned 2,958,551 positions and formulated hypotheses regarding
their outcomes. We chose them such that if all these hypotheses were proven correct, it would prove that the initial
position results in a draw.
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.
"Weakly solving" a game is a technical term. If you have weakly solved a game, you can play perfectly (achieve the optimal result) when the game starts from its initial position. If you have strongly solved it, you can play perfectly starting from any position.
Sorry, I was unclear: I know what weakly solved means. What I find curious is that the title and abstract refer to "solved", and don't mention what they actually mean. To me "solved" would suggest "strongly solved". But perhaps equating "solved" with "weakly solved" is default in this area? Still, I would like expect an abstract to say something like that explicitly.
But given the overall state of that paper I think this is a side concern at best anyway.
> To me "solved" would suggest "strongly solved". But perhaps equating "solved" with "weakly solved" is default in this area?
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.
And you can go further Heads Up (ie two player) Limit (ie you decide to raise or not, the size of the raise is fixed) Texas Hold 'Em (the style of Poker most played today) is essentially weakly solved.
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.
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.
Poker being one of my favorite hobbies (probably 300k hands played lifetime), it's wild how much variance matters. Like a 4BB/100 winrate (aka you win 4 big blinds every 100 hands) is very much an "I can be a professional" winrate.
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.
I only skimmed it, but it looks like they described this to me.
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.
I also got confused at this part. I've now read the paper twice and I'm not sure I understand their method. Overall the way the paper is written is not straightforward.
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’m not taking a stance on “Othello is solved”, but offer a digression about a lookup table being a valid solution to a tractable problem, or its subproblem.
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.
It wouldn't be the first time an unknown solves a major problem. And Othello is not exactly the Riemann hypotheses - meaning it wasn't as studied and there could be a low-hanging fruit.
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.
If you consider that in the early game you want to keep low your number of pieces (because it keeps the number of possible moves high), it becomes somewhat obvious that going second is not a disadvantage at all.
There is no disadvantage to going second... in fact, in tournament games, the player to go second (white) wins about 2% more often than black does. All of black's first moves actually transpose, so white has the first real choice in the game, and also usually has the last move in the game, which can be an advantage.
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.
A small amount of basic theory (which areas to target and which to avoid, how to keep your numbers low in the early game, etc) is enough to look like a master among casual players; but the advanced game can be fiendishly hard.
Othello is a great game to demonstrate how powerful some basic heuristics can be.
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.
Yeah, I remember my ~200 lines Pascal program running on PDP-11 beat everyone in the lab, that was quite astonishing. It completely solved the rest of the game when 19 free spaces remained.
I read an article many years ago on programing Othello. I think it was BYTE Magazine, circa early 1980s. It mentioned pitting an app using a simple heuristic technique similar to the one you describe against an app using an equally simple (but devastatingly horrible) "flip the most squares" approach.
The heuristic algorithm won by a landslide -- 60 to 4 or worse (I don't remember exactly).
Not the article you mention but there is a fun article in this BYTE from 1981 on a computer Othello tournament that really illustrates how far we've come. This edition of tha mag is also notable for its point in time history, as it has an editorial about the coming IBM PC and quanit ads from Apple and Microsoft that give no clue as to the revolution coming.
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.
Who is actually "ascribing intelligence" to this? Othello has been on $10 LCD games that take double AA batteries.
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.
Back in the day, when normal people hadn't been exposed to these things (let alone understand them), there was a strong tendency for people to ascribe intelligence to them. Making that sort of mistake really is a strong human tendency that has to be guarded against.
Impressive! I used to play this all the time as a kid but I kinda forgot it existed for a while, so this was fun :) I scored 31 against the computer's 33 :/
The thing I love about Othello is the contradiction between action and territory. While the game develops, playing your turn is in some sense against you, yet you must. Hence, you need to remain compact and inner while you occupy, until space becomes too small and its time to reclaim definite influence.
Correct title: an unknown author from an unknown startup claims in an arXiv preprint (listed somehow in the cs.AI archive) that Othello has been solved. The paper is 13 pages long.
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.
Trust but verify. People were excited, but pretty much the first thing on everyone's mind was looking for replication.
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.
It's not obvious to me that othello is much more complicated than checkers. Admittedly, I haven't played since I was a kid and I don't completely remember what the rules are.
So you don't really know much about the computational complexity of the game and you're saying it's trivial.
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.
In the past, "solving" games has often been done through novel changes in hardware and/or approaches and algorithms as I understand it. The person you replied to stated that they didn't know why Othello was an achievement beyond checkers. That doesn't mean it's trivial, but it also doesn't mean it required any additional insight or advances to do so if it's not specifically more complicated than checkers.
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'm not sure if it's a matter of good faith or not to see that you were responding to statements that not only the person you're responding to didn't say, but weren't actually said by the original person (trivia != trivial). That said, I assumed you actually care about what you are communicating, so provided what I thought was constructive criticism.
I guess you're either in a frame of mind you can accept it as it was meant or you aren't.
I didn't say Checkers was trivial to solve. I said Othello is much harder to solve than Checkers and therefore not trivial to solve as OP implied.
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.
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.
You really wouldn't want to have a post sit on top of Hacker News for an hour and nothing comes of it. Think of how much we could have gotten done on this messageboard otherwise!
Boo. The paper is cautiously written, addresses a very tractable and well-defined problem, confirms what experts expected, and is straightforward to implement (the source code is on Github). And yet this posturing is the #1 comment on this thread right now.
Great, then let's name it "Othello claimed to be solved", then pound it with peer reviews and reproductions for a bit, then we can phrase it as "Othello is solved".
You need to prove that the code is correct, that's the tricky part. Otherwise I could just write `return true;` as the whole code and tell people to run it, it's easy, just do the peer review yourself.
Given the myriad posts and articles about "huge breakthrough", "industry changing" and so on, scepticism in that case would translate to way more cynicism.
I thought the post is #1 on HN because people here are genuinely interested in the topic and would like to at least examine the paper and discuss the merits of it.
I was watching every development of that superconductivity claim. I was quite enthused! But never once did I move beyond "groundbreaking if true." This doesn't even have the potential to be groundbreaking. Get over yourself, let people get excited about little stuff.
> Get over yourself, let people get excited about little stuff.
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.
You can be enthusiastic and excited while looking for facts and science. In fact, my interest in rooting out truths tends to go hand in hand with my passion for the topic. Negative results are important for scientific advancement, and I was just as excited to see LK99 fully analyzed, despite it not turning out to be the holy grail. We always knew that was a longshot; I enjoyed the journey regardless of the destination.
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.
I would not call Preferred Networks an "unknown startup" - They've been prominent within the AI research community for quite some time and have contributed important projects such as CuPy and Chainer, the latter introducing the "define-by-run" concept which was later implemented in frameworks such as PyTorch and Tensorflow.
I had this for the Apple ][e and would play it, obsessively. At one point I had gotten good enough against the computer that the average game took ninety seconds, with the computer taking about as much time as I did. I eventually learned how to completely beat the computer such that it had no cells of its color. I took photos of a couple of instances just as proof.
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?
If you've played only Reversi the Othello variant may have some differences. Mainly, the starting board already has some pieces on it. The general gameplay and goal is maintained though.
Reversi is what I grew up playing back in Ukraine. I was pleasantly surprised to find out that it's popular (well, relatively) in the US as well under the Othello name and have taught both of my kids to play it too. They love it, and I love playing it with them.
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.
That is super cool. I’ve played Mankala for years and would love to hear more.
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.
> 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.
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.
Not the same. Because there is a penalty to challenging a word that turns out to be a real obscure word found in the dictionary (the official Scrabble dictionary if you playing seriously), it is a legitimate strategy (not cheating) to use obscure words early on, be proven correct when challenged, and then use fake words that opponents are wary of challenging.
It’s a famous saying from NASCAR and sort of tongue-in-cheek about how everyone is probably bending the rules as much as they can and if you aren’t you can’t compete with those that are.
It's said in many contexts. I have no interest in a civilization in which the only skill we select for is ability to eat and deceive your fellow man. And I don't believe nature would have much interest in it either.
The stats from various anti-cheat companies like Vanguard, PunkBuster, and BattleEye demonstrate that some nationalities/cultures believe this more than others.
Even when you adjust for population and CD key pricing.
I also wouldn't equate it with bluffing at all, but from the description, maybe also not palming a chip. It's possible for something that's cheating among one group to be a part of the game among another.
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.
I'm not sure I agree with this take on basketball strategy. I'm no expert, but my understanding is that intentionally fouling in basketball is largely a time-management move? Like, you want to be "caught" because that's the whole point -- you aren't seeking an advantage in play that the penalty is meant to offset, you're seeking the penalty.
Time management are an extreme scenario, NOT the main use of fouls.
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!"
When I was 14 and in my first year of college, the lady teaching my course in C gave me a project for an extra grade (because I had skipped a lot of classes, I think). Anyway, it was to program Mancala in C, which I did using Allegro Library I think at the time. Fun times!
Simpler times! I remember working on "Skateopoly", a skateboarding themed Monopoly, in middle school with JavaScript. I should code a fun little game, it's been a while...
It’s a lowly profession for those less cunning, scarcely worthy of mention alongside the intellectual ballet that is the domain of software and computers.
This is usually my approach when I'm playing too much of a game. I cracked my sudoku addiction by writing a solver. Got a lot less fun when I could tell my computer to solve it how I would solve it.
I carefully refrained from building an actual word-ladder solver, for that reason - instead I have a little dictionary-explorer script which will show me the next two layers of the tree, should I get stuck.
I can't remember the source for it (help me out if you know it), but people only like to play games when they're in the band of 30-70% winrate. Win too much or too little, and they'll stop enjoying playing the game.
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.
Also if you have time to play multiple rounds, then with a handicap you can set that you both have 50-50% chance to win, thus making the game really good, with adrenaline, the possibility to do your best for an extended period of time, and the reward for that.
284 comments
[ 3.1 ms ] story [ 256 ms ] threadIs 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""
[1]https://en.wikipedia.org/wiki/Lee_Sedol
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’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.
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://katagobooks.org/9x9highlights.html
"Othello is now solved, computationally proved that perfect play by both players lead to a draw."
I could never win against my creation :-)
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"
https://webstersdictionary1828.com/Dictionary/innumerable
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.
Did not see that coming. That just makes the game more interesting I think.
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.
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/
Against who? You were playing against beginners?
https://mame.github.io/6x6-reversi-oracle/
via: https://twitter.com/mametter/status/1476379841004183556
I didn't know 8x8 was unsolved until now.
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?
(The ‘AI’ player is very weak)
(Nice job BTW)
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.
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?
Original author’s website: http://radagast.se/othello/
A github source: https://github.com/hoshir/zebra
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
https://en.wikipedia.org/wiki/Southeast_Asian_mancala
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.