37 views

Skip to first unread message

Sep 23, 1992, 11:05:56 AM9/23/92

to

Here are my thoughts on this matter, which come more from philosophy than

from game theory. I operate on the assumption that from the initial position

neither side can force a win. This assumption may be mathematically unprovable

but neither can it be disproved, and moreover, I suspect that the vast

majority of chessmasters would agree with it based on personal experience.

(What's more, I suspect most chessmasters would reject the game theorists

idea that the starting position is (or could be) a win for Black as sheer

hogwash). Anyways, if the starting position represents a balance (a "draw"

from the perspective of game theorists), than it strikes me that the game

can only be won if someone disturbs the balance (ie, makes mistakes). So

long as the balance is held, who can say there is any theoretical upper

limit to the number of possibilities (actual moves plus the vast horizon

of possible variants). A machine which conducts a search for a win X number

of ply (whether 10 ply or a zillion) will never find it if the game is a

draw from the position where it begins its analysis (such as before move

one). However, when can the machine stop its analysis and declare the

position conclusively a draw? However many ply it goes, it finds the

position a draw, but how does it know it will not find the win by searching

one ply further? It will have to search to infinity. If it ever did

get to infinity (which by definition is impossible), could it then supply

us with "the solution" to chess in the form of the moves of the "ultimate

draw" or "ultimate game"? Or would it not provide us with an infinite

number of drawn games? One last thought comes out of this: since the

number of possibilities in a chess game is by this analysis infinite, the

computer will reach the end of them and thus never play "the" perfect

move. It may play well enough to hold the draw, but perhaps it will not

play well enough to never make mistakes. And so, even in its most

advanced state (which it will also never reach, because it will keep

improving to infinity), it may still lose.

Jerry Meyers

Sep 23, 1992, 12:46:09 PM9/23/92

to

I don't see what the problem is.

There are only a finite number of possible chess games.

Potentially, one could examine each one and determine

the possible outcomes. Whether there is or is not a

forced win for either side is theoretically computable.

There are only a finite number of possible chess games.

Potentially, one could examine each one and determine

the possible outcomes. Whether there is or is not a

forced win for either side is theoretically computable.

John.

Sep 23, 1992, 1:13:50 PM9/23/92

to

In article <cek8TIW2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes:

>

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory. I operate on the assumption that from the initial position

>neither side can force a win. This assumption may be mathematically unprovable

Well, I'm finally kicking in my .02 cents worth to this banal topic.>

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory. I operate on the assumption that from the initial position

>neither side can force a win. This assumption may be mathematically unprovable

Philosophy has nothing to do with game theory and there are not an infinite

amount of chess positions. There are 32 pieces and 64 squares, you figure.

To say it's solvable does not mean that one side must win; perhaps the game

is a draw. The general game theory idea is that chess is a FINITE game.

There exists only a FINITE number of legal postions. Perhaps at some point a

game can not move any further with perfect play, and then a draw by repitition

occur eventially, or one must make a mistake. Make sense?

If the game progresses farther and farther with nothing dynamic happening,

then at some point the position will repeat itself three times, a draw.

My .02 regarding the insipid topic of a God chess playing device. My

idea of a god and a perfect chess computer are quite different. A god should

by definition be omniniscient. This would mean that the god could quite

easily understand exactly what position needs to be reached to inspire the

opponent to fall in to a trap. This would be possible because the mortal

man, alas (or thank God), is NOT perfect and all-knowing. Since a perfect

chess computer could not set these traps, but only play "the solution" it

is plausible that the games would consist only of draws, wins or losses

depending on how the solution to chess pans out. Nobody can beat God, the

question is, how many pieces can he spot you...

My thanks to Mr. Fry for posting the Fischer/Spassky games. They

are much-appreciated.

Cheers and insert ;-) and :-) wherever you must to feel better.

-Michael "How Swede it is" Nyman

--

--------------------------------------------------------------------------------I know you believe you understand what you think I said, but I am not sure you

realise that what you read is not what I mean.

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

Sep 23, 1992, 3:45:53 PM9/23/92

to

John Eisenberg writes:

While this is true (in my experience statements from CSLI often are), it

might be more illuminating to consider the status quo. For persons playing

the game right now it might be smart to think of chess as a classic game

in the Neumann sense. That is, and depending on the understanding of your

own and your adversaries levels of skill, it might be smart to introduce

an element of randomness on those occasions when there is not a known

best move. The same thing goes for computer algorithms. They should learn

to learn the adversaries skill levels and gamesmanship and play accordingly.

Fido

Sep 23, 1992, 5:15:30 PM9/23/92

to

Fido writes:

>While this is true (in my experience statements from CSLI often are), it

>might be more illuminating to consider the status quo. For persons playing

>the game right now it might be smart to think of chess as a classic game

>in the Neumann sense. That is, and depending on the understanding of your

>own and your adversaries levels of skill, it might be smart to introduce

>an element of randomness on those occasions when there is not a known

>best move. The same thing goes for computer algorithms. They should learn

>to learn the adversaries skill levels and gamesmanship and play accordingly.

This can be very true. The "Best" move can be the wrong move in some situations.

Take the case where you time handicap speed chess. I play my 9 year old son this

way adding 30 seconds to the time I have each time I lose and taking away 30

seconds each time I win. When you must win in 1 minute, the slow steady correct

method simply will not work against him. Gambits, wild sacs, etc. are the order

of the day. I can't count the number of times I have lost where I had an

overwhealming position that I wasn't able to cash in on quickly enough. Sure a

trap might be incorrect and even losing if he realizes what is going on but the

odds of that happening are pretty slim.

Sure you say but that is speed chess and we are talking "real" chess. Then how

about when you get in a time scramble at the end of the game. The "correct" move

might be so complicated you don't have time to deal with the complications.

Better to take the simplifying move that ensures you getting to the next limit.

How about when you enter an ending you are 99% sure you can grind out to a win

instead of entering a variation that probably leads to a mate in a dozen moves

for you?

How about when you open d4 instead of e4 just to shock the bejeebers out of

your opponent since you have never played d4 in a tournament.

Sep 23, 1992, 8:33:11 PM9/23/92

to

