Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

10 views

Skip to first unread message

Jun 29, 1998, 3:00:00â€¯AM6/29/98

to

Hi all

I was wondering if some time in the future backgammon will be able to

be completely solved?

Is it theoretically possible to work backwards and calculate all the

permutations from bearing back in to the starting set up assuming all

the best plays are made ?

With the progress of computing speed is this likely to be achievable

in my lifetime?

Maverick

Jun 30, 1998, 3:00:00â€¯AM6/30/98

to

The same idea had occured to me a while back, but I doubt whether it

is possible to do it for contact situations. In any situation involving

the possiblity of hitting blots it is no doubt possible to come up

with sequences of hits and counter-hits of enormous - theoretically

infinite - length. It is not obvious that, for any given position the

contribution to the equity from such sequences is going to be

calculable, though if they make a suitably small contribution to the

total equity they can be included roughly. But then the game won't

have been exactly 'solved'.

Just my own thoughts on the subject.

Phill

Jun 30, 1998, 3:00:00â€¯AM6/30/98

to

!remove!this!ph...@sun.leeds.ac.uk (Phill Skelton) writes:

Infinite sequences aren't a problem -- there are a finite number of

possible board states in backgammon, and so you can treat backgammon

as a Markov process over a finite number of states. The probabilities

of a transition from one state to any other form an n x n matrix --

there IS enough information in the matrix to determine the probability

of reaching any terminal state (if you ignore the cube, there are 6

terminal states: win, gammon, and backgammon for each player); it's

analogous to a simultaneous equation with n equations and n unknowns.

The difficulty then lies not with the possibility of infinitely long

games, but the size of n -- if I got it right, then there's

63,432,274,896 ways to arrange 15 chequers among 24 points, the bar,

and borne off. That's only one player's chequers -- once you include

the opponent's chequers, the number of legal positions is of the order

of 10^18.

If we make a conservative assumption that the computer already has

some kind of partial ordering of the positions so that given all

preceding positions, it can calculate the equity of the current one;

and it typically takes 400 operations to calculate the equity of a

position (21 possible dice rolls by around 20 ways to play each roll),

and a computer can currently perform 500 million operations per second,

then a contemporary computer would require over 25,000 years to evaluate

the equity of every position. According to Moore's Law, this computation

time will halve approximately every 18 months; if we assume you will

live for 48 more years then computation speeds will have increased by

a factor of 2^32, and the complete backgammon analysis will take about

3 minutes. In money play there are only 4 possible cube states (centred,

owned by X, owned by O, and let's add cubeless for completeness) so a

cubeful analysis would take just over 12 minutes.

(As a side note: such a computer is not entirely out of the question.

Bremermann [I don't have a proper reference sorry... I recently moved

from New Zealand to Arizona and left most of my books behind] conjectured

based on quantum mechanical arguments that no computer, living or artificial,

can process more than 10^47 (I think) bits per gram of its mass per second.

In 48 years, the computer above would still be under 10^17 bits per second and

theoretically can be built with less than a 10^-30g of matter. However,

another of Moore's Laws states that the cost of semiconductor manufacturing

plants is also growing exponentially. At current growth rates, the

international revenue spent on semiconductors is projected to equal the

total global GDP by around 2020. So I guess we can expect a slowdown in

computer development sometime in the next 25 years, assuming humans will

continue to want to spend some money on trivial things like food :-)

So the short answers to your three questions are: Very likely, yes, and

perhaps.

Cheers,

Gary.

--

Gary Wong, Department of Computer Science, University of Arizona

ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/

Jul 1, 1998, 3:00:00â€¯AM7/1/98

to

maverick wrote:

: Hi all

: I was wondering if some time in the future backgammon will be able to

: be completely solved?

There is little question that it will, eventually, be solved.

: Is it theoretically possible to work backwards and calculate all the

: permutations from bearing back in to the starting set up assuming all

: the best plays are made ?

Absolutely. It would take a long time, though, unless computer

power improves.

: With the progress of computing speed is this likely to be achievable

: in my lifetime?

That's not a bad guess, IMHO. It might happen in 30 years,

since computer tecnology is changing so much. Within 100

years, it will certainly be solved, given the present rate

or computer technolog growth. Computers have already solved

Connect 4 (win for first player, I think) and Nine Men's

Morris (draw, as I recall).

Jul 1, 1998, 3:00:00â€¯AM7/1/98

to

Gary Wong (ga...@cs.arizona.edu) wrote:

: theoretically can be built with less than a 10^-30g of matter. However,

: another of Moore's Laws states that the cost of semiconductor manufacturing

: plants is also growing exponentially. At current growth rates, the

: international revenue spent on semiconductors is projected to equal the

: total global GDP by around 2020. So I guess we can expect a slowdown in

: computer development sometime in the next 25 years, assuming humans will

: continue to want to spend some money on trivial things like food :-)

Great posting and procedural deductive analysis. But isn't there

talk nowadays about designing chips with ultra-tiny circuits,

of nanometer thickness and less? Such chips might require fewer

resources to manufacture, with a much higher speed ceiling than

today's chips.

Jul 2, 1998, 3:00:00â€¯AM7/2/98

to

I have seen the posting about the "future of backgammon", and I have a

related and maybe more fundamental question: I wonder if there exists

a best strategy in Backgammon, i.e. a strategy that is better than any

other strategy.

I do not talk about roll-outs or calculations that suppose that both

players play always the "best" move, since this has to be proven

first. Is it theoretical impossible that there are for instance three

strategies A, B and C, such that A is better than B, B better than C

and C better than A (and which are better than any other strategy)?

Maybe it's trivial but I couldn't figure it out. I think, the problem

is that in contact situations, the equities of two positions can

depend on each other, so you can not just work backwards and calculate

the equities. You do not even know, if and how two positions depend on

each other, since you need to know your "best" move to do so. However,

I might be wrong and following is correct.

Gary Wong proposed the following approach (in Re: The future of

backgammon):

> Infinite sequences aren't a problem -- there are a finite number of

> possible board states in backgammon, and so you can treat backgammon

> as a Markov process over a finite number of states. The probabilities

> of a transition from one state to any other form an n x n matrix --

> there IS enough information in the matrix to determine the probability

> of reaching any terminal state (if you ignore the cube, there are 6

> terminal states: win, gammon, and backgammon for each player); it's

> analogous to a simultaneous equation with n equations and n unknowns.

I do not know the framework of simultaneous equations, but how can you

know that there is enough information in the matrix? If I understand

you correctly, the matrix elements are the transition probablities

between two states. But these probablities are also unknown (at least

for

some positions, i.e. most/several contact positions), since you need

to know the best moves to compute them.

So, is there the Holy Grail of a best strategy out there???

Holger

-------------------------------------------------------------

Holger Bosch

Dept. of Computer Science, University of Geneva

24, rue du General Dufour, 1211 Geneva 4, Switzerland

Phone: +41 (22) 705-7642, Fax: +41 (22) 705-7780

E-mail: bo...@cui.unige.ch, http://cuiwww.unige.ch/~bosch

-------------------------------------------------------------

Jul 2, 1998, 3:00:00â€¯AM7/2/98

to

>Computers have already solved

>Connect 4 (win for first player, I think) and Nine Men's

>Morris (draw, as I recall).

And also Othello (actually humans have), and Checkers. There are computers

that beat the world champions on these games. I'll not say also chess

because there's too much speculation about whether Deep Blue (the computer

who beat the world Champion Garry Kasparov last year) cheated or not.

Rodrigo

Jul 2, 1998, 3:00:00â€¯AM7/2/98

to

BOSCH Holger <bo...@CUI.UNIGE.CH> writes:

> I have seen the posting about the "future of backgammon", and I have a

> related and maybe more fundamental question: I wonder if there exists

> a best strategy in Backgammon, i.e. a strategy that is better than any

> other strategy.

Subject to one or two restrictions, the answer is yes. (Several strategies

that are no worse than any other strategy, at least.)

> I do not talk about roll-outs or calculations that suppose that both

> players play always the "best" move, since this has to be proven

> first. Is it theoretical impossible that there are for instance three

