17 ms·

Othello Is Solved?

607 points by Tepix 3y ago

lukasb 3y ago
So the perfect game is played to a draw - does this mean that competitive play is over? Or is it impractical for human players to memorize the moves required to punish deviation from the perfect game?
Tepix 3y ago
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
- bediger4000 3y ago
  Does this paper render the championship moot? Is any software based on the paper entered? Is Othello like checkers, where there were mostly draws in high level games?
  - axlee 3y ago
    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.
    - Diggsey 3y ago
      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.
      - axlee 3y ago
        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.
        jfengel 3y ago
        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.
        forty 3y ago
        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.
        Detrytus 3y ago
        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.
        forty 3y ago
        Solve a 2x2 Rubik's cube and see if that helps solving a 4x4 ^^ From the computer point of view, it's more possible states to explore, so I think it makes things much harder
        Detrytus 3y ago
        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.
    - kelsey9876543 3y ago
      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.
      - addaon 3y ago
        > 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.)
        uxp8u61q 3y ago
        Foot races are also solved - these losers should just get a car!
        kelsey9876543 3y ago
        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.
        coldtea 3y ago
        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).
    - mtlmtlmtlmtl 3y ago
      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.
      - mkesper 3y ago
        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-profiteure/ https://www.fiaa.at/theories/die-3-punkte-regel-und-ihre-pro...
      - bluGill 3y ago
        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.
      - axlee 3y ago
        > 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.
        3y ago
  - graphe 3y ago
    Depends if you like 'solved' games. Are chess tournaments useless if computers are better? https://www.chess.com/forum/view/general/chess-will-never-be-solved-heres-why https://www.chess.com/forum/view/general/chess-will-never-be...
  - Someone 3y ago
    > Is Othello like checkers, where there were mostly draws in high level games? Othello tends to have huge score swings in the end game. I think it’s even hard to get a draw from a typical mid game position if both players were to aim for it. This result may change that, of course.
  - cvoss 3y ago
    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.
    - charcircuit 3y ago
      >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.
      - lcuff 3y ago
        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.
        deleted 3y ago
        [deleted]
      - deleted 3y ago
  - AndrewKemendo 3y ago
    Probably See: Le Sedol [1] after AlphaGo: "On 19 November 2019, Lee announced his retirement from professional play, stating that he could never be the top overall player of Go due to the increasing dominance of AI. Lee referred to them as being "an entity that cannot be defeated"" [1]https://en.wikipedia.org/wiki/Lee_Sedol https://en.wikipedia.org/wiki/Lee_Sedol
    - kadoban 3y ago
      That is one player's choice, but not even close to a majority one. Chess and Go and Checkers competitions have not disappeared after humans stopped being the best players of them.
    - JoeDaDude 3y ago
      IN what could be interpreted as irony, Lee Seedol went on to invent more board games. https://www.dicebreaker.com/series/wizstone/news/go-player-designs-abstract-games https://www.dicebreaker.com/series/wizstone/news/go-player-d...
    - nimih 3y ago
      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.
  - bluecalm 3y ago
    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.
    - tromp 3y ago
      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.
    - coldtea 3y ago
      "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).
      - bluecalm 3y ago
        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.
        coldtea 3y ago
        >Yeah but this is not very useful concept in practical play and that was the context of my comment. This depends on whether the solution can be "memorized" so to speak. For games where it can, it makes playing meaningless.
  - rc_mob 3y ago
    I don't understand this comment. Computers are not allowed to play in the championship.
    - bediger4000 3y ago
      I confess to being dumb and not understanding it's a human championship. My bad!
  - waveBidder 3y ago
    chess engines are good enough to be effectively solved compared to human play, so not really more than chess tournaments.
Waterluvian 3y ago
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.
- captn3m0 3y ago
  I also like Blokus for similar reasons.
  - ramses0 3y ago
    Blokus Duo is king!
- hermitcrab 3y ago
  Suggest also having a look at Hus (one of the family of African stone games): https://mancala.fandom.com/wiki/Hus https://mancala.fandom.com/wiki/Hus 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.
bradwood 3y ago
How about the ancient Chinese game of "go", next? Not convinced that can easily be solved at all.
- mikpanko 3y ago
  Among popular board games, Go is more computationally complex than chess, so the latter would probably be solved first.