In article 6958, John Eisenberg responds to my article ("Chess is not

solvable", article 6947) as follows:

>

>

>I don't see what the problem is.

>There are only a finite number of possible chess games.

>Potentially, one could examine each one and determine

>the possible outcomes. Whether there is or is not a

>forced win for either side is theoretically computable.

In article 6962, Nordic Man writes, in the same vein:

>

>The general game theory idea is that chess is a FINITE game. There exist

>only a finite number of legal positions.

These arguments do not prove to me that chess is solvable, because it seems

obvious that even if a computer had a list containing every possible chess

position, this would not, in and of itself, constitute a complete evaluation

of all the nuances (ie, possible continuations and their evaluations) of each

and every one of those positions. Nothing less than such a complete

evaluation would constitute, to my mind, the "solution" to chess. The

existence of such a list would not even, in and of itself, constitute

any kind of evaluation at all (even in the crude sense of saying whether

any one of the positions in the list is a win or a draw). The whole problem,

as I see it, comes with the evaluation process, which I think will take one

on an infinite loop, as I described in my previous post. The languages of

the world are also composed of a finite number of words, but linguists tell

us that the number of sentences (or expressions) is infinite. To say that

"potentially, one could examine each one (of the positions) and determine

the possible outcomes" is to say something more than 'there are a finite

number of positions'. Just what assumptions are involved in that statemene,

are not entirely clear.

Jerry Meyers

Sep 23, 1992, 11:21:23 PM9/23/92

to

In article <1992Sep23.1...@CS.ORST.EDU> nym...@prism.CS.ORST.EDU (The Nordic Man) writes:

<There exists only a FINITE number of legal postions. Perhaps at some point a

<game can not move any further with perfect play, and then a draw by repitition

<occur eventially, or one must make a mistake. Make sense?

<If the game progresses farther and farther with nothing dynamic happening,

<then at some point the position will repeat itself three times, a draw.

<There exists only a FINITE number of legal postions. Perhaps at some point a

<game can not move any further with perfect play, and then a draw by repitition

<occur eventially, or one must make a mistake. Make sense?

<If the game progresses farther and farther with nothing dynamic happening,

<then at some point the position will repeat itself three times, a draw.

For the record, threefold repetition and the fifty-move rule do not result

in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

Hence technically a chess game can go on forever, so the theorem that either

chess is a draw or one side can force a win does not apply.

--

Tim Chow tyc...@math.mit.edu

Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs

30 tons, computers in the future may have only 1,000 vacuum tubes and weigh

only 1 1/2 tons. ---Popular Mechanics, March 1949

Sep 23, 1992, 8:20:18 PM9/23/92

to

Teri A Meyers writes

> Anyways, if the starting position represents a balance (a "draw"

> from the perspective of game theorists), than it strikes me that the game

> can only be won if someone disturbs the balance (ie, makes mistakes).

It troubles me that you equate "disturbs the balance" with "makes mistakes".

There are many forms of balance. A key to the strategy of many chessplayers is to

upset the balance by making concessions in one area while strengthening the other

side. So while both players may be theoretically equal on the board, there is

still the possibility that one player can use his partial advantage in one area to

prove a win.

> However, when can the machine stop its analysis and declare the

> position conclusively a draw? However many ply it goes, it finds the

> position a draw, but how does it know it will not find the win by searching

> one ply further? It will have to search to infinity.

There are positions which are conclusively a draw. The simplest of these is King

vs. King. There is absolutely no way for either player to win this (sadly, most

computers don't recognize these types of draws -- many computers lose when they

are ahead materially but the position is a draw. The game is played, with the

computer avoiding three-time repetition, and eventually makes a worsening move,

thereby losing). There are also positions where the losing player forces a draw.

Any draw on the board (stalemate, for instance) can be considered the end point.

So infinite regression is not required.

> Jerry Meyers

Sep 23, 1992, 8:22:10 PM9/23/92

to

John Eisenberg writes

But this problem is most likely intractable. The number of possible games is so

very large that it would take a vast amount of time to compute.

Sep 23, 1992, 4:06:11 PM9/23/92

to

In article <cek8TIW2A...@pitt.edu> Teri A Meyers <tas...@pitt.edu> writes:

>

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory.

>

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory.

Game theory also comes from philosophy, but one that works.

> I operate on the assumption that from the initial position

>neither side can force a win.

No, no! That's not called philosophy, that's called religion. And what you

call 'assumption' is called a dogma. Philosophy must start from much more

general, abstract assumptions.

> This assumption may be mathematically unprovable

>but neither can it be disproved,

You are too religion-minded. This is not God we are discussing, it's a finite

human artefact, which can indeed be mathematically proved or disproved.

Your dogma might well be shown true (I bet it is!) but it must be shown, not

postulated.

> and moreover, I suspect that the vast

>majority of chessmasters would agree with it based on personal experience.

That's a well-known faulty argument. At one point vast majority of scholars

agreed that it was the Sun that orbited the Earth.

>(What's more, I suspect most chessmasters would reject the game theorists

>idea that the starting position is (or could be) a win for Black as sheer

>hogwash).

That is not an idea about chess. It is one of the three possibilities. The

idea of the theorem you are bashing is that those three are *only* possibi-

lities, which is quite profound regardless of how you feel about it.

>long as the balance is held, who can say there is any theoretical upper

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

>limit to the number of possibilities (actual moves plus the vast horizon

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

>of possible variants). A machine which conducts a search for a win X number

>of ply (whether 10 ply or a zillion) will never find it if the game is a

>draw from the position where it begins its analysis (such as before move

>one). However, when can the machine stop its analysis and declare the

>position conclusively a draw? However many ply it goes, it finds the

>position a draw, but how does it know it will not find the win by searching

>one ply further? It will have to search to infinity. If it ever did

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

>get to infinity (which by definition is impossible), could it then supply

>us with "the solution" to chess in the form of the moves of the "ultimate

>draw" or "ultimate game"? Or would it not provide us with an infinite

>number of drawn games? One last thought comes out of this: since the

>number of possibilities in a chess game is by this analysis infinite, the

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

>computer will reach the end of them and thus never play "the" perfect

>move. It may play well enough to hold the draw, but perhaps it will not

>play well enough to never make mistakes. And so, even in its most

>advanced state (which it will also never reach, because it will keep

>improving to infinity), it may still lose.

This is completely wrong. There is no infinity in chess. Number of positions

is finite. Number of ways to reach them is finite. Maximum length of the game

is finite (~5000 moves with both players cooperating, much less if they are

playing as opponents).

Sven

Sep 23, 1992, 9:51:10 PM9/23/92

to

There's a maximum length to a chess game, due to the 50-move rule. I think

it's something like 5000 moves. Technically, it's dependent on a player's

actually claiming the draw, but wouldn't even a computer claim the draw out of

sheer boredom? Anyway, there's no possibility of the computer losing the

game.

Rujith de Silva.

Carnegie-Mellon.

Sep 24, 1992, 8:40:19 AM9/24/92

to

In article <1992Sep24....@galois.mit.edu>, tyc...@riesz.mit.edu (Timothy Y. Chow) writes:

|> In article <1992Sep23.1...@CS.ORST.EDU> nym...@prism.CS.ORST.EDU (The Nordic Man) writes:

|> <There exists only a FINITE number of legal postions. Perhaps at some point a

|> <game can not move any further with perfect play, and then a draw by repitition

|> <occur eventially, or one must make a mistake. Make sense?

|> <If the game progresses farther and farther with nothing dynamic happening,

|> <then at some point the position will repeat itself three times, a draw.

|>

|> For the record, threefold repetition and the fifty-move rule do not result

|> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

|> Hence technically a chess game can go on forever, so the theorem that either

|> chess is a draw or one side can force a win does not apply.

|> In article <1992Sep23.1...@CS.ORST.EDU> nym...@prism.CS.ORST.EDU (The Nordic Man) writes:

|> <There exists only a FINITE number of legal postions. Perhaps at some point a

|> <game can not move any further with perfect play, and then a draw by repitition

|> <occur eventially, or one must make a mistake. Make sense?

|> <If the game progresses farther and farther with nothing dynamic happening,

|> <then at some point the position will repeat itself three times, a draw.

|>

|> For the record, threefold repetition and the fifty-move rule do not result

|> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

|> Hence technically a chess game can go on forever, so the theorem that either

|> chess is a draw or one side can force a win does not apply.

So under these rules, we will program the computer to always claim a

draw when a three-fold repetition or 50-move rule applies. Current

computer programs already do this, i.e. when there is Q + K vs. K, the

side with the material advantage can put the lone king in perpetual

check, but there are better moves that leads to checkmate. The

mythical, perfect computer would do the same thing, i.e. choose

forcing moves to lead to checkmate, and if there are none, be

satisfied with a draw rather than risk losing by making an inferior

move and hoping the opponent makes a bad move (this is the basic idea

behind the mini-max algorithm, i.e. minimizing your opponent's maximum

gain).

So under the USCF rules, a chess game with our mythical, perfect

computer *cannot* go on forever (because of the 50-move rule); the

theorem *does* applies; and chess *is* solvable.

|> --

|> Tim Chow tyc...@math.mit.edu

|> Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs

|> 30 tons, computers in the future may have only 1,000 vacuum tubes and weigh

|> only 1 1/2 tons. ---Popular Mechanics, March 1949

--

Cheong Yu | | (513) 865-7048

Mead Data Central | | Fax: (513) 865-1755

P.O. Box 933 | | k...@meaddata.com

Dayton, Ohio 45401 | | uunet!meaddata!kcy

Sep 24, 1992, 11:58:05 AM9/24/92

to

1. the game of chess *IS* solvable. That is, from the opening move, either

white wins, black wins (unlikely) or the perfect game is a draw. As a

scientist, I would call this "theoretically solvable" because, given a

fast enough computer it can be done..... The reason is that the game of

chess has a finite number of possible moves before a draw occurs, so one

side must either win or eventually reach a draw (50 move rule.)

2. Computers will never brute-force solve the game. Therefore, they will

*never* solve it. Searching partial trees won't cut it as you also eliminate

many paths that might disturb the final results. The biggest problem to

overcome are laws of physics that strictly limit the speed at which a computer

can operate and the physical size of the computer further limits it's speed.

To keep everyone happy, let me modify this to say "computers based on the

current technological level will never solve the game". This gives me an

out if if someone one day figures out how to quarks or whatever to make a

working circuit. Then the laws change a little.

3. The starting position is *not* equal. White has a distinct advantage in

that he is on move. Once white mates black, black can't respond and mate

white and "restore" the balance. Because of this, that tempo is worth some-

thing (unless the poster who mentioned zugszwang for white on the starting

board is correct.....)

Bob Hyatt

By the way, I think that the world champion is safe for several more years,

but he will eventually fall to a computer - and may even fall to a microcomputer

of the 21st century if they continue to improve. However, the game of chess

is safe.... we will never know if e4 wins or if g4 loses, etc.

--

!Robert Hyatt Computer and Information Sciences !

!hy...@cis.uab.edu University of Alabama at Birmingham !

Sep 24, 1992, 4:04:30 PM9/24/92

to

In article <4ekEn7i2A...@pitt.edu> Teri A Meyers <tas...@pitt.edu> writes:

>

>These arguments do not prove to me that chess is solvable, because it seems

>obvious that even if a computer had a list containing every possible chess

>position, this would not, in and of itself, constitute a complete evaluation

>of all the nuances (ie, possible continuations and their evaluations) of each

>and every one of those positions. Nothing less than such a complete

>evaluation would constitute, to my mind, the "solution" to chess. The

>existence of such a list would not even, in and of itself, constitute

>any kind of evaluation at all (even in the crude sense of saying whether

>any one of the positions in the list is a win or a draw).

>

>These arguments do not prove to me that chess is solvable, because it seems

>obvious that even if a computer had a list containing every possible chess

>position, this would not, in and of itself, constitute a complete evaluation

>of all the nuances (ie, possible continuations and their evaluations) of each

>and every one of those positions. Nothing less than such a complete

>evaluation would constitute, to my mind, the "solution" to chess. The

>existence of such a list would not even, in and of itself, constitute

>any kind of evaluation at all (even in the crude sense of saying whether

>any one of the positions in the list is a win or a draw).

All positions are either a completed win for one side (i.e. mate) or draw by

rules or on a path leading to one of the previous cases. Therefore, a complete

list of positions AND transitions (moves) from one position to another already

contains all evaluation information.

> The whole problem,

>as I see it, comes with the evaluation process, which I think will take one

>on an infinite loop, as I described in my previous post. The languages of

>the world are also composed of a finite number of words, but linguists tell

>us that the number of sentences (or expressions) is infinite.

That is because a sentence has unlimited length.

> To say that

>"potentially, one could examine each one (of the positions) and determine

>the possible outcomes" is to say something more than 'there are a finite

>number of positions'. Just what assumptions are involved in that statemene,

>are not entirely clear.

>

From all the postings that appeared so far, it should be clear by now.

Sven

Sep 24, 1992, 3:55:30 PM9/24/92

to

In article <1992Sep24....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:

>

>For the record, threefold repetition and the fifty-move rule do not result

>in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

>Hence technically a chess game can go on forever, so the theorem that either

>chess is a draw or one side can force a win does not apply.

>--

>

>For the record, threefold repetition and the fifty-move rule do not result

>in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

>Hence technically a chess game can go on forever, so the theorem that either

>chess is a draw or one side can force a win does not apply.

>--

By the same token, mate doesn't result in automatic win. You mate your opponent

and don't realise it, he escapes with an illegal move and you don't realise it,

and you play on...

Absent-mindedness is assumed not to be part of the game, just like Turkish

bullets (there's a multi-stage problem based on a story in which some general

is playing chess during a battle with Turks, and every time he announces mate,

a bullet removes a piece, but he announces another mate, and so on...)

If you are looking for an algorithm for BEST play, you'll obviously claim

draw by repetition if it is to your advantage and will not allow it if it is

not.

Sven

Sep 24, 1992, 5:15:13 PM9/24/92

to

In article <4ekEn7i2A...@pitt.edu>, tas...@pitt.edu (Teri A Meyers) writes:

|>

|> In article 6958, John Eisenberg responds to my article ("Chess is not

|> solvable", article 6947) as follows:

|> >

|> >

|> >I don't see what the problem is.

|> >There are only a finite number of possible chess games.

|> >Potentially, one could examine each one and determine

|> >the possible outcomes. Whether there is or is not a

|> >forced win for either side is theoretically computable.

|>

|>

|> In article 6962, Nordic Man writes, in the same vein:

|> >

|> >The general game theory idea is that chess is a FINITE game. There exist

|> >only a finite number of legal positions.

|>

|> These arguments do not prove to me that chess is solvable, because it seems

|> obvious that even if a computer had a list containing every possible chess

|> position, this would not, in and of itself, constitute a complete evaluation

^^^^^^^^^^^^^^^^^^^|>

|> In article 6958, John Eisenberg responds to my article ("Chess is not

|> solvable", article 6947) as follows:

|> >

|> >

|> >I don't see what the problem is.

|> >There are only a finite number of possible chess games.

|> >Potentially, one could examine each one and determine

|> >the possible outcomes. Whether there is or is not a

|> >forced win for either side is theoretically computable.

|>

|>

|> In article 6962, Nordic Man writes, in the same vein:

|> >

|> >The general game theory idea is that chess is a FINITE game. There exist

|> >only a finite number of legal positions.

|>

|> These arguments do not prove to me that chess is solvable, because it seems

|> obvious that even if a computer had a list containing every possible chess

|> position, this would not, in and of itself, constitute a complete evaluation

|> of all the nuances (ie, possible continuations and their evaluations) of each

|> and every one of those positions. Nothing less than such a complete

|> evaluation would constitute, to my mind, the "solution" to chess. The

I think you would have to define "evaluation" more clearly. Do you

want the computer to give you a solution and *explain* its reasoning

as well? That's asking a little too much.

|> existence of such a list would not even, in and of itself, constitute

|> any kind of evaluation at all (even in the crude sense of saying whether

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

|> any one of the positions in the list is a win or a draw). The whole problem,

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This definition of "evaluation" is not crude at all, but very precise.

If given a position and perfect play on both sides, we can always

evaluate the current position as a forced win or a forced draw by

examining all the positions resulting from the current position.

By "perfect play", I mean the mini-max algorithm in game theory. I

don't have the definition at hand, but the basic idea of mini-max is

to minimize your opponent's maximal gain. For example, if given the

choice of making a move that will lead to 99 replies from your

opponent that are forced wins for me, but 1 reply that will allow my

opponent to force me to lose, under mini-max, I would not make that

move hoping my opponent doesn't see that 1 of out 100 replies that

would beat me.

|> as I see it, comes with the evaluation process, which I think will take one

|> on an infinite loop, as I described in my previous post. The languages of

^^^^^^^^^^^^^

Under the three-fold repetition and 50-move rule, a chess game is not

infinitely long.

|> the world are also composed of a finite number of words, but linguists tell

|> us that the number of sentences (or expressions) is infinite. To say that

^^^^^^^^^^^

However, if you impose the restriction that your sentences and

expressions must have finite length (analogous to the finite length of

a chess game), then the set of all such sentences is finite.

|> "potentially, one could examine each one (of the positions) and determine

|> the possible outcomes" is to say something more than 'there are a finite

|> number of positions'. Just what assumptions are involved in that statemene,

|> are not entirely clear.

The assumption is that the mini-max algorithm is being applied and the

normal rules of chess regarding repetition of positions is used.

Therefore, all possible chess positions can be generated and evaluated

as win or a draw at the leaf nodes of our game tree.

The point is that chess is theoretically solvable, but not in

practical amount of time.

|>

|>

|> Jerry Meyers

Sep 24, 1992, 6:58:45 PM9/24/92

to

>2. Computers will never brute-force solve the game. Therefore, they will

>*never* solve it. Searching partial trees won't cut it as you also eliminate

>many paths that might disturb the final results.

>*never* solve it. Searching partial trees won't cut it as you also eliminate

>many paths that might disturb the final results.

It is fair game to eliminate paths that *provably* do not disturb the final

results. And to terminate search on paths that have a provable result.

For example, many positions can be proven "drawn"

due to insufficient mating material.

In 100 years we (or some other intelligence) might develop a

sophisticated new "algebra" that allows us to calculate

the game-theoretic value of large classes of chess positions.

That would reduce the search space to the point that chess could

be solved in a practical amount of time.

Tom Truscott

Sep 24, 1992, 7:55:30 PM9/24/92

to

In article <1992Sep24....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:

> For the record, threefold repetition and the fifty-move rule do not result

> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

> Hence technically a chess game can go on forever, so the theorem that either

> chess is a draw or one side can force a win does not apply.

... except that there is only a finite number of possible positions anyway.

--

--Andrew Koenig

a...@europa.att.com

Sep 24, 1992, 7:26:50 PM9/24/92

to

In article <4ekEn7i2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes:

>These arguments do not prove to me that chess is solvable, because it seems

>obvious that even if a computer had a list containing every possible chess

>position,

>These arguments do not prove to me that chess is solvable, because it seems

>obvious that even if a computer had a list containing every possible chess

>position,

Well, these arguments weren't talking about a *list* of positions, but

rather a *graph* that showed how positions were connected to each other

(a "connection" occurs when there is a legal move that can transform

one position into another). The arguments didn't mention this explicitly,

however, so your confusion is not surprising.

>this would not, in and of itself, constitute a complete evaluation

>of all the nuances (ie, possible continuations and their evaluations) of each

>and every one of those positions.

And that's *exactly* what this graph is...the possible continuations and

evaluation of every single position.

>Nothing less than such a complete

>evaluation would constitute, to my mind, the "solution" to chess.

Yep...that's why we've said that chess is solvable!

>[...] the evaluation process, which I think will take one

>on an infinite loop, as I described in my previous post.

Loops pose no theoretical limitation, since loops only kill you if you

perform the evaluation depth-first, which is unnecessary (although that's

the most practical way of proceeding).

For example, a graph for the "toy" example KQ vs KQ will contain loops, but

such a graph contains only 32,000,000 positions, which can be solved on a

workstation using the approach I described in my other message. Build the

graph, evaluate the final positions, cyclically evaluate the non-final

positions, and evaluate the "loop" (no forced mate) positions...then you

can lookup the evaluation of the initial position K(e1)Q(d1) vs K(e8)Q(d8).

>The languages of

>the world are also composed of a finite number of words, but linguists tell

>us that the number of sentences (or expressions) is infinite.

Yes...and I agree that, because of loops (reusing the same "word", in your

analogy), the number of possible chess games in infinite. However, this

merely says is that the number of ways of traversing the graph is infinite.

The *graph* *itself* is finite in size, and each node (position) can

be evaluated in finite time, as I described before.

If this is still unclear to you, I'm just down the street, so maybe we could

meet and discuss it in person. We might even (*gasp*) play an actual game.

-Joe Mattis ARPA: j...@isl1.ri.cmu.edu

UUCP: ...!ucbvax!isl1.ri.cmu.edu!j...@ucbvax.berkeley.edu

Sep 24, 1992, 6:28:22 PM9/24/92

to

In article <cek8TIW2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes

:

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory.

:

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory.

Don't be put off by the term "game theory"...that's just an intimidating

phrase for some ideas that follow from common-sense reasoning.

>I operate on the assumption that from the initial position

>neither side can force a win.

Well, that assumption might be wrong (that's why you called it an

"assumption"), which makes the rest of your analysis invalid. But you still

raise some interesting points, so I'll address those.

>This assumption may be mathematically unprovable

>but neither can it be disproved,

Not quite true. The assumption is *practically* unprovable/undisprovable...

i.e. we cannot prove/disprove it in actual practice. However, the assumption

IS theoretically (mathematically) provable/disprovable...you just don't know

how such proofs work (yet!).

>Anyways, if the starting position represents a balance (a "draw" [...]),

>than it strikes me that the game

>can only be won if someone disturbs the balance (ie, makes mistakes).

Your statement captures the essence of the "minimax" algorithm for games.

Assign the following numeric evaluations to all possible final game positions:

Black to move (in check); no legal moves (checkmate): +1

Black to move (not in check); no legal moves (stalemate): 0

White to move (not in check); no legal moves (stalemate): 0

White to move (in check); no legal moves (checkmate): -1

Unless a player makes a mistake, White will always move in such a manner

so as to reach a position with the "maximum" possible evaluation, and Black

will move so as to reach a position with the "minimum" possible evaluation.

>[...] who can say there is any theoretical upper

>limit to the number of possibilities (actual moves plus the vast horizon

>of possible variants).

But there *is* one, since "vast" does not mean "infinite"! First, there's the

"50 move rule"...if no pawn was advanced or piece captured in the last 50

moves, either player may claim a draw. With 16 pawns (which can advance

6 ranks) and 30 pieces (which can be captured), games can last at most:

(16 * 6 + 30) * 50 = 6300 moves

before the "50 move rule" can be invoked for a draw.

But even if we ignore the "50 move rule", there are only a finite number

of possible positions. With 64 squares, which can be in one of (at most)

13 states (empty or occupied by W/B * KQRBNP), there are (at most) 13 ^ 64

board configurations. For each configuration, either W/B moves next (2),

each king can/cannot castle K/Q-side ((2*2)^2), and there are (at most)

9 "en passant" states (none or file abcdefgh). So there are (at most):

(13 ^ 64) * 2 * (4 ^ 2) * 9 ~= 5.6 * 10^73 positions

Each of these positions will either be a final position (with an evaluation

of +1, 0, or -1), or it will lead into a few of the 5.6 * 10^73 other

positions, based on the range of possible legal moves. Thus, all of chess

can be represented by a huge cyclic directed graph, where the nodes represent

positions, and the links represent legal moves. The task of "solving

chess" consists of determining evaluations for all of the unevaluated

(non-final) positions:

White to move, and can force checkmate: +1

White to move, and can force stalemate: 0

Black to move, and can force stalemate: 0

Black to move, and can force checkmate: -1

This is actually very simple! Cycle through the unevaluated positions,

performing the following computation:

IF White to move THEN

IF some move leads to a +1 position THEN

evaluate this position as +1

ELSE IF all moves lead to evaluated positions THEN

evaluate this position as the MAXIMUM of the

evaluations of all possible moves

ELSE this position remains unevaluated this cycle.

ELSE /* Black to move */

IF some move leads to a -1 position THEN

evaluate this position as -1

ELSE IF all moves lead to evaluated positions THEN

evaluate this position as the MINIMUM of the

evaluations of all possible moves

ELSE this position remains unevaluated this cycle.

Keep doing these cycles until an entire cycle is performed during which

no new evaluations were determined. The remaining unevaluated positions

represent positions where, due to repetition or lack of material, neither

side can force checkmate or stalemate. Evaluate all such positions as:

Neither side can force checkmate or stalemate: 0

Now, every possible chess position, including the initial position, has

an evaluation:

Black is checkmated, or White can force checkmate: +1

Neither side can force checkmate, thus both sides

can force a draw: 0

White is checkmated, or Black can force checkmate: -1

Theoretically, this evaluated graph can be constructed, so theoretically,

chess is solvable! But, practically, I'm confident that it will never

actually be solved.

>[...] However, when can the machine stop its analysis and declare the

>position conclusively a draw? [...] how does it know it will not find the

>win by searching one ply further? [...]

This is rather insightful for somebody who (apparently) doesn't know anything

about game theory and searching. What you've described is a serious concern

for computerized theorem provers...such programs never can be sure when to

give up and declare a theorem "unprovable", since applying "reduction" just

one more time might yield a completed proof.

But since chess positions are finite in number (unlike proofs), this concern

does not apply to chess.

Sep 24, 1992, 9:24:16 PM9/24/92

to

In article <1992Sep24.1...@cis.uab.edu> hy...@cis.uab.edu (Robert Hyatt) writes:

>1. the game of chess *IS* solvable. That is, from the opening move, either

>white wins, black wins (unlikely) or the perfect game is a draw.

>1. the game of chess *IS* solvable. That is, from the opening move, either

>white wins, black wins (unlikely) or the perfect game is a draw.

OR the game has an "undetermined" result because the game never

ends. As long as we are talking nuances, I still see some hand-waving

in the arguments that an "optimal" player can be theoretically

developed. If the result of "solving" the game is that the game

has either a solution of "white draws or it is undetermined" then

I think it is not strictly solved. In any case, I don't see that

an "optimal" solution can be found. It will depend upon the choice

of the value of "undetermined" loops.

Sep 25, 1992, 1:52:42 AM9/25/92

to

My previous posts on "solvability" have generated more responses than I can

keep up with, but I will try to deal with a few of them.

In article 6997 Sven Hauptfeld chides me for my perspective as follows:

Me: "Here are my thoughts on the matter, which come more from philosophy

than game theory".

Him: "Game theory also comes from philosophy, but one that works."

Me: "I operate on the assumption that from the initial position neither

side can force a win."

Him: "No, no! That's not called philosophy, that's called religion. And

what you call 'assumption' is called a dogma. Philosophy must start

from much more general, abstract assumptions."

Obviously, Sven has a very particular version of philosophy in mind here;

certainly anyone versed in the history of philosophy will know that there

are many other ways to approach it than deduction from abstract principles.

If anything, people who insist that's the only way to go will find many other

philosophers who will accuse them of being dogmatic! All I wish to do in

working from the assumption that the initial position is dynamically

balanced (a "draw" to those who wish to assign a discrete value to my

concept of 'dynamic balance'), is to begin my chess philosophizing from

an experiential starting point (drawing on my background as a chess master),

rather than from a game theory starting point. Certainly from within

philosophy the experiential starting point is a well established approach,

though it is only one of many approaches. One can attempt to deny its

validity (as Sven later did by pointing out that at one point scholars

believed the Sun orbited the Earth, or refering to optical illusions), but

then one can also point to certain absurdities that a purely deductive

approach can lead one to; in this instance, the idea that the initial

position in chess may turn out to be a win for Black. Logically this is

true, but experientially it is a canard. If, in fact, chess were

solvable, and it were just to happen, just by chance, that as Sven

himself writes:

"Your dogma might well be shown true (I bet it is!), but it must be shown,

not postulated",

then how will the game theorist account for it? He can only say 'that's

just how it turned out,' or something of the sort. For him, it must be

shown (empirically, I suppose, since Sven says not postulated); experience

cannot count because it might be an illusion.

The truth is, experience sometimes can produce illusions, but most of the

time, it doesn't (unless we are Bobby Fischer?!), and even when it does

produce illusions, most of the time we can discover it, either on our own

or with the help of others (ie., intersubjective experience). At any rate,

I am not saying that the game theory approach to chess is not useful or

valid, I only wish to claim it is not the only useful and valid approach.

Also, I disagree with some of its conclusions. I agree there are a finite

number of legal positions. I disagree with the claim that a list of these

positions constitutes a solution to chess. Two people responded to this:

Sven, in article 7063, and Cheong Yu in article 7068.

Sven wrote "All positions are either a completed win for one side (ie. mate)

or draw by rules or on a path leading to one of the previous cases. Therefore

a complete list of positions AND transitions (moves) from one position to

another already contains all evaluation information." Well, a list of all

games possible from the initial position will contain wins, losses, and draws.

In order to separate the wheat from the chaff, you will have to make use of

some type of evaluation process not contained in your list.

Cheong Yu responds more directly to my definition of what a 'solution' to

chess would entail. First he quotes me as saying "even if a computer had

a list containing every possible chess position, this would not, in and of

itself, constitute a complete evaluation of all the nuances (ie, possible

continuations and their evaluations) of each and every one of those positions.

Nothing less than such a complete evaluation would constitute, to my mind,

the "solution" to chess."

He responds: "...Do you want the computer to give you a solution and

*explain* its reasoning as well? That's asking a little

too much."

Perhaps it is asking "too much"--too much for anyone to actually do, but

not too much to require anyone claiming to have the 'solution' to chess

to provide. Some people have argued that the computer may eventually

provide us with a forced win for White in 40 or 20 moves (or even several

different ways to force a win -- what does it matter if one is 25 moves

and another 26--mathematically, a win is win is a win)--but unless the

machine can tell us everything there is to know about all the immortal

games of chess it will not have "solved" chess in any complete sense.

Suppose (at the end of time) it finishes its analyses and tells us, Chess

is a draw. Would that be the 'solution'? It would certainly answer the

game theorist's question whether it is a win for white, black, or draw.

For myself and those like me who want to know something about that

beautiful little world that stirs our emotions, it would be pale comfort.

Jerry Meyers

(I speak for myself only, and not my wife Teri, whose ignorance of chess

is its own form of bliss).

Sep 25, 1992, 12:56:37 AM9/25/92

to

In article <cek8TIW2A...@pitt.edu> Teri A Meyers <tas...@pitt.edu> writes:

Here are my thoughts on this matter, which come more from philosophy than

from game theory. I operate on the assumption that from the initial position

neither side can force a win.

So, in your philosophy, assuming the conclusion is not a fallacy?

Maybe you _should_ go back and try game theory, then :-)

-- Craig Presson

Sep 25, 1992, 12:47:39 PM9/25/92

to

In article <4ekEn7i2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes:

>>These arguments do not prove to me that chess is solvable, because it seems

>>obvious that even if a computer had a list containing every possible chess

>>position,

>>These arguments do not prove to me that chess is solvable, because it seems

>>obvious that even if a computer had a list containing every possible chess

>>position,

>>this would not, in and of itself, constitute a complete evaluation

>>of all the nuances (ie, possible continuations and their evaluations) of each

>>and every one of those positions.

>>of all the nuances (ie, possible continuations and their evaluations) of each

>>and every one of those positions.

Joe Mathis responds:

>Well, these arguments weren't talking about a *list* of positions, but

>rather a *graph* that showed how positions were connected to each other

>(a "connection" occurs when there is a legal move that can transform

>one position into another). The arguments didn't mention this explicitly,

>however, so your confusion is not surprising.

If you use rectograde analysis, you don't need to show all the connections.

All you need to do is mark down whether the position is a white win or not.

You start by finding all the positions in your database where black is mated.

These are white wins. You then look through all the positions with white

to move and see if any white can make a move that would result in one of the

won positions you've previously found. If so, then that position can also

be classified as a win for white. Then look at the positions with black

to move. If ALL black's moves result in positions you've classified as won for white,

then that position is also marked as a white win. Continue this procedure until

you can't find any more white wins. Then find the mirror image of all these

white wins with the opposite side on move. These are all the black wins. The

remaining unclassified positions are drawn.

This was how that KBR vs KNN endgame was solved about a year ago.

Sep 25, 1992, 12:34:27 PM9/25/92

to

If no one has already done this already, could someone list

a book that demonstrates that chess is theoretically solvable

so we can stop wasting time on this subject due to all the

people who don't have enough common sense (or whatever it takes)

to figure it out for themselves. It's getting ridiculous

reading all those articles.

I don't mind discussions on the practical part (computer

limitations, speculations on how long it would take to

solve chess, etc.), but CHESS DOES HAVE A SOLUTION!!!!! Just

because it may take 10^100 years to find it, doesn't mean

there isn't one!

Maybe we should stop using the word "solvable," because some

people seem to use that term to basically say "If the universe

comes to an end before we can solve chess, it's not solvable."

-Andy

Sep 25, 1992, 12:19:39 PM9/25/92

to

For all intents and purposes, the three-fold repetition and 50-move

rules DO constitute and automatic draw. Consider the two scenarios:

1) Chess is a game where either white can force mate at move 1 OR

