| |
Main
Date: 16 Mar 2008 09:01:04
From: samsloan
Subject: Has Checkers Been Solved?
|
It has been published that checkers has been solved. See:
http://www.sciencemag.org/cgi/content/abstract/317/5844/1518
However, I am hearing that checkers has not been solved at all. Only
free-style checkers has been solved. Tournament style checkers where
there is a drawing to determine the first three moves is still an
actively contested game.
Which is true? Does anybody know?
Sam Sloan
|
|
| |
Date: 29 Mar 2008 23:25:38
From: jefk
Subject: Re: Has Checkers Been Solved?
|
On 29, 4:56 pm, [email protected] wrote:
>
> I'm sure Bob realised 1.e4 is probably a draw. Bob was conducting a thought
>experiment which _assumes_ e4 is a win so your reply misses the point.
well i'm aware the discussion/thread was about checkers,
and in the latest postings about specific openings used, or
left out by Schaeffer in his billion numbers database crunching.
but from what i've read in some articles (June 2007) it's
believed that these openings are irrelevant so they
really think checkers is solved, ie a draw.
Now i made a jump back to chess again as
rec.games.chess etc. is about chess, isnt it.
And with similar reasoning, lets say that. after 10 or 20
years or so someone would bother to do a similar
exercise as Schaeffer, but now for chess, starting with
openings d4, e4, Nf3, c4, and then would claim
its a draw. Then of course some people might
say: well you haven't tested e.g. 1.a3! or 1. h3 yet,
so it's not 'proven' yet that chess is a draw.
This then would not be a strong argument, as
after 1.a3 d5! 2.d4 we would get similar positions
as d4 opening lines, whereas after 1.h3 e5 2.e4 we would
get similar opening lines as e4 e5 by transposition.
Only relevant reasoning seems to be to investigate
what opening lines are more double-edged, like eg Sicilian
rather than drawish. If in certain tournaments one would
like to stimulate exciting play, than eg. as response
to e4 they could make eg. c5 obligatory.
But this would change such tournaments into
specific theme-tournaments, as eg. often
is done already in correspondence chess
(eg. d4 games with Benko gambit only or so).
Not the way to go forward imho.
Better extend chess to chess960 i would say,
probably (indeed) much more exciting
:)
best regards
jef
|
| | |
Date: 02 Apr 2008 17:44:26
From: Ray Gordon, creator of the \pivot\
Subject: Re: Has Checkers Been Solved?
|
"jefk" <[email protected] > wrote in message
news:[email protected]...
> On 29, 4:56 pm, [email protected] wrote:
>>
>> I'm sure Bob realised 1.e4 is probably a draw. Bob was conducting a
>> thought
>>experiment which _assumes_ e4 is a win so your reply misses the point.
>
> >>well i'm aware the discussion/thread was about checkers,
>>> and in the latest postings about specific openings used, or
>>> left out by Schaeffer in his billion numbers database crunching.
] >>> but from what i've read in some articles (June 2007) it's
>>> believed that these openings are irrelevant so they
>>> really think checkers is solved, ie a draw.
That's a practical, not absolute, solution. We were talking about working
out EVERY combination for every opening, and how the solved openings can be
avoided by force of rule, leaving the unsolved remainder for tournaments.
The point was that it's possible for a GAME to be solved but for rules to be
enacted that change the game to something not solved.
Then again, my name isn't Bob, so....
|
| |
Date: 29 Mar 2008 07:56:30
From:
Subject: Re: Has Checkers Been Solved?
|
On 29, 9:24=A0pm, jefk <[email protected] > wrote:
> On 16, 7:05 pm, "Ray Gordon, creator of the \"pivot\""
>
> <[email protected]> wrote:
> > > It has been published that checkers has been solved. See:
>
> > Applied to chess, if 1. e4 proved a forced win for White, but no one sol=
ved
> > 1. d4, and you banned 1. e4 from tournament play, then tournament chess
> > would not be solved, while chess as a whole, would be.
>
> interesting idea, but as stated earlier, i believe for 1.e4 it's also
> a draw; =A0not
> only in =A0the Ruy Lopez Closed Zaitsev (with 16..g6! in the main line)
> but also
> in the Chigorin/Keres, look eg. at the game Timoshenko-Rogers,2007;
> in
> the RybkaII book by J.Noomen a novelty 21 Qd3 is indicated =A0(instead
> of the usual Bb3), but this also doesnt lead to significant advantage
> for white; so no need to ban 1.e4
> :)
> best regards,
> jefhttp://superchess.blogspot.com
I'm sure Bob realised 1.e4 is probably a draw. Bob was conducting a
thought experiment which _assumes_ e4 is a win so your reply misses
the point.
You're like B in this conversation: A) A British pound is worth two
US dollars. Therefore, a person carrying two hundred pounds of cash
could exchange that cash for 400 dollars. B) Interesting idea but it
is in fact statistically unlikely that a person is carrying exactly
two hundred pounds of cash on them...
Paul Epstein
|
| |
Date: 29 Mar 2008 06:24:36
From: jefk
Subject: Re: Has Checkers Been Solved?
|
On 16, 7:05 pm, "Ray Gordon, creator of the \"pivot\""
<[email protected] > wrote:
> > It has been published that checkers has been solved. See:
>
> Applied to chess, if 1. e4 proved a forced win for White, but no one solved
> 1. d4, and you banned 1. e4 from tournament play, then tournament chess
> would not be solved, while chess as a whole, would be.
interesting idea, but as stated earlier, i believe for 1.e4 it's also
a draw; not
only in the Ruy Lopez Closed Zaitsev (with 16..g6! in the main line)
but also
in the Chigorin/Keres, look eg. at the game Timoshenko-Rogers,2007;
in
the RybkaII book by J.Noomen a novelty 21 Qd3 is indicated (instead
of the usual Bb3), but this also doesnt lead to significant advantage
for white; so no need to ban 1.e4
:)
best regards,
jef
http://superchess.blogspot.com
|
| |
Date: 27 Mar 2008 15:07:51
From: bob
Subject: Re: Has Checkers Been Solved?
|
On 27, 1:13=A0am, [email protected] wrote:
> On 27, 12:43=A0pm, bob <[email protected]> wrote:
>
>
>
>
>
> > On 26, 9:13=A0pm, [email protected] wrote:
>
> > > On 26, 11:14=A0pm, bob <[email protected]> wrote:
>
> > > > On 25, 9:11=A0pm, [email protected] wrote:
>
> > > > > Almost surely, there _are_ situations like that in backgammon. =A0=
Can't
> > > > > you mimic the above scenario in backgammon by postulating 18 monst=
er
> > > > > rolls for each side?
> > > > > But, suppose there are such situations in backgammon, why does it =
then
> > > > > follow that the value of a cube, as well as its position, can affe=
ct
> > > > > theoretical money play? =A0This seems to be a hole in your argumen=
t. =A0So
> > > > > let us assume that your scenario is exactly replicated in backgamm=
on
> > > > > where there's a stalemate but each side has 18 monster winning rol=
ls,
> > > > > and no gammons are possible. =A0Please explain why this scenario l=
eads
> > > > > to the conclusion that the scenario with a 2 cube is essentially
> > > > > different than the scenario with a 1024 cube.
>
> > > > =A0 =A0I doubt that there is a siutation like that in backgammon. No=
te
> > > > that you would need the 18 non-monster rolls to lead to repeating
> > > > positions. There has been one proposed but it only can arise as the
> > > > result of an illegal checker play.
>
> > > > =A0Here is why such a situation will affect theoretical money play:
>
> > > > =A0Theoretical money play means making the move that maximizes equit=
y,
> > > > assuming perfect play from the opponent. Equity means the expected
> > > > value of the position. Take my coin flipping example again. If both
> > > > players use the always double/take strategy then the player on turn
> > > > will win $2 with probability 1/2, will lose $4 with probability 1/4,=
> > > > will win $8 with probability 1/8, will lose $16 with probability
> > > > 1/16 ... =A0The expected value is 2(1/2) + (-4)(1/4) + (8)(1/8) + (-=
16)
> > > > (1/16) + ... which does not converge. The expected value is not even=
> > > > defined.
>
> > > > Bob Koca
>
> > > Yes, indeed. =A0I realised that. =A0However, you appeared to claim tha=
t
> > > this no-equity position implies that the value of the cube needs to be=
> > > taken into account when enumerating positions. =A0You don't show this.=
> > > In your example, whether the cube is on 2 or 4 or whatever, it's still=
> > > the same no-equity verdict.
>
> > > Paul Epstein- Hide quoted text -
>
> > > - Show quoted text -
>
> > =A0 Torben wrote in this thread how a set of equations could be written
> > and solved to find the equity of any
> > backgammon position. The solutions only make sense as equities though
> > if the equities are all defined.
> > In my coin example one can give an equation and solve it but that does
> > not mean it gives the expected value of the game. If double take is
> > correct then the player on turn either wins 2 points or gives his
> > opponent the exact same situation but with the cube doubled. It is
> > very tempting though wrong to think that E(X) =3D (1/2)(2) + (1/2)
> > (-2E(X))
> > whose solution gives E(X) =3D 1/2.
>
> > Bob Koca- Hide quoted text -
>
> > - Show quoted text -
>
> Ok but you did say that your paradox makes the potential number of
> positions infinite. =A0I still don't see how. =A0You have never explained,=
> why, even assuming your paradoxical scenarios exist, a 32 cube should
> be regarded differently to a 64 cube. =A0Both lead to the same
> conclusion -- equity undefined.
>
> You said this:
>
> If you are talking about
> money backgammon though then the cube position and value makes the
> NUMBER OF POSITIONS INFINITE. Now one might say that its position is
> all that matters since if you know the correct theoretical play
> holding a 2 cube then you also know the correct theoretical play
> holding a 4 or any higher value cube. There is a problem though in
> that the equations might not have a solution....
>
> (caps added)
>
> Yet you never explain why your paradox would lead to an infinity of
> positions.
>
> Paul- Hide quoted text -
>
I clearly said that considering the position and value gives an
infinite number of positions. Ignoring the value does give a finite
number of positions. One must be careful though since equations can be
made but there is no guarantee that the solutions actually give
equities as one might expect.
Bob Koca
|
| |
Date: 26 Mar 2008 22:13:01
From:
Subject: Re: Has Checkers Been Solved?
|
On 27, 12:43=A0pm, bob <[email protected] > wrote:
> On 26, 9:13=A0pm, [email protected] wrote:
>
>
>
>
>
> > On 26, 11:14=A0pm, bob <[email protected]> wrote:
>
> > > On 25, 9:11=A0pm, [email protected] wrote:
>
> > > > Almost surely, there _are_ situations like that in backgammon. =A0Ca=
n't
> > > > you mimic the above scenario in backgammon by postulating 18 monster=
> > > > rolls for each side?
> > > > But, suppose there are such situations in backgammon, why does it th=
en
> > > > follow that the value of a cube, as well as its position, can affect=
> > > > theoretical money play? =A0This seems to be a hole in your argument.=
=A0So
> > > > let us assume that your scenario is exactly replicated in backgammon=
> > > > where there's a stalemate but each side has 18 monster winning rolls=
,
> > > > and no gammons are possible. =A0Please explain why this scenario lea=
ds
> > > > to the conclusion that the scenario with a 2 cube is essentially
> > > > different than the scenario with a 1024 cube.
>
> > > =A0 =A0I doubt that there is a siutation like that in backgammon. Note=
> > > that you would need the 18 non-monster rolls to lead to repeating
> > > positions. There has been one proposed but it only can arise as the
> > > result of an illegal checker play.
>
> > > =A0Here is why such a situation will affect theoretical money play:
>
> > > =A0Theoretical money play means making the move that maximizes equity,=
> > > assuming perfect play from the opponent. Equity means the expected
> > > value of the position. Take my coin flipping example again. If both
> > > players use the always double/take strategy then the player on turn
> > > will win $2 with probability 1/2, will lose $4 with probability 1/4,
> > > will win $8 with probability 1/8, will lose $16 with probability
> > > 1/16 ... =A0The expected value is 2(1/2) + (-4)(1/4) + (8)(1/8) + (-16=
)
> > > (1/16) + ... which does not converge. The expected value is not even
> > > defined.
>
> > > Bob Koca
>
> > Yes, indeed. =A0I realised that. =A0However, you appeared to claim that
> > this no-equity position implies that the value of the cube needs to be
> > taken into account when enumerating positions. =A0You don't show this.
> > In your example, whether the cube is on 2 or 4 or whatever, it's still
> > the same no-equity verdict.
>
> > Paul Epstein- Hide quoted text -
>
> > - Show quoted text -
>
> =A0 Torben wrote in this thread how a set of equations could be written
> and solved to find the equity of any
> backgammon position. The solutions only make sense as equities though
> if the equities are all defined.
> In my coin example one can give an equation and solve it but that does
> not mean it gives the expected value of the game. If double take is
> correct then the player on turn either wins 2 points or gives his
> opponent the exact same situation but with the cube doubled. It is
> very tempting though wrong to think that E(X) =3D (1/2)(2) + (1/2)
> (-2E(X))
> whose solution gives E(X) =3D 1/2.
>
> Bob Koca- Hide quoted text -
>
> - Show quoted text -
Ok but you did say that your paradox makes the potential number of
positions infinite. I still don't see how. You have never explained,
why, even assuming your paradoxical scenarios exist, a 32 cube should
be regarded differently to a 64 cube. Both lead to the same
conclusion -- equity undefined.
You said this:
If you are talking about
money backgammon though then the cube position and value makes the
NUMBER OF POSITIONS INFINITE. Now one might say that its position is
all that matters since if you know the correct theoretical play
holding a 2 cube then you also know the correct theoretical play
holding a 4 or any higher value cube. There is a problem though in
that the equations might not have a solution....
(caps added)
Yet you never explain why your paradox would lead to an infinity of
positions.
Paul
|
| |
Date: 26 Mar 2008 21:43:54
From: bob
Subject: Re: Has Checkers Been Solved?
|
On 26, 9:13=A0pm, [email protected] wrote:
> On 26, 11:14=A0pm, bob <[email protected]> wrote:
>
>
>
>
>
> > On 25, 9:11=A0pm, [email protected] wrote:
>
> > > Almost surely, there _are_ situations like that in backgammon. =A0Can'=
t
> > > you mimic the above scenario in backgammon by postulating 18 monster
> > > rolls for each side?
> > > But, suppose there are such situations in backgammon, why does it then=
> > > follow that the value of a cube, as well as its position, can affect
> > > theoretical money play? =A0This seems to be a hole in your argument. =
=A0So
> > > let us assume that your scenario is exactly replicated in backgammon
> > > where there's a stalemate but each side has 18 monster winning rolls,
> > > and no gammons are possible. =A0Please explain why this scenario leads=
> > > to the conclusion that the scenario with a 2 cube is essentially
> > > different than the scenario with a 1024 cube.
>
> > =A0 =A0I doubt that there is a siutation like that in backgammon. Note
> > that you would need the 18 non-monster rolls to lead to repeating
> > positions. There has been one proposed but it only can arise as the
> > result of an illegal checker play.
>
> > =A0Here is why such a situation will affect theoretical money play:
>
> > =A0Theoretical money play means making the move that maximizes equity,
> > assuming perfect play from the opponent. Equity means the expected
> > value of the position. Take my coin flipping example again. If both
> > players use the always double/take strategy then the player on turn
> > will win $2 with probability 1/2, will lose $4 with probability 1/4,
> > will win $8 with probability 1/8, will lose $16 with probability
> > 1/16 ... =A0The expected value is 2(1/2) + (-4)(1/4) + (8)(1/8) + (-16)
> > (1/16) + ... which does not converge. The expected value is not even
> > defined.
>
> > Bob Koca
>
> Yes, indeed. =A0I realised that. =A0However, you appeared to claim that
> this no-equity position implies that the value of the cube needs to be
> taken into account when enumerating positions. =A0You don't show this.
> In your example, whether the cube is on 2 or 4 or whatever, it's still
> the same no-equity verdict.
>
> Paul Epstein- Hide quoted text -
>
> - Show quoted text -
Torben wrote in this thread how a set of equations could be written
and solved to find the equity of any
backgammon position. The solutions only make sense as equities though
if the equities are all defined.
In my coin example one can give an equation and solve it but that does
not mean it gives the expected value of the game. If double take is
correct then the player on turn either wins 2 points or gives his
opponent the exact same situation but with the cube doubled. It is
very tempting though wrong to think that E(X) =3D (1/2)(2) + (1/2)
(-2E(X))
whose solution gives E(X) =3D 1/2.
Bob Koca
|
| |
Date: 26 Mar 2008 18:13:39
From:
Subject: Re: Has Checkers Been Solved?
|
On 26, 11:14=A0pm, bob <[email protected] > wrote:
> On 25, 9:11=A0pm, [email protected] wrote:
>
> > Almost surely, there _are_ situations like that in backgammon. =A0Can't
> > you mimic the above scenario in backgammon by postulating 18 monster
> > rolls for each side?
> > But, suppose there are such situations in backgammon, why does it then
> > follow that the value of a cube, as well as its position, can affect
> > theoretical money play? =A0This seems to be a hole in your argument. =A0=
So
> > let us assume that your scenario is exactly replicated in backgammon
> > where there's a stalemate but each side has 18 monster winning rolls,
> > and no gammons are possible. =A0Please explain why this scenario leads
> > to the conclusion that the scenario with a 2 cube is essentially
> > different than the scenario with a 1024 cube.
>
> =A0 =A0I doubt that there is a siutation like that in backgammon. Note
> that you would need the 18 non-monster rolls to lead to repeating
> positions. There has been one proposed but it only can arise as the
> result of an illegal checker play.
>
> =A0Here is why such a situation will affect theoretical money play:
>
> =A0Theoretical money play means making the move that maximizes equity,
> assuming perfect play from the opponent. Equity means the expected
> value of the position. Take my coin flipping example again. If both
> players use the always double/take strategy then the player on turn
> will win $2 with probability 1/2, will lose $4 with probability 1/4,
> will win $8 with probability 1/8, will lose $16 with probability
> 1/16 ... =A0The expected value is 2(1/2) + (-4)(1/4) + (8)(1/8) + (-16)
> (1/16) + ... which does not converge. The expected value is not even
> defined.
>
> Bob Koca
Yes, indeed. I realised that. However, you appeared to claim that
this no-equity position implies that the value of the cube needs to be
taken into account when enumerating positions. You don't show this.
In your example, whether the cube is on 2 or 4 or whatever, it's still
the same no-equity verdict.
Paul Epstein
|
| |
Date: 26 Mar 2008 20:48:40
From: Guy Macon
Subject: Re: Has Checkers Been Solved?
|
(Why did you post this to rec.games.chess.politics?
It has nothing to do with FIDE or USCF politics.)
[email protected] wrote:
>If we agree that owning a 2-cube has the same theoretical
>meaning at owning a 4-cube or 16-cube (or whatever level)
Are we allowed to factor in human psychology, or are we
assuming a perfectly rational player? To a real human,
there is an intangable value to seeing which way the
game goes, and a variable cost to making a bet that
approaches his net worth.
Even assuming a perfectly rational player, he has a finite
net worth, and thus a point comes where he *must* resign
rather than accept the double even though he has a 90% plus
chance of winning, because he cannot cover the bet.
That being said, none of the above assumptions leads to an
infinite number. A bet that is twice what he can afford to
cover is the same as a bet that is four or eight times what
he can afford to cover -- none are attanable states. Thus
the doubling cube itself does not make backgammon infinitely
long / unsolvable.
--
misc.business.product-dev: a Usenet newsgroup
about the Business of Product Development.
-- Guy Macon <http://www.guymacon.com/ >
|
| |
Date: 26 Mar 2008 08:14:38
From: bob
Subject: Re: Has Checkers Been Solved?
|
On 25, 9:11=A0pm, [email protected] wrote:
> Almost surely, there _are_ situations like that in backgammon. =A0Can't
> you mimic the above scenario in backgammon by postulating 18 monster
> rolls for each side?
> But, suppose there are such situations in backgammon, why does it then
> follow that the value of a cube, as well as its position, can affect
> theoretical money play? =A0This seems to be a hole in your argument. =A0So=
> let us assume that your scenario is exactly replicated in backgammon
> where there's a stalemate but each side has 18 monster winning rolls,
> and no gammons are possible. =A0Please explain why this scenario leads
> to the conclusion that the scenario with a 2 cube is essentially
> different than the scenario with a 1024 cube.
>
I doubt that there is a siutation like that in backgammon. Note
that you would need the 18 non-monster rolls to lead to repeating
positions. There has been one proposed but it only can arise as the
result of an illegal checker play.
Here is why such a situation will affect theoretical money play:
Theoretical money play means making the move that maximizes equity,
assuming perfect play from the opponent. Equity means the expected
value of the position. Take my coin flipping example again. If both
players use the always double/take strategy then the player on turn
will win $2 with probability 1/2, will lose $4 with probability 1/4,
will win $8 with probability 1/8, will lose $16 with probability
1/16 ... The expected value is 2(1/2) + (-4)(1/4) + (8)(1/8) + (-16)
(1/16) + ... which does not converge. The expected value is not even
defined.
Bob Koca
|
| |
Date: 26 Mar 2008 06:59:58
From: [email protected]
Subject: Re: Has Checkers Been Solved?
|
> I wouldn't be all that surprised if instead he finds that some of the
> 156 accepted three-move tournament choices are not draws. After all,
> the ones that were rejected were obvious losses, so openings that
> provided one player sufficient advantage to narrowly force a win with
> perfect play might not have been noted.
Obviously I can't say for sure until the computer analysis is
complete. You could very well be correct. But the trend has been in
the other direction. It used to be that there were 144 accepted 3-
move ballots. 12 more were added a few years back based to a large
extent on computer analysis that shows that despite their seeming
unbalance (which was why they originally were left out), they are
likely to be draws. One of them, "The Black Hole," a notoriously
difficult ballot, under computer analysis is showing more and more
drawing lines.
As checkers is analyzed more deeply, more drawing resources seem to be
found all the time. But it would be a rather exciting find if one of
the accepted ballots could be shown to be a win!
|
| |
Date: 26 Mar 2008 06:08:26
From:
Subject: Re: Has Checkers Been Solved?
|
On 26, 4:49=A0am, [email protected] (Torben =C6gidius Mogensen)
wrote:
>
> > and three possible positions of the doubling cube
>
> I can't see how this would affect the winning probability.
>
> > plus 24 possible slots for each checker.
>
> You forgot the bar and home, so there are 26 possible positions. =A0But
> since the checkers are not distinct, and since black and white pieces
> can't coexist (except on the bar and in the home), you get a lot fewer
> than the 30^26 different positions you imply.
>
> In any case, my point was that the number of positions is finite (but
> huge), so arguing that there are many possible rolls and positions of
> doubling cubes and pieces doesn't change that, unless you can show
> something is infinute.
>
> The doubling cube is normally limited to 7 possible positions (absent
> or 2, 4, ..., 64), but even if you allow unbounded doubling, this
> doesn't change the probability of winning.
>
> =A0 =A0 =A0 =A0 Torben- Hide quoted text -
>
> - Show quoted text -
If we agree that owning a 2-cube has the same theoretical meaning at
owning a 4-cube or 16-cube (or whatever level), how do you get 7
possible cube positions? I count only three: centered, owned by me,
or owned by the opponent.
--
Gregg C.
|
| |
Date: 26 Mar 2008 02:41:53
From:
Subject: Re: Has Checkers Been Solved?
|
On 26, 4:49=A0pm, [email protected] (Torben =C6gidius Mogensen)
wrote:
=2E..
>
> The doubling cube is normally limited to 7 possible positions (absent
> or 2, 4, ..., 64), ....
This is completely false. There is nothing wrong or problematic with
a double to 128. Admittedly, this can't be recorded on a normal
doubling cube but players can just write it down. Also, doubling
"cubes" are available which reach a max value of 256. Doubles beyond
64 are rare among good players, but if you're talking about what is
rare rather than what is legal, you shouldn't include 64 since good
players don't often let the cube get even that high.
Paul Epstein
|
| |
Date: 26 Mar 2008 01:47:34
From:
Subject: Re: Has Checkers Been Solved?
|
> samsloan wrote:
>
> Even that is not obvious. There are 21 possible rolls of the dice (6!
> = 21) and three possible positions of the doubling cube plus 24
> possible slots for each checker.
>
I haven't been following this thread so maybe I've missed something...
BUT
from what I read above: What do you mean by "possible rolls of the
dice"?
Combinations or Permutations? There are 21 of the former but 36 of
the
latter. Also 6! (6 factorial) is 720 not 21. Now, where did I go
wrong???
LRB
|
| |
Date: 25 Mar 2008 19:11:21
From:
Subject: Re: Has Checkers Been Solved?
|
On 26, 1:45=A0am, bob <[email protected] > wrote:
> On 25, 11:18=A0am, [email protected] (Torben =C6gidius Mogensen)
> wrote:
>
>
>
>
>
> > samsloan <[email protected]> writes:
> > > One factor to be considered is that the number of possible moves in a
> > > backgammon games is infinite. The players could easily just keeping
> > > hitting each other to infinity.
>
> > That doesn't matter, as long as the number of possible board positions
> > is finite (which it is).
>
> > The main difference between Backgammon and, say, Checkers is not the
> > possibility of infinite play but the fact that Backgammon involves
> > random elements, so few positions are definitely winning or definitely
> > losing -- all you can say is the probability of winning with perfect
> > play (i.e., always picking the move that gives you the best winning
> > probability after moving).
>
> > You can solve Backgammon by for each possible position have edges to
> > every other position that it is possible to get to in one move, and
> > label each edge with the dice outcome that allow this move).
>
> > This can be translated into a set of equations that you can solve to
> > find the probability of each possible position being winning or
> > losing. =A0The set of equations is huge, but finite.
>
> > =A0 =A0 =A0 =A0 Torben
>
> =A0 Agree for backgammon played without a cube, for backgammon played
> with a cap on the cube, or for match play. If you are talking about
> money backgammon though then the cube position and value makes the
> number of positions infinite. Now one might say that its position is
> all that matters since if you know the correct theoretical play
> holding a 2 cube then you also know the correct theoretical play
> holding a 4 or any higher value cube. There is a problem though in
> that the equations might not have a solution. As a simple example of
> how this might come about suppose we are betting on the flip of a
> coin. The first person to toss a head wins. Before each flip a
> doubling cube may be used as in backgammon. Solving the equations
> gives that every turn is a double and take but this leads to undefined
> equities. How to prove there is no situation like that possible in
> backgammon?
>
> Bob Koca- Hide quoted text -
>
> - Show quoted text -
Interesting example but I'm surprised by "How to prove there is no
situation like that possible in
> backgammon?"
Almost surely, there _are_ situations like that in backgammon. Can't
you mimic the above scenario in backgammon by postulating 18 monster
rolls for each side?
But, suppose there are such situations in backgammon, why does it then
follow that the value of a cube, as well as its position, can affect
theoretical money play? This seems to be a hole in your argument. So
let us assume that your scenario is exactly replicated in backgammon
where there's a stalemate but each side has 18 monster winning rolls,
and no gammons are possible. Please explain why this scenario leads
to the conclusion that the scenario with a 2 cube is essentially
different than the scenario with a 1024 cube.
Paul Epstein
|
| |
Date: 25 Mar 2008 10:45:05
From: bob
Subject: Re: Has Checkers Been Solved?
|
On 25, 11:18=A0am, [email protected] (Torben =C6gidius Mogensen)
wrote:
> samsloan <[email protected]> writes:
> > One factor to be considered is that the number of possible moves in a
> > backgammon games is infinite. The players could easily just keeping
> > hitting each other to infinity.
>
> That doesn't matter, as long as the number of possible board positions
> is finite (which it is).
>
> The main difference between Backgammon and, say, Checkers is not the
> possibility of infinite play but the fact that Backgammon involves
> random elements, so few positions are definitely winning or definitely
> losing -- all you can say is the probability of winning with perfect
> play (i.e., always picking the move that gives you the best winning
> probability after moving).
>
> You can solve Backgammon by for each possible position have edges to
> every other position that it is possible to get to in one move, and
> label each edge with the dice outcome that allow this move).
>
> This can be translated into a set of equations that you can solve to
> find the probability of each possible position being winning or
> losing. =A0The set of equations is huge, but finite.
>
> =A0 =A0 =A0 =A0 Torben
Agree for backgammon played without a cube, for backgammon played
with a cap on the cube, or for match play. If you are talking about
money backgammon though then the cube position and value makes the
number of positions infinite. Now one might say that its position is
all that matters since if you know the correct theoretical play
holding a 2 cube then you also know the correct theoretical play
holding a 4 or any higher value cube. There is a problem though in
that the equations might not have a solution. As a simple example of
how this might come about suppose we are betting on the flip of a
coin. The first person to toss a head wins. Before each flip a
doubling cube may be used as in backgammon. Solving the equations
gives that every turn is a double and take but this leads to undefined
equities. How to prove there is no situation like that possible in
backgammon?
Bob Koca
|
| |
Date: 25 Mar 2008 09:50:18
From: samsloan
Subject: Re: Has Checkers Been Solved?
|
On 25, 10:18 am, [email protected] (Torben =C6gidius Mogensen)
wrote:
> samsloan <[email protected]> writes:
> > One factor to be considered is that the number of possible moves in a
> > backgammon games is infinite. The players could easily just keeping
> > hitting each other to infinity.
>
> That doesn't matter, as long as the number of possible board positions
> is finite (which it is).
>
> The main difference between Backgammon and, say, Checkers is not the
> possibility of infinite play but the fact that Backgammon involves
> random elements, so few positions are definitely winning or definitely
> losing -- all you can say is the probability of winning with perfect
> play (i.e., always picking the move that gives you the best winning
> probability after moving).
>
> You can solve Backgammon by for each possible position have edges to
> every other position that it is possible to get to in one move, and
> label each edge with the dice outcome that allow this move).
>
> This can be translated into a set of equations that you can solve to
> find the probability of each possible position being winning or
> losing. The set of equations is huge, but finite.
>
> Torben
Even that is not obvious. There are 21 possible rolls of the dice (6!
=3D 21) and three possible positions of the doubling cube plus 24
possible slots for each checker.
The average chess position has 27 moves and most chess games are over
in 50 moves.
I have written a chess playing computer program and a shogi playing
computer program. However, I once tried to write a backgammon playing
computer program and I quickly gave it up as hopeless. It is much
harder than it looks.
Although backgammon seems to be an easier game than chess, I am not
sure that this is really true.
Sam Sloan
|
| | |
Date: 26 Mar 2008 09:49:59
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen
Subject: Re: Has Checkers Been Solved?
|
samsloan <[email protected] > writes:
> On 25, 10:18 am, [email protected] (Torben �gidius Mogensen)
> wrote:
>> samsloan <[email protected]> writes:
>> > One factor to be considered is that the number of possible moves in a
>> > backgammon games is infinite. The players could easily just keeping
>> > hitting each other to infinity.
>>
>> That doesn't matter, as long as the number of possible board positions
>> is finite (which it is).
>> [...]
>> This can be translated into a set of equations that you can solve to
>> find the probability of each possible position being winning or
>> losing. The set of equations is huge, but finite.
>>
>> Torben
>
> Even that is not obvious. There are 21 possible rolls of the dice (6!
> = 21)
6! is 720, actually. But you are right that the number of different
rolls is 21 = 6*7/2. This is still finite, though.
> and three possible positions of the doubling cube
I can't see how this would affect the winning probability.
> plus 24 possible slots for each checker.
You forgot the bar and home, so there are 26 possible positions. But
since the checkers are not distinct, and since black and white pieces
can't coexist (except on the bar and in the home), you get a lot fewer
than the 30^26 different positions you imply.
In any case, my point was that the number of positions is finite (but
huge), so arguing that there are many possible rolls and positions of
doubling cubes and pieces doesn't change that, unless you can show
something is infinute.
The doubling cube is normally limited to 7 possible positions (absent
or 2, 4, ..., 64), but even if you allow unbounded doubling, this
doesn't change the probability of winning.
Torben
|
| | |
Date: 25 Mar 2008 12:15:42
From: Kenneth Sloan
Subject: Re: Has Checkers Been Solved?
|
samsloan wrote:
>
> Even that is not obvious. There are 21 possible rolls of the dice (6!
> = 21) and three possible positions of the doubling cube plus 24
> possible slots for each checker.
BZZZT!
Are the checkers in your backgammon set ked in some way?
--
Kenneth Sloan [email protected]
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
|
| |
Date: 25 Mar 2008 09:19:03
From: Quadibloc
Subject: Re: Has Checkers Been Solved?
|
On 16, 8:39=A0pm, "[email protected]" <[email protected] > wrote:
> First, what Schaeffer did is to show that freestyle (unrestricted)
> checkers is an absolute draw.
>
> He has not analyzed all of the 3-move restriction openings so he has
> not proven that tournament checkers is a draw. =A0He has proven that
> some of the 3-movers are a draw, and will likely eventually show that
> all 156 of the accepted tournament choices are a draw (the other few
> are almost certain losses and are not used). =A0Of course, there could
> be a deeply-buried surprise in one or more of the 156, but with the
> amount of other computer analysis done to date, it's not very likely
> --- but it hasn't been categorically proven yet.
I wouldn't be all that surprised if instead he finds that some of the
156 accepted three-move tournament choices are not draws. After all,
the ones that were rejected were obvious losses, so openings that
provided one player sufficient advantage to narrowly force a win with
perfect play might not have been noted.
I realize that this is a fairly large advantage, though, and that
might mean it would have been suspected, but then the fact that
freestyle checkers was a draw wasn't known for certain until it was
proved.
John Savard
|
| |
Date: 17 Mar 2008 17:09:22
From: bob
Subject: Re: Has Checkers Been Solved?
|
And the ironic thing is everything I wrote was accurate. Checkers
has only been weakly solved.
From the referenced paper, "With this paper we announce that checkers
has been weakly solved".
Thus my reply was spot on after Frank wrote,
"in the recent ICGA Journal ( www.icga.org) was a lengthy article
about checkers being solved. And AFAIK tournament checkers is a subset
of
freestyle so if the later is solved...."
Nospam, are you this obnoxious when you are not anonymous?
Bob Koca
|
| |
Date: 17 Mar 2008 22:20:24
From:
Subject: Re: Has Checkers Been Solved?
|
Content-Transfer-Encoding: 8Bit
[email protected] wrote:
>On 17, 4:15�pm, [email protected] wrote:
>> bob wrote:
>> >Suppose that it has been discovered that with a certain opening
>> >play that the first player can force a win. One might then say that
>> >checkers has been solved. This knowledge though does not say what the
>> >theoretical status of the game is if a different opening play is
>> >forced.
>>
>> Do a Google search on phrases (with the quotation ks) such as:
>>
>> "weakly solved"
>> "strongly solved"
>> "ultra-weakly solved"
>> "ultra-strongly solved"
>>
>> ...then come back and post an answer that DOESN'T suck.
>
>Bob's answer was fine. Some of us actually have to work for a
>living. We don't all have time to do 5 hours of research before
>posting.
>
>Paul
If you don't have time to get true information (five minutes tops using the
search terms above), you should simply STFU rather than posting false information.
"Suppose that it has been discovered that with a certain opening play that
the first player can force a win" is a description of weakly solved. "if
a different opening play is forced" is a description of strongly solved.
If you two dim bulbs would spend five minutes doing the search I suggested,
this would not confuse you so.
|
| | |
Date: 17 Mar 2008 22:31:53
From: Gutless Umbrella Carrying Sissy
Subject: Re: Has Checkers Been Solved?
|
[email protected] wrote in
news:[email protected]:
>
> Content-Transfer-Encoding: 8Bit
>
> [email protected] wrote:
>>On 17, 4:15�pm, [email protected] wrote:
>>> bob wrote:
>>> >Suppose that it has been discovered that with a certain
>>> >opening play that the first player can force a win. One might
>>> >then say that checkers has been solved. This knowledge though
>>> >does not say what the theoretical status of the game is if a
>>> >different opening play is forced.
>>>
>>> Do a Google search on phrases (with the quotation ks) such
>>> as:
>>>
>>> "weakly solved"
>>> "strongly solved"
>>> "ultra-weakly solved"
>>> "ultra-strongly solved"
>>>
>>> ...then come back and post an answer that DOESN'T suck.
>>
>>Bob's answer was fine. Some of us actually have to work for a
>>living. We don't all have time to do 5 hours of research before
>>posting.
>>
>>Paul
>
> If you don't have time to get true information (five minutes
> tops using the search terms above), you should simply STFU
> rather than posting false information.
>
> "Suppose that it has been discovered that with a certain opening
> play that the first player can force a win" is a description of
> weakly solved. "if a different opening play is forced" is a
> description of strongly solved. If you two dim bulbs would spend
> five minutes doing the search I suggested, this would not
> confuse you so.
>
On the other hand, there's a fair degree of entertainment value is
pissing tight-ass pricks like you off.
--
Terry Austin
"There's no law west of the internet."
- Nick Stump
Jesus forgives sinners, not criminals.
|
| |
Date: 17 Mar 2008 07:15:14
From: [email protected]
Subject: Re: Has Checkers Been Solved?
|
> My recollection is slightly different. I remember looking at results
> from the highest level of checkers play and a player would win a match
> by 1 game to 0 with 20 draws. However, that's an impression from
> memory only -- I haven't been able to check it. Can you back up your
> claim with hard stats? If the world no. 1 plays the world no. 2,
> would they draw less than 95% of their games? (I doubt it.) I think
> it's a pretty dead game at the highest level.
I could get exact stats from the American Checker Federation. I am
pretty sure though that, for instance world championship matches, are
something above 80% draws, if maybe not 95%, even with 3-move
restriction. Whether that means it's a "dead" game is a matter of
definition. Certainly at the NON-championship level, the percentage
of draws is very much lower (you can verify this by looking at on-line
play sites). High-level tournaments, when they achieve under 75%
draws, are considered "lively."
But my point was that, while computer analysis shows an absolute draw
for unrestricted play and very likely will show the same for 3-move
play, humans still win and lose. As you point out, it is at a
relatively low percentage, but still, the game continues to be played.
|
| |
Date: 17 Mar 2008 06:46:12
From:
Subject: Re: Bob seen after a long time.
|
On 17, 8:46=A0pm, bob <[email protected] > wrote:
> On 17, 7:08=A0am, Sanny <[email protected]> wrote:
>
>
>
>
>
> > > =A0 Am I missing something in my intuitive argument or is one of the
> > > calculations incorrect? The Trice argument looks solid to me.
>
> > Are you the one who used to play with username "Bob" at GetClub? I was
> > searching for Bob for long time. You left playing long before. Play a
> > few games at GetClub and see how well it plays now.
>
> > Play Chess at:http://www.GetClub.com/Chess.html
>
> > Help Bot used to say that you use Computer's help while playing
> > against GetClub is that True?
>
> > Your games are rekable. Only Zebediah matches your game style.
>
> > Bye
> > Sanny
>
> > Play Chess at:http://www.GetClub.com/Chess.html
>
> =A0 =A0A different Bob than me.
>
> Bob Koca- Hide quoted text -
>
> - Show quoted text -
Huge coincidence since Bob is an extremely uncommon name.
Paul Epstein
|
| |
Date: 17 Mar 2008 05:46:31
From: bob
Subject: Re: Bob seen after a long time.
|
On 17, 7:08=A0am, Sanny <[email protected] > wrote:
> > =A0 Am I missing something in my intuitive argument or is one of the
> > calculations incorrect? The Trice argument looks solid to me.
>
> Are you the one who used to play with username "Bob" at GetClub? I was
> searching for Bob for long time. You left playing long before. Play a
> few games at GetClub and see how well it plays now.
>
> Play Chess at:http://www.GetClub.com/Chess.html
>
> Help Bot used to say that you use Computer's help while playing
> against GetClub is that True?
>
> Your games are rekable. Only Zebediah matches your game style.
>
> Bye
> Sanny
>
> Play Chess at:http://www.GetClub.com/Chess.html
A different Bob than me.
Bob Koca
|
| |
Date: 17 Mar 2008 04:08:01
From: Sanny
Subject: Bob seen after a long time.
|
> =A0 Am I missing something in my intuitive argument or is one of the
> calculations incorrect? The Trice argument looks solid to me.
Are you the one who used to play with username "Bob" at GetClub? I was
searching for Bob for long time. You left playing long before. Play a
few games at GetClub and see how well it plays now.
Play Chess at: http://www.GetClub.com/Chess.html
Help Bot used to say that you use Computer's help while playing
against GetClub is that True?
Your games are rekable. Only Zebediah matches your game style.
Bye
Sanny
Play Chess at: http://www.GetClub.com/Chess.html
|
| |
Date: 17 Mar 2008 01:40:05
From:
Subject: Re: Has Checkers Been Solved?
|
On 17, 4:15=A0pm, [email protected] wrote:
> bob wrote:
> >Suppose that it has been discovered that with a certain opening
> >play that the first player can force a win. One might then say that
> >checkers has been solved. This knowledge though does not say what the
> >theoretical status of the game is if a different opening play is
> >forced.
>
> Do a Google search on phrases (with the quotation ks) such as:
>
> "weakly solved"
> "strongly solved"
> "ultra-weakly solved"
> "ultra-strongly solved"
>
> ...then come back and post an answer that DOESN'T suck.
Bob's answer was fine. Some of us actually have to work for a
living. We don't all have time to do 5 hours of research before
posting.
Paul
|
| |
Date: 17 Mar 2008 08:15:29
From:
Subject: Re: Has Checkers Been Solved?
|
bob wrote:
>Suppose that it has been discovered that with a certain opening
>play that the first player can force a win. One might then say that
>checkers has been solved. This knowledge though does not say what the
>theoretical status of the game is if a different opening play is
>forced.
Do a Google search on phrases (with the quotation ks) such as:
"weakly solved"
"strongly solved"
"ultra-weakly solved"
"ultra-strongly solved"
...then come back and post an answer that DOESN'T suck.
|
| |
Date: 16 Mar 2008 20:24:57
From:
Subject: Re: Has Checkers Been Solved?
|
On 17, 10:39=A0am, "[email protected]" <[email protected] >
wrote:
> On 16, 2:55 pm, [email protected] wrote:
>
> > IIRC all tournament openings are shown to be a draw. IIRC further the
> > other openings are not selected in tournament play because they gave
> > one player a too large advantage.
>
> Almost.
>
> First, what Schaeffer did is to show that freestyle (unrestricted)
> checkers is an absolute draw.
>
> He has not analyzed all of the 3-move restriction openings so he has
> not proven that tournament checkers is a draw. =A0He has proven that
> some of the 3-movers are a draw, and will likely eventually show that
> all 156 of the accepted tournament choices are a draw (the other few
> are almost certain losses and are not used). =A0Of course, there could
> be a deeply-buried surprise in one or more of the 156, but with the
> amount of other computer analysis done to date, it's not very likely
> --- but it hasn't been categorically proven yet.
>
> But translate this over to human players, and checkers is certainly
> not a draw when played by real people, even at the very highest
> current level of human skill. =A0So people are going to keep playing.
My recollection is slightly different. I remember looking at results
from the highest level of checkers play and a player would win a match
by 1 game to 0 with 20 draws. However, that's an impression from
memory only -- I haven't been able to check it. Can you back up your
claim with hard stats? If the world no. 1 plays the world no. 2,
would they draw less than 95% of their games? (I doubt it.) I think
it's a pretty dead game at the highest level.
Paul Esptein
|
| |
Date: 16 Mar 2008 19:39:56
From: [email protected]
Subject: Re: Has Checkers Been Solved?
|
On 16, 2:55 pm, [email protected] wrote:
> IIRC all tournament openings are shown to be a draw. IIRC further the
> other openings are not selected in tournament play because they gave
> one player a too large advantage.
Almost.
First, what Schaeffer did is to show that freestyle (unrestricted)
checkers is an absolute draw.
He has not analyzed all of the 3-move restriction openings so he has
not proven that tournament checkers is a draw. He has proven that
some of the 3-movers are a draw, and will likely eventually show that
all 156 of the accepted tournament choices are a draw (the other few
are almost certain losses and are not used). Of course, there could
be a deeply-buried surprise in one or more of the 156, but with the
amount of other computer analysis done to date, it's not very likely
--- but it hasn't been categorically proven yet.
But translate this over to human players, and checkers is certainly
not a draw when played by real people, even at the very highest
current level of human skill. So people are going to keep playing.
|
| |
Date: 16 Mar 2008 13:55:08
From:
Subject: Re: Has Checkers Been Solved?
|
IIRC all tournament openings are shown to be a draw. IIRC further the
other openings are not selected in tournament play because they gave
one player a too large advantage.
All from the memory...
|
| |
Date: 16 Mar 2008 13:51:47
From:
Subject: Re: Has Checkers Been Solved?
|
Checker pieces can be crowned to make kings. That accounts for the
extra positions.
Tom
On 16, 11:27 am, bob <[email protected] > wrote:
> The abstract states "The game of checkers has roughly 500 billion
> billion possible positions (5 x 10 ^ 20)" Walter Trice calculated
> about 1.8 x 10^19 positions for backgammonhttp://www.bkgm.com/rgb/rgb.cgi?view+371.
> His calculation is actually a little too large because he did not
> worry about if the positions could actually arise or not but that is
> probably an insignificant factor.
>
> I am surprised that checkers has more possible positions than
> backgammon. I figure that the 30 backgammon pieces instead of 24 for
> checkers would about balance 33 locations in checkers forthose pieces
> instead of only 26 locations for them in backgammon. Backgammon would
> then pull way ahead becuase there can be up to 15 checkers at a
> location as opposed to 2 for the all the checker locations except "off
> the board".
>
> Am I missing something in my intuitive argument or is one of the
> calculations incorrect? The Trice argument looks solid to me.
>
> Bob Koca
|
| |
Date: 16 Mar 2008 14:05:55
From: Ray Gordon, creator of the \pivot\
Subject: Re: Has Checkers Been Solved?
|
> It has been published that checkers has been solved. See:
>
> http://www.sciencemag.org/cgi/content/abstract/317/5844/1518
>
> However, I am hearing that checkers has not been solved at all. Only
> free-style checkers has been solved. Tournament style checkers where
> there is a drawing to determine the first three moves is still an
> actively contested game.
>
> Which is true? Does anybody know?
Both can be true, in that the moves that "solved" the game can be excluded
for other territory that is not solved but which are made moot by the
solution, except when the solution moves cannot be played.
Applied to chess, if 1. e4 proved a forced win for White, but no one solved
1. d4, and you banned 1. e4 from tournament play, then tournament chess
would not be solved, while chess as a whole, would be.
--
Ray Gordon, The ORIGINAL Lifestyle Seduction Guru
http://www.cybersheet.com/library.html
Includes 29 Reasons Not To Be A Nice Guy
Ray's new "Project 5000" is here:
http://groups.yahoo.com/group/project-5000
Don't rely on overexposed, mass-keted commercial seduction methods which
no longer work.
Thinking of taking a seduction "workshiop?" Read THIS:
http://www.dirtyscottsdale.com/?p=1187
Beware! VH-1's "The Pickup Artst" was FRAUDULENT. Six of the eight
contestants were actors, and they used PAID TARGETS in the club. The paid
targets got mad when VH-1 said "there are no actors in this club" and ruined
their prromised acting credit. What else has Mystery lied about?
|
| |
Date: 16 Mar 2008 11:00:18
From: bob
Subject: Re: Has Checkers Been Solved?
|
On 16, 1:32=A0pm, [email protected] wrote:
> in the recent ICGA Journal (www.icga.org) was a lengthy article about
> checkers being solved. And AFAIK tournament checkers is a subset of
> freestyle so if the later is solved....
Suppose that it has been discovered that with a certain opening
play that the first player can force a win. One might then say that
checkers has been solved. This knowledge though does not say what the
theoretical status of the game is if a different opening play is
forced.
Bob Koca
|
| |
Date: 16 Mar 2008 10:32:29
From:
Subject: Re: Has Checkers Been Solved?
|
in the recent ICGA Journal ( www.icga.org) was a lengthy article about
checkers being solved. And AFAIK tournament checkers is a subset of
freestyle so if the later is solved....
ciao
Frank
BTW: Have you read "one jump ahead" If you either interested in
checkers or in programming board game AIs it's a good book to read.
|
| |
Date: 16 Mar 2008 10:16:37
From: samsloan
Subject: Re: Has Checkers Been Solved?
|
One factor to be considered is that the number of possible moves in a
backgammon games is infinite. The players could easily just keeping
hitting each other to infinity.
The number of possible chess games, while very large, is not infinite.
After a few billion moves the 50-move rule becomes a factor.
Except for the fact that checkers does not have a 50-move rule, the
number of possible checker games is relatively small.
None of this addresses the basic question being asked here, of course.
Sam Sloan
|
| | |
Date: 25 Mar 2008 16:18:22
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen
Subject: Re: Has Checkers Been Solved?
|
samsloan <[email protected] > writes:
> One factor to be considered is that the number of possible moves in a
> backgammon games is infinite. The players could easily just keeping
> hitting each other to infinity.
That doesn't matter, as long as the number of possible board positions
is finite (which it is).
The main difference between Backgammon and, say, Checkers is not the
possibility of infinite play but the fact that Backgammon involves
random elements, so few positions are definitely winning or definitely
losing -- all you can say is the probability of winning with perfect
play (i.e., always picking the move that gives you the best winning
probability after moving).
You can solve Backgammon by for each possible position have edges to
every other position that it is possible to get to in one move, and
label each edge with the dice outcome that allow this move).
This can be translated into a set of equations that you can solve to
find the probability of each possible position being winning or
losing. The set of equations is huge, but finite.
Torben
|
| | |
Date: 17 Mar 2008 15:37:48
From: David Richerby
Subject: Re: Has Checkers Been Solved?
|
[ Crosspost trimmed. ]
samsloan <[email protected] > wrote:
> One factor to be considered is that the number of possible moves in
> a backgammon games is infinite. The players could easily just
> keeping hitting each other to infinity.
>
> The number of possible chess games, while very large, is not
> infinite. After a few billion moves the 50-move rule becomes a
> factor.
No, the number of possible chess games is infinite, since claiming a
draw under the fifty move rule or threefold repetition is not
mandatory. For analytical purposes, one can consider the game to be
finite, on the assumption that a player who can't win will always
claim the draw as soon as he can and that a player who can win will
never offer a repetition or a fifty-move draw.
Dave.
--
David Richerby Slimy Toy (TM): it's like a fun
www.chiark.greenend.org.uk/~davidr/ child's toy but it's covered in goo!
|
| |
Date: 16 Mar 2008 09:27:04
From: bob
Subject: Re: Has Checkers Been Solved?
|
The abstract states "The game of checkers has roughly 500 billion
billion possible positions (5 x 10 ^ 20)" Walter Trice calculated
about 1.8 x 10^19 positions for backgammon http://www.bkgm.com/rgb/rgb.cgi?view+371.
His calculation is actually a little too large because he did not
worry about if the positions could actually arise or not but that is
probably an insignificant factor.
I am surprised that checkers has more possible positions than
backgammon. I figure that the 30 backgammon pieces instead of 24 for
checkers would about balance 33 locations in checkers forthose pieces
instead of only 26 locations for them in backgammon. Backgammon would
then pull way ahead becuase there can be up to 15 checkers at a
location as opposed to 2 for the all the checker locations except "off
the board".
Am I missing something in my intuitive argument or is one of the
calculations incorrect? The Trice argument looks solid to me.
Bob Koca
|
|