- tromp 3y ago
  Go is considered close to being solved on a 7x7 board [1]. The grand challenge would be solving 9x9 Go, the standard beginner board size. 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/38521 https://forums.online-go.com/t/katago-attempts-to-solve-7x7/...
  - mafuy 3y ago
    There was a recent push for 9x9. It's not solved but it is believed to be near perfect play. https://katagobooks.org/9x9highlights.html https://katagobooks.org/9x9highlights.html
KingOfCoders 3y ago
One of the first games I've coded as a kid was Othello. "Othello is now solved, computationally proved that perfect play by both players lead to a draw." I could never win against my creation :-)
- antivirus0101 3y ago
  If your creation plays perfectly ;)
sdwr 3y ago
> 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.
- dist-epoch 3y ago
  More likely, those 2587 positions cover all possibilities. 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.
  - BlackFingolfin 3y ago
    But none of this explicit. This is at best an announcement of a potential proof. But it isn't a proof yet. Also curious: in the end of the paper they talk about having "weakly solve" Othello... the paper overall reads really strangely.
    - dfan 3y ago
      "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.
      - BlackFingolfin 3y ago
        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.
phkahler 3y ago
>> Othello is now solved, computationally proved that perfect play by both players lead to a draw. Did not see that coming. That just makes the game more interesting I think.
sciolist 3y ago
Is this legit? It seems weird to me that this paper has one author, from a deep-learning startup which I've never heard of before.
- dist-epoch 3y ago
  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.
- thenoblesunfish 3y ago
  The fact that they describe their own result as monumental raised my eyebrows. Presumably this is being peer reviewed?
makach 3y ago
Does that mean there are no disadvantages going second?
- chaboud 3y ago
  Having not read the paper, it sounds like the author is asserting that the game is solved under perfect play as a draw. https://en.m.wikipedia.org/wiki/Solved_game 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.
- toyg 3y ago
  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.
- foompy_katt 3y ago
  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.
fidotron 3y ago
There is a lot of good background on Othello like: https://en.wikipedia.org/wiki/Computer_Othello https://en.wikipedia.org/wiki/Computer_Othello And especially: https://archive.org/details/byte-magazine-1980-07/page/n57/mode/2up?view=theater 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://luduxia.com/reversi/
Avlin67 3y ago
no, Othello is not complex, I do not remember exactly how but i did play a lot when i was you and did find a way to win consistently...
- jmmcd 3y ago
  And if you played against yourself, did you still win?
  - sebastiennight 3y ago
    Plot twist: GP is the author of the paper, and your question is how they demonstrated that "both players playing perfectly leads to a draw".
- laurentlb 3y ago
  > did find a way to win consistently... Against who? You were playing against beginners?
- toyg 3y ago
  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.
omoikane 3y ago
Related, here is one that plays 6x6 perfectly: https://mame.github.io/6x6-reversi-oracle/ https://mame.github.io/6x6-reversi-oracle/ via: https://twitter.com/mametter/status/1476379841004183556 https://twitter.com/mametter/status/1476379841004183556 I didn't know 8x8 was unsolved until now.
- namtab00 3y ago
  I can't get one single black... it's this what perfectly means?
  - Tepix 3y ago
    It will manage a draw even when the opponent plays perfectly, too. And it will get the optimum number of pieces.
orzig 3y ago
"Minutes to learn ... A lifetime to master" Not anymore!
Elena120 3y ago
[dead]
iamflimflam1 3y ago
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.
- EVa5I7bHFq9mnYK 3y ago
  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.
- keitmo 3y ago
  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).
  - kjellsbells 3y ago
    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. https://vintageapple.org/byte/pdf/198107_Byte_Magazine_Vol_06-07_Energy_Conservation.pdf https://vintageapple.org/byte/pdf/198107_Byte_Magazine_Vol_0...
  - lanstin 3y ago
    I read that same byte article, wrote a basic version that played the heuristic way, and was unable to beat it. Good times.
  - 3y ago
gmac 3y ago
If anyone fancies playing the game, I made this for/with my kids: https://jawj.github.io/fliptiles https://jawj.github.io/fliptiles (The ‘AI’ player is very weak)
- hermitcrab 3y ago
  I was even weaker. ;0) (Nice job BTW)
- deleted 3y ago
  [deleted]