one where black can force mate at move 1.

As soon as one of the rules comes up, the side that cannot force mate

will immediately claim the draw to avoid mate. Of course this would

never occur in this case (scenario 1 in effect) unless the side that

can force mate lets it happen. Otherwise scenario 1 would not have

been true in the first place. Hmm. This was a little more

complicated to explain than I thought it would be.

2) Chess is a game where either side can force a draw.

The draw rules don't matter since if the two sides continue playing,

the game will still be a draw.

-Andy

Sep 24, 1992, 5:57:00 AM9/24/92

to

> >The general game theory idea is that chess is a FINITE game. There exist

> >only a finite number of legal positions.

>

> These arguments do not prove to me that chess is solvable, because it seems

> obvious that even if a computer had a list containing every possible chess

> position, this would not, in and of itself, constitute a complete evaluation

> of all the nuances (ie, possible continuations and their evaluations) of each

> and every one of those positions. Nothing less than such a complete

> evaluation would constitute, to my mind, the "solution" to chess. The

> existence of such a list would not even, in and of itself, constitute

> any kind of evaluation at all (even in the crude sense of saying whether

> any one of the positions in the list is a win or a draw).

> >only a finite number of legal positions.

>

> These arguments do not prove to me that chess is solvable, because it seems

> obvious that even if a computer had a list containing every possible chess

