Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old March 2nd 04, 10:20 AM
Death Eater Dan
 
Posts: n/a
Default Perfect Chess

Hi,
Are there any sources available online that discuss the mathematics of
calculating every possible chess board position and linking the positions
with every possible move. Obviously the number is far beyond what computers
are capable today, but I am interested in some exact numbers to predict how
much longer we will have to wait to see a computer play a 'perfect' game of
chess.

After much time and work, I believe I have calculated the exact number of
possible board positions. Has anyone else calculated such a number?

Cheers,
Dan


  #2   Report Post  
Old March 2nd 04, 12:17 PM
Will McGugan
 
Posts: n/a
Default Perfect Chess


"Death Eater Dan" wrote in message
...
Hi,
Are there any sources available online that discuss the mathematics of
calculating every possible chess board position and linking the positions
with every possible move. Obviously the number is far beyond what

computers
are capable today, but I am interested in some exact numbers to predict

how
much longer we will have to wait to see a computer play a 'perfect' game

of
chess.

After much time and work, I believe I have calculated the exact number of
possible board positions. Has anyone else calculated such a number?


I'd be impressed if you did! Sure you could calculate the number of possible
piece positions with basic arithmetic but that wouldn't be the whole answer.
You would have to throw out positions where the king is in check, and other
impossible positions. You'd also need to account for the 50 move rule, and 3
move repetition - boards with identical arangement of pieces are not
neccesary identical positions (eg has the rook or king moved).

But you did say after much time and work, so perhaps you have done it! Whats
the answer? Please show your working

Regards,

Will McGugan


  #3   Report Post  
Old March 2nd 04, 02:25 PM
Kerry Liles
 
Posts: n/a
Default Perfect Chess

Best of luck on your 'much time and work' - see this:

http://mathworld.wolfram.com/Chess.html

How does your answer compare?




"Death Eater Dan" wrote in message
...
Hi,
Are there any sources available online that discuss the mathematics of
calculating every possible chess board position and linking the positions
with every possible move. Obviously the number is far beyond what computers
are capable today, but I am interested in some exact numbers to predict how
much longer we will have to wait to see a computer play a 'perfect' game of
chess.

After much time and work, I believe I have calculated the exact number of
possible board positions. Has anyone else calculated such a number?

Cheers,
Dan




  #4   Report Post  
Old March 2nd 04, 06:27 PM
Mikko Nummelin
 
Posts: n/a
Default Perfect Chess

On Tue, 2 Mar 2004, Nanga Parbat wrote:

Death Eater Dan wrote:


Are there any sources available online that discuss the mathematics of
calculating every possible chess board position and linking the
positions with every possible move. Obviously the number is far beyond
what computers are capable today, but I am interested in some exact
numbers to predict how much longer we will have to wait to see a
computer play a 'perfect' game of chess.


After much time and work, I believe I have calculated the exact number
of possible board positions. Has anyone else calculated such a number?


I've once read an article that said that such a program was already
developped 50 years ago.


Any correctly programmed chess program which is based on full width search
and given infinite time and memory will do. Evaluation function needs to
care only for mate, stalemate, threefold rep. and 50-move rule.


Mikko Nummelin
  #5   Report Post  
Old March 2nd 04, 11:11 PM
George
 
Posts: n/a
Default Perfect Chess

"Death Eater Dan" wrote in message u...
Hi,
Are there any sources available online that discuss the mathematics of
calculating every possible chess board position and linking the positions
with every possible move. Obviously the number is far beyond what computers
are capable today, but I am interested in some exact numbers to predict how
much longer we will have to wait to see a computer play a 'perfect' game of
chess.

After much time and work, I believe I have calculated the exact number of
possible board positions. Has anyone else calculated such a number?

I can't believe that one can calculate it (correctly and accurately)
in a
time less than 8 years. Anyway i may be wrong and you may succeeded it
in a much shorter time.

But what correctly means? It means it has to be definitely a legal
position. So which are the illegal positions you should exclude? There
are the positions where one player is in check and it's not his move.
Also other countless types of illegal positions like:
8/8/5K2/8/2k5/1p6/1P6/B7 w - - that can't be reached with legal play.
BUT also you have to define if you will handle the positions, taking
into account the "En Passant" rule, or the "50 Move Rule", or the "3
Move Repetition" rule, or the "Stalemate"(??) rule, or the "Castle"
rule or the player turn. And this is important.
What this means? ###It means that if in one position X a player can
"Castle" and in the same position X the same player can't "Castle",
then how do you treat these 2 positions? Like one or like two? ###It
means that if in one position X a player can capture "En Passant" and
in the same position X the same player can't capture "En Passant",
then how do you treat these 2 positions? Like one or like two? ###It
means that if in one position X a player can "Castle" and capture "En
Passant" and in the same position X the same player can't "Castle",
and can't capture "En Passant" then how do you treat these 2
positions? Like one or like 2? ###It means that if in one position X a
player can make a move and draw with the "50 move rule" and in the
same position X the same player can't draw with the "50 move rule",
then how do you treat these 2 positions? Like one or like 2? ###And
generally all the combinations between them.
So although it's a matter of definition of: "possible positions in
chess"
and one can ignore the above rules, i think one should take into
account the above chess rules to be more general.

