*Zaccheus* on 21/7/2007 at 15:36
(
http://www.newscientisttech.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html) Checkers 'solved' after years of number crunching
Quote:
The ancient game of checkers (or draughts) has been pronounced dead. The game was killed by the publication of a mathematical proof showing that
draughts always results in a draw when neither player makes a mistake. For computer-game aficionados, the game is now "solved".
Isn't that true of any non-chance based board game?
demagogue on 21/7/2007 at 16:38
Maybe non-linear is the better term, since some games might not have a random "chance" element per se, but are still self-referentially dynamic. But if the game-tree is essentially linear and doesn't backtrack on itself, then yeah I think it's theoretically solvable ... an algorithm just has to account for every available path down the game-tree.
A game like Go is theoretically "solvable", but the game-tree allows for something like 10^10^171 possible paths (depending on how you calculate it; 10^360 was another lower bound)! To give perspective on that, wiki tells me that "Two back-of-envelope calculations give the number of atoms in the observable universe to be around 10^80", a minuscule fraction. We'd sooner find a computer model that tracks the position of every single atom in the universe in real time for the universe's lifetime, before solving Go. (Well, assuming atoms move like billiard balls).
The depth of the game-tree is basically why a computer can "solve" checkers, "merely" beat the greatest human grandmaster at chess, but still play like a 7 year old at Go.
*Zaccheus* on 21/7/2007 at 18:51
Those are fair points.
Another example would be: If someone asks you just 32 questions which have yes/no answers, then there are 2^32 (that's around 4,000,000,000) possible combinations of answers.
But like you say, there is a fundamental difference between whether a game can be solved and whether we can solve a game.
OrbWeaver on 21/7/2007 at 20:50
I think it's true by definition -- if neither player makes a mistake, then every player makes the optimum move at each stage, and the game must result in a draw (unless the game is so hideously imbalanced that the first player to make a move can irreversibly determine the outcome).
In this sense, chess is a game of chance: the chance that your opponent will make a mistake.
mopgoblin on 21/7/2007 at 22:54
It's quite possible that any game of this type <em>is</em> so "unbalanced" that one side can have a strategy that guarantees a win, even if the starting position and rules appear symmetrical. In Connect Four, the first player has such a strategy, for example.
Mortal Monkey on 21/7/2007 at 23:48
I've made an AI that can beat any human at any board game ever (except for those with timers).
Code:
MakeAMove()
{
for (;;);
}
Win by default.
cabellero on 22/7/2007 at 00:48
Threadjack, but..
Where I come from, there's a game that we play (or don't), called The Game.
Once you've heard how to play the game, you're playing it - forever. The rules are quite simple - if you remember the game at any point (even years from now), you've lost it, and you've got to tell someone you've lost it. The only way to win is by enver thinking about it.
So yeah, I thought the thread title was some reference to this game.. and that made me loose the game. Bastard.
I was in France a bit back, me and a friend had flown over to do some skiing - we'd just finished our first black run and had come to a stop at the bottom. My friend lifts his goggles and his first words are 'I lost the game'. It's annoying how it crops up.
fett on 22/7/2007 at 01:07
i think I speak for the rest of us when I say WHAT THE FUCK
Keeper_Andrus on 22/7/2007 at 01:27
thanks for making me lose the game, taffer.
SubJeff on 22/7/2007 at 02:37
Quote Posted by cabellero
Where I come from, there's a game that we play (or don't), called The Game.
Yup. I lost thanks to you, but now... YOU LOSE.