> position, this would not, in and of itself, constitute a complete evaluation

> of all the nuances (ie, possible continuations and their evaluations) of each

> and every one of those positions. Nothing less than such a complete

> evaluation would constitute, to my mind, the "solution" to chess. The

> existence of such a list would not even, in and of itself, constitute

> any kind of evaluation at all (even in the crude sense of saying whether

> any one of the positions in the list is a win or a draw).

Completely wrong. You never heard about perfect endgames or retrograde

analysis.. If a computer has the power to manage all possible positions,

it can build a game tree up from the simplest endgames to the starting

position and thus decide if it is won/draw/lost.

Think of it: If position A (with black to move) is proven won for white,

then all positions where white can make a move that leads to position A

are won for white, and so on...

--ralf

Sep 26, 1992, 1:39:01 AM9/26/92

to

In article <gekeYe_2A...@pitt.edu> Teri A Meyers <tas...@pitt.edu> writes:

>

>In article 6997 Sven Hauptfeld chides me for my perspective as follows:

>

>Me: "Here are my thoughts on the matter, which come more from philosophy

> than game theory".

>

>Him: "Game theory also comes from philosophy, but one that works."

>

>Me: "I operate on the assumption that from the initial position neither

> side can force a win."

>

>Him: "No, no! That's not called philosophy, that's called religion. And