- mumintrollet 3y ago
  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 :/
  - gmac 3y ago
    Likewise! My daughter played it at a friend’s house and enjoyed it, which is what reminded me and prompted me to make this.
- simondebbarma 3y ago
  Not sure how impressive a draw is, but I did a 32-32 for my first play through. Thanks for teaching me a new game!
amelius 3y ago
Ok, so we just have to keep adding rows and columns to the game in order to keep the game from being "solved"?
- dzolob 3y ago
  Someday there might be a theorem. Something on the line of “for all nxn boards, a perfect game ends in a tie”.
  - amelius 3y ago
    Next challenge: (n+1)xn boards
dzolob 3y ago
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.
uxp8u61q 3y ago
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.
- fbdab103 3y ago
  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.
  - uxp8u61q 3y ago
    > a mathematical puzzle that is mostly trivia "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.
    - sebzim4500 3y ago
      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.
      - WoodenChair 3y ago
        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.
deleted 3y ago
[deleted]
at_a_remove 3y ago
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?
- pvg 3y ago
  That's more or less coming up with one of the ideas of Core War due to Othello Implementation Boredom.
CodeCompost 3y ago
Used to play an Othello game on my phone many moons ago. I always won by always going inside-out.
dzolob 3y ago
For those of you who think Othello is trivial, try Zebra. Original author’s website: http://radagast.se/othello/ http://radagast.se/othello/ A github source: https://github.com/hoshir/zebra https://github.com/hoshir/zebra
- NooneAtAll3 3y ago
  for those not getting what is "Othello" - it is also called Reversi
  - zamadatix 3y ago
    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.
  - archon810 3y ago
    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.
mark_l_watson 3y ago
This is cool. 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.
- notfed 3y ago
  Classic "Why nerds don't get invited to parties"!
  - roughly 3y ago
    > computer scientist vs an optometrist There’s a joke in here about perspective
    - rst4455 3y ago
      I'll byte... C#?
      - ornornor 3y ago
        Nice
    - elromulous 3y ago
      The brother lacked vision
    - gkuhl21 3y ago
      The optometrist couldn't believe his eyes. ... I'll see myself out.
- bentcorner 3y ago
  > an African game with about 10 pits on each side of the board that hold stones https://en.wikipedia.org/wiki/Mancala https://en.wikipedia.org/wiki/Mancala if you want more info
uncletaco 3y ago
Good ol’ Othello. I got an A in AI because I beat everyone else’s Othello player. You will always be the final boss of grad school.
avipars 3y ago
Link to paper: https://arxiv.org/pdf/2310.19387.pdf https://arxiv.org/pdf/2310.19387.pdf
gtbcb 3y ago
I would love a Wikipedia list article of games that have been solved computationally and but also games where humans can still beat computers / AI, discussing the challenges and context behinds wins / losses.
- Y_Y 3y ago
  Are there any board games left where humans beat the best computers? On a related note, are there any Wikipedia list articles which are empty lists?
  - kibwen 3y ago
    > Are there any board games left where humans beat the best computers? Rest assured that no computer will ever dominate a human opponent at Candyland.
    - musicale 3y ago
      The youngest player goes first in Candyland and has an edge on average. I assume this is by design. For the spinner version of the game, the computer could use a physical or statistical spinner model to gain an edge.
  - Marazan 3y ago
    I couldn't imagine any computer beating a human at any Collectable Card Game in the near term. Likewise I'd imagine that computers would be at a insurmountable disadvantage at Deck Builders like Dominion in the general case (in that I could easily imagine a Computer being trained to play perfectly on a specific Kingdom but no where close to a top human on a randomly selected Kingdom).
  - occamrazor 3y ago
    AFAIK there are no good bridge computer programs. A crucial difficulty is making sense of the bidding phase, and of signals during the card playing phase.
- Someone 3y ago
snitty 3y ago
Until someone gives me a convincing reason why Iago did it, Othello is NOT solved.
thomastjeffery 3y ago
weakly solved
Andrew018 3y ago
[dead]
entelechy0 3y ago
Because Othello is in PSPACE, and NP is in PSPACE, does this mean that P=NP?
- gus_massa 3y ago
  The preprint claims to have solved the standard 8x8 board. The result probably applied to smaller boards and perhaps wit some tweaks to slighty bigger boards (10x10???). To conclude something about P ?= NP, they would have to have solved the NxN board for all N.
