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

271–280 of 285 posts

Re: Othello Is Solved?

#271

Post by [deleted] »

SamBam wrote: post #248
bluecalm wrote: post #43

Earlier quoted context omitted.

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…

Chess isn't remotely solved. AlphaZero trounced StockFish, playing moves that StockFish never thought possible. Meanwhile, some say that StockFish has since caught up. But regardless, if cheese engines keep getting better and bearing previous ones, then in no way can you say that any current engine has "solved" chess because a different version will beat it next year. "Solved" doesn't mean "beats humans." I see your…

[deleted]

Re: Othello Is Solved?

#272

Post by bluecalm »

SamBam wrote: post #248
bluecalm wrote: post #43

Earlier quoted context omitted.

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…

Chess isn't remotely solved. AlphaZero trounced StockFish, playing moves that StockFish never thought possible. Meanwhile, some say that StockFish has since caught up. But regardless, if cheese engines keep getting better and bearing previous ones, then in no way can you say that any current engine has "solved" chess because a different version will beat it next year. "Solved" doesn't mean "beats humans." I see your…

I am sorry but this is completely wrong. It's true old Stockfish lost to Alpha Zero with specific rules, most notably no opening book which classical engines weren't supposed to be used at in competitive play (which is the reason SF doesn't ship with even a basic one - the user is supposed to use their own) and only one minute per move.

People were able to beat "Stockfish with one minute per move with no opening book" back then given enough time and strong hardware. It's no longer the case. Chess from starting position is completely dead in computer/centaur play/correspondence play. No one is able to win a single game vs an engine running on a home PC even if they can use arbitrary amount of computing power to help.

As to engines getting better: they don't get better anymore at playing chess from starting position. They get better at playing chess starting from set of unbalanced positions (chosen to be on the edge of winning/drawn) which would never occur from engine play from starting position.

My point wasn't about humans but about chess in fact being weakly solved. We just don't have a mathematical proof yet.

Re: Othello Is Solved?

#273

Post by Someone »

gtbcb wrote: post #129

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.

> I would love a Wikipedia list article of games that have been solved computationally

https://en.wikipedia.org/wiki/Solved_game#Solved_games

Not being on that list doesn’t necessarily make a game harder; it may just be less popular with computer scientists.

Re: Othello Is Solved?

#274

Post by hgfghui7 »

cvoss wrote: post #16
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?

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…

This is a misunderstanding. To give an example. A perfect 1.e4 player needs a response to every possible move including 1.. f6. But he doesn't need to know how to respond to 1. d4 d5 because he avoids ever ending up in that position.

Re: Othello Is Solved?

#275

Post by SamBam »

bluecalm wrote: post #272
SamBam wrote: post #248

Earlier quoted context omitted.

Chess isn't remotely solved. AlphaZero trounced StockFish, playing moves that StockFish never thought possible. Meanwhile, some say that StockFish has since caught up. But regardless, if cheese engines keep getting better and bearing previous ones, then in no way can you say that any current engine has "solved" chess because a different version will beat it next year. "Solved" doesn't mean "beats humans." I see your…

I am sorry but this is completely wrong. It's true old Stockfish lost to Alpha Zero with specific rules, most notably no opening book which classical engines weren't supposed to be used at in competitive play (which is the reason SF doesn't ship with even a basic one - the user is supposed to use their own) and only one minute per move. People were able to beat "Stockfish with one minute per move with no opening book…

What? The idea that chess engines have stopped improving is ridiculous. StockFish is continuously improving. And is not just better hardware. For instance, just a couple of years ago StockFish added NNUE. This actually decreased the number of nodes it could look at per second, but the improved algorithm was so much better it bumped it's ELO by another 80 points.

It would be hubris to say "Ok, it kept improving up until last month or so, but now it's perfect."

If it's still improving, that means the current version can be beaten. If it can be beaten, that means we haven't solved it yet.

> No one is able to win a single game vs an engine running on a home PC even if they can use arbitrary amount of computing power to help.

I'm not quite sure I understand what you're suggesting, because it's not clear what "arbitrary computing power" means -- are they also running StockFish? If so, we already know that StockFish in better hardware runs better, so this is meaningless in a normal game, but I am guessing you mean with no time limits.

Is your suggestion that StockFish of 2020 will always draw against StockFish of 2023 if they have "unlimited time?"

If so, this seems slightly tautological. Chess is finite, so we have always known that "given enough time" anyone could enumerate all the possibilities. But if we restrict the time to, say, an hour per move, perhaps you'd say that's not "unlimited" enough.

But I'm actually interested. Has anyone tried 2020 StockFish vs 2023 StockFish with huge time allowances?

Re: Othello Is Solved?

#276

Post by musicale »

kibwen wrote: post #183
Y_Y wrote: post #144

Earlier quoted context omitted.

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?

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

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.

Re: Othello Is Solved?

#277

Post by bluecalm »

SamBam wrote: post #275
bluecalm wrote: post #272

Earlier quoted context omitted.

I am sorry but this is completely wrong. It's true old Stockfish lost to Alpha Zero with specific rules, most notably no opening book which classical engines weren't supposed to be used at in competitive play (which is the reason SF doesn't ship with even a basic one - the user is supposed to use their own) and only one minute per move. People were able to beat "Stockfish with one minute per move with no opening book…

What? The idea that chess engines have stopped improving is ridiculous. StockFish is continuously improving. And is not just better hardware. For instance, just a couple of years ago StockFish added NNUE. This actually decreased the number of nodes it could look at per second, but the improved algorithm was so much better it bumped it's ELO by another 80 points. It would be hubris to say "Ok, it kept improving up unt…

I have written that chess engines stopped improving at chess played from starting position - it's a draw every time (well, unless you really push them to play very fast on limited hardware). The reason we assess current Stockfish as stronger engine than Stockfish from 2 years ago is that it is better at playing chess starting from different positions than a standard starting one.

In terms of weakly and strongly solved you could say that modern Stockfish is a step closer to strongly solving chess than previous one (it is able to win more winning positions and find draws in more difficult drawn positions). It is however not able to win from standard starting position (what we call chess).

It seems to me you're not familiar with how chess engines are tested and compared and your misunderstanding of the state of the affairs stems from that.

>>Is your suggestion that StockFish of 2020 will always draw against StockFish of 2023 if they have "unlimited time?"

You don't need unlimited time. You need less than 30 minutes per move on modern top of the line consumer CPU. Probably much less but I want to be safe. You also need an opening book if using Stockfish before NNUE. It had a very well known weakness in the openings and wasn't designed to be used without an opening book. If the goal was to ship a strongest engine in as-is state the programmers would add a few megabytes of book moves - resulting in still smaller executable than modern NNUE version. They didn't because everyone used their own book anyway.

If NN engine "contains" an opening book is a philosophical question heavily debated by chess programmers. It didn't matter for a long time until Alpha Zero team exploited it to make their engine look much better than it really was.

>>But I'm actually interested. Has anyone tried 2020 StockFish vs 2023 StockFish with huge time allowances?

It's pointless from starting position (with caveats above). That's also the reason correspondence chess is dead. Rare wins come from mistakes in move entry or failure to run an engine for 30 seconds for whatever reason. Top correspondence players - guys who used to run multiple huge machines for days or weeks to find any tiny edge with often custom software to guide the engine can't win vs bare unattended Stockfish running on a Threadripper for 30 minutes or less per move anymore.

Re: Othello Is Solved?

#278

Post by earthboundkid »

david422 wrote: post #236
earthboundkid wrote: post #199

Earlier quoted context omitted.

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.

3 queens ... and slide a 4th card sideways underneath.

Yep.

Re: Othello Is Solved?

#279

Post by sudosysgen »

Scarblac wrote: post #231
charcircuit wrote: post #169

Earlier quoted context omitted.

>He will deviate fro| the sequence and you won't know the perfect responses to his moves. Even if you don't know the moves you will know that you are in a winning / drawn position. Magnus can not find a way to get to a winning position unless you make a mistake.

That'll be very little help if the perfect game you have starts with 1.e4, but Magnus plays 1.d4. Yes, you're not losing, congratulations. You're still on your own against Carlsen now.

You can just evaluate whether or not a given move will change from a +1 or 0 position to a 0 or -1 position and play it from there.

Perfect play in a perfect game means that the objective won't change - in optimal control theory this is called Pontryagin's Maximum Principle or the Bellman optimality criteria. A "value to go" function is enough to find the optimal solution.

Re: Othello Is Solved?

#280

Post by geon »

keitmo wrote: post #79
iamflimflam1 wrote: post #38

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…

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

A very effective heuristic is to count the number of legal moves for each player.
Post reply on HN