> strategies A, B and C, such that A is better than B, B better than C

> and C better than A (and which are better than any other strategy)?

Three strategies certainly exist such that each is better than one of the

others and worse than the third (ie. those three strategies are

non-transitive); here's one example of strategies A, B and C:

A: Form a forward anchor and make low points in home board to blitz.

B: Overly `pure' play: Slot like crazy, try to prime. Bruce Becker :-)

C: Play safe and don't leave blots.

If you adjust the overall strengths of three players using these strategies

so they end up roughly equal in "skill", then A will tend to beat B because

his forward anchor is an excellent defence against being primed. B will

beat C a little more often than not, because C's back men will easily be

trapped. And it's conceivable that there is a player C who, despite losing

to B because of his weakness against primes, can nevertheless beat A through

superior skill in other areas and the fact that C will not easily be blitzed.

So these strategies are non-transitive.

However, it is _impossible_ for any set of non-transitive strategies to be

better than every remaining strategy. The complete proof is beyond the

scope of this article (that phrase is so much more appealing than "I'm

kind of hazy on the details" ;-) but there is a theorem (the Minimax

Theorem) that states that "every finite, zero-sum, two-person game has

optimal mixed strategies" (see the definition of "Minimax theorem" in

the Encyclopaedia of Mathematics at

http://www.astro.virginia.edu/~eww6n/math/). Money backgammon is actually

_not_ a finite game because the cube can take on arbitrarily many values, but

match backgammon is finite.

A _mixed strategy_ is a general class of strategy including those where a

player makes decisions probabilistically (an example of why this may be

necessary is the game "paper, scissors, rock" where the best strategy is to

pick a move at random -- always picking "paper" is not the best strategy).

Since backgammon is a game of complete information (both players can see the

state of the board and dice) we can actually go slightly stronger than the

Minimax theorem and claim that backgammon has optimal _pure_ strategies (ie.

strategies where the same move is always made in the same position). Note

that non-transitive strategies (eg. the A, B and C above) _cannot_ be optimal;

the Minimax theorem states that any optimal strategy must lie at a "saddle

point" of the payoff matrix. A strategy belonging to a non-transitive set

cannot possibly lie at a saddle point because by definition there is another

strategy along the same row/column of the matrix with a better payoff. The

practical upshot is that if you believe the Minimax Theorem (and you can

read a proof elsewhere :-) then yes, there are optimal strategies for

backgammon. (There is more than one optimal strategy because different

actions may result in identical payoff; eg. accepting or declining a double

that would result in a dead cube when you have exactly 25% chance of winning).

If you're a glutton for punishment and want to read about why this proof

does not suffice for money backgammon (with an unlimited cube) and an

attempt to find an alternate proof/disproof that optimal strategies exist

for money backgammon, look at http://www.dejanews.com/ for a position posted

by Paul Tanenbaum entitled "Extremely theoretical" and a discussion with

David Ullrich and others "Under-doubling dice". We never quite got a

rigourous proof, but personally I suspect that there is an `optimal' strategy

