My blog has moved! Redirecting...

You should be automatically redirected. If not, visit and update your bookmarks.

20 July 2007

Checkers Solved

I always said the game is not interesting, compared to chess and Go.

This Slashdot post confirms it - someone solved Checkers (שש בש), by creating a big ass database containing all possible positions...


Ido said...

Checkers isn't "shesh-besh", mate. It's Damka

ripper234 said...

You're right of course, this is the result of writing a post in 5 seconds without thinking :)

Now that I think about it, I doubt Shesh-Besh (Backgammon) could actualy be solved so easily - it's randomized, which adds another dimension of complexity to it all. It's still a sucky game though, and I enjoy Checkers more as it's less dependant on luck.

I know some players adhere to the view that backgammon is a game of skill, but to me it always looked like an ars game.

Eli said...

While backgammon can't be "solved" because of its probabilistic nature, programs play it way better than humans for a long time now. IIRC, the guy who wrote the program used Neural Nets to study games and infer strategy.

ripper234 said...

I don't agree. Even probabilistic games (as long as they're Perfect Information) can have an optimal strategy.

One could theoretically construct a database with all possible backgammon games and deduce the chances of winning from every position - and so come with the best strategy. I think the problem is this database would be extremely large.

Games that may not have a winning strategy are those with some hidden information - Prisoner's Dilemma and Poker come to mind.

ripper234 said...

On a partially related subject, see an example of
a perfect information deterministic game with no winning strategy
(that is, if you believe
the Axiom of Choise).

eli said...

Optimal strategy - yes.
Solution - no.

What is usually implied by solution is a strategy that *guarantees* some result. An optimal strategy in a probabilistic game can perhaps guarantee an average result over many games, but not a result in a single game.

ripper234 said...

Well I guess it depends on the definition. I would define a game as "solved" if the solution gives the optimal strategy at any given game state. On probabilistic games this does not guarantee victory, but it does guarantee the best chance of victory.