> what you call 'assumption' is called a dogma. Philosophy must start

> from much more general, abstract assumptions."

>

>Obviously, Sven has a very particular version of philosophy in mind here;

>certainly anyone versed in the history of philosophy will know that there

>are many other ways to approach it than deduction from abstract principles.

>

>In article 6997 Sven Hauptfeld chides me for my perspective as follows:

>

>Me: "Here are my thoughts on the matter, which come more from philosophy

> than game theory".

>

>Him: "Game theory also comes from philosophy, but one that works."

>

>Me: "I operate on the assumption that from the initial position neither

> side can force a win."

>

>Him: "No, no! That's not called philosophy, that's called religion. And

> what you call 'assumption' is called a dogma. Philosophy must start

> from much more general, abstract assumptions."

>

>Obviously, Sven has a very particular version of philosophy in mind here;

>certainly anyone versed in the history of philosophy will know that there

>are many other ways to approach it than deduction from abstract principles.

"Deduction from abstract principles" is quite different from what I said.

Anyway, starting from such a particular and arbitrary statement as "starting

position is a draw" is certainly contrary to the spirit of philosophy, math

or science.

> All I wish to do in

>working from the assumption that the initial position is dynamically

>balanced (a "draw" to those who wish to assign a discrete value to my

>concept of 'dynamic balance'), is to begin my chess philosophizing from