munificent 3y ago
> The Othello result is a monumental achievement for humanity Imagine having the hubris to describe your own paper like this.
- lagt_t 3y ago
  A before and after in the history of mankind. A milestone carved in the memory of all mankind through time and space.
- ksd482 3y ago
  Perhaps its humor?
  - whirlwin 3y ago
    Maybe Schrödinger's satire. Either it's satire or not based on the reaction of the reader
- prof-dr-ir 3y ago
  The sentence certainly sounds arrogant, but I have seen such phrasing used also by novice authors who were simply trying to sell a result that they were enthusiastic about. Like the present article's author, these were always non-native speakers.
- deleted 3y ago
  [deleted]
- NotYourLawyer 3y ago
  Look upon my works, ye mighty, and despair.
- deleted 3y ago
  [deleted]
- deleted 3y ago
  [deleted]
gus_massa 3y ago
I'm very surprised it's a draw. It's not like chess where it's "easy" to exchange a piece for an equal one until the board is "empty" and it's a draw. (Yes, it's more complicated. I played a lot of chess until secondary school, and it's more complicated. But trading equal pieces is a good strategy to get a draw.) 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?
- Tepix 3y ago
  The most promising lines have long (decades) been known to result in a draw. There wasn't enough CPU power to brute force the entire search space.
  - gus_massa 3y ago
    Which is the bigest board that has been bruteforced?
- jchook 3y ago
  Starting with a 1x1, 2x2, 3x3, etc board size seems like a reasonable strategy for developing an intuition of the solution.
blindriver 3y ago
It sounds like they "solved" this using 2 AI players playing "perfect" Othello? 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?
- doikor 3y ago
  The AI can always continue with the perfect play from that imperfect state. That is what happens in chess as you can’t fool a good chess AI by making intentionally imperfect moves (chess is not solved so we don’t know if a move is perfect or not but you get the idea) 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.
  - 542458 3y ago
    > you can’t fool a good chess AI by making intentionally imperfect moves 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).
codr7 3y ago
Dang, brings back memories from AI class at university. 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.
einpoklum 3y ago
Oh, it's Reversi! https://en.wikipedia.org/wiki/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.
musicale 3y ago
Given that 6x6 Othello/Reversi was solved 30+ years ago, I'm a bit surprised it took this long for 8x8.
deleted 3y ago
[deleted]

607 points by Tepix 3y ago

So the perfect game is played to a draw - does this mean that competitive play is over? Or is it impractical for human players to memorize the moves required to punish deviation from the perfect game?

Tepix 3y ago

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

bediger4000 3y ago
Does this paper render the championship moot? Is any software based on the paper entered? Is Othello like checkers, where there were mostly draws in high level games?
- axlee 3y ago
  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.
  - Diggsey 3y ago
    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.
    - axlee 3y ago
      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.
      - jfengel 3y ago
        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.
      - forty 3y ago
        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.
        Detrytus 3y ago
        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.
        forty 3y ago
        Solve a 2x2 Rubik's cube and see if that helps solving a 4x4 ^^ From the computer point of view, it's more possible states to explore, so I think it makes things much harder
        Detrytus 3y ago
        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.
  - kelsey9876543 3y ago
    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.
    - addaon 3y ago
      > 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.)
      - uxp8u61q 3y ago
        Foot races are also solved - these losers should just get a car!
        kelsey9876543 3y ago
        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.
        coldtea 3y ago
        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).
  - mtlmtlmtlmtl 3y ago
    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.
    - mkesper 3y ago
      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-profiteure/ https://www.fiaa.at/theories/die-3-punkte-regel-und-ihre-pro...
    - bluGill 3y ago
      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.
    - axlee 3y ago
      > 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.
      - 3y ago
- graphe 3y ago
  Depends if you like 'solved' games. Are chess tournaments useless if computers are better? https://www.chess.com/forum/view/general/chess-will-never-be-solved-heres-why https://www.chess.com/forum/view/general/chess-will-never-be...
- Someone 3y ago
  > Is Othello like checkers, where there were mostly draws in high level games? Othello tends to have huge score swings in the end game. I think it’s even hard to get a draw from a typical mid game position if both players were to aim for it. This result may change that, of course.
- cvoss 3y ago
  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.
  - charcircuit 3y ago
    >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.
    - lcuff 3y ago
      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.
      - deleted 3y ago
        [deleted]
    - deleted 3y ago
