[HN Gopher] Othello Is Solved?
___________________________________________________________________
Othello Is Solved?
Author : Tepix
Score : 448 points
Date : 2023-11-04 14:35 UTC (8 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| Tepix wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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
| RetroTechie wrote:
| 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.
| kelsey9876543 wrote:
| 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 wrote:
| > 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 wrote:
| Foot races are also solved - these losers should just get
| a car!
| kelsey9876543 wrote:
| 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 wrote:
| 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).
| uxp8u61q wrote:
| ...is this satire?
| kelsey9876543 wrote:
| 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.
| coldtea wrote:
| > _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?"
| mtlmtlmtlmtl wrote:
| 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 wrote:
| 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...
| bluGill wrote:
| 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.
| graphe wrote:
| 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...
| Someone wrote:
| > 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 wrote:
| 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 wrote:
| >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 wrote:
| 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.
| SonOfLilit wrote:
| 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.
| leoff wrote:
| > 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.
| bluGill wrote:
| You don't, you trust that God has proved.
| kreetx wrote:
| I don't get then, how the paper "solves Othello": how
| does it determine the perfect game (why is it perfect)?
| bluGill wrote:
| 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.
| Asraelite wrote:
| "Weakly solved" does actually imply that perfect
| strategy. I think you're referring to "ultra-weakly
| solved", which seems to be what the paper did.
| charcircuit wrote:
| >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.
| tromp wrote:
| > 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.
| NooneAtAll3 wrote:
| > Such is the difference between weakly and strongly
| solving.
|
| no, you described difference between storing the result
| and not storing it
|
| strongly solving means allowing arbitrary amount of
| mistakes from either player before giving to the solver
| foota wrote:
| 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.
| AndrewKemendo wrote:
| 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
| kadoban wrote:
| 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 wrote:
| IN what could be interpreted as irony, Lee Seedol went on
| to invent more board games.
|
| https://www.dicebreaker.com/series/wizstone/news/go-
| player-d...
| nimih wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| "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 wrote:
| 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 wrote:
| > _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.
| bluecalm wrote:
| 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.
| rc_mob wrote:
| I don't understand this comment. Computers are not allowed to
| play in the championship.
| bediger4000 wrote:
| I confess to being dumb and not understanding it's a human
| championship. My bad!
| waveBidder wrote:
| chess engines are good enough to be effectively solved
| compared to human play, so not really more than chess
| tournaments.
| Waterluvian wrote:
| 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 wrote:
| I also like Blokus for similar reasons.
| ramses0 wrote:
| Blokus Duo is king!
| hermitcrab wrote:
| Suggest also having a look at Hus (one of the family of African
| stone games): 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 wrote:
| How about the ancient Chinese game of "go", next? Not convinced
| that can easily be solved at all.
| mikpanko wrote:
| Among popular board games, Go is more computationally complex
| than chess, so the latter would probably be solved first.
| tromp wrote:
| 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/...
| mafuy wrote:
| 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
| KingOfCoders wrote:
| 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 :-)
| sdwr wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| "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 wrote:
| 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.
| anigbrowl wrote:
| They wrote about this in the introduction and in the
| context of algorithm 2.
| NooneAtAll3 wrote:
| > 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.
| light_hue_1 wrote:
| > But perhaps equating "solved" with "weakly solved" is
| default in this area?
|
| 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.
| jmmcd wrote:
| "weakly solve" is not curious. Read from the start, they
| define this.
| sdwr wrote:
| This looks like a George W "Mission Accomplished" moment.
|
| - 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!
| sebzim4500 wrote:
| The concept of "weakly solved" is not original to this
| effort. IIRC checkers was weakly solved for years but is
| now strongly solved.
| tialaramex wrote:
| 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.
|
| 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.
| missblit wrote:
| 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.
|
| (The algorithm is also printed out)
| sdwr wrote:
| Algorithm 1 doesn't say shit! It says "pick the best move",
| or "pick all the moves".
|
| 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.
| notdonspaulding wrote:
| > From start of game to 50 squares left is enumerable.
|
| 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
| sdwr wrote:
| Enumerable as in "computationally enumerable", or "able
| to be enumerated in a reasonable amount of time x cpu x
| memory"
|
| 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 ;)
| CSMastermind wrote:
| 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.
| devit wrote:
| They computed results for a bunch of 36-empty-squares positions
| on their clusters and uploaded them to
| https://figshare.com/articles/dataset/Analyses_of_the_Game_o...
|
| 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.
| phkahler wrote:
| >> 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 wrote:
| 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 wrote:
| 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 wrote:
| The fact that they describe their own result as monumental
| raised my eyebrows. Presumably this is being peer reviewed?
| makach wrote:
| Does that mean there are no disadvantages going second?
| chaboud wrote:
| 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
|
| 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 wrote:
| 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 wrote:
| 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 wrote:
| There is a lot of good background on Othello like:
| https://en.wikipedia.org/wiki/Computer_Othello
|
| 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/
| Avlin67 wrote:
| 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 wrote:
| And if you played against yourself, did you still win?
| sebastiennight wrote:
| 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 wrote:
| > did find a way to win consistently...
|
| Against who? You were playing against beginners?
| toyg wrote:
| 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 wrote:
| Related, here is one that plays 6x6 perfectly:
|
| https://mame.github.io/6x6-reversi-oracle/
|
| via: https://twitter.com/mametter/status/1476379841004183556
|
| I didn't know 8x8 was unsolved until now.
| namtab00 wrote:
| I can't get one single black... it's this what perfectly means?
| orzig wrote:
| "Minutes to learn ... A lifetime to master" Not anymore!
| iamflimflam1 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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_0.
| ..
| lanstin wrote:
| I read that same byte article, wrote a basic version that
| played the heuristic way, and was unable to beat it. Good
| times.
| CyberDildonics wrote:
| _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.
| iamflimflam1 wrote:
| People see something behaving based on some very simple rules
| and assume that it is "thinking".
| CyberDildonics wrote:
| This is just repeating what you said before, but who are
| these 'people' that you're talking about?
| Tao3300 wrote:
| > Double AA
|
| So you mean AAAA?
| CyberDildonics wrote:
| I actually remember those things taking two AA batteries,
| so I may have flubbed my way into something that is still
| technically true.
| gmac wrote:
| If anyone fancies playing the game, I made this for/with my kids:
| https://jawj.github.io/fliptiles
|
| (The 'AI' player is very weak)
| hermitcrab wrote:
| I was even weaker. ;0)
|
| (Nice job BTW)
| mumintrollet wrote:
| 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 wrote:
| Likewise! My daughter played it at a friend's house and
| enjoyed it, which is what reminded me and prompted me to make
| this.
| amelius wrote:
| Ok, so we just have to keep adding rows and columns to the game
| in order to keep the game from being "solved"?
| dzolob wrote:
| Someday there might be a theorem. Something on the line of "for
| all nxn boards, a perfect game ends in a tie".
| amelius wrote:
| Next challenge: (n+1)xn boards
| dzolob wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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.
| kbenson wrote:
| The person you're responding to wasn't the one that said
| it was "trivia" (much less trivial).
|
| I don't think anyone was saying it's easy, just that they
| didn't think it was very useful to know.
| WoodenChair wrote:
| The post I'm replying to said:
|
| > 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.
| kbenson wrote:
| 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.
| notfed wrote:
| > Trust but verify.
|
| 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.
| coldtea wrote:
| > _Trust but verify_
|
| 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.
| throw101010 wrote:
| > And yet this is the #1 post on HN right now.
|
| 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.
| scythe wrote:
| 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!
| mcphage wrote:
| Boy are you gonna feel foolish when the #2 post on HN is
| "Cancer _almost_ cured", and you realize how dangerous a
| diversion this was...
| anigbrowl wrote:
| 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.
| notfed wrote:
| 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".
| SomaticPirate wrote:
| The source code is on Github? Why not run it yourself and
| perform the peer review? The implementation is quite
| straightforward
| uxp8u61q wrote:
| 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.
| cwillu wrote:
| There was absolutely nothing wrong with the superconductor
| "debacle". What you're preaching is not skepticism, but
| cynicism.
| coldtea wrote:
| Given the myriad posts and articles about "huge
| breakthrough", "industry changing" and so on, scepticism in
| that case would translate to way more cynicism.
| g9yuayon wrote:
| 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.
| klyrs wrote:
| 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.
| jmye wrote:
| > 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.
| notfed wrote:
| > Get over yourself, let people get excited about little
| stuff.
|
| Some people are looking for facts and science, and some are
| looking for enthusiasm and excitement. Can't discount either
| one, I suppose.
| CyberDildonics wrote:
| _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.
| klyrs wrote:
| 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.
| gfodor wrote:
| Calling it a debacle is an admission you yourself could benefit
| from your own advice.
| satoqz wrote:
| 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.
| at_a_remove wrote:
| 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 wrote:
| That's more or less coming up with one of the ideas of Core War
| due to Othello Implementation Boredom.
| CodeCompost wrote:
| Used to play an Othello game on my phone many moons ago. I always
| won by always going inside-out.
| dzolob wrote:
| For those of you who think Othello is trivial, try Zebra.
|
| Original author's website: http://radagast.se/othello/
|
| A github source: https://github.com/hoshir/zebra
| NooneAtAll3 wrote:
| for those not getting what is "Othello" - it is also called
| Reversi
| zamadatix wrote:
| 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.
| mark_l_watson wrote:
| 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 wrote:
| Classic "Why nerds don't get invited to parties"!
| roughly wrote:
| > computer scientist vs an optometrist
|
| There's a joke in here about perspective
| rst4455 wrote:
| I'll byte... C#?
| ornornor wrote:
| Nice
| elromulous wrote:
| The brother lacked vision
| bentcorner wrote:
| > _an African game with about 10 pits on each side of the board
| that hold stones_
|
| https://en.wikipedia.org/wiki/Mancala if you want more info
| neontomo wrote:
| Also, another version I'm more familiar with from childhood
| is https://en.wikipedia.org/wiki/Kalah
| Magi604 wrote:
| Here is the game I played with my grandma when I was
| younger:
|
| https://en.wikipedia.org/wiki/Southeast_Asian_mancala
| sundarurfriend wrote:
| Reminded me of https://en.wikipedia.org/wiki/Pallanguzhi
|
| And it is indeed mentioned under the Names and Variants
| section. Seems likely that there's a historical connection
| somewhere.
| kiviuq wrote:
| "The game was played by enslaved Africans to foster community
| and develop social skills."
|
| ..cringe...
| bee_rider wrote:
| I don't get it, what makes you want to cringe?
| earthboundkid wrote:
| They're humans and humans play games for fun.
| probablynish wrote:
| I played this game growing up (we called it Bao) - now I know
| what my next party trick is going to be
| sonofhans wrote:
| 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.
| jonahx wrote:
| > 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.
| weatherlight wrote:
| Sometimes there's an implicit its only cheating if you get
| caught.
| buzzy_hacker wrote:
| Yeah, in monopoly you don't have to pay rent if the
| property owner doesn't notice.
| jhbadger wrote:
| And in Scrabble it's fine to use a nonsense word if
| nobody challenges it.
| _justinfunk wrote:
| And in American Football it's fine to deflate the ball if
| no one measures it.
| pests wrote:
| This is not implicit though.
|
| The rules state that property owners can ask for the rent
| until the next player rolls the dice.
| earthboundkid wrote:
| In Bullshit, I always felt that if you could trick them
| into taking the hand or not noticing you added an extra
| card, it was all part of the game.
| webkike wrote:
| IMO that's still not cheating
| elwell wrote:
| > It can become more like poker, where deceit is a part of
| the game.
|
| 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".
| furyofantares wrote:
| 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.
| CyberDildonics wrote:
| Mancala and connect four are classic examples of solved games.
|
| _computer scientist vs. an optometrist._
|
| What does being an optometrist have to do with anything?
| coffee_ wrote:
| One solves problems and the other is a computer scientist.
| rendall wrote:
| Well as a computer scientist and programmer, I for one
| laughed.
| libraryatnight wrote:
| Wasted his time learning to help people see, now he can't
| even kick ass at Mancala! The rube!
| hombre_fatal wrote:
| 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.
| easton wrote:
| It's a joke. As in "CS vs Optometry, who will win in the
| mancala battle of the century?!"
| Keyframe wrote:
| Unless it turns out OP is an optometrist
| elwell wrote:
| > This was a classic match up
|
| "classic" here is tongue-in-cheek
| qubex wrote:
| I did something similar for my (then) favourite game _Pentago_
| , with similar results: I drained all the fun from it.
| jmholla wrote:
| 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.
| dbrueck wrote:
| Haha, I did this for Wordle - same result!
| marssaxman wrote:
| 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.
| grensley wrote:
| 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.
| passion__desire wrote:
| If your team always wins, there is no point in supporting it,
| no thrill. Everything in moderation, even winnings.
| jholloway7 wrote:
| Now that you mention it, this might be why my family stopped
| playing Rack-O with me
| uncletaco wrote:
| 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 wrote:
| Link to paper: https://arxiv.org/pdf/2310.19387.pdf
| gtbcb wrote:
| 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 wrote:
| 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 wrote:
| _> 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.
| Marazan wrote:
| 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).
| snitty wrote:
| Until someone gives me a convincing reason why Iago did it,
| Othello is NOT solved.
| thomastjeffery wrote:
| _weakly solved_
| munificent wrote:
| _> The Othello result is a monumental achievement for humanity_
|
| Imagine having the hubris to describe your own paper like this.
| lagt_t wrote:
| A before and after in the history of mankind. A milestone
| carved in the memory of all mankind through time and space.
| ksd482 wrote:
| Perhaps its humor?
| whirlwin wrote:
| Maybe Schrodinger's satire. Either it's satire or not based
| on the reaction of the reader
| prof-dr-ir wrote:
| 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.
| NotYourLawyer wrote:
| Look upon my works, ye mighty, and despair.
| gus_massa wrote:
| 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 wrote:
| 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.
| blindriver wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| Oh, it's 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.
___________________________________________________________________
(page generated 2023-11-04 23:00 UTC)