>an experiential starting point (drawing on my background as a chess master),

You failed. There is no experimental evidence that the initial position is

ballanced, on the contrary, tournament results favor white by almost 6-4,

so from the experimental point of view (of which I am far more qualified to

speak than of the philosophical), the assumption you based your whole

philosophy on has a very high likelihood of being false.

BTW, one doesn't have to be a master to see that the initial position is only

*statically* ballanced, while *dynamically* white is a tempo up.

>then one can also point to certain absurdities that a purely deductive

>approach can lead one to; in this instance, the idea that the initial

>position in chess may turn out to be a win for Black.

The theorem around which this discussion developed says *nothing* of the kind.

It says that possibilities *other than* forced win for white, forced draw and

forced win for black (in other words, the infamous 'undeternined value'

positions, which keep popping out in so many postings) are *not* possible.

> Logically this is

>true, but experientially it is a canard.

I've just shown that this is irrelevant, but even 'experimentally' it is well

justified. Many games of the same class actually favor black. While this is

highly unlikely to be true for chess, that is just a particular example.

>"Your dogma might well be shown true (I bet it is!), but it must be shown,

>not postulated",

>

>then how will the game theorist account for it? He can only say 'that's

>just how it turned out,' or something of the sort. For him, it must be

>shown (empirically, I suppose, since Sven says not postulated); experience

>cannot count because it might be an illusion.

This is nonsense. Postulated means 'not derived'. There is no dogma in game

theory nor is there a 'postulate' that chess is solvable. It is a theorem,