- AndrewKemendo 3y ago
  Probably See: Le Sedol [1] after AlphaGo: "On 19 November 2019, Lee announced his retirement from professional play, stating that he could never be the top overall player of Go due to the increasing dominance of AI. Lee referred to them as being "an entity that cannot be defeated"" [1]https://en.wikipedia.org/wiki/Lee_Sedol https://en.wikipedia.org/wiki/Lee_Sedol
  - kadoban 3y ago
    That is one player's choice, but not even close to a majority one. Chess and Go and Checkers competitions have not disappeared after humans stopped being the best players of them.
  - JoeDaDude 3y ago
    IN what could be interpreted as irony, Lee Seedol went on to invent more board games. https://www.dicebreaker.com/series/wizstone/news/go-player-designs-abstract-games https://www.dicebreaker.com/series/wizstone/news/go-player-d...
  - nimih 3y ago
    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.
- bluecalm 3y ago
  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.
  - tromp 3y ago
    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.
  - coldtea 3y ago
    "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).
    - bluecalm 3y ago
      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.
      - coldtea 3y ago
        >Yeah but this is not very useful concept in practical play and that was the context of my comment. This depends on whether the solution can be "memorized" so to speak. For games where it can, it makes playing meaningless.
- rc_mob 3y ago
  I don't understand this comment. Computers are not allowed to play in the championship.
  - bediger4000 3y ago
    I confess to being dumb and not understanding it's a human championship. My bad!
- waveBidder 3y ago
  chess engines are good enough to be effectively solved compared to human play, so not really more than chess tournaments.

Waterluvian 3y ago

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.

captn3m0 3y ago
I also like Blokus for similar reasons.
- ramses0 3y ago
  Blokus Duo is king!
hermitcrab 3y ago
Suggest also having a look at Hus (one of the family of African stone games): https://mancala.fandom.com/wiki/Hus https://mancala.fandom.com/wiki/Hus 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.

bradwood 3y ago

How about the ancient Chinese game of "go", next? Not convinced that can easily be solved at all.

mikpanko 3y ago
Among popular board games, Go is more computationally complex than chess, so the latter would probably be solved first.
tromp 3y ago
Go is considered close to being solved on a 7x7 board [1]. The grand challenge would be solving 9x9 Go, the standard beginner board size. 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/38521 https://forums.online-go.com/t/katago-attempts-to-solve-7x7/...
- mafuy 3y ago
  There was a recent push for 9x9. It's not solved but it is believed to be near perfect play. https://katagobooks.org/9x9highlights.html https://katagobooks.org/9x9highlights.html

KingOfCoders 3y ago

One of the first games I've coded as a kid was Othello. "Othello is now solved, computationally proved that perfect play by both players lead to a draw." I could never win against my creation :-)

antivirus0101 3y ago
If your creation plays perfectly ;)

sdwr 3y ago

> 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.

dist-epoch 3y ago
More likely, those 2587 positions cover all possibilities. 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.
- BlackFingolfin 3y ago
  But none of this explicit. This is at best an announcement of a potential proof. But it isn't a proof yet. Also curious: in the end of the paper they talk about having "weakly solve" Othello... the paper overall reads really strangely.
  - dfan 3y ago
    "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.
    - BlackFingolfin 3y ago
      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.

phkahler 3y ago

>> Othello is now solved, computationally proved that perfect play by both players lead to a draw. Did not see that coming. That just makes the game more interesting I think.

sciolist 3y ago

Is this legit? It seems weird to me that this paper has one author, from a deep-learning startup which I've never heard of before.

dist-epoch 3y ago
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.
thenoblesunfish 3y ago
The fact that they describe their own result as monumental raised my eyebrows. Presumably this is being peer reviewed?

makach 3y ago

Does that mean there are no disadvantages going second?

chaboud 3y ago
Having not read the paper, it sounds like the author is asserting that the game is solved under perfect play as a draw. https://en.m.wikipedia.org/wiki/Solved_game 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.
toyg 3y ago
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.
foompy_katt 3y ago
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.

fidotron 3y ago

There is a lot of good background on Othello like: https://en.wikipedia.org/wiki/Computer_Othello https://en.wikipedia.org/wiki/Computer_Othello And especially: https://archive.org/details/byte-magazine-1980-07/page/n57/mode/2up?view=theater 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://luduxia.com/reversi/