for money backgammon too (depending how you define `optimal').

> Maybe it's trivial but I couldn't figure it out. I think, the problem

> is that in contact situations, the equities of two positions can

> depend on each other, so you can not just work backwards and calculate

> the equities. You do not even know, if and how two positions depend on

> each other, since you need to know your "best" move to do so. However,

> I might be wrong and following is correct.

>

> Gary Wong proposed the following approach (in Re: The future of

> backgammon):

> > Infinite sequences aren't a problem -- there are a finite number of

> > possible board states in backgammon, and so you can treat backgammon

> > as a Markov process over a finite number of states. The probabilities

> > of a transition from one state to any other form an n x n matrix --

> > there IS enough information in the matrix to determine the probability

> > of reaching any terminal state (if you ignore the cube, there are 6

> > terminal states: win, gammon, and backgammon for each player); it's

> > analogous to a simultaneous equation with n equations and n unknowns.

>

> I do not know the framework of simultaneous equations, but how can you

> know that there is enough information in the matrix? If I understand

> you correctly, the matrix elements are the transition probablities

> between two states. But these probablities are also unknown (at least

> for

> some positions, i.e. most/several contact positions), since you need

> to know the best moves to compute them.

You are quite right, my explanation glossed over part of the problem. The

statement about the Markov process and probability matrix holds if an

optimal strategy is known, but is not a practical way to find one.

Nevertheless I claim it is possible to find such a strategy by computer

(eg. the truly ugly brute force method of enumerating all strategies and

finding a saddle point of the payoff matrix).

> So, is there the Holy Grail of a best strategy out there???

Yes -- as it is written in the Gospel according to Saint John :-) (John von

Neumann proved the Minimax Theorem in 1928).

Cheers,

Gary.

--

Gary Wong, Department of Computer Science, University of Arizona

ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/

Jul 3, 1998, 3:00:00â€¯AM7/3/98

to

In article <6ngrqq$ia9$1...@news4.wt.net> Rodrigo Andrade,

candrade@_R_E_M_O_V_E_wt.net writes:

>And also Othello (actually humans have), and Checkers. There are computers

>that beat the world champions on these games. I'll not say also chess

>because there's too much speculation about whether Deep Blue (the computer

>who beat the world Champion Garry Kasparov last year) cheated or not.

>

And how, pray tell, does Deep Blue cheat at chess? Give

itself an extra pawn? Take two moves in a row? Knock the

board over just before losing?

With millions watching every move, the machine scrutinized

by scientific and chess experts around the world, I fail to

see how anyone could believe that Deep Blue somehow cheated

at chess (unless they've added dice to the game recently).

//fergy

Jul 3, 1998, 3:00:00â€¯AM7/3/98

to

Rodrigo Andrade (candrade@_R_E_M_O_V_E_wt.net) wrote:

: And also Othello (actually humans have), and Checkers. There are computers

: that beat the world champions on these games. I'll not say also chess

: because there's too much speculation about whether Deep Blue (the computer

: who beat the world Champion Garry Kasparov last year) cheated or not.

: Rodrigo

These three games haven't been solved, even though computer

versions can beat the strongest human players.

Jul 6, 1998, 3:00:00â€¯AM7/6/98

to

Sorry. I assumed that "being solved" meant "can't be beaten." Please clarify

the term "being solved."

Rodrigo

Jul 7, 1998, 3:00:00â€¯AM7/7/98

to

Rodrigo Andrade (candrade@_R_E_M_O_V_E_wt.net) wrote:

: Sorry. I assumed that "being solved" meant "can't be beaten." Please clarify

: the term "being solved."

: Sorry. I assumed that "being solved" meant "can't be beaten." Please clarify

: the term "being solved."

: Rodrigo

"Being solved" means that all the values of all theoretical outcomes

possible have been computed and analyzed, such that the

computer can play the game perfectly. "Can't be beaten" means it

can beat all human players, but not necessarily that it plays perfectly.

So if, say, the best human players can make perfect moves 90% of

the time, a computer would only need to make pefect moves a little

over 90% of the time to beat all humans (assuming a perfect information

game).

Jul 7, 1998, 3:00:00â€¯AM7/7/98

to

David desJardins <de...@math.berkeley.edu> writes:

> BOSCH Holger <bo...@CUI.UNIGE.CH> writes:

> > I have seen the posting about the "future of backgammon", and I have a

> > related and maybe more fundamental question: I wonder if there exists

> > a best strategy in Backgammon, i.e. a strategy that is better than any

> > other strategy.

>

> There are several problems, some of which you have identified:> BOSCH Holger <bo...@CUI.UNIGE.CH> writes:

> > I have seen the posting about the "future of backgammon", and I have a

> > related and maybe more fundamental question: I wonder if there exists

> > a best strategy in Backgammon, i.e. a strategy that is better than any

> > other strategy.

>

>

> 1. Some positions are known not to have a finite equity; i.e., with

> "best play" on both sides, the expected value of the position is a sum

> of a divergent sequence. This problem can be avoided if a cap is placed

> on the cube value, or in match play, or in cubeless play, or if some

> settlement value is simply imposed on such positions. No one knows how

> many such positions there are, or if they will ever be reached from the

> standard starting position with "best play".

This is true. However, it's not clear that this implies that a "best

strategy" does not exist. I can demonstrate that the correct

behaviour is a double/take in Paul Tanenbaum's position for instance,

without requiring the expected equity to be defined. And note that

the _distribution_ of X (where X is the random variable representing

the points won in a game by a particular player, given particular

strategies) is well-defined, even if E( X ) is not. We can calculate

P( X ) > 0, for instance. And if S is the sum of a large sequence of

independent and identically distributed X's, then does P( S > 0 ) >=

P( S < 0 ) for every strategy your opponent can use imply your

strategy is optimal? If so, I believe it is possible to find such

strategies without requiring E( X ) to exist. I'm not entirely sure

what a good definition of optimality is. "S is a martingale or

submartingale" might work, too.

And as you note, this restriction only applies to money games with an

unlimited cube. Another way to avoid the problem is to calculate not

the money amount, but the (logarithmic) utility function of that

amount of cash -- note that E( X ) is not defined, but E( log( X ) )

_is_.

> 2. Backgammon is not guaranteed to terminate. In theory, there could be

> positions in which there is a positive probability that the game never

> terminates (because the players keep hitting each other, and the pieces

> recycle). Our experience tells us that this is not the case, but it

> remains to be proved.

I don't believe that this matters. For a game to be infinitely long, it

must have repeat the same position (since there are a finite number of

positions). I assert that from every legal position, there is a non-zero

probability of reaching a terminal position, no matter what strategies the

players apply. So, the probability of a position later repeating itself

in the same game is strictly less than one; the probability of a game

repeating through n iterations of the same position then becomes

monotonically decreasing on n and the probability of an infinitely long

game becomes arbitrarily small.

> 4. If the convergence problem is solved, there's still the problem of

> solving the equations in the first place. In general, solving a system

> of equations in N variables takes O(N^2) time. This means that

> estimates for when we might be able to solve backgammon completely,

> based on the number of positions, might vastly underestimate the work

> required. If we have to perform work proportional to the square of the

> number of positions, that's a much bigger problem.

This is true in the worst case. The lower bound on time taken to

solve the equations would be a very sparse matrix (each row has 21

elements, one for each dice roll; the remaining columns are zero)

making the original assumption that the partial ordering exists and

the "best moves" are known. For very sparse matrices, Gaussian

elimination takes linear time. The quadratic worst case applies if

the matrix is dense. In reality the complexity will be somewhere in

between.

> 5. Solving the game by computing a value for every position implies that

> we use memory proportional to the number of positions. Even if

> computers become fast enough to solve the equations, they may well not

> have that much memory.

I'm pretty sure the computation is "worse" than the memory required;

if memory density is assumed to increase at the same rate then in 48

years we expect the same 2^32 factor in storage space. If a typical

contemporary computer is assumed to have 2^40 bits of memory, then we

expect 2^72 by then; we also assume 10^18 positions which is roughly

2^60 so we still have 2^72 / 2^60 = 2^12 = 4096 bits of memory per

position.

> In summary, I'd say that all of these problems can potentially be

> overcome or addressed, but solving backgammon seems to involve a lot

> more than just waiting for computers a million times faster than what we

> have now. There's also a lot of theoretical and practical progress that

> would have to be made.

True. I'm almost certain it can be done eventually. But in the meantime,

we'll still have a lot to argue about on r.g.b. ;-)

Jul 7, 1998, 3:00:00â€¯AM7/7/98

to

Gary Wong <ga...@cs.arizona.edu> writes:

> And as you note, this restriction only applies to money games with an

> unlimited cube. Another way to avoid the problem is to calculate not

> the money amount, but the (logarithmic) utility function of that

> amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> _is_.

> And as you note, this restriction only applies to money games with an

> unlimited cube. Another way to avoid the problem is to calculate not

> the money amount, but the (logarithmic) utility function of that

> amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> _is_.

Sure, you might solve some different problem. But this won't give you

anything resembling "optimal" play (aka "best strategy"), which was the

original goal.

If you play to maximize the logarithm of your winnings, and I play to

maximize my actual winnings, you are going to lose a *lot* of money to

me, until you wise up.

> I assert that from every legal position, there is a non-zero

> probability of reaching a terminal position, no matter what strategies

> the players apply.

Great, I look forward to seeing your proof. Please post it here.

> For very sparse matrices, Gaussian elimination takes linear time. The

> quadratic worst case applies if the matrix is dense.

This is just wrong. Gaussian elimination on dense matrices takes O(N^3)

time. Solving sparse systems of linear equations (which doesn't use

Gaussian elimination, but other techniques suited to sparse matrices)

takes O(N^2) time. As I said.

David desJardins

Jul 7, 1998, 3:00:00â€¯AM7/7/98

to

Gary Wong <ga...@cs.arizona.edu> writes:

> This is true. However, it's not clear that this implies that a "best

> strategy" does not exist. I can demonstrate that the correct

> behaviour is a double/take in Paul Tanenbaum's position for instance,

> without requiring the expected equity to be defined.

> This is true. However, it's not clear that this implies that a "best

> strategy" does not exist. I can demonstrate that the correct

> behaviour is a double/take in Paul Tanenbaum's position for instance,

> without requiring the expected equity to be defined.

I frankly think you are wrong. I'd very much like to see your rigorous

definition of "correct behavior" and rigorous proof of its application

to positions with undefined equity.

If your argument starts with "let the value of the position be X", then

it's completely bogus, because the position doesn't have a value. I

don't understand how you are going to define "correct behavior" except

as "move to the position with the highest equity; this definition won't

work except for positions which have a defined equity.

David desJardins

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

In article <vohww9p...@bosco.berkeley.edu>,

David desJardins <da...@desjardins.org> wrote:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > And as you note, this restriction only applies to money games with an

> > unlimited cube. Another way to avoid the problem is to calculate not

> > the money amount, but the (logarithmic) utility function of that

> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> > _is_.

>

David desJardins <da...@desjardins.org> wrote:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > And as you note, this restriction only applies to money games with an

> > unlimited cube. Another way to avoid the problem is to calculate not

> > the money amount, but the (logarithmic) utility function of that

> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> > _is_.

>

> Sure, you might solve some different problem. But this won't give you

> anything resembling "optimal" play (aka "best strategy"), which was the

> original goal.

> anything resembling "optimal" play (aka "best strategy"), which was the

> original goal.

Well, this is not really true. The solution of the logarithmic equity

equations will result in a program that plays risk-averse backgammon,

to be sure, but it will play risk-averse backgammon very, very well.

Gary's point is that we can construct approximations to the ideal

strategy that represent practical solutions. If you don't like Gary's

suggestion because it is too risk-averse, we can change it. For example,

use linear utility until the cube hits 64, then switch to an appropriately-

scaled logarithmic utility.

My reservation about Gary's proposal is that it changes the problem

into one requiring a lot more space. The original problem required just

3 cube locations for every checker position. Gary's proposal requires

unbounded space, since the logarithmic utility function doesn't scale

linearly. (That is, you cannot compute the utility of owning a 16-cube

based upon knowing the utility of owning a 2-cube.)

The ideal approximation will involve storing just 3 cube positions per

checker position.

> If you play to maximize the logarithm of your winnings, and I play to

> maximize my actual winnings, you are going to lose a *lot* of money to

> me, until you wise up.

I agree that a practical "solution" to backgammon must approach the

ideal behavior as closely as possible.

The key is to limit approximations to the smallest degree necessary. You

will need to construct an approximation that deals with undefined equity

as tightly as possible. It is a challenging problem simply to identify

positions that have undefined equity. A second challenging problem is to

define a reasonable approximation.

Note that I don't care about theoretical soundness as much as

practical effectiveness. A theoretical proof that says "No ideal moves

exist in backgammon" is completely worthless even if it is completely true.

Every opponent has a model of the game which is an approximation to the

ideal. The appropriate goal is to create an approximation that has

practical value.

> > I assert that from every legal position, there is a non-zero

> > probability of reaching a terminal position, no matter what strategies

> > the players apply.

>

> Great, I look forward to seeing your proof. Please post it here.

It seems to me that Gary has already done so, David, at least with respect

to the requirements of this problem. Gary pointed out that when a move

sequence revisits a position we obtain closure on the equations that

define equity. Since there are a finite number of positions, every

sufficiently long move sequence must eventually revisit a position.

Also, please note that the system of equations depends only on one-move

of lookahead. If a cycle occurs in one move (that is, after our move

the opponent faces the exact same position that we had before our move),

then the equation is no more complicated than if it doesn't.

On balance, it seems to me that the possibility of arbitrarily long games

poses no theoretical difficulty.

> > For very sparse matrices, Gaussian elimination takes linear time. The

> > quadratic worst case applies if the matrix is dense.

>

> This is just wrong. Gaussian elimination on dense matrices takes O(N^3)

> time. Solving sparse systems of linear equations (which doesn't use

> Gaussian elimination, but other techniques suited to sparse matrices)

> takes O(N^2) time. As I said.

Good point.

In the context of solving the equations of a game, we also have to deal

with the minimax problem, which is the problem of finding the best move.

Specifically: the transition probabilities for a given position are not

known until we know which move we will select for each roll, but we don't

know the move until we have solved the equations.

The minimax problem has a far more greater impact on the running time of

the algorithm than the equation-solving part. Let's look at why, under

the assumption that we have somehow dealt with the "undefined equity"

problem.

When we start our solution we have no knowledge of how to make good moves,

so the program initially moves arbitrarily. The first iteration of the

solution will establish some values, but it will turn out that many of

the moves we made to establish those values were bad, so the values

themselves aare bad. We have to solve again.

On the second iteration, the situation will improve because we have

correct equities for any position in which the program played best moves

for all possible continuations. Of course, after just one iteration that

is probably a vanishingly small fraction of all positions, but the beauty

of the algorithm is that subsequent iterations will never change those values.

So we iterate and iterate until the values converge. Each iteration involves

a solution of the system of sparse equations mentioned by Gary and David.

Each iteration plays at least as well as the previous.

Convergence is assured under the assumption that ideal play exists, which

is equivalent to the assumption that every position has a well-defined

equity. But the number of iterations before convergence is anybody's guess.

Brian Sheppard

-----== Posted via Deja News, The Leader in Internet Discussion ==-----

http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

In article <vohvhp9...@bosco.berkeley.edu>,

> > This is true. However, it's not clear that this implies that a "best

> > strategy" does not exist. I can demonstrate that the correct

> > behaviour is a double/take in Paul Tanenbaum's position for instance,

> > without requiring the expected equity to be defined.

>

> > strategy" does not exist. I can demonstrate that the correct

> > behaviour is a double/take in Paul Tanenbaum's position for instance,

> > without requiring the expected equity to be defined.

>

> I frankly think you are wrong. I'd very much like to see your rigorous

> definition of "correct behavior" and rigorous proof of its application

> to positions with undefined equity.

>

> If your argument starts with "let the value of the position be X", then

> it's completely bogus, because the position doesn't have a value. I

> don't understand how you are going to define "correct behavior" except

> as "move to the position with the highest equity; this definition won't

> work except for positions which have a defined equity.

> definition of "correct behavior" and rigorous proof of its application

> to positions with undefined equity.

>

> If your argument starts with "let the value of the position be X", then

> it's completely bogus, because the position doesn't have a value. I

> don't understand how you are going to define "correct behavior" except

> as "move to the position with the highest equity; this definition won't

> work except for positions which have a defined equity.

This is a good question.

Gary assumed that the hold-cube-forever strategy cannot be better than

the reserve-the-right-to-double strategy. Possibly that is invalid in

the undefined equity situation. But it is hard to see how reserving the

right to double can be worse than keeping the right to double. Anyway,

here is the outline of Gary's proof.

We will show that doubling is better for the first player by showing

that doubling works out better than no-double even if we use the

take-and-hold strategy after we are redoubled. (Details omitted; the

arithmetic is easy.)

Then we show that taking is better, using the strategy of take-and-hold if

we redouble and are then reredoubled.

I admit that Paul Tanenbaum's position put me into a state of "cognitive

dissonance." (If you didn't major in psychology: "I couldn't tell which

way is up.") I suspect that the final word hasn't been spoken on this

subject. I am very interested in hearing your viewpoint, David.

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

I just have a few (amateurish) thoughts before I go

back to lurking.

back to lurking.

1. If I told you I had solved the game of *cubeless*

backgammon, that is, I had a function that returned

the exact cubeless equity for any position,

how hard would it be to solve backgammon with the cube?

2. A method for solving cubeless backgammon: Can you

start from the end and work backwards? I.e. generate

all terminating nodes in the mini-max tree (positions

in which X has 15 checkers borne off and O does not).

Then for each end position, generate all possible nodes

that can lead to that position, and building on what

you already know, define an equity for these positions,

continue looking backwards, etc. etc.

Or would that only work for non-contact positions?

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

I forgot to clarify the [*]:

[*] I didn't feel like calculating a more reasonable upper bound, but clearly

10,000 is a very crude upper bound on the number of 2-4 rolls necessary.

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

In article <vohpvfl...@bosco.berkeley.edu> David desJardins <de...@math.berkeley.edu> writes:

>BOSCH Holger <bo...@CUI.UNIGE.CH> writes:

>> I have seen the posting about the "future of backgammon", and I have a

>> related and maybe more fundamental question: I wonder if there exists

>> a best strategy in Backgammon, i.e. a strategy that is better than any

>> other strategy.

>There are several problems, some of which you have identified:

>1. [...]

>2. Backgammon is not guaranteed to terminate. In theory, there could be

>positions in which there is a positive probability that the game never

>terminates (because the players keep hitting each other, and the pieces

>recycle). Our experience tells us that this is not the case, but it

>remains to be proved.

The sequence of dice rolls in which each player rolls 2-4 10,000 [*] times in

succession will terminate almost all legal initial backgammon positions. For

those initial positions in which both players start with both men on the bar

with each player also having at least 2 men on each of his 2 and 4 pts., we

can give player 1 dice rolls which force him off one of these pts. and then

give both players 2-4 10,000 [*] times in succession. This will terminate any

backgammon position.

Thus there is a zero probability that the game never terminates. So this

solves problem #2.

I can't take credit for this (outline of a) proof. It was discovered and

written on r.g.b. in 1994(?) by C. [Curt?] McMullen (c...@maize.berkeley.edu].

Chris

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

David desJardins <de...@math.berkeley.edu> writes:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > And as you note, this restriction only applies to money games with an

> > unlimited cube. Another way to avoid the problem is to calculate not

> > the money amount, but the (logarithmic) utility function of that

> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> > _is_.

>

> Gary Wong <ga...@cs.arizona.edu> writes:

> > And as you note, this restriction only applies to money games with an

> > unlimited cube. Another way to avoid the problem is to calculate not

> > the money amount, but the (logarithmic) utility function of that

> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )

> > _is_.

>

> Sure, you might solve some different problem. But this won't give you

> anything resembling "optimal" play (aka "best strategy"), which was the

> original goal.

> anything resembling "optimal" play (aka "best strategy"), which was the

> original goal.

Well, I'm only proposing the maximal utility as an interesting problem we

can attempt to solve. The problem "show me a strategy that maximises E(X)" is

not interesting, the answer is "you can't, E(X) isn't defined for all possible

strategies". Several other propositions (such as match play, and money

play with a cash limit) as you mentioned in your previous article are

valid and interesting problems too.

> If you play to maximize the logarithm of your winnings, and I play to

> maximize my actual winnings, you are going to lose a *lot* of money to

> me, until you wise up.

That's not true. Maximising one's GLOBAL utility is rational behaviour (and

some kind of "utility = log( dollars )" definition is reasonable). I am

not claiming "total utility = utility in game one + utility in game two";

that is clearly not true for nonlinear dollar/utility relations.

> > I assert that from every legal position, there is a non-zero

> > probability of reaching a terminal position, no matter what strategies

> > the players apply.

>

> Great, I look forward to seeing your proof. Please post it here.

OK, here's an informal proof. Assume the contradiction is true (ie. that

there exists a position p from which the probability of finishing the game

in finite time is zero). Note that every position has at least one legal

move by at least one player to another position (the position where neither

player has a possible move, ie. both on the bar against closed boards, cannot

be reached through legal play). Since there are a finite number of

positions, and we assumed the probability of finishing the game from this

position is zero, the only way for this game to continue indefinitely is

for it to repeat this same position again at some point in the future -- with

probability one. Since we established above that there must be at least one

possible move from every legal position, that must mean that all _subsequent_

positions must lead to the current position too, again with probability one.

But this is impossible -- from any legal position, I can show you a possible

sequence that results in an irreversible change in the game state (eg.

bearing a chequer off, or dumping more than one chequer onto the ace point).

This sequence can occur with probability greater than zero. The events

"irreversible change" and "repeat the same position" are clearly distinct.

"Irreversible change" has positive probability, and so "repeat the same

position" must have probability less than or equal to one less "irreversible

change" -- ie. less than one. But we saw that the assumption that such a

position p exists implies that the "repeat the same position" probability

_IS_ one. Therefore the original assumption is wrong, and no such

position p exists.

> > For very sparse matrices, Gaussian elimination takes linear time. The

> > quadratic worst case applies if the matrix is dense.

>

> This is just wrong. Gaussian elimination on dense matrices takes O(N^3)

> time. Solving sparse systems of linear equations (which doesn't use

> Gaussian elimination, but other techniques suited to sparse matrices)

> takes O(N^2) time. As I said.

I don't think we're being precise enough about what kind of matrices

we mean. We could claim that solving Ax = b takes no time at all, if

A is the identity matrix. If A has arbitrary elements along the

leading diagonal and zeroes everywhere else (and we know this to be

the case in advance), then solving the equation requires n divisions

for O(n) time. If we add a single element to every row above the

diagonal, then we require an additional multiplication and subtraction

for each row, which still leaves us in O(n) time. The sparse matrix

I'm talking about will have up to 21 such non-zero elements and could

require 21 multiplications and subtractions before the division --

it's still only O(n) though. (We don't have to search for the 21

non-zero elements -- we already know where they are because we stored

that information when we generated the thing in the first place.) I

readily admit that it will be a problem coming up with such a matrix,

but once we have it, it can be solved in linear time. I don't mean to

claim that I can reduce any other kind of matrix in this time.

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

bshe...@my-dejanews.com writes:

> The key is to limit approximations to the smallest degree necessary. You

> will need to construct an approximation that deals with undefined equity

> as tightly as possible. It is a challenging problem simply to identify

> positions that have undefined equity. A second challenging problem is to

> define a reasonable approximation.

> The key is to limit approximations to the smallest degree necessary. You

> will need to construct an approximation that deals with undefined equity

> as tightly as possible. It is a challenging problem simply to identify

> positions that have undefined equity. A second challenging problem is to

> define a reasonable approximation.

The main thing that concerns me is that given that positions that have

clearly undefined equities exist, any position with a non-zero probability

of reaching one of those positions must also have undefined equity. To be

slightly more precise, here's a definition:

A position p is "troublesome" for a pair of players' strategies if the

probability of reaching the same board position p with the cube

greater by a factor of c is greater than or equal to 1/c, under those

strategies.

Paul Tanenbaum's position is troublesome if and only if both players'

strategies are "double/take", because then the same position will be

reached if both players dance (probability p = 25/36 x 25/36), and the

cube will be higher by a factor of c = 4 (being turned twice).

p > 1/c, so the position is troublesome.

But how do we go about calculating equities (and strategies) in positions

that could lead to troublesome positions? That's what I'm not sure about.

If, instead of maximising E(X) we are allowed to say that a strategy that

ensures P( S > 0 ) >= 0 (see older article for definition of S) is "good"

or "optimal" or whatever, then I can do slightly better. Note that S

is the sum of two sequences: the winnings from games that included

troublesome positions S_t, and the winnings from games that don't,

S_u. We can calculate the probability of a troublesome position

being reached from the current position given a pair of strategies,

P(T). We can calculate the equity of the current position assuming

a troublesome position will not be reached, E(X|not T). We can

(almost -- see below) maximise S_u by maximising E(X|not T), and we

can maximise P( S_t > 0 ) by other means. Therefore, the total P( S > 0 )

should be maximised. I claim that this indicates something good about our

strategy, but I don't know what :-) I can't claim it's "optimal" without

a better understanding of what optimality _is_.

The main objection I have with the reasoning so far is that it assumes

the strategy is entirely "passive" towards T -- ie. we start playing

rationally, ignoring the possibility of troublesome positions until one

occurs, at which point we switch to our "maximise P( S_t > 0 )" plan.

It does _not_ allow for discrimination between positions with different

P(T)s. If the optimal (whatever that means) backgammon strategy

happens to be one where positions with high or low P(T) are deliberately

sought after, then that strategy lies outside the set of strategies

that can be evaluated in this manner.

Related questions: the player on roll in Tanenbaum's position has a

greater probability of winning. Is this an advantage? If so, is

it worth sacrificing equity for? How much? For instance, if you had

the choice of two plays: (a) has a higher probability of reaching

Tanenbaum's position with you on roll but a slightly lower equity

otherwise; (b) has a lower probability of reaching T but slightly

higher equity otherwise. Which play would you choose? If (b) can

be an "optimal" strategy, then the set of strategies above (P( S > 0 ))

do include optimal strategies. If optimal strategies always answer

(a) or "it depends", then we need a better definition.

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

> > This is true. However, it's not clear that this implies that a "best

> > strategy" does not exist. I can demonstrate that the correct

> > behaviour is a double/take in Paul Tanenbaum's position for instance,

> > without requiring the expected equity to be defined.

>

> > strategy" does not exist. I can demonstrate that the correct

> > behaviour is a double/take in Paul Tanenbaum's position for instance,

> > without requiring the expected equity to be defined.

>

> I frankly think you are wrong. I'd very much like to see your rigorous

> definition of "correct behavior" and rigorous proof of its application

> to positions with undefined equity.

> definition of "correct behavior" and rigorous proof of its application

> to positions with undefined equity.

Brian Sheppard already answered most of this (thanks Brian -- you have a

great memory, I had to go to Deja News to remember most of this stuff :-)

but for completeness, here it is. I don't claim it's rigorous, but you're

welcome to prove or disprove any of it.

Assume the first player to roll a 6 wins and there are no gammon

possibilities. (You could estimate gammons and losses if you like, the

numbers would change a bit.)

First of all, is it a take or a drop? Assume your opponent offers you a

2-cube (the results generalise to any value) -- if you drop your equity

is well-defined, it's -1. If you take, then you can guarantee yourself

at least -0.36 points simply by taking the cube and then forgetting

about it until you can cash -- you lose 59% of the games with a 2 cube

for -1.18, but win 41% at 2 for 0.82 for total equity -0.36. So you

clearly lose less by taking.

Now, is it a double? Assume the cube is centred. The cube is worthless

to you if you enter (we've assumed you win regardless of whether you

own the cube). Since the cube is centred, your opponent can already

double so you're not giving them any additional recube vig by doubling

now. Therefore, you have nothing to lose by doubling; you also have

something to gain because you are a slight favourite with cubeless

equity 0.18. So I believe it _is_ correct to double (and take) here.

Is the situation any different for a redouble? In this case you might be a

little more reluctant to give your opponent the cube because you're giving

them the chance to double they wouldn't otherwise have had. However, I don't

believe this makes any difference; the cube will still die if you don't double

now. Since it was a correct initial double, we know we'd prefer to have our

opponent holding a live doubled cube than a dead one in any position; this

makes it a correct redouble too.

Brian questions whether it could be correct to hold onto the cube and

double later. I don't believe this strategy can be correct -- the key

is that you will be faced with _exactly the same position_ every move

from now until when somebody enters (when they are assumed to become

massive favourites to win; if your opponent enters you obviously no

longer want to double, and if you enter then you've lost your market

by a long way). The only thing that can change between this turn and

your next turn (assuming nobody enters) is the value of the cube,

which makes utterly no difference to your doubling strategy in an

unlimited money game (it might make a difference in a match game of

course, or in a money game if the value of the cube starts approaching

the cash in your pocket, but that's a different story). Therefore, if

it will be correct to double next turn, it is also correct to double

this turn. Your market cannot possibly improve under these conditions

but can get worse (if somebody enters), and so if it is correct to

double at all, it's correct to double now.

Is this conjecture true? I believe it is. I would be keen to see any

proof or disproof if you have any ideas for attacking the problem in

another way. In fact I would very much _like_ to see it proven wrong,

because such a disproof (ie. that double/take is not correct behaviour)

would imply that troublesome positions cannot exist under an optimal

strategy, which simplifies our search for an optimal strategy

enormously :-) But personally I believe the double/take is correct.

If I were playing for money and the position came up, I would certainly

double/take until the cube got so high I was unwilling to risk that

amount of cash; at that point I would be willing to either offer or

accept a cash settlement for around 15% of the cube value. This

strategy may not be optimal, but it's good enough for me.

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

Gary Wong <ga...@cs.arizona.edu> writes:

> > > I assert that from every legal position, there is a non-zero

> > > probability of reaching a terminal position, no matter what strategies

> > > the players apply.

> >

> [desJardins remarks:]> > > I assert that from every legal position, there is a non-zero

> > > probability of reaching a terminal position, no matter what strategies

> > > the players apply.

> >

> > Great, I look forward to seeing your proof. Please post it here.

>

> ...

> But this is impossible -- from any legal position, I can show you a possible

> sequence that results in an irreversible change in the game state (eg.

> bearing a chequer off, or dumping more than one chequer onto the ace point).

> This sequence can occur with probability greater than zero.

This is where your proof falls apart. Certainly there are legal moves

that would result in an irreversible change of state, but these moves

might NOT occur with probability greater than zero, because the players

might choose to make other moves given those rolls.

In effect, what you are trying to prove is that "backgammon to lose", i.e.

you "win" if the OTHER player bears off his last checker, has a non-zero

chance of terminating under optimal play. I.e., can two players who are

TRYING to keep the game going forever, always do so?

I saw another posting elsewhere in this thread that claims somebody did

solve this problem (the proof involved a large number of "2-4" rolls),

but he didn't include enough details to convince me and I haven't yet

tried chasing down his reference on DejaNews.

-- Don.

-------------------------------------------------------------------------------

--

-- Don Woods (d...@clari.net) ClariNet provides on-line news.

-- http://www.clari.net/~don I provide personal opinions.

--

Jul 8, 1998, 3:00:00â€¯AM7/8/98

to

Don Woods <d...@clari.net> writes:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > > > I assert that from every legal position, there is a non-zero

> > > > probability of reaching a terminal position, no matter what strategies

> > > > the players apply.

> > >

> > [desJardins remarks:]> Gary Wong <ga...@cs.arizona.edu> writes:

> > > > I assert that from every legal position, there is a non-zero

> > > > probability of reaching a terminal position, no matter what strategies

> > > > the players apply.

> > >

> > > Great, I look forward to seeing your proof. Please post it here.

> >

> > ...

> > But this is impossible -- from any legal position, I can show you a possible

> > sequence that results in an irreversible change in the game state (eg.

> > bearing a chequer off, or dumping more than one chequer onto the ace point).

> > This sequence can occur with probability greater than zero.

>

> This is where your proof falls apart. Certainly there are legal moves

> that would result in an irreversible change of state, but these moves

> might NOT occur with probability greater than zero, because the players

> might choose to make other moves given those rolls.

> that would result in an irreversible change of state, but these moves

> might NOT occur with probability greater than zero, because the players

> might choose to make other moves given those rolls.

Admittedly I didn't demonstrate that this was impossible. I should have

quoted a stronger result that there are sequences of dice rolls that

_must_ result in an irreversible change of state no matter how they are

played.

> In effect, what you are trying to prove is that "backgammon to lose", i.e.

> you "win" if the OTHER player bears off his last checker, has a non-zero

> chance of terminating under optimal play. I.e., can two players who are

> TRYING to keep the game going forever, always do so?

No, not if they roll certain sequences.

> I saw another posting elsewhere in this thread that claims somebody did

> solve this problem (the proof involved a large number of "2-4" rolls),

> but he didn't include enough details to convince me and I haven't yet

> tried chasing down his reference on DejaNews.

The key is that _odd_ points for me (my 1, 3, 5... etc.) are _even_ points

for you (24, 22, 20...). If I only roll even numbers, I enter from the bar

onto odd numbered points. If you only roll even numbers, you enter from

the bar onto (my) _even_ numbered points. The only way positions can

recur is if a blot is hit (otherwise, the pip counts are monotonically

decreasing and so trivially acyclic). If blots entering from the bar

always end up on odd/even points, and only even numbers are rolled

subsequently, then you can see that none of my recirculated blots can

ever contact any of your recirculated blots. Eventually I'm going to have

to dump multiple chequers onto my ace point (which is one of the odd points

my recirculated blots will be restricted to), or bear off. Once my ace

point is made, dumping multiple chequers onto my 3 point becomes irreversible,

too, and so on. There are a finite number of pips made up of my chequers

on my even points, so I can't keep moving them forever to delay the

inevitable -- eventually they'll end up on my 2 point, or be hit and

recirculated onto an odd point. The objection about making the 2, 4 and 6

points to prevent chequers from entering was addressed in another article

(you can't hold your board forever; if _both_ players are on the bar against

made 2, 4 and 6 points then give one player odd numbers until he's entered

and then wait for his board to crunch).

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

In article <6o08rr$dh9$1...@nnrp1.dejanews.com>,

my_...@hotmail.com wrote:

> 1. If I told you I had solved the game of *cubeless*

> backgammon, that is, I had a function that returned

> the exact cubeless equity for any position,

> how hard would it be to solve backgammon with the cube?

my_...@hotmail.com wrote:

> 1. If I told you I had solved the game of *cubeless*

> backgammon, that is, I had a function that returned

> the exact cubeless equity for any position,

> how hard would it be to solve backgammon with the cube?

The ideal answer is that there are 3 times as many positions in money

games using the cube as in money games cubeless. The positions have the

same checker positions with 3 possible cube locations for each.

That answer is complicated by the observation that cube-using positions

may not have well-defined equities. (The classic example is "Tanenbaum's

Position," in which each side has a man on the bar against a 5-point

board, with an opponent's blot on the 6 point. Each side also has a

plethora of outfield blots.)

The equity of positions like Tanenbaum's depends on how much money each

player is willing to lose, which means that the exact level of the cube

is important. And this is a problem because there are an infinitude of

possible levels.

So the answer is that somewhere between 3 times and infinitely many times

as much space is required. (I'm happy to have narrowed this down for you.)

My instinct is that there are really excellent approximations to cube-using

play that use only 3 times as much space.

> 2. A method for solving cubeless backgammon: Can you

> start from the end and work backwards? I.e. generate

> all terminating nodes in the mini-max tree (positions

> in which X has 15 checkers borne off and O does not).

> Then for each end position, generate all possible nodes

> that can lead to that position, and building on what

> you already know, define an equity for these positions,

> continue looking backwards, etc. etc.

>

> Or would that only work for non-contact positions?

The method you describe depends on establishing a "partial ordering" among

backgammon positions. That is, we need to order all backgammon positions

such that all successors of any position occur before the position does.

If we have such an ordering then we can solve backgammon by computing

equities until an equity is assigned to the initial position.

Unfortunately, a partial ordering of backgammon positions does not exist,

because it is possible for a position to lead to itself a few rolls down

the road. More complicated problems occur when you have 2 positions such

that A leads to B and B leads to A.

Other posts describe how equities can be computed in spaces that do not

have a partial ordering. There are four parts to the computation. First you

guess what the best moves are for every roll. Second, you set up transition

equations for every position on the assumption that the moves you think

are best really are best. Third, you solve the equations. Finally, you

check to see if all of your selected moves really are best, and if not you

repeat the process. Termination is guaranteed eventually.

Brian Sheppard

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

In article <wt4swst...@brigantine.CS.Arizona.EDU>,

Gary Wong <ga...@cs.arizona.edu> wrote:

> bshe...@my-dejanews.com writes:

> > The key is to limit approximations to the smallest degree necessary. You

> > will need to construct an approximation that deals with undefined equity

> > as tightly as possible. It is a challenging problem simply to identify

> > positions that have undefined equity. A second challenging problem is to

> > define a reasonable approximation.

>

Gary Wong <ga...@cs.arizona.edu> wrote:

> bshe...@my-dejanews.com writes:

> > The key is to limit approximations to the smallest degree necessary. You

> > will need to construct an approximation that deals with undefined equity

> > as tightly as possible. It is a challenging problem simply to identify

> > positions that have undefined equity. A second challenging problem is to

> > define a reasonable approximation.

>

> The main thing that concerns me is that given that positions that have

> clearly undefined equities exist, any position with a non-zero probability

> of reaching one of those positions must also have undefined equity. To be

> slightly more precise, here's a definition:

> clearly undefined equities exist, any position with a non-zero probability

> of reaching one of those positions must also have undefined equity. To be

> slightly more precise, here's a definition:

Thank you, Gary, for your insights into how we can handle troublesome

positions.

I propose solving the cubeless game, which has the virtue of having

1/3 of the number of positions as the cube-using game. (Happily, we can

solve the cubeless game after only 46 years of technological progress,

rather than 48!) The cubeless game also has no troublesome positions.

The we can use a search engine to solve the cube-handling problem.

In 46 years, we should be able to look ahead about 6 ply, so the cube-

handling consequences of moves should be apparent. Alternatively, we

can do full-game rollouts at a rate of about 1,600,000,000 games per second.

(Assuming the rate of CPU speed improvements slows to only a doubling

every 2 years.)

Brian Sheppard

BTW: I am only partly serious about this post. After all, if we had that

much CPU power we could solve much bigger problems than backgammon!

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

Brian Shppard <bshe...@my-dejanews.com> writes:

> Convergence is assured under the assumption that ideal play exists, which

> is equivalent to the assumption that every position has a well-defined

> equity.

> Convergence is assured under the assumption that ideal play exists, which

> is equivalent to the assumption that every position has a well-defined

> equity.

This blanket statement needs a proof to support it. It's not obvious

that this process (choose a move in each position, solve for the

equities, then if they suggest a better move use that as the new move,

and repeat) will converge to a "best move" in each position. If you

want to claim that it does for backgammon, then you have to prove that.

In any case, it's not a very practical algorithm, either, especially as

long as the solving requires time proportional to the square of the

number of positions.

David desJardins

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

Gary Wong <ga...@cs.arizona.edu> writes:

> If we add a single element to every row above the diagonal, then we

> require an additional multiplication and subtraction for each row,

> which still leaves us in O(n) time.

> If we add a single element to every row above the diagonal, then we

> require an additional multiplication and subtraction for each row,

> which still leaves us in O(n) time.

Putting every nonzero element of the matrix on or above the diagonal

corresponds to imposing a total order on backgammon positions, and

guaranteeing that from a given position you only move to positions which

succeed it in that total order. We all know that's not possible for

backgammon, because positions can repeat.

In the backgammon transition matrix, there will be entries both above

and below the diagonal.

> The sparse matrix I'm talking about will have up to 21 such non-zero

> elements and could require 21 multiplications and subtractions before

> the division -- it's still only O(n) though. (We don't have to search

> for the 21 non-zero elements -- we already know where they are because

> we stored that information when we generated the thing in the first

> place.) I readily admit that it will be a problem coming up with such

> a matrix, but once we have it, it can be solved in linear time.

You seem to be claiming that you can solve arbitrary systems of linear

equations in N variables, with at most 21 terms in each equation, in

O(N) time. If true that would be a revolutionary breakthrough. I hope

that you will explain how to do this.

David desJardins

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

David desJardins <de...@math.berkeley.edu> writes:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > If we add a single element to every row above the diagonal, then we

> > require an additional multiplication and subtraction for each row,

> > which still leaves us in O(n) time.

>

> Gary Wong <ga...@cs.arizona.edu> writes:

> > If we add a single element to every row above the diagonal, then we

> > require an additional multiplication and subtraction for each row,

> > which still leaves us in O(n) time.

>

> Putting every nonzero element of the matrix on or above the diagonal

> corresponds to imposing a total order on backgammon positions,

> corresponds to imposing a total order on backgammon positions,

Exactly. This is all derived from the "...assume a partial ordering

exists..." from several articles ago, and leads directly to the

estimated 25,000 year solution time now/3 minute solution time in 2046

result. It can be interpreted as the expected time to calculate

an approximate equity of every position; time to calculate one iteration

of the convergence; a lower bound on the time to calculate a perfect

equity of each position; etc. etc.

> > The sparse matrix I'm talking about will have up to 21 such non-zero

> > elements and could require 21 multiplications and subtractions before

> > the division -- it's still only O(n) though. (We don't have to search

> > for the 21 non-zero elements -- we already know where they are because

> > we stored that information when we generated the thing in the first

> > place.) I readily admit that it will be a problem coming up with such

> > a matrix, but once we have it, it can be solved in linear time.

>

> You seem to be claiming that you can solve arbitrary systems of linear

> equations in N variables, with at most 21 terms in each equation, in

> O(N) time. If true that would be a revolutionary breakthrough. I hope

> that you will explain how to do this.

I never said I was solving _arbitrary_ systems. I can reduce sparse

(ie. a constant limit on the number of terms per row) upper triangular

matrices in linear time (because there are n rows; each row can be

reduced in constant time because there a constant number of elements

to eliminate).

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

Brian Sheppard <bshe...@my-dejanews.com> writes:

> I propose solving the cubeless game, which has the virtue of having

> 1/3 of the number of positions as the cube-using game. (Happily, we can

> solve the cubeless game after only 46 years of technological progress,

> rather than 48!)

> I propose solving the cubeless game, which has the virtue of having

> 1/3 of the number of positions as the cube-using game. (Happily, we can

> solve the cubeless game after only 46 years of technological progress,

> rather than 48!)

Once again: no, we can't. We don't have any method that will do this.

The straightforward methods (based on solving linear equations) require

around a billion billion times more work than that.

David desJardins

Jul 9, 1998, 3:00:00â€¯AM7/9/98

to

> > Exactly. This is all derived from the "...assume a partial ordering

> > exists..." from several articles ago, and leads directly to the

> > estimated 25,000 year solution time now/3 minute solution time in 2046

> > result.

>

> > exists..." from several articles ago, and leads directly to the

> > estimated 25,000 year solution time now/3 minute solution time in 2046

> > result.

>

> > I never said I was solving _arbitrary_ systems. I can reduce sparse

> > (ie. a constant limit on the number of terms per row) upper triangular

> > matrices in linear time ....> > (ie. a constant limit on the number of terms per row) upper triangular

>

> Why would we "assume" a partial ordering of the positions, when we know

> that backgammon positions aren't in fact so ordered? Are you saying

> that in the past several articles you've deliberately been assuming

> something contrary to fact, and then working out what the work would be

> under that false assumption?

In some sense yes, but I wouldn't word it like that. I clearly expressed

the assumption I was making, and derived a result that directly follows

from that assumption. The result is directly applicable to the model in

use, and approximately applicable to backgammon as far as that model

approximates backgammon. You can regard it as a lower bound or an

inequality if you like.

> What good is that? I thought the thread was supposed to be about

> determining the best strategy for backgammon. We can't do that if we

> start with false assumptions.

This thread seems to be about lots of things :-) I'd feel very reluctant

to claim that we're discussing determining the best strategy for backgammon

in anything other than a very abstract and hypothetical sense. Very little

of this is at all practical. Historically (as far as I know), every

non-trivial game that has been solved by computer (Connect Four, go-moku,

etc.) has been attacked with lots of Shannon C-type strategy and a little

bit of brute force. It would be unprecedented if backgammon were ever to be

solved by brute force alone. And by my reckoning, we have easily 4 decades

to think about intelligent solutions before we should even be allowed to

think about brute force again :-)

> It sounds like you now agree with what I've been saying all along:

> solving backgammon using any of the obvious methods takes at least time

> proportional to the square of the number of positions.

I don't see how you can reject my approximation as being based on false

assumptions, and then present another approximation that's equally invalid.

I'm not sure what assumptions you based the O(n^2) result on -- that every

position could potentially lead to every other position, I guess? Well,

that's just as bad as my assumption that a partial ordering exists. Your

result is a valid upper bound, just as mine is a valid lower bound. We

can refine these bounds by using models that more closely approximate

backgammon, for example:

Although there are around 10^18 positions, the majority of those include

at least one man borne off. These positions can clearly not lead to a

subsequent position where all men are in play. We can go further than

that, and partition the set of positions into 256 subsets, one for every

combination of numbers of chequers borne off by each player. It is clear

that a partial ordering _does_ exist between these sets, because a man borne

off cannot come back into play. All cyclic dependencies between positions

must take place within one of these subsets; the subsets themselves are

partially ordered. Other partitions are possible too (eg. number of men

over one on the ace point; number of men over one on the deuce point if

the ace point is made; contact vs. non-contact; etc.)

Furthermore, of the 10^18, a _huge_ majority will be exotic positions

that are extremely unlikely to arise through the optimal play we're

evaluating (a player has a man borne off yet still has many chequers

in the outfield; both players leaving huge numbers of blots exposed;

positions in which players abandon their 6 points long before contact

is broken; etc. etc.) Many of these can be heuristically evaluated to

be trivial double/drops (if you don't mind a heuristic approximation

-- if you want to be pure, you can still arrive at an early

double/drop result by computing enough of the pure subsequent

positions that the equity will be in the double/drop range regardless

of the partial equities of the remaining possibilities).

It's exceedingly difficult to be quantitative about any of this, but I

suspect these measures (and others like them I haven't mentioned, or

haven't thought of) save you a few orders of magnitude if you stay

pure, or several orders of magnitude if you take heuristic shortcuts.

Jul 10, 1998, 3:00:00â€¯AM7/10/98

to

Gary Wong <ga...@cs.arizona.edu> writes:

> This thread seems to be about lots of things :-) I'd feel very reluctant

> to claim that we're discussing determining the best strategy for backgammon

> in anything other than a very abstract and hypothetical sense.

> This thread seems to be about lots of things :-) I'd feel very reluctant

> to claim that we're discussing determining the best strategy for backgammon

> in anything other than a very abstract and hypothetical sense.

I certainly am. I won't claim what you are discussing, if you don't

claim what I'm discussing.

Several people seem to have read your postings and gone away with the

impression that "in 40 years we'll be able to solve backgammon exactly".

So I wasn't the only one who misunderstood what you wrote.

> Very little of this is at all practical.

That's your opinion. I see lots of "practical" applications (to the

extent that playing games is practical at all). For example, we could

solve smaller variants of backgammon (with fewer points and checkers) to

get insight into the real game. We could solve restricted backgammon

positions, such as those where one player has only one man left on the

board. Before devoting any significant computing power to that, we'd

want to try to find the best methods.

> I don't see how you can reject my approximation as being based on false

> assumptions, and then present another approximation that's equally invalid.

> I'm not sure what assumptions you based the O(n^2) result on -- that every

> position could potentially lead to every other position, I guess?

O(N^2) is the time that it takes to solve general sparse systems of

linear equations using the best known techniques. If every position

could lead to every other, then it would take more time---you can't

solve dense systems of linear equations in O(N^2) time.

You're certainly right that you can do better, for example by using

"blocking" of the equations (what you call a partial ordering of the

positions). A useful contribution would be to specify a real algorithm

and then try to get real estimates of the work. I don't think that's so

impractical as you do---for example, one can learn a lot by working on

toy problems.

David desJardins

Jul 11, 1998, 3:00:00â€¯AM7/11/98

to

David desJardins <de...@math.berkeley.edu> writes:

> Gary Wong <ga...@cs.arizona.edu> writes:

> > This thread seems to be about lots of things :-) I'd feel very reluctant

> > to claim that we're discussing determining the best strategy for backgammon

> > in anything other than a very abstract and hypothetical sense.

>

> Gary Wong <ga...@cs.arizona.edu> writes:

> > This thread seems to be about lots of things :-) I'd feel very reluctant

> > to claim that we're discussing determining the best strategy for backgammon

> > in anything other than a very abstract and hypothetical sense.

>

> I certainly am. I won't claim what you are discussing, if you don't

> claim what I'm discussing.

> claim what I'm discussing.

That's certainly fair :-) I think I'm discussing determining the best

strategy for backgammon in the same sense that I might discuss the

best approach for factoring a 2048 bit integer. I would say "25,000

years (or whatever) is the best we can do with current hardware: out

of the question. We expect to wait at least 40 years for future

hardware to provide the solution with current algorithms: better, but

we're still too impatient. Therefore, we reject both of those

approaches and try to be clever _now_." To be less than abstract and

hypothetical, we either need to find an algorithm with significantly

better performance than the best currently known, or prove that none

such exist. (Incidentally, doing either would require somebody far

cleverer than me, so at that point I give up and remain being abstract

and hypothetical :-)

> Several people seem to have read your postings and gone away with the

> impression that "in 40 years we'll be able to solve backgammon exactly".

> So I wasn't the only one who misunderstood what you wrote.

I reread my original article (wtg1gmu...@brigantine.CS.Arizona.EDU)

and that isn't quite what I said. There were three questions asked

("...will backgammon [eventually] be completely solved", "is it theoretically

possible [to solve]", and "is this likely to be achievable in my lifetime").

My responses were "very likely", "yes", and "perhaps".

I think the ambiguous part that caused confusion is the sentence:

"If we make a conservative assumption that the computer already has

some kind of partial ordering [...] then a contemporary computer would

require over 25,000 years." I should have been specific that this

assumption is conservative only for computing a _lower_ bound. When

considering it from the other point of view (ie. an upper bound) it

is a very _liberal_ (unjustified) assumption. Apologies for being vague

about that.

> > Very little of this is at all practical.

>

> That's your opinion. I see lots of "practical" applications (to the

> extent that playing games is practical at all). For example, we could

> solve smaller variants of backgammon (with fewer points and checkers) to

> get insight into the real game. We could solve restricted backgammon

> positions, such as those where one player has only one man left on the

> board.

That's very true. I believe Hugh Sconyers has already found the equities

of every position of backgammon where each player plays with 3 or less

chequers. I would be interested to know what the asymptotic performance

of his algorithm is -- given that it has terminated already, I guess that

it is significantly better than the O(n^2) upper bound on the number of

positions. There are going on 10 million legal positions with 3 chequers

each, so an O(n^2) approach would require well over 10^13 characteristic

operations. I claim this is beyond current capabilities (for moderately

complex operations, on moderately priced hardware, in a moderate length of

time). It also far exceeds the 3x10^9 operations to calculate the equities

of all positions where players have up to 15 chequers in their home boards

(which he has also solved). So his algorithm seems much better than O(n^2).

Unfortunately, we need it to be better than O(n) to solve the 15-chequer

problem any time soon (which is essentially equivalent to finding a general

backgammon solution that's a member of P with respect to the number of

chequers). Either that, or build a nondeterministic computer ;-)

> Before devoting any significant computing power to that, we'd want to

> try to find the best methods.

I couldn't agree more. Which is why I think it's pointless worrying about

whether a brute force approach is O(n) or O(n^2) or somewhere in between --

to be at all practical, we need to find an algorithm _better_ than O(n)

(or prove that none exists). We obviously can't calculate and store the

equity of every position in better than O(n) time and space (since there are

n positions, and we can't store one position without O(1) time and space),

but is there a way to find an optimal strategy _without_ all the equities?

That question's too hard for me, but I'm eager to listen if anybody else

has a good idea :-)

0 new messages