i.e. it is derived from more general statements. (Yes, eventually it is

derived from postulates. But not postulates like "initial position is

ballanced" but those like "one is greather than zero". See the difference?)

>I am not saying that the game theory approach to chess is not useful or

>valid, I only wish to claim it is not the only useful and valid approach.

For the issues it addresses, it is. If you disagree, don't bug me, but

construct a concurring theory. (Friendly advice: don't try.)

>Also, I disagree with some of its conclusions. I agree there are a finite

>number of legal positions. I disagree with the claim that a list of these

>positions constitutes a solution to chess. Two people responded to this:

You are really obnoxious. This is not a 'conclusion' of the game theory, nor

has anybody stated anything like that in this discussion.

>Sven wrote "All positions are either a completed win for one side (ie. mate)

>or draw by rules or on a path leading to one of the previous cases. Therefore

>a complete list of positions AND transitions (moves) from one position to

>another already contains all evaluation information." Well, a list of all

>games possible from the initial position will contain wins, losses, and draws.

>In order to separate the wheat from the chaff, you will have to make use of

>some type of evaluation process not contained in your list.

You only need 'evaluation' if you are not certain of the outcome. If you have

a graph of all paths among all positions, you can trivially evaluate every

path by inspection - does it end in 1, 1/2 or 0?

>but unless the

>machine can tell us everything there is to know about all the immortal

>games of chess it will not have "solved" chess in any complete sense.

First of all, you seem to impose an entirely different definition of "solved"

than the one being discussed (which had been clearly stated), which makes

your argument invalid. But even so, we *would* know everything there is to

know about all immortal games (as well as about not-so-immortal ones), i.e.

we would know exactly which moves were mistakes and which were exceptionally

good.

>Suppose (at the end of time) it finishes its analyses and tells us, Chess

>is a draw. Would that be the 'solution'? It would certainly answer the

>game theorist's question whether it is a win for white, black, or draw.

>For myself and those like me who want to know something about that

>beautiful little world that stirs our emotions, it would be pale comfort.

What is your point? Let me use a loose - but illustrative - analogy: I *know*

that I'll die. Therefore, the final result of my life is 'solved'. Does that

make my life any less interesting?

Sven

Sep 27, 1992, 2:33:35 PM9/27/92

to

In article <1992Sep25....@noose.ecn.purdue.edu> wat...@alcohol.ecn.purdue.edu (Bradley S Watson) writes:

>Joe Mattis (not Mathis!) responds:

>>Well, these arguments weren't talking about a *list* of positions, but

>>rather a *graph* that showed how positions were connected to each other

>

>Joe Mattis (not Mathis!) responds:

>>Well, these arguments weren't talking about a *list* of positions, but

>>rather a *graph* that showed how positions were connected to each other

>

>If you use rectograde analysis, you don't need to show all the connections.

True, explicit connections aren't being maintained, but connections *are*

being derived "on the fly" (and then forgotten) as part of the steps:

>...[if white] can make a move that would result in one of the [+1] positions

and

>...If ALL black's moves result in [+1] positions...

So mathematically, you're still working with a graph. I thought it was

important to emphasize these implicit links between the evaluated positions.

Anyway, thanks for providing a concise description of "retrograde analysis".

I'd been wondered exactly how it worked!

Sep 27, 1992, 5:02:08 PM9/27/92

to

In article <Bv3t3K...@cs.cmu.edu> ja...@cs.cmu.edu (Joe Mattis) writes:

>Keep doing these cycles until an entire cycle is performed during which

>no new evaluations were determined. The remaining unevaluated positions

>represent positions where, due to repetition or lack of material, neither

>side can force checkmate or stalemate. Evaluate all such positions as:

> Neither side can force checkmate or stalemate: 0

>Keep doing these cycles until an entire cycle is performed during which

>no new evaluations were determined. The remaining unevaluated positions

>represent positions where, due to repetition or lack of material, neither

>side can force checkmate or stalemate. Evaluate all such positions as:

> Neither side can force checkmate or stalemate: 0

You have to make an assumption in order to assign this a value. The

method you are using is searching for "best play" by looking for

the best possible value for downstream (one ply hence) positions.

When that turns out to depend upon the value of the node itself

you are ARBITRARILY assigning the value zero. This does not

consistitute a proof that the best play leads to a value of

+1, 0. or -1 for the initial position.

Consider the following trivial graph tree. It has two nodes

A and B. B is a final position and has value zero. The linkages

are two arcs. The first goes from A to B. The second goes from

A to A. So, what value do we give to node A? It should have the best

of the two possibilities (A or B). We know B is zero, but we

don't know A. According to your argument, we must assign

the value zero, because there can be no other outcome. I think

this is using an additional assumption.

(Note that when A is life and B is death, we find a way to choose

life -- and are comfortable with the evaluation that it is better

than death.)

Anyway, I'm awaiting a proof.

Sep 27, 1992, 5:58:49 PM9/27/92

to

All of this discussion of games in which positions occur infinitely

many times and neither player claims a draw leave me puzzled.

many times and neither player claims a draw leave me puzzled.

A min-max algorithm considering a line in which either player can

claim a draw will assign it the value "draw". Why? Because neither

player can force a better result. The value of the position is a

draw. The best White can do against best play is a draw and the

best Black can do against best play is a draw.

Only by changing the rules of chess and giving a continuing game

a value greater than a draw can this be avoided, and there is no

such rule. Even in that case, the value of the unfinished game

would have to be greater than a draw *for both players*. And finally,

assuming "unfinished" has a value greater than "draw", even in

positions where neither player can force a win (which can be

identified by min-max) the value is "unfinished" and analysis may

stop. There wouldn't be a lot of drawn games under that strange

assumption, though. Most draws are "I don't have winning chances

so let's stop playing".

Is all of this really so hard to understand?

-- Don Varvel (var...@cs.utexas.edu)

Sep 27, 1992, 9:53:08 PM9/27/92

to

In article <1992Sep27.2...@cbnewsl.cb.att.com> e...@cbnewsl.cb.att.com (edward.m.hummel) writes:

>In article <Bv3t3K...@cs.cmu.edu> ja...@cs.cmu.edu (Joe Mattis) writes:

>>[...] The remaining unevaluated positions>In article <Bv3t3K...@cs.cmu.edu> ja...@cs.cmu.edu (Joe Mattis) writes:

>>represent positions where, due to repetition or lack of material, neither

>>side can force checkmate or stalemate. Evaluate all such positions as:

>> Neither side can force checkmate or stalemate: 0

>

>You have to make an assumption in order to assign this a value.

Not at all. This evaluation, which seems so capricious to you, is *only*

applied to positions where (with best play) neither player can forcibly reach

+1 or -1...that's why these positions remained unassigned! Now, a completed

chess game must end with a White win (+1), a Black win (-1), or a draw (0).

Since it's impossible to reach +1 or -1, the only possible completion (with

best play) is 0. Therefore, IF THE GAME EVER ENDS from one of these

positions (with best play), it must end in a draw.

Note that I haven't proved that such games must end...indeed, they might not.

But I *have* proved that the only possible result from such positions (with

best play) is a draw. If it turns out that the initial position is such a

position, that would be enough (in and of itself) to "solve" chess. After

all, if we determined that neither White nor Black could forcibly checkmate

the other (with best play), that would certainly answer the question that

started this whole discussion, the intent of which was (paraphrasing):

Which is correct? (a) White can forcibly win.

(b) Black can forcibly win.

(c) Neither can forcibly win.

>When [a downstream value] turns out to depend upon the value of the node

>itself you are ARBITRARILY assigning the value zero.

Untrue! After all, *most* positions "depend" on the value of the node

itself, since most positions can lead to back to themselves (e.g. players can

usually shuffle their kings endlessly). Yet many such positions get +1 or -1

evaluations. For example, the potential for king-shuffling in

K(a1)Q(a2) vs K(h1) doesn't alter the fact that the position is +1 (a win

for White). Furthermore, there is no chance that Black could forcibly

enter a "loop" from a +1 position. Positions are only assigned +1

if White can forcibly avoid all loops (as in the KQvsK example).

The only positions that get evaluated as 0 by the passage you quoted above

are those where no +1 or -1 positions can be forcibly reached (with best

play). (Note that this handles all of the "drawn by fiat" positions (KvsK,

KvsKNN, etc) without resorting to special rules.)

>Consider the following trivial graph tree. It has two nodes

>A and B. B is a final position and has value zero. The linkages

>are two arcs. The first goes from A to B. The second goes from

>A to A. So, what value do we give to node A? It should have the best

>of the two possibilities (A or B). We know B is zero, but we

>don't know A.

But we do know *something* about A...we know that neither player can forcibly

reach +1 or -1! Therefore, we know that from this position (with best play)

IF THE GAME EVER ENDS, it must end in a draw.

>According to your argument, we must assign

>the value zero, because there can be no other outcome. I think

>this is using an additional assumption.

Not if "0" means "Neither can forcibly win."

So, I've proved that it's theoretically possible to answer the question

above as (a) (b) or (c). The fact that (c) implies that a game might

never end (with best play) is just as uninteresting and irrelevant from the

initial position as it is from KQvsKQ...either way, it's a drawn position

(with best play).

If you can't understand the proof or its consequences, you'll have to ask

someone else for help.