Avlin67 3y ago

no, Othello is not complex, I do not remember exactly how but i did play a lot when i was you and did find a way to win consistently...

jmmcd 3y ago
And if you played against yourself, did you still win?
- sebastiennight 3y ago
  Plot twist: GP is the author of the paper, and your question is how they demonstrated that "both players playing perfectly leads to a draw".
laurentlb 3y ago
> did find a way to win consistently... Against who? You were playing against beginners?
toyg 3y ago
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.

omoikane 3y ago

Related, here is one that plays 6x6 perfectly: https://mame.github.io/6x6-reversi-oracle/ https://mame.github.io/6x6-reversi-oracle/ via: https://twitter.com/mametter/status/1476379841004183556 https://twitter.com/mametter/status/1476379841004183556 I didn't know 8x8 was unsolved until now.

namtab00 3y ago
I can't get one single black... it's this what perfectly means?
- Tepix 3y ago
  It will manage a draw even when the opponent plays perfectly, too. And it will get the optimum number of pieces.

orzig 3y ago

"Minutes to learn ... A lifetime to master" Not anymore!

Elena120 3y ago

[dead]

iamflimflam1 3y ago

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.

EVa5I7bHFq9mnYK 3y ago
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.
keitmo 3y ago
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).
- kjellsbells 3y ago
  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. https://vintageapple.org/byte/pdf/198107_Byte_Magazine_Vol_06-07_Energy_Conservation.pdf https://vintageapple.org/byte/pdf/198107_Byte_Magazine_Vol_0...
- lanstin 3y ago
  I read that same byte article, wrote a basic version that played the heuristic way, and was unable to beat it. Good times.
- 3y ago

gmac 3y ago

If anyone fancies playing the game, I made this for/with my kids: https://jawj.github.io/fliptiles https://jawj.github.io/fliptiles (The ‘AI’ player is very weak)

hermitcrab 3y ago
I was even weaker. ;0) (Nice job BTW)
deleted 3y ago
[deleted]
mumintrollet 3y ago
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 :/
- gmac 3y ago
  Likewise! My daughter played it at a friend’s house and enjoyed it, which is what reminded me and prompted me to make this.
simondebbarma 3y ago
Not sure how impressive a draw is, but I did a 32-32 for my first play through. Thanks for teaching me a new game!

amelius 3y ago

Ok, so we just have to keep adding rows and columns to the game in order to keep the game from being "solved"?

dzolob 3y ago
Someday there might be a theorem. Something on the line of “for all nxn boards, a perfect game ends in a tie”.
- amelius 3y ago
  Next challenge: (n+1)xn boards

dzolob 3y ago

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.

uxp8u61q 3y ago

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.

fbdab103 3y ago
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.
- uxp8u61q 3y ago
  > a mathematical puzzle that is mostly trivia "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.
  - sebzim4500 3y ago
    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.
    - WoodenChair 3y ago
      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.

deleted 3y ago

[deleted]

at_a_remove 3y ago

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?

pvg 3y ago
That's more or less coming up with one of the ideas of Core War due to Othello Implementation Boredom.

CodeCompost 3y ago

Used to play an Othello game on my phone many moons ago. I always won by always going inside-out.

dzolob 3y ago

For those of you who think Othello is trivial, try Zebra. Original author’s website: http://radagast.se/othello/ http://radagast.se/othello/ A github source: https://github.com/hoshir/zebra https://github.com/hoshir/zebra

NooneAtAll3 3y ago
for those not getting what is "Othello" - it is also called Reversi
- zamadatix 3y ago
  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.
- archon810 3y ago
  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.

mark_l_watson 3y ago

This is cool. 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.

notfed 3y ago
Classic "Why nerds don't get invited to parties"!
- roughly 3y ago
  > computer scientist vs an optometrist There’s a joke in here about perspective
  - rst4455 3y ago
    I'll byte... C#?
    - ornornor 3y ago
      Nice
  - elromulous 3y ago
    The brother lacked vision
  - gkuhl21 3y ago
    The optometrist couldn't believe his eyes. ... I'll see myself out.
bentcorner 3y ago
> an African game with about 10 pits on each side of the board that hold stones https://en.wikipedia.org/wiki/Mancala https://en.wikipedia.org/wiki/Mancala if you want more info

