Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old September 9th 05, 10:54 PM
Junior Member
 
First recorded activity by ChessBanter: Sep 2005
Posts: 3
Default solve for chess

In Matiyasevich's book on Hilbert's 10th problem, there was a passage on how it was undecidable for a result of a game to be determined from an arbitrary game. Is it still possible for a unavoidable algorithm/gambit for a win/loss/stalemat for either black or white to be determined. If so, what is computational complexity of solving chess?
  #2   Report Post  
Old September 10th 05, 06:25 AM
 
Posts: n/a
Default

Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be
made from any position. Therefore, it is POSSIBLE to determine best
play for any position by analyzing the tree of all possible moves for
that position all the way out to their game-ending state, exactly like
endgame databases do now.

However, EGDBs are at this time only created for up to 6 pieces on the
board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
It's taken about 6-8 years just to go from 5 to 6 pieces as being the
"state of the art", because of the necessary computation time and
storage requirements.

How long will it take to get to 32 pieces? Even if progress is linear
(and it won't be), at best it's going to take close to 200 years before
chess is solved!

jm

  #3   Report Post  
Old September 10th 05, 11:23 AM
Guy Macon
 
Posts: n/a
Default


Content-Transfer-Encoding: 8Bit


wrote:

However, EGDBs are at this time only created for up to 6 pieces on the
board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
It's taken about 6-8 years just to go from 5 to 6 pieces as being the
"state of the art", because of the necessary computation time and
storage requirements.


I wasn't aware of the entire 6 man Nalimov tablebases being completed.
Do you have a source and a hard figure for how many bytes it takes
to hold all of the 3-man, 4-man, 5-man and 6-man Nalimov tablebases?

How long will it take to get to 32 pieces? Even if progress is linear
(and it won't be), at best it's going to take close to 200 years before
chess is solved!


Complete 3 man Nalimov Tablebase...80 kB (measured)
Complete 3+4 man Nalimov Tablebases...30 MB (measured)
Complete 3+4+5 man Nalimov Tablebases...7.5 GB (measured)
Complete 3+4+5+6 man Nalimov Tablebases...1-2 TB (estimated)
Complete 3+4+5+6+7 man Nalimov Tablebases...200-600 TB (estimated)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180 PB (estimated)
....
Complete 3+4+5+...+30+31+32 man Nalimov Tatablebases...????

I welcome any estimates that are better than the ones above,
and I especially welcome anyone who has the courage to give me
an estimate to replace the ??? above. I would also very much
like some data on how long it takes/took to generate each set.

--
Guy Macon http://www.guymacon.com/




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

BTW, Here is a handy reference for expressing large numbers:

************************************************** ***********

SHORT VERSION:

k kilo- 1.0E+3 x1,000 Thousand(US,UK)
M mega- 1.0E+6 x1,000,000 Million (US,UK)
G giga- 1.0E+9 x1,000,000,000 Billion(US)
T tera- 1.0E+12 x1,000,000,000,000 Trillion(US), Billion(UK)
P peta- 1.0E+15 x1,000,000,000,000,000 Quadrillion(US)
E exa- 1.0E+18 x1,000,000,000,000,000,000 Quintillion(US), Trillion(UK)
Z zetta- 1.0E+21 x1,000,000,000,000,000,000,000 Sextillion(US)
Y yotta- 1.0E+24 x1,000,000,000,000,000,000,000,000 Septillion(US), Quadrillion(UK)

Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[
http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answ...re.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]

LONG VERSION:

************************************************** ***********

NAMED POWERS OF TEN - US VERSION
--------------------------------
- N/A 1.0E+36 N/A 1 000 000 000 000 000 000 000 000000 000 000 000
- N/A 1.0E+33 decillion 1 000 000 000 000 000 000 000 000000 000 000
- N/A 1.0E+30 N/A 1 000 000 000 000 000 000 000 000000 000
- N/A 1.0E+27 octillion 1 000 000 000 000 000 000 000 000000
Y yotta- 1.0E+24 septillion 1 000 000 000 000 000 000 000 000
Z zetta- 1.0E+21 sextillion 1 000 000 000 000 000 000 000
E exa- 1.0E+18 quintillion 1 000 000 000 000 000 000
P peta- 1.0E+15 quadrillion 1 000 000 000 000 000
T tera- 1.0E+12 trillion 1 000 000 000 000
G giga- 1.0E+9 billion 1 000 000 000
M mega- 1.0E+6 million 1 000 000
k kilo- 1.0E+3 thousand 1 000
h hecto- 1.0E+2 hundred 100
da deca- 1.0E+1 ten 10
d deci- 1.0E-1 tenth 0.1
c centi- 1.0E-2 hundredth 0.01
m milli- 1.0E-3 thousandth 0.001
micro- 1.0E-6 millionth 0.000 001
n nano- 1.0E-9 billionth 0.000 000 001
p pico- 1.0E-12 trillionth 0.000 000 000 001
f femto- 1.0E-15 quadrillionth 0.000 000 000 000 001
a atto- 1.0E-18 quintillionth 0.000 000 000 000 000 001
z zepto- 1.0E-21 sextillionth 0.000 000 000 000 000 000 001
y yocto- 1.0E-24 septillionth 0.000 000 000 000 000 000 000 001
- N/A 1.0E-27 octillionth 0.000 000 000 000 000 000 000 000 001
- N/A 1.0E-30 N/A 0.000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-33 decillionth 0.000 000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-36 N/A 0.000 000 000 000 000 000 000 000 000 000 000 001

Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[ http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answ...re.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]

************************************************** ***********

NAMED POWERS OF TEN - UK VERSION
--------------------------------
- N/A 1.0E+36 sextillion 1 000 000 000 000 000 000 000 000000 000 000 000
- N/A 1.0E+33 N/A 1 000 000 000 000 000 000 000 000000 000 000
- N/A 1.0E+30 quintillion 1 000 000 000 000 000 000 000 000000 000
- N/A 1.0E+27 N/A 1 000 000 000 000 000 000 000 000000
Y yotta- 1.0E+24 quadrillion 1 000 000 000 000 000 000 000 000
Z zetta- 1.0E+21 N/A 1 000 000 000 000 000 000 000
E exa- 1.0E+18 trillion 1 000 000 000 000 000 000
P peta- 1.0E+15 N/A 1 000 000 000 000 000
T tera- 1.0E+12 billion 1 000 000 000 000
G giga- 1.0E+9 milliard 1 000 000 000
M mega- 1.0E+6 million 1 000 000
k kilo- 1.0E+3 thousand 1 000
h hecto- 1.0E+2 hundred 100
da deca- 1.0E+1 ten 10
d deci- 1.0E-1 tenth 0.1
c centi- 1.0E-2 hundredth 0.01
m milli- 1.0E-3 thousandth 0.001
micro- 1.0E-6 millionth 0.000 001
n nano- 1.0E-9 milliardh 0.000 000 001
p pico- 1.0E-12 billionthh 0.000 000 000 001
f femto- 1.0E-15 N/A 0.000 000 000 000 001
a atto- 1.0E-18 trillionth 0.000 000 000 000 000 001
z zepto- 1.0E-21 N/A 0.000 000 000 000 000 000 001
y yocto- 1.0E-24 quadrillionth 0.000 000 000 000 000 000 000 001
- N/A 1.0E-27 N/A 0.000 000 000 000 000 000 000 000 001
- N/A 1.0E-30 quintillionth 0.000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-33 N/A 0.000 000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-36 sextillionth 0.000 000 000 000 000 000 000 000 000 000 000 001

Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[ http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answ...re.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]

************************************************** ***********

--
Guy Macon http://www.guymacon.com/

  #4   Report Post  
Old September 10th 05, 05:57 PM
[email protected]
 
Posts: n/a
Default

I wasn't aware of the entire 6 man Nalimov tablebases being completed.
Do you have a source and a hard figure for how many bytes it takes
to hold all of the 3-man, 4-man, 5-man and 6-man Nalimov tablebases?


IIRC, the entire 6-man tablebases in De Koning format were completed
quite some time ago (meaning, possibly as much as a year ago) by Marc
Bourzutschky. I do not know how much space they take up, but I have a
vague memory of somebody saying that it was around 1.7 TB. I don't even
know if he kept all of them, as his main goal was to produce the most
interesting ones to verify certain well-known studies.

I'm pretty sure that Nalimov has personally completed all of the TBs in
his format, but hasn't published them all yet.

Guy Haworth, who keeps abreast of these things, might know more of the
particulars.

jm

  #5   Report Post  
Old September 10th 05, 10:47 PM
Junior Member
 
First recorded activity by ChessBanter: Sep 2005
Posts: 3
Default

Thanks for the information, can someone describe what method of encoding the Nalimov databases use for moves, pieces, games.

Last edited by entropy : September 10th 05 at 10:52 PM


  #6   Report Post  
Old September 11th 05, 06:54 AM
Anders Thulin
 
Posts: n/a
Default

entropy wrote:
Thanks for the information, can someone describe what method of encoding
the Nalimov databases use for moves, pieces, games.


None. They're endgame databases: they provide the 'score' for positions.
The position is encoded to a number -- that number is used to look up
the score corresponding to that position: won in N moves, lost in N moves, or
drawn.

The position-to-number transformation is as far as I know not documented,

--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
  #7   Report Post  
Old September 11th 05, 10:32 PM
[email protected]
 
Posts: n/a
Default

wrote:
Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be
made from any position. Therefore, it is POSSIBLE to determine best
play for any position by analyzing the tree of all possible moves for
that position all the way out to their game-ending state, exactly like
endgame databases do now.


It isn't possible, for two reasons: first, because there is no
meaningful definition of "best play" for *every* position; and second,
because even deciding what a "good" move is, in any provable sense,
requires full advance knowledge of the response of one's opponent under
every possible variation from that position onward; this is not
forthcoming from human players, and even chess engines may employ
partial move randomization. A move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence, and
some moves that are bad in the short term may end up being good, or
even decisive, in the long term, in ways that are unpredictable at the
time they are made (because the subsequent move sequence is unknown and
unknowable). Even the blunder of a piece may result in the
repositioning of other pieces in a way that permits the blunderer to
force mate in some future position, i.e., a blunder may inadvertently
place the right piece in the right place at what (in a future position)
will be the right time; this is equivalent to a very long range
combination, except that it is inadvertent.

Let the position to be analyzed be the opening of the game from the
starting position, before White moves. There is no "best play" for
White. What criterion does one use for "best"? To achieve checkmate
in the shortest number of moves? The shortest mate possible is not a
static figure because subsequent moves alter the position and thus the
figure, and it is not generally possible ahead of time to know which
moves will be made by one's opponent; therefore nothing can be proven
except provisionally, and the conditions upon which this provisional
proof are predicated may change with subsequent moves. Furthermore,
there are many ways to checkmate in, say, 20 moves. Which of them is
"best"? Even in the case where a forced mate exists from a given
position, more than one forced mate of the same (shortest) number of
moves may be possible from that position. Furthermore, not every
position is guaranteed to result in a forced mate, and there may also
be many ways to draw in cases where it is possible to force a draw --
not to mention many ways to lose in cases where it is possible to lose!

For all of these reasons, it is not possible to "solve" chess.

Mark Adkins


  #8   Report Post  
Old September 11th 05, 10:53 PM
[email protected]
 
Posts: n/a
Default

P.S. To further clarify what I have written below: It is not even
theoretically possible to solve chess, no matter what the computing
power involved. Until a position is reached where a forced mate is
guaranteed, there is no move sequence proven to win; and because such
positions are always in advance of the starting position, a computer
will never be able to determine whether it (or its opponent) can force
mate until *after* some unknown (and unknowable) future move of its
opponent places the board in such a position.

wrote:
wrote:
Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be
made from any position. Therefore, it is POSSIBLE to determine best
play for any position by analyzing the tree of all possible moves for
that position all the way out to their game-ending state, exactly like
endgame databases do now.


It isn't possible, for two reasons: first, because there is no
meaningful definition of "best play" for *every* position; and second,
because even deciding what a "good" move is, in any provable sense,
requires full advance knowledge of the response of one's opponent under
every possible variation from that position onward; this is not
forthcoming from human players, and even chess engines may employ
partial move randomization. A move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence, and
some moves that are bad in the short term may end up being good, or
even decisive, in the long term, in ways that are unpredictable at the
time they are made (because the subsequent move sequence is unknown and
unknowable). Even the blunder of a piece may result in the
repositioning of other pieces in a way that permits the blunderer to
force mate in some future position, i.e., a blunder may inadvertently
place the right piece in the right place at what (in a future position)
will be the right time; this is equivalent to a very long range
combination, except that it is inadvertent.

Let the position to be analyzed be the opening of the game from the
starting position, before White moves. There is no "best play" for
White. What criterion does one use for "best"? To achieve checkmate
in the shortest number of moves? The shortest mate possible is not a
static figure because subsequent moves alter the position and thus the
figure, and it is not generally possible ahead of time to know which
moves will be made by one's opponent; therefore nothing can be proven
except provisionally, and the conditions upon which this provisional
proof are predicated may change with subsequent moves. Furthermore,
there are many ways to checkmate in, say, 20 moves. Which of them is
"best"? Even in the case where a forced mate exists from a given
position, more than one forced mate of the same (shortest) number of
moves may be possible from that position. Furthermore, not every
position is guaranteed to result in a forced mate, and there may also
be many ways to draw in cases where it is possible to force a draw --
not to mention many ways to lose in cases where it is possible to lose!

For all of these reasons, it is not possible to "solve" chess.

Mark Adkins


  #9   Report Post  
Old September 12th 05, 12:51 AM
[email protected]
 
Posts: n/a
Default


wrote:
wrote:
Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be
made from any position. Therefore, it is POSSIBLE to determine best
play for any position by analyzing the tree of all possible moves for
that position all the way out to their game-ending state, exactly like
endgame databases do now.


It isn't possible, for two reasons: first, because there is no
meaningful definition of "best play" for *every* position; and second,
because even deciding what a "good" move is, in any provable sense,
requires full advance knowledge of the response of one's opponent under
every possible variation from that position onward; this is not
forthcoming from human players, and even chess engines may employ
partial move randomization. A move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence, and
some moves that are bad in the short term may end up being good, or
even decisive, in the long term, in ways that are unpredictable at the
time they are made (because the subsequent move sequence is unknown and
unknowable). Even the blunder of a piece may result in the
repositioning of other pieces in a way that permits the blunderer to
force mate in some future position, i.e., a blunder may inadvertently
place the right piece in the right place at what (in a future position)
will be the right time; this is equivalent to a very long range
combination, except that it is inadvertent.

Let the position to be analyzed be the opening of the game from the
starting position, before White moves. There is no "best play" for
White. What criterion does one use for "best"? To achieve checkmate
in the shortest number of moves? The shortest mate possible is not a
static figure because subsequent moves alter the position and thus the
figure, and it is not generally possible ahead of time to know which
moves will be made by one's opponent; therefore nothing can be proven
except provisionally, and the conditions upon which this provisional
proof are predicated may change with subsequent moves. Furthermore,
there are many ways to checkmate in, say, 20 moves. Which of them is
"best"? Even in the case where a forced mate exists from a given
position, more than one forced mate of the same (shortest) number of
moves may be possible from that position. Furthermore, not every
position is guaranteed to result in a forced mate, and there may also
be many ways to draw in cases where it is possible to force a draw --
not to mention many ways to lose in cases where it is possible to lose!

For all of these reasons, it is not possible to "solve" chess.

Mark Adkins


You're wrong, and it's very simple to prove.

But, to start with the definition of "best play" that you asked for:
-- For any position that can be shown as won by the side to move, it is
the move(s) that result in the shortest mate.
-- For any position that is drawn, it is any move that does not turn
the position into a lost game.
-- For any position that can as lost by the side to move, it is the
move(s) that result in forcing the opponent to take the longest path to
mate.

This is exactly how DTM endgame databases define it, and they work very
well for that purpose.

But your argument about requiring "full advance knowledge of the
response of one's opponent" is completely beside the point. If you have
a won position, it doesn't matter what your opponent plays as long as
you still have a won position after your move. The same is true for a
drawn position. You also say that "a move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence", but
if there are 6 pieces left on the board, and I have all 6-man EGDB
files, there is no "potential" about it -- the move is not only either
"good or bad", but is actually "best play or not best play". The entire
set of legal moves for every position involving 6 men HAS been
determined to be either "best play or not best play".

Additionally, I never said that "solving chess" meant "finding a move
that wins". Your clarification in your follow-up post seems to imply
that this is something that I stated. But it is not true. I'm only
talking about finding "best play" from the starting position -- not a
WIN from the starting position.

So, if it has been already done for 6 pieces, why not 7, or 8, or 16 or
32? The exact same mechanism that has SOLVED chess for 6 pieces can
solve it for a larger number of pieces. And once it is done for all 32
pieces, (and it "only" needs to be solved from the starting position),
chess will be solved.

Whether the final result of chess is that it is drawn or won for White
remains to be seen.

jm

p.s. And, yes, I'm aware of all the technical issues involving
computing and storing the necessary data to get to this solution.
That's not part of this discussion. In a mathematical sense, but not
necessarily in a practical sense, chess can be solved.

  #10   Report Post  
Old September 12th 05, 03:19 AM
Guy Macon
 
Posts: n/a
Default




wrote:

It isn't possible, for two reasons: first, because there is no
meaningful definition of "best play" for *every* position; and second,
because even deciding what a "good" move is, in any provable sense,
requires full advance knowledge of the response of one's opponent under
every possible variation from that position onward; this is not
forthcoming from human players, and even chess engines may employ
partial move randomization.


You are wrong. Chess can be solved, given enough computing power and
storage. (The computing power and storage required might be to large
to fit in the universe, but that's another discussion...)

Here is a simple exercise that may help you to understand
your error:

Make a simple paper-and-pencil list that allows perfect play of the
game of tic-tac-toe. You should easily be able to make a "if in
this position make this move" list that results in perfect play.
You will have to make two lists so you can play X or O.

Note that there is indeed a meaningful definition of "best play"
for every possible tic-tac-toe position.

Note that you do *not* need "full advance knowledge of the
response of one's opponent under every possible variation from
that position onward." All you need to know is the present
position of the tic-tac-toe board and what move to make in
that position.

Note that it doesn't matter whether your opponent makes random
moves, and it doesn't even matter whether he has his own list
that allows him to play perfectly. You aren't considering any
of his future moves. You are just looking up the current
position on the list and making the move it tells you to make.

Note that it doesn't even take any brains to generate your list.
It can be generated by a stupid brute-force program with ease.

This being Usenet, There is at least a 90% chance that you will
either withdraw without further comment or defend your position.
If you choose to defend it, please explain the difference between
tic-tac-toe and chess other than the size and complexity of the
move tree being much larger in chess.

Also, please consider the fact that there exists a list such as
I described above for every possible chess position having six or
fewer men on the board. Please explain why someone with enough
computing power and storage couldn't do the same for seven or eight
man positions. Then explain why someone with enough computing power
and storage couldn't do the same for one particular thirty-two man
position.

--
Guy Macon http://www.guymacon.com/


Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
How long will it take to solve chess - please post a thousand replies Tiger Forest rec.games.chess.computer (Computer Chess) 3 September 30th 04 11:51 AM
What do you do when you can't solve a chess book problem? Advice please. Tushar Mithaiwala rec.games.chess.misc (Chess General) 6 February 27th 04 04:45 AM
No computer programs can solve this study! (and no, it is not retrograde) Bojan Basic rec.games.chess.computer (Computer Chess) 2 January 10th 04 11:45 PM
stuck trying to solve mate in 1 puzzle Jackie rec.games.chess.misc (Chess General) 2 December 6th 03 07:55 PM
Fritz 8 - Solve for mate MinnesotaKid rec.games.chess.computer (Computer Chess) 14 October 13th 03 08:17 AM


All times are GMT +1. The time now is 10:53 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017