Sep 27, 1992, 11:03:02 PM9/27/92

to

In article <Bv9MKK...@cs.cmu.edu> ja...@cs.cmu.edu (Joe Mattis) writes:

>Note that I haven't proved that such games must end...indeed, they

>might not. But I *have* proved that the only possible result from

>such positions (with best play) is a draw. If it turns out that

>the initial position is such a position, that would be enough (in

>and of itself) to "solve" chess. After all, if we determined that

>neither White nor Black could forcibly checkmate

>the other (with best play), that would certainly answer the question that

>started this whole discussion, the intent of which was (paraphrasing):

> Which is correct? (a) White can forcibly win.

> (b) Black can forcibly win.

> (c) Neither can forcibly win.

>Note that I haven't proved that such games must end...indeed, they

>might not. But I *have* proved that the only possible result from

>such positions (with best play) is a draw. If it turns out that

>the initial position is such a position, that would be enough (in

>and of itself) to "solve" chess. After all, if we determined that

>neither White nor Black could forcibly checkmate

>the other (with best play), that would certainly answer the question that

>started this whole discussion, the intent of which was (paraphrasing):

> Which is correct? (a) White can forcibly win.

> (b) Black can forcibly win.

> (c) Neither can forcibly win.

Joe, you missed the turn. I have never been challenging Z's result.

Instead, I have been adressing the question of "What is the outcome

(if any) of a game which proceeds with "best play" by both sides?"

The answer could be: (a) White wins,

(b) Black wins,

(c) The game is drawn, or

(d) None of the above, i.e., "best play"

leads to a game with no outcome.

The rules assign values for wins (1), losses (0) and draws (.5).

The analysis to answer this question is very similar to the

analysis to answer the question you mention, BUT it turns out

to require some additional information. To many people, this is

somewhat bothersome.

>If you can't understand the proof or its consequences, you'll have

>to ask someone else for help.

I understand the proof you have laid out (I always did). If you

don't understand the issue I have raised, please feel free to post

a followup or contact me by email. I'll try to explain it more

clearly.

Ed Hummel

Sep 25, 1992, 12:28:22 AM9/25/92

to

Organization: School of Computer Science, Carnegie Mellon

In article <cek8TIW2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes

:

>Here are my thoughts on this matter, which come more from philosophy than

>from game theory.

Don't be put off by the term "game theory"...that's just an intimidating

phrase for some ideas that follow from common-sense reasoning.

>I operate on the assumption that from the initial position

>neither side can force a win.

Well, that assumption might be wrong (that's why you called it an

Keep doing these cycles until an entire cycle is performed during which

no new evaluations were determined. The remaining unevaluated positions

represent positions where, due to repetition or lack of material, neither

side can force checkmate or stalemate. Evaluate all such positions as:

Neither side can force checkmate or stalemate: 0

Now, every possible chess position, including the initial position, has

an evaluation:

Black is checkmated, or White can force checkmate: +1

Neither side can force checkmate, thus both sides

can force a draw: 0

White is checkmated, or Black can force checkmate: -1

Theoretically, this evaluated graph can be constructed, so theoretically,

chess is solvable! But, practically, I'm confident that it will never

actually be solved.

>[...] However, when can the machine stop its analysis and declare the

>position conclusively a draw? [...] how does it know it will not find the

>win by searching one ply further? [...]

This is rather insightful for somebody who (apparently) doesn't know anything

about game theory and searching. What you've described is a serious concern

for computerized theorem provers...such programs never can be sure when to

give up and declare a theorem "unprovable", since applying "reduction" just

one more time might yield a completed proof.

But since chess positions are finite in number (unlike proofs), this concern

does not apply to chess.

-Joe Mattis ARPA: j...@isl1.ri.cmu.edu

UUCP: ...!ucbvax!isl1.ri.cmu.edu!j...@ucbvax.berkeley.edu

* Origin: The Electronic Mailbox (1:348/7.0)

Sep 25, 1992, 12:58:45 AM9/25/92

to

Organization: IBM RTP

Tom Truscott

* Origin: The Electronic Mailbox (1:348/7.0)

Sep 25, 1992, 3:24:16 AM9/25/92

to

Organization: AT&T

* Origin: The Electronic Mailbox (1:348/7.0)

Sep 25, 1992, 1:55:30 AM9/25/92

to

Organization: AT&T Bell Laboratories, Murray Hill NJ

Reply-To: a...@alice.UUCP ()

Reply-To: a...@alice.UUCP ()

In article <1992Sep24....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:

> For the record, threefold repetition and the fifty-move rule do not result

> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).

> Hence technically a chess game can go on forever, so the theorem that either

> chess is a draw or one side can force a win does not apply.

... except that there is only a finite number of possible positions anyway.

--

--Andrew Koenig

a...@europa.att.com

* Origin: The Electronic Mailbox (1:348/7.0)

Sep 29, 1992, 7:02:51 PM9/29/92

to

In article <1992Sep25.1...@ninja.csuohio.edu> an...@ninja.csuohio.edu (andy) writes:

>If no one has already done this already, could someone list

>a book that demonstrates that chess is theoretically solvable

>so we can stop wasting time on this subject due to all the

>If no one has already done this already, could someone list

>a book that demonstrates that chess is theoretically solvable

>so we can stop wasting time on this subject due to all the

Good idea! Go to the source:

Zermelo, Ernst, U"ber eine Anwendung der Mengenlehre auf die Theorie des

Schachspiels, Proc. Fifth International Congress of Mathematicians,

(Cambridge, 1912), 501-504.

Enough already!

--

Jim Gillogly

j...@rand.org

Sep 29, 1992, 9:58:30 PM9/29/92

to

Ok, the last word on chess solvabilty.

1. IF chess is solvable it would have been solved.

2. Chess has not been solved.

3. Therefore to date chess is not solvable.

Only the solution will prove this wrong, so if you don't agree please post

the solution to chess for all to read. ;-)

Sep 29, 1992, 1:04:14 PM9/29/92

to

In article <cek8TIW2A...@pitt.edu>, Teri A Meyers <tas...@pitt.edu> writes:

>

> of possible variants). A machine which conducts a search for a win X number

> of ply (whether 10 ply or a zillion) will never find it if the game is a

> draw from the position where it begins its analysis (such as before move

> one). However, when can the machine stop its analysis and declare the

> position conclusively a draw? However many ply it goes, it finds the

> position a draw, but how does it know it will not find the win by searching

> one ply further? It will have to search to infinity. If it ever did

> get to infinity (which by definition is impossible), could it then supply

>

> of possible variants). A machine which conducts a search for a win X number

> of ply (whether 10 ply or a zillion) will never find it if the game is a

> draw from the position where it begins its analysis (such as before move

> one). However, when can the machine stop its analysis and declare the

> position conclusively a draw? However many ply it goes, it finds the

> position a draw, but how does it know it will not find the win by searching

> one ply further? It will have to search to infinity. If it ever did

> get to infinity (which by definition is impossible), could it then supply

This cannot happen because there are theoretical limits on the number of

moves which can be made in chess (ie. 50 move rule, redundant moves, etc.)

When (IF!) a computer follows ALL moves to a draw condition (easily tested)

then it will pick a move at random.

It will continue to do this hoping an error is made on the other side.

--

Don Schiewer | Internet schi...@pa881a.inland.com | Onward Great

Inland Steel | UUCP: !uucp!pa881a.inland!schiewer | Stream...

Sep 30, 1992, 4:16:05 PM9/30/92

to

Same logical pattern (albeit without the same bad grammar):

1. If I were mortal, I would be dead.

2. I am not dead.

3. Therefore to date I am not mortal.

There are two mistakes. One is logical, but not too relevant: a new condition

("to date"), not in the premises, appears in the conclusion. The other is

logically fine, but factually wrong: the premise 1. is false.

Sven

Reply all

Reply to author

Forward

0 new messages