uncletaco 3y ago

Good ol’ Othello. I got an A in AI because I beat everyone else’s Othello player. You will always be the final boss of grad school.

avipars 3y ago

Link to paper: https://arxiv.org/pdf/2310.19387.pdf https://arxiv.org/pdf/2310.19387.pdf

gtbcb 3y ago

I would love a Wikipedia list article of games that have been solved computationally and but also games where humans can still beat computers / AI, discussing the challenges and context behinds wins / losses.

Y_Y 3y ago
Are there any board games left where humans beat the best computers? On a related note, are there any Wikipedia list articles which are empty lists?
- kibwen 3y ago
  > Are there any board games left where humans beat the best computers? Rest assured that no computer will ever dominate a human opponent at Candyland.
  - musicale 3y ago
    The youngest player goes first in Candyland and has an edge on average. I assume this is by design. For the spinner version of the game, the computer could use a physical or statistical spinner model to gain an edge.
- Marazan 3y ago
  I couldn't imagine any computer beating a human at any Collectable Card Game in the near term. Likewise I'd imagine that computers would be at a insurmountable disadvantage at Deck Builders like Dominion in the general case (in that I could easily imagine a Computer being trained to play perfectly on a specific Kingdom but no where close to a top human on a randomly selected Kingdom).
- occamrazor 3y ago
  AFAIK there are no good bridge computer programs. A crucial difficulty is making sense of the bidding phase, and of signals during the card playing phase.
Someone 3y ago

snitty 3y ago

Until someone gives me a convincing reason why Iago did it, Othello is NOT solved.

thomastjeffery 3y ago

weakly solved

Andrew018 3y ago

[dead]

entelechy0 3y ago

Because Othello is in PSPACE, and NP is in PSPACE, does this mean that P=NP?

gus_massa 3y ago
The preprint claims to have solved the standard 8x8 board. The result probably applied to smaller boards and perhaps wit some tweaks to slighty bigger boards (10x10???). To conclude something about P ?= NP, they would have to have solved the NxN board for all N.

munificent 3y ago

> The Othello result is a monumental achievement for humanity Imagine having the hubris to describe your own paper like this.

lagt_t 3y ago
A before and after in the history of mankind. A milestone carved in the memory of all mankind through time and space.
ksd482 3y ago
Perhaps its humor?
- whirlwin 3y ago
  Maybe Schrödinger's satire. Either it's satire or not based on the reaction of the reader
prof-dr-ir 3y ago
The sentence certainly sounds arrogant, but I have seen such phrasing used also by novice authors who were simply trying to sell a result that they were enthusiastic about. Like the present article's author, these were always non-native speakers.
deleted 3y ago
[deleted]
NotYourLawyer 3y ago
Look upon my works, ye mighty, and despair.
deleted 3y ago
[deleted]
deleted 3y ago
[deleted]

gus_massa 3y ago

I'm very surprised it's a draw. It's not like chess where it's "easy" to exchange a piece for an equal one until the board is "empty" and it's a draw. (Yes, it's more complicated. I played a lot of chess until secondary school, and it's more complicated. But trading equal pieces is a good strategy to get a draw.) 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?

Tepix 3y ago
The most promising lines have long (decades) been known to result in a draw. There wasn't enough CPU power to brute force the entire search space.
- gus_massa 3y ago
  Which is the bigest board that has been bruteforced?
jchook 3y ago
Starting with a 1x1, 2x2, 3x3, etc board size seems like a reasonable strategy for developing an intuition of the solution.

blindriver 3y ago

It sounds like they "solved" this using 2 AI players playing "perfect" Othello? 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?

doikor 3y ago
The AI can always continue with the perfect play from that imperfect state. That is what happens in chess as you can’t fool a good chess AI by making intentionally imperfect moves (chess is not solved so we don’t know if a move is perfect or not but you get the idea) 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.
- 542458 3y ago
  > you can’t fool a good chess AI by making intentionally imperfect moves 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).

codr7 3y ago

Dang, brings back memories from AI class at university. 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.

einpoklum 3y ago

Oh, it's Reversi! https://en.wikipedia.org/wiki/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.

musicale 3y ago

Given that 6x6 Othello/Reversi was solved 30+ years ago, I'm a bit surprised it took this long for 8x8.

deleted 3y ago

[deleted]