So you should first give how did you define the "possible positions
in chess" you are about to count(or that you have counted them), and
then calculate them.

Although i suspect that by saying "possible board positions" you
refer to only the possible legal positions and not taking account the
rules like "50 move rule", "Castle rule", etc... , if your number is
something like 10^40 then you
can write here the method and the number of course.


  #6   Report Post  
Old March 3rd 04, 09:24 AM
David Richerby
 
Posts: n/a
Default Perfect Chess

George wrote:
But what correctly means? It means it has to be definitely a legal
position. So which are the illegal positions you should exclude? There
are the positions where one player is in check and it's not his move.
Also other countless types of illegal positions like:
8/8/5K2/8/2k5/1p6/1P6/B7 w - - that can't be reached with legal play.


Just because a position can't be reached from the initial position doesn't
mean that it isn't a position. It could be set as a problem, for example.

BUT also you have to define if you will handle the positions, taking
into account the "En Passant" rule, or the "50 Move Rule", or the "3
Move Repetition" rule, or the "Stalemate"(??) rule, or the "Castle"
rule or the player turn. And this is important.


The 50-move rule and three-fold repetition are irrelevant. Any position
that can be reached after repetitions can be reached without those
repetitions. Even taking this into account, these two rules only _allow_
the claim of a draw; they do not mandate it. Stalemate is irrelevant:
just because one of the players is stalemated in a position doesn't make
it any less of a position. Castling and en-passant are relevant: the FIDE
laws of chess define two positions as being different if they allow
different combinations of castling and en passant.


Dave.

--
David Richerby Crystal Drink (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ refreshing juice beverage but it's
completely transparent!
  #7   Report Post  
Old March 5th 04, 06:27 PM
laocmo
 
Posts: n/a
Default Perfect Chess

I think, no matter how strong a chess engine can become, or how far it
can
see ahead, it will be limited by the quantum laws of nature and a
maybe
small but always present bit-error-rate as applied to the computer
itself.
In other words, even after an exhausting 100 ply search it will
occasionally
make a random error on its final choice of move. This random error may
mask a truley decisive move later in the search.
  #8   Report Post  
Old March 9th 04, 09:24 PM
Kelsey Bjarnason
 
Posts: n/a
Default Perfect Chess

[snips]

On Tue, 02 Mar 2004 20:27:37 +0200, Mikko Nummelin wrote:

Any correctly programmed chess program which is based on full width search
and given infinite time and memory will do. Evaluation function needs to
care only for mate, stalemate, threefold rep. and 50-move rule.


Actually... infinite time and memory don't apply. A chess game has an
upper bound on the number of turns involved (I *think* I recall Levy
suggesting the limit was 3150 moves) and there's a finite number of
options per move.

One estimate suggests an upper bound of some 10^120 positions. Assuming
the computer can examine one position per nanosecond, this would take
about a trillion, trillion [6 more of these] trillion times longer than
the universe has existed, it is not, technically, infinite.

On the other hand, you'll have plenty of time to bone up on opening theory
while the computer ponders its first move.


  #9   Report Post  
Old March 9th 04, 10:40 PM
David Richerby
 
Posts: n/a
Default Perfect Chess

Kelsey Bjarnason wrote:
One estimate suggests an upper bound of some 10^120 positions.


10^40-ish is the number I've heard. 10^120 is vastly too big: the crudest
possible upper bound comes from the observation that each of the sixty-
four squares is either empty or has one of twelve different types of piece
on it. 13^64 is about 10^71. And that includes the `position' where
every square has a white king on it. :-)


On the other hand, you'll have plenty of time to bone up on opening
theory while the computer ponders its first move.


Research was done recently that said that, if you want to buy a computer
to do a computation that will take longer than two years (I think), it is
better to invest the money that you were going to spend on the computer
and come back in a year. Then, the combination of the interest on the
investment (which means you have more money to spend on computers) with
the decreased price of higher-performance computers means that the
computation will finish sooner than it would have done if you'd bought
the best computer you could afford on day one.


Dave.

--
David Richerby Dangerous Love Bulb (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a light bulb that you can share with
someone special but it could explode
at any minute!
  #10   Report Post  
Old March 10th 04, 03:01 PM
Anders Thulin
 
Posts: n/a
Default Perfect Chess

David Richerby wrote:

10^40-ish is the number I've heard. 10^120 is vastly too big:


Depends entirely on what state you include. 10^40 is on the
order of how many ways you can place the pieces in the original
array on a chess board without taking the laws of chess into consideration
-- and it's high, as it includes pawns on first and last row, and
other impossible positions.

But as promoted pieces aren't included, it's also too low.
2*10^52 is said to be a better estimate.

However, if the position includes state such as 50-move clock
and/or count of repeated positions, you get a lot more positions ...


--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
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



All times are GMT +1. The time now is 01:36 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