Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Othello Is Solved?

arxiv.org

Post reply on HN
Print view View original

91–100 of 285 posts

Re: Othello Is Solved?

#91

Post by tromp »

charcircuit wrote: post #46
cvoss wrote: post #16

Earlier quoted context omitted.

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…

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

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

Re: Othello Is Solved?

#92

Post by CSMastermind »

sdwr wrote: post #10

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

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.

Re: Othello Is Solved?

#93

Post by notfed »

mark_l_watson wrote: post #89

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…

Classic "Why nerds don't get invited to parties"!

Re: Othello Is Solved?

#94

Post by devit »

sdwr wrote: post #10

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

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.

Re: Othello Is Solved?

#95

Post by dzolob »

amelius wrote: post #45

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

Someday there might be a theorem. Something on the line of “for all nxn boards, a perfect game ends in a tie”.

Re: Othello Is Solved?

#96

Post by bentcorner »

mark_l_watson wrote: post #89

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…

> 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

Re: Othello Is Solved?

#98

Post by tromp »

bluecalm wrote: post #43
bediger4000 wrote: post #3

Earlier quoted context omitted.

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?

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 r…

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.

Re: Othello Is Solved?

#99

Post by bigbacaloa »

uxp8u61q wrote: post #51

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.

[dead]

Re: Othello Is Solved?

#100

Post by tromp »

bradwood wrote: post #7

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

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

Post reply on HN