Mathematical Resolution Of Chess
Marcel van Kervinck
GrahamLaight wrote:
: In one of the "The Art Of Programming" books by Donald Knuth, he states that
: problems like chess defy analytical solution.
: How does he know?
: Does anyone know if any serious work has been done to try to resolve (or at
: least play better) chess mathematically?
Plenty of work has been done. Zermelo showed how to solve chess
mathematically in the 1930s. I don't know exactly where Knuth
makes his statement. He has formally proven the correctness
of the alpha-beta search algorithm in the 1970s. Perhaps you
need to quote him more accurately.
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| bue...@urc.tue.nl
graham_laight
In one of the "The Art Of Programming" books by Donald Knuth, he states that
problems like chess defy analytical solution.
How does he know?
Does anyone know if any serious work has been done to try to resolve (or at
least play better) chess mathematically?
Simple geometric formulae should allow you to see where pieces can get to n
moves ahead. And in numerical analysis, there are recursive formulae for grids
to find out weightings of grid positions based on the calculated weightings of
grid positions surrounding them. My intuition is that you could build a program
based on mathematics if you tried.
brucemo
Go for it. Report back when finished.
bruce
graham_laight
In article <4ud9jh$k...@tuegate.tue.nl>, bue...@asterix.urc.tue.nl says...
>
>GrahamLaight wrote:
>: In one of the "The Art Of Programming" books by Donald Knuth, he states that
>: problems like chess defy analytical solution.
>
>: How does he know?
>
>: Does anyone know if any serious work has been done to try to resolve (or at
>: least play better) chess mathematically?
>
>mathematically in the 1930s. I don't know exactly where Knuth
>makes his statement. He has formally proven the correctness
>of the alpha-beta search algorithm in the 1970s. Perhaps you
>need to quote him more accurately.
Marcel, Thankyou for your reply.
OK I haven't read Donald Knuth since 1984, and the statement, made casually, comes,
as far as I remember, in a section about writing programs to generate game trees.
Zermelo's work sounds interesting - do you know if it is in print? If not, could
you tell us, briefly, how he believes chess can be solved, please?
graham_laight
Sorry to start a new thread when there was already one there, but my copy
of the newsgroup has lost everything posted before Sunday.
If anyone knows of anything I can read of work done on attempts to resolve (or
play better) chess mathematically, could you please mail me at the address below
or reply here.
A gentleman from Holland had replied, but I've lost his reply and his e-mail
address now. Thanks to him - but could he re-post or mail me privately please?
Komputer Korner
Graham, Laight wrote:
>
> Sorry to start a new thread when there was already one there, but my copy
not attemt to show legality of positions or no. of positions that could be reached in a
normal chess game.
a programme to count all possible distributions. Here are the results:
(the first number in each line specifies the number of chessmen which
are on the board)
0 1.00000000000000E+0000
1 7.68000000000000E+0002
2 2.82240000000000E+0005
3 6.60791040000000E+0007
4 1.10669791680000E+0010
5 1.41123617510400E+0012
6 1.42390120115712E+0014
7 1.16633837020954E+0016
8 7.89728074625821E+0017
9 4.47876247780741E+0019
10 2.14860450983861E+0021
11 8.78575016063924E+0022
12 3.08071500859834E+0024
13 9.30990640171747E+0025
14 2.43527272051156E+0027
15 5.53599569784193E+0028
16 1.09792825396875E+0030
17 1.90708105480270E+0031
18 2.91257894836325E+0032
19 3.92604874203569E+0033
20 4.68713768635647E+0034
21 4.96954373601900E+0035
22 4.68630481206492E+0036
23 3.92962279471786E+0037
24 2.92328856899730E+0038
25 1.92039016495760E+0039
26 1.10606844418109E+0040
27 5.52580750219879E+0040
28 2.35457308380588E+0041
29 8.31347462279611E+0041
30 2.30497103042602E+0042
31 4.49428043208515E+0042
32 4.63472669558781E+0042
total number of chessmen distributions: 1.25693589378386E+0043
This number has still be unterstood as an upper boundary,
since you have to consider that
- the game is over when one king is missing
- there`s a black-white-symmetry
- there`s a left/right symmetry
If only 2 bits are stored for every bord distributions, the amount
of required memory keeps huge. To tackle this problem intelligent
compression schemes could be applied - no I don`t know which one;
I encourage everybody to think about this problem.
An interesting result of my computation is, that the number of
of all distributions is strongly dominated by those distributions
whith roughly the equal number of black and white chessmen.
The blank line indicates the status-quo of end-game-tables
used by deep blue (deepblue). With this table you can estimate
the power of chessprogrammes as a function of the available
hardware power.
How have I calulated those numbers?
12
-- 64!
\ ----------------------------
/ __ __
-- ( || n ! )( 64- \ n )!
i=1 i i / i
--
You have to add all terms with ni running this way:
n1=0..8
n2=0..8
n3=0..1
n4=0..1
n5=0..1
n6=0..1
n7=0..2
n8=0..2
n9=0..2
n10=0..2
n11=0..2
n12=0..2
Don't forget, this was posted by Daniel Gembris. I would hope that Andy Walker would
verify these no.
--
Komputer Korner
graham_laight
In article <32101F...@netcom.ca>, Komputer says...
{snip}
{snip}
This is a good and important piece of work. Thankyou KK for bringing it back up.
Does anyone know of any work that has been done in terms of applying maths to the
selection of moves?
And if this work was unsuccessful, why was it so?
A method of using maths to help with move selection could bypass all the problems
of generating a game tree.
A simple example of maths avoiding computer work lies in analysing the UK
lottery: a simple way to do this would be to generate all possible tickets one
by one, and "evaluate" the value of each ticket against every other possible
ticket. There are about 14,000,000 combinations, so to compare each ticket
against every other would require 1.4 E7 squared loops - or about 2 E14 loops.
If you're using a pocket computer, the batteries would go flat before it
finished! However, all readers of this newsgroup will know that a probability
expert would calculate the percentages of each type of win before the batteries
were aware that they were out of the packet.
Chess is a much tougher nut to crack than probability, but the tools for the job
are better as well these days - what with mathcad, mathmetica etc. Could it be
that it has been seriously attempted, but that mathematicians will only ever
reveal things that they've done which have been successful - and they've managed
to neither demonstrate nor refute the idea that maths can help in move
selection?
Komputer Korner
There is another very important no. we are all forgetting. That is the
total no. of tablebases. By that I mean the total no. of different piece
and pawn configurations. It seems to be easy to calculate but I am not a
mathematician, so we need help here. For 32 pieces, there is only 1
piece configuration. For 31 pieces, there are 30 piece configurations.
For 30 pieces, there are 30C28 piece configurations etc....or am I on
the wrong track here? OOOPS,There is another problem that I haven't
taken into account, the fact that there are 8 pawns and 2 knights and 2
rooks on each side. Help!!! we need a mathematician here !!
--
Komputer Korner
Claude Chaunier
Komputer Korner wrote:
> There is another very important no. we are all forgetting. That is the
> total no. of tablebases. By that I mean the total no. of different piece
> and pawn configurations. It seems to be easy to calculate but I am not a
> mathematician, so we need help here. For 32 pieces, there is only 1
> piece configuration. For 31 pieces, there are 30 piece configurations.
> For 30 pieces, there are 30C28 piece configurations etc....or am I on
> the wrong track here? OOOPS,There is another problem that I haven't
> taken into account, the fact that there are 8 pawns and 2 knights and 2
> rooks on each side. Help!!! we need a mathematician here !!
> --
> Komputer Korner
Why should it be important? Anyway,
without promoted pieces your number would be:
9x3x3x3x2 x 9x3x3x3x2 = 486 x 486 = 236196
according to how many black pawns, knights, etc.
and white pawns, knights, etc. there are.
But with promotion there could be 10 black knights
if there were no black pawns and a sufficient
number of captured white pieces. A short computer
enumeration is more likely to give you a tight
upper bound than mathematics on paper.
Komputer Korner
I don't understand your no.'s. in the section w/o promotions.
--
Komputer Korner
Claude Chaunier
Komputer Korner wrote:
> I don't understand your no.'s. in the section w/o promotions.
Sorry I was rather enigmatic. Imagine I choose a tablebase and
I want you to guess it. Now you ask me how many black pawns there
are, then how many black knights, etc., and the same for the white
pieces. With my answers you are able to know which tablebase I
have in mind. (I mean which name of a tablebase I have in mind :)
Therefore we can uniquely identify a tablebase with 10 numbers.
More precisely, with the ordered list of 10 number. The first
number, between 0 and 8 included, would say how many black pawns
there are. The second number, between 0 and 10, would say how
many black knights there are. etc.
Now, if promotion is not allowed, the 10 numbers are totally
independant. We can choose any number between 0 and 8 included
for the first number. Whatever the others numbers are. We can
also choose any number between 0 and 2 included for the second
number. Whatever the first number and the others are. etc. There
shall always be a non-empty corresponding tablebase.
Since there are 9 different choices for the number of black
pawns, the first number, 3 independant different choices for
the number of black knights, 3 for black bishops, 3 for black
rooks, 2 for black queens (remember, no promotion), 9 for
for white pawns, 3 for white knights, 3 for white bishops,
3 for white rooks and finally 2 independant different choices
for the number of white queens (there could be 0 or 1 white
queen), there are finally
9x3x3x3x2 x 9x3x3x3x2 = 486 x 486 = 236196
'tablebases' without promotion having occured earlier.
Regards.
graham_laight
I thought I'd rename the thread in the hope that someone knows something about
the subject I'm really interested in! If you do, and you don't want to go public,
you can reach me at Graham...@largotim.co.uk
In article <321261...@netcom.ca>, Komputer says...
>Claude Chaunier wrote:
>>
>> Komputer Korner wrote:
{snip}
>> Why should it be important? Anyway,
Hear hear! If you want to talk about cracking chess with knowledge, you should be
talking to Chris Whittington. I'd just like to say 2 quick things about that:
* In "Chess Skill In Man And Machine", one of the best books ever written, I
vaguely remember them saying that a grandmaster has expert knowledge on 50,000
different positional patterns - so this is what the Whittington brigade should
be aiming for
* In the CS-Tal games I've played through, apart from the odd brilliant sacrifice,
CS-Tal seems to play much like any other computer
>> without promoted pieces your number would be:
>>
>> 9x3x3x3x2 x 9x3x3x3x2 = 486 x 486 = 236196
>>
>> according to how many black pawns, knights, etc.
>> and white pawns, knights, etc. there are.
>> But with promotion there could be 10 black knights
{snip}
>I don't understand your no.'s. in the section w/o promotions.
This is a standard combination calculation. There are 9 different combinations of
pawn numbers (0-8), three different combinations of rook numbers, three
combinations of knight numbers, three combination of bishop numbers, and two
combinations of queen numbers (0 or 1). To get the total numbers of combinations,
you multiply the individual combinations together. But I agree with Claude - I
don't think this is a useful number:
* It takes no account of pawn promotion
* It would take more than a table base entry to know how to play all the
different positions that could arise within a combination of pieces. I think
that maybe "Chess Skill In Man And Machine" already had it sussed all those
years ago.
To get to the point, however, I am interested in knowing whether any good
mathematicians have ever tried to resolve the problem of SELECTING A GOOD MOVE
mathematically - saving on all the computer time needed to do game tree
generation, and hence enabling the machine to play better chess in the same
amount of time. I instinctively believe it can be done - I just want to know if
anyone has tried it, and if they've been open enough to share the results with
the rest of the world.
Come on - someone out there must know something on this subject!
gerhard_kohl
>>
>> Sorry to start a new thread when there was already one there, but my copy
>>Daniel Gembris posted this some time ago. Please note the no. is an upper bound and does
>not attemt to show legality of positions or no. of positions that could be reached in a
>normal chess game.
>
> - the game is over when one king is missing
> - there`s a black-white-symmetry
> - there`s a left/right symmetry
>
> If only 2 bits are stored for every bord distributions, the amount
> of required memory keeps huge. To tackle this problem intelligent
> compression schemes could be applied - no I don`t know which one;
> I encourage everybody to think about this problem.
>
> An interesting result of my computation is, that the number of
> of all distributions is strongly dominated by those distributions
> whith roughly the equal number of black and white chessmen.
>
> The blank line indicates the status-quo of end-game-tables
> used by deep blue (deepblue). With this table you can estimate
> the power of chessprogrammes as a function of the available
> hardware power.
>
It is often said that the number of possible chess games is > 1 E125.
But there are 6 different pieces (RKBQKP), 2 colors, and blank squares, making
13 possibilities per square. There are 64 squares, so the upper bound for the
number of possible positions is 13/\64 = 2 E71.
The number of legal and attainable positions is only a small proportion of this
number.
Komputer Korner
Can we attribute the difference between the 2 no. 10^43 and 2x10^71 as
being because not all squares can have pawns on them or are there other
differences?
--
Komputer Korner
Nathalie HEURTAULT
> Gerhard Kohl wrote...
> It is often said that the number of possible chess games is > 1 E125.
> But there are 6 different pieces (RKBQKP), 2 colors, and blank squares,
making
> 13 possibilities per square. There are 64 squares, so the upper bound
for the
> number of possible positions is 13/\64 = 2 E71.
>
> The number of legal and attainable positions is only a small proportion
of this
> number.
>
You're talking about positions, not games, and there are far more chess
games than chess positions...
Jeff
Wolfgang Kuechle
Gerhard, Kohl wrote:
> It is often said that the number of possible chess games is > 1 E125.
> But there are 6 different pieces (RKBQKP), 2 colors, and blank squares, making
> 13 possibilities per square. There are 64 squares, so the upper bound for the
> number of possible positions is 13/\64 = 2 E71.
>
> The number of legal and attainable positions is only a small proportion of this
> number.
on the board.
Kind regards,
Wolfgang Kuechle
graham_laight
The following is interesting, but doesn't answer my REAL question - does anyone
know of any work done by a mathematician in terms of using mathematics to help
select chess moves without having to generate a game tree???
In article <32139C...@netcom.ca>, Komputer says...
>
>Gerhard, Kohl wrote:
>>
>> In article <32101F...@netcom.ca>, Komputer says...
>> >
>> >Graham, Laight wrote:
>> >>
>>
>>
>> It is often said that the number of possible chess games is > 1 E125.
>> But there are 6 different pieces (RKBQKP), 2 colors, and blank squares, making
>> 13 possibilities per square. There are 64 squares, so the upper bound for the
>> number of possible positions is 13/\64 = 2 E71.
>>
>> The number of legal and attainable positions is only a small proportion of this
>> number.
>
>
>Can we attribute the difference between the 2 no. 10^43 and 2x10^71 as
>being because not all squares can have pawns on them or are there other
>differences?
>--
>Komputer Korner
In Gerhard's model, you can have any number of any piece, which is clearly going
to go way to high.
Daniel's number gives us an upper bound for the number of possible positions. The
number 10^125 comes from the idea that there are an average of 30 choices in
a position, and an average of 85 (half) moves to a result - hence there are
30^85 games possible = 10^125 (roughly).
To go back to Daniel's model of 2 E43 positions being possible, and combining it
with the 85 move average game, an upper bound for the max possible games would
be 2 E43!/(85! * (2 E43 - 85)!). This is calculating on the same basis as
combinations in the UK lottery, which is 6 numbers out of 49, giving
49!/(6! * 43!) possible tickets - = 14 million. The chess number is too big to
calculate exactly, so I'll do it with base 10 logs. To make it easier to
calculate, I'm going to say that 2 e43!/(2 e43 - 85)! is equal to, within my
rounding errors, 2 e43 ^85. This leaves (2 e43 ^85)/85!
This equals 10^(log(2 e43) * 85 - log(85!)), which is roughly 10^3552
Of course, it's not really possible to have any combination of 85 legal positions
in a game, so the number is way to high. Oh well.
Kevin James Begley
GrahamLaight wrote:
: To get to the point, however, I am interested in knowing whether any good
: mathematicians have ever tried to resolve the problem of SELECTING A GOOD MOVE
: mathematically - saving on all the computer time needed to do game tree
: generation, and hence enabling the machine to play better chess in the same
: amount of time. I instinctively believe it can be done - I just want to know if
: anyone has tried it, and if they've been open enough to share the results with
: the rest of the world.
: Come on - someone out there must know something on this subject!
OK, suppose their was such a mathematics which could be used
to select a move -- what would it look like? Would it first
calculate which piece had to move, and then where? Would it
simply calculate that a square needed defending, and then
calculate which of the pieces should be moved to defend? Or,
would it just crunch out the mother of all exclaims without
a single constraint, or search?
I submit to you that developing such a "math" is equivalent
to reducing the endgame tables size by a few magnitude.
You may disagree, but the problem is essentially the
same, except that the entire game is much more complex.
Still, if you could represent the positions as binary,
then the problem boils down to running a collosal iterative
consensus on the entire database, until you can find a
winning line by applying the resulting minimized equation
which provides full coverage.
Sub-optimal moves might be added to the database (provided
they are both winning, and non-cyclical) in the form of
"don't care" terms, to assure optimally minimal equations.
Still, you'd be a long way from having the perfect
evaluation function, but you'd have something that would
solve ALL of the positions that you fed it. And, you don't
have to limit it's consumption to endgames, but, you should
be absolutely certain about a position before including its
move into the database.
I think if you try this, you'll probably soon find that the
resulting equation only compresses the database by %60 or so.
Which is to say, that the equation may exist, but is nearly
non-intelligible, and far too complex, and far too difficult
to calculate. You are probably thinking to yourself, if it's
non-intelligible, how can humans play? Well, humans can
ignore terms at their discretion, and we ignore a vast
number of irrelevant (and sometimes very relevant)
information (terms). For that reason, we can sometimes play like
a GM, and sometimes like a real moron.
Building a machine that can ignore terms (like humans can)
is an interesting problem, but hardly worthwhile when
you consider that there are plenty of human thinkers
around already.
If there is an equation, a simple equation, then this
approach attempts to "curve-fit" it based upon known
data. But, we don't know enough data yet, and the
data we do have is staggering. We don't even know
what kind of curve we are dealing with (polynomial,
exponential, logarithmic) here! The universe that we
know is made up of simple laws -- and, you probably
have the intuition that everything must be made up of
beautiful, simple, elegant laws (why not chess?).
But, consider for a moment if these laws are in fact
simple only _because_ we understand them! Consider
the possibility that they are actually special cases
of special cases of what is an extremely complex
arrray of laws which our pea-brains couldn't begin
to understand.
I'm trying to tell you that your intuition may need
adjustment. Something about us humans, we want
everything to be simple -- we want the universe
to be made up of rational, real numbers, and revolving
about the earth based upon the mother of all grand
unification theories like the music of the spheres.
But, then there's pi, and that imaginary number,
and the sun, and gravity, and a bunch of noise
out there in space. And then, there's chess...
And, after all that, we still talk about
_transcending logic_ as if our intuition were
our greatest faculty. I submit to you that
human intuition and $350K could buy a house in
the Bay Area, nothing more. Of course, I might
just be saying this because I want to motivate
you to prove me wrong -- you decide which (use
your ...um...uh...well you decide).
Kevin.
Tina Long
Claude Chaunier <chau...@handy.univ-lyon1.fr> wrote:
>there are finally
> 9x3x3x3x2 x 9x3x3x3x2 = 486 x 486 = 236196
>'tablebases' without promotion having occured earlier.
>Regards.
I thought so, what was the question again?
graham_laight
Kevin,
Thankyou very much for this post. I'm so glad that someone, somewhere, is
prepared to put their oar in the water on this subject - I was beginning to
wonder what was wrong with it. Now we can have dialogue instead of monologue.
What you seem to be saying, Kevin, is that chess belongs to a category of problem
which is too difficult to resolve with today's tools - and you ask what a
math program to resolve chess would look like.
To take the second point first, a program that could play perfect chess would
look like a nim player. In nim, you have several piles of matchsticks, and on
your turn, you may remove as many matchsticks from any pile as you like (there
are variations in the rules, but in essence it's the same game). The object of
the game is to be the last person to take the last matchstick(s) so that your
opponent cannot move. The insight you need to make a computer play the game
perfectly, is that every position is either "winning" or "losing". If you are in
a "winning" position, you must take the right number of matchsticks froma pile
to put your opponent in a "losing" position. Keep on doing this, and eventually
your program will win.
To apply this to chess, you program your computer so that, on it's turn, it looks
at every legal move it has, and determines whether this is winning or losing in
(say) the next 50 moves. Having done this, just pick one of the winning moves
and avoid all of the losing moves (if you can).
The other question Kevin challenges with is this: can this be done?
It is true that occasionaly scientists pick a bad problem, which turns out to
be impossibly difficult to solve. Look at the sums of money that were spent
trying to do computer language translation in the sixties. Turned out to be a
tougher nut to crack than first expected - still unsolved. And visual interpretation -
of it weren't for the example of the human eye, experts would have long ago have
abandoned it as an impossible task.
In the case of chess, I believe maths could make an enormous contribution, but
the way things are going, the problem of making computers play better than humans
will be resolved by knowledge before it gets done by maths, making it a less
interesting problem for a mathematician to look at.
If no-one can tell me of any work done to try to resolve chess by maths, I must
assume that any work done has not been successful enough for the author to publish,
otherwise there would be world beating computers out there.
Aren't there any mathematicians out there who are a little bit miffed that a
simple looking man made game, developed nearly two thousand years ago, is still
beyond their wit to resolve?
In article <4v2u5o$j...@mark.ucdavis.edu>, kjbe...@chimi.engr.ucdavis.edu says...
>
>GrahamLaight wrote:
>: To get to the point, however, I am interested in knowing whether any good
>: mathematicians have ever tried to resolve the problem of SELECTING A GOOD MOVE
>: mathematically - saving on all the computer time needed to do game tree
>: generation, and hence enabling the machine to play better chess in the same
>: amount of time. I instinctively believe it can be done - I just want to know if
>: anyone has tried it, and if they've been open enough to share the results with
>: the rest of the world.
>
>: Come on - someone out there must know something on this subject!
>
>OK, suppose their was such a mathematics which could be used
>to select a move -- what would it look like? Would it first
>calculate which piece had to move, and then where? Would it
>simply calculate that a square needed defending, and then
>calculate which of the pieces should be moved to defend? Or,
>would it just crunch out the mother of all exclaims without
>a single constraint, or search?
>
>I submit to you that developing such a "math" is equivalent
>to reducing the endgame tables size by a few magnitude.
>You may disagree, but the problem is essentially the
>same, except that the entire game is much more complex.
From time to time, people get stuck in a groove - thinking that what's true today
will always be true. In 1989, the accepted wisdom in the UK was that house prices
would never fall - and people would bid up house prices to outrageous levels.
In the South East of the UK, house prices then fell by over a third!
Today the prevailing doctrine in chess is that tables are the great white hope.
Lets hope that someone comes up with something better - soon.
>
>Still, if you could represent the positions as binary,
>then the problem boils down to running a collosal iterative
>consensus on the entire database, until you can find a
>winning line by applying the resulting minimized equation
>which provides full coverage.
>
>Sub-optimal moves might be added to the database (provided
>they are both winning, and non-cyclical) in the form of
>"don't care" terms, to assure optimally minimal equations.
>
>Still, you'd be a long way from having the perfect
>evaluation function, but you'd have something that would
>solve ALL of the positions that you fed it. And, you don't
>have to limit it's consumption to endgames, but, you should
>be absolutely certain about a position before including its
>move into the database.
>
>I think if you try this, you'll probably soon find that the
>resulting equation only compresses the database by %60 or so.
>Which is to say, that the equation may exist, but is nearly
>non-intelligible, and far too complex, and far too difficult
>to calculate. You are probably thinking to yourself, if it's
>non-intelligible, how can humans play? Well, humans can
>ignore terms at their discretion, and we ignore a vast
>number of irrelevant (and sometimes very relevant)
>information (terms). For that reason, we can sometimes play like
>a GM, and sometimes like a real moron.
If you only select moves at random, over 3% of your moves will be of grandmaster
standard anyway! Therefore, by random selection, you've got about the same
chance of making 9 successive GM moves as you have of winning the UK lottery.
>
>Building a machine that can ignore terms (like humans can)
>is an interesting problem, but hardly worthwhile when
>you consider that there are plenty of human thinkers
>around already.
The idea is to use maths to bypass the issue - resolve the good, the bad, and the
ugly all in mathematical equations that can see them all. There are loads of
equations that can solve problems that would take masses of computer time to do
them in a more simplistic way.
>
>If there is an equation, a simple equation, then this
>approach attempts to "curve-fit" it based upon known
>data. But, we don't know enough data yet, and the
>data we do have is staggering. We don't even know
>what kind of curve we are dealing with (polynomial,
>exponential, logarithmic) here! The universe that we
>know is made up of simple laws -- and, you probably
>have the intuition that everything must be made up of
>beautiful, simple, elegant laws (why not chess?).
>But, consider for a moment if these laws are in fact
>simple only _because_ we understand them! Consider
>the possibility that they are actually special cases
>of special cases of what is an extremely complex
>arrray of laws which our pea-brains couldn't begin
>to understand.
Anyone of normal intelligence can understand anything - if it's explained to them
in a straightforward way.
>
>I'm trying to tell you that your intuition may need
>adjustment. Something about us humans, we want
>everything to be simple -- we want the universe
>to be made up of rational, real numbers, and revolving
>about the earth based upon the mother of all grand
>unification theories like the music of the spheres.
>But, then there's pi, and that imaginary number,
>and the sun, and gravity, and a bunch of noise
>out there in space. And then, there's chess...
What's wrong with pi? It's the circumference of a circle divided by the diameter.
Maths for 10 year olds. "That imaginary number"? Which one? There's millions of
them. The sun? A mass of heavy water under sufficient temperature & pressure to
enable nuclear fusion to take place at a slow rate. Gravity? Isaac Newton sussed#
out the rules for its behaviour hundreds of years ago. Noise in space? Wouldn't
you expect there to be electromagnetic noise in space? Chess? Easy game to play.
It's just that it would be nice to consistently beat the grandmasters!
>
>And, after all that, we still talk about
>_transcending logic_ as if our intuition were
>our greatest faculty. I submit to you that
>human intuition and $350K could buy a house in
>the Bay Area, nothing more. Of course, I might
You must be American. Most of us think we could make better use of $350K then
that. It's not always the deepest pockets that get to the answers first...
>just be saying this because I want to motivate
>you to prove me wrong -- you decide which (use
>your ...um...uh...well you decide).
I'd love to prove you wrong - its just that unfortunately, linear algebra,
numerical analysis and discrete mathematics are the subjects I
believe are needed to attack the problem. Unfortunately, they were not my strong
subjects at university.
>
>Kevin.
>
Regards - Graham
Hans Havermann
Komputer Korner <kor...@netcom.ca> wrote:
> a programme to count all possible distributions. Here are the results:
> (the first number in each line specifies the number of chessmen which
> are on the board)
>
> 0 1.00000000000000E+0000
> 1 7.68000000000000E+0002
> 2 2.82240000000000E+0005
> 3 6.60791040000000E+0007
> 4 1.10669791680000E+0010
etc. to
> 32 4.63472669558781E+0042
Komputer Korner points out that the numbers *are* upper bound with no
attempt to distinguish legality. Legal chess positions become
progressively more difficult to discern as the number of pieces on the
board increase, but this should not constrain us from calculating
*actual* numbers for a small number of pieces.
There are, of course, no positions for zero or one piece. Assuming that
Black/White and Left/Right are *not* interchangeable (symmetry will only
complicate calculations when more pieces are introduced), for two pieces
(both necessarily Kings), I believe there are 3612 board positions.
Three pieces yield 2127600; and four pieces, 1205537008 *minus* the
number of boards that have both Kings in check.
These calculations were done by hand a number of years ago and I would
not be overly surprised if they were wrong. I would expect the number of
legal board positions for 32 pieces to be relatively small (nowhere near
10^42) because of the impossibility of pawns passing each other, etc.,
but the actual number might be fiendishly difficult to calculate. Any
logically-thinking number-crunchers out there?
--
Nature requires five,
Custom allows seven,
Idleness takes nine,
And wickedness eleven.
Kevin James Begley
ppo.com>
Organization: College of Engineering - University of California - Davis
Distribution:
GrahamLaight wrote:
: Kevin,
: Thankyou very much for this post. I'm so glad that someone, somewhere, is
: prepared to put their oar in the water on this subject - I was beginning to
: wonder what was wrong with it. Now we can have dialogue instead of monologue.
: What you seem to be saying, Kevin, is that chess belongs to a category of
: problems which is too difficult to resolve with today's tools - and you
: ask what a : math program to resolve chess would look like.
Well, I'm not just arguing that it's "too difficult." Such an argument
would, after all, be immune to rebutal were it not for my concrete
example of what makes it "too difficult." Matchsticks, which I presume
has been solved mathematically, I argue, is in another category altogether.
Why? because, if you construct a database of winning positions for that
game, I argue that you could determine a set of rules which would allow
for considerable reduction in the space needed to store these positions.
In other words, a rule would be found that eliminates 20 positions, and
another rule found that eliminates 20 more, and the two rules could be
merged into one rule, and so on until every position is covered by a
considerably small set of rules.
I argue that this is not the case in chess. But, more than just state
what my feeling is in this matter, I argue that one cannot reduce the
size of a simple endgame database by a significant percentage, and if
this is the case, then certainly, one cannot reduce the entire game
into a few rules.
Finding mathematical rules for chess is akin to an iterative consensus
of terms. Consider that if we somehow knew all winning moves for all
positions, and we somehow could assure that no cycles would result from
these "winning" moves, and if we had the position & moves stored as
binary files somewhere, then we could simply solve for a minimum
coverage of these positions. It might take forever for the algorithm
to crunch out the equation, but that''s not the point -- the point
is, in theory, it is equivalent to building a mathematical method.
The point is, if one cannot obtain significant reduction in space from
a small set of simple endgames, then one certainly cannot be expected
to reduce the game itself into any small set of rules.
It seems we are at a standoff until someone can provide data
on the minimization yeilded by some simple (but unrelated)
endgames. I would suggest K&R vs K, and K&B&N vs K endgames,
since they should be unrelated enough, and well enough known.
If these can in fact be reduced together into a small set of
equations, then, certainly, there is potential in your idea
for searching for a mathematical solution. If there is not
a significant minization yeild, then we can be quite sure
that any solution will be nearly as complex as entire database
of positions itself, and therefore, would be, as I suggest it
is, a complete waste of time.
Kevin.
Hauke Reddmann
Hans Havermann (ha...@astral.magic.ca) wrote:
:
: These calculations were done by hand a number of years ago and I would
: not be overly surprised if they were wrong. I would expect the number of
: legal board positions for 32 pieces to be relatively small (nowhere near
: 10^42) because of the impossibility of pawns passing each other, etc.,
: but the actual number might be fiendishly difficult to calculate. Any
: logically-thinking number-crunchers out there?
Let's see: On every rank, there are 15 legal pawn positions.
15^8*50^16 (the latter an upper estimate for the rest of the figures)
<10^37 indeed.
--
Hauke Reddmann <:-EX8
fc3...@math.uni-hamburg.de PRIVATE EMAIL
fc3...@rzaixsrv1.rrz.uni-hamburg.de BACKUP
redd...@chemie.uni-hamburg.de SCIENCE ONLY
John P DeMastri
The point is that the rules for "nim" are determined by examining the
COMPLETE GAME TREE!!! This is not available for chess. Therefore that
analogy, and all of the related analysis is not helpful. The complete
chess tree won't be available until CM6000.
That last sentence was a joke. The rest was not.
Tim Firman
Hauke Reddmann wrote:
>
> Hans Havermann (ha...@astral.magic.ca) wrote:
> : relatively small (nowhere near
> : 10^42) because of the impossibility of pawns passing each other, etc.,
> 15^8*50^16 (the latter an upper estimate for the rest of the figures)
> <10^37 indeed.
Hmmm... pawns don't move linearly when they capture. There are a
lot more than 15 legal pawn positions per rank. I'm not sure what
you mean by pawns can't pass each other, but nothing precludes an
indirect pass through a capture...
I think there are 1*3*3*3*3*3*3*1=6561 legal positions per rank,
corresponding to empty/white pawn/black pawn possibilities.
plus you'd have to take into account promotion of pawns...
dividing it up this way does not help simplify the problem.
Tim
Kenneth Sloan
In article <321A31...@ils.nwu.edu>,
John P DeMastri <dema...@ils.nwu.edu> wrote:
>The point is that the rules for "nim" are determined by examining the
>COMPLETE GAME TREE!!!
If you think this is the point, then you have missed the point.
NIM can be played perfectly without generating *any* of the game tree,
much less *all* of it. It turns out that you can perfectly evaluate any
NIM position. If it is your turn to move, and the position is LOST -
then there is absolutely nothing you can do about it. If it is WON,
then you can always make a move which generates a position which is LOST
for your opponent - the point is that you can do this without any
lookahead whatsoever.
> This is not available for chess.
The complete game tree is not available (and probably never will be).
The open question is whether or not there is a procedure which can
evaluate positions perfectly without lookahead. The failure to produce
such a beast does not prove that it doesn't exist.
Notice that it *may* be possible to perfectly evaluate positions IFF you
also lookahead some number of ply; call this number P. For NIM, the
value of P is 0. For Chess, it is very likely that P > 10. Suppose
that, for Chess, P=20. Then, Chess may eventually be soluble. All we
need to do is:
*improve the technology so that full-width A-B search to depth 20
is feasible
*discover the evaluation function which works perfectly when
coupled with 20-ply search
--
Kenneth Sloan sl...@cis.uab.edu
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/
Hans Havermann
Tim Firman <fir...@lombardi.chem.wisc.edu> wrote:
> Hmmm... pawns don't move linearly when they capture. There are a
> lot more than 15 legal pawn positions per rank. I'm not sure what
> you mean by pawns can't pass each other, but nothing precludes an
> indirect pass through a capture...
Hauke Reddmann was calculating an (upper bound) number of legal board
positions when *all* 32 pieces are (still) on the board. Thus nothing
has been captured.
Hans Havermann
Hauke Reddmann <fc3...@AMRISC02.math.uni-hamburg.de> (in calculating
the number of legal chess board positions with all 32 pieces still in
play) wrote:
> Let's see: On every rank, there are 15 legal pawn positions.
> 15^8*50^16 (the latter an upper estimate for the rest of the figures)
> <10^37 indeed.
It's been a while since I've done combinations and permutations.
Nevertheless, I'll buy the 2562890625 possible pawn placements. Of the
48 squares left to consider, 32 are going to remain empty: 2254848913647
ways of choosing which (I hope). We've now got 10 pieces to choose from,
until 6 duplicates are eliminated [1000000] and then 10! for the
remainder [3628800]. Thus the total number < 2.1*10^34.
Of course, for each of the pawn placements, certain regions of the board
are going to be inaccessible to any number of pieces. And then, on into
the finer details of Tim Mirabile's legality list.
J. P. Hyltin
Kenneth Sloan wrote:
[snip]
> NIM can be played perfectly without generating *any* of the game tree,
> much less *all* of it. It turns out that you can perfectly evaluate any
> NIM position. If it is your turn to move, and the position is LOST -
> then there is absolutely nothing you can do about it. If it is WON,
> then you can always make a move which generates a position which is LOST
> for your opponent - the point is that you can do this without any
Thank you for this thread. One of my professors, Dr. Hugh Maynard at the U.
of Texas at San Antonio, took 2 lecture periods to discuss the application
of NIM to games and sciences. I thught I had dreamed this, because no one
I met after college had ever heard of it, even though I have worked on
several commercial expert system applications.
In my most amatuer opinion, I personally think chess is too complicated to
reduce to an equation of NIM sums, but then I have also thought chess was
too complex to write a reasonably good playing algorithm in a single
lifetime, and I suppose that's been disproven, eh? Maybe it's just too
much for me.
The NIM approach does seem *very* appropriate for simple games, so I have
often wondered if checkers would be a more reasonable format for this?
Has this been attempted? Is it possible that even Checkers is too complex
for NIM?
--
J. P. Hyltin
"'No thru road' - This must be it." - Big Bird
Tim Mirabile
ha...@astral.magic.ca (Hans Havermann) wrote:
>Komputer Korner <kor...@netcom.ca> wrote:
>
>> a programme to count all possible distributions. Here are the results:
>> (the first number in each line specifies the number of chessmen which
>> are on the board)
>>
>> 0 1.00000000000000E+0000
>> 1 7.68000000000000E+0002
>> 2 2.82240000000000E+0005
>> 3 6.60791040000000E+0007
>> 4 1.10669791680000E+0010
>etc. to
>> 32 4.63472669558781E+0042
>
>Komputer Korner points out that the numbers *are* upper bound with no
>attempt to distinguish legality. Legal chess positions become
>progressively more difficult to discern as the number of pieces on the
>board increase, but this should not constrain us from calculating
>*actual* numbers for a small number of pieces.
>
>There are, of course, no positions for zero or one piece. Assuming that
>Black/White and Left/Right are *not* interchangeable (symmetry will only
>complicate calculations when more pieces are introduced), for two pieces
>(both necessarily Kings), I believe there are 3612 board positions.
>Three pieces yield 2127600; and four pieces, 1205537008 *minus* the
>number of boards that have both Kings in check.
>
>These calculations were done by hand a number of years ago and I would
>not be overly surprised if they were wrong. I would expect the number of
>legal board positions for 32 pieces to be relatively small (nowhere near
>10^42) because of the impossibility of pawns passing each other, etc.,
>but the actual number might be fiendishly difficult to calculate. Any
>logically-thinking number-crunchers out there?
>
>--
>Nature requires five,
>Custom allows seven,
>Idleness takes nine,
>And wickedness eleven.
Items to consider when trying to get the exact number of legal chess positions:
1. Both kings cannot be in check.
2. The king of the color not to move cannot be in check.
3. A king cannot be in check from three different pieces.
4. A king cannot be in check from two different pieces unless both were
produced by the opponents last move.
5. Positions that are legal with either side to move should be counted as two
positions.
6. Positions where castling may or may not be legal should be counted
separately.
7. Positions where en passant may or may not be legal should be counted
separately.
8. A Bishop cannot trapped by pawns on its first rank on a square other than
its original square.
9. Pawns cannot change files without capturing, so, for example, in positions
doubled pawns, the opponent cannot have his full army.
10. Pawns cannot promote without some capturing having occurred.
11. Each provably promoted piece (second queen, second bishop on the same color
square, third rook, etc.) must be accounted for as having been a pawn.
12. Any position where retrograde analysis shows that one side had to have been
checkmated or stalemated in a previous position is illegal.
13. Positions where non Knights are outside the pawn chain when the pawns have
not been moved to let them out are illegal.
14. Pawns cannot be on the first or eighth ranks.
15. Any other position which for any reason cannot be reached from the initial
position is illegal. (this is a catch all, maybe there are other specific
points that can be enumerated, but I even then I don't think it's possible to
eliminate the need for this point.)
And you can't try to tighten your upper bound by calculating how many of each
of these there are and subtracting, because they are not independent. I think
this is enough to show that there is no way to calculate the number of legal
positions without checking them all with retrograde analysis, or searching the
entire game tree. Sorry guys, this can't be done with Excel or Mathematica.
+-----------------------------------------------------------------------------+
| Tim Mirabile <t...@mail.htp.com> http://www.angelfire.com/pg9/timm/ |
| TimM on FICS. TheSentinel on FIBS. PGP Key ID: B7CE30D1 |
+-----------------------------------------------------------------------------+
Hans Havermann
Tim Mirabile <t...@mail.htp.com> wrote:
> Items to consider when trying to get the exact number of legal chess
> positions:
Thank you for your list. There are a few things here I hadn't explicitly
considered before.
> And you can't try to tighten your upper bound by calculating how many of
> each of these there are and subtracting, because they are not independent.
> I think this is enough to show that there is no way to calculate the
> number of legal positions without checking them all with retrograde
> analysis, or searching the entire game tree. Sorry guys, this can't be
> done with Excel or Mathematica.
Not even Mathematica 3.0? :-)
Adam Whiteson
>
> Aren't there any mathematicians out there who are a little bit miffed that a
> simple looking man made game, developed nearly two thousand years ago, is still
> beyond their wit to resolve?
>
I doubt it. A good student of mathematics arrives quickly at the understanding that
a few simple rules, carefuly chosen, can give rise to patterns of astounding
complexity. Chess is just another example of this.
> Anyone of normal intelligence can understand anything - if it's explained to them
> in a straightforward way.
>
A pleasant fantasy that has nothing to do with the facts. The normal IQ is 100.
For such people, algebra is at the edge of their reach. Furthermore, many
things defy straightforward explanation.
> What's wrong with pi? It's the circumference of a circle divided by the diameter.Yes and please, exactly how much is that. Can you answer without using the
number pi?
>"That imaginary number"? Which one? There's millions ofSlightly more than millions. Uncountably infinite. But I think the writer meant
that just the concept of i - square root of -1 is difficult for many to comprehend.
I know of many intelligent people who find this idea utterly confusing. And what
could be more straight forward an explanation than "i is square root of -1"?
>The sun? A mass of heavy water under sufficient temperature & pressure to
> enable nuclear fusion to take place at a slow rate.Actually the nature of the sun is only partly understood even today. Where
are the neutrinos?
> Gravity? Isaac Newton sussed out the rules for its behaviour hundreds of years ago.Actually not. Newton made revolutionary advances in our understanding of gravity
but he missed a lot - as was pointed out by Einstein. Today there are many open
questions about the nature of gravity. Newton also was not comfortable with
imaginary numbers.
It is easy to dismiss problems with a glib comment "Oh that's just an example
of this or that principle." If one is after real understanding one will find
that many problems, simple at first blush, defy any simple explanation.
> I'd love to prove you wrong - its just that unfortunately, linear algebra,
> numerical analysis and discrete mathematics are the subjects I
> believe are needed to attack the problem. Unfortunately, they were not my strong
> subjects at university.
Well then, try your hand at this problem ( I hear tell its for 10 year olds )
- PI is the circumference of a circle divided by its diameter. How does PI
relate to other numbers? Or in other words, how much is PI? When we try to
describe PI as a decimal we get an infinite sequence of digits which start
3.1415926...
Many infinite decimals have simple patterns in their digits that allow
us to glibly summmarize them in a few words - e.g. 3.333333333...
is described as 3.3 recurring. Find a pattern in the digits of PI
that would allow us to summarize the sequence.
Adam
Enoch Peserico
> > : 10^42) because of the impossibility of pawns passing each other, etc.,
> > 15^8*50^16 (the latter an upper estimate for the rest of the figures)
> > <10^37 indeed.
>
> lot more than 15 legal pawn positions per rank. I'm not sure what
> you mean by pawns can't pass each other, but nothing precludes an
> indirect pass through a capture...
Except the fact that you have ALL the 32 pieces on the board, unless you
are playing a version of chess which allows ransom...
The upper bound can be lowered a LITTLE bit more IMHO with more accurate
numbercrunching: 8^15 < 2.57E9. The remaining pieces can fit in the
remaining cases in no more than
(48!/(48-16)!)*((24*24*23*23)/(48*47*46*45)) <4.7178E25 ways (the
(24*24*23*23)/(48*47*46*45) is accounted for by the fact that the bishops
must stay on only one colour - asymmetric pawn distribution would reduce
that still further). This brings us down to less than 7.89E33 The
reduction of legal positions due to the fact that bishops can leave their
original cases only by passing through either of the two cases diagonally
adjacent to each, and a similar thing for rooks (there must be one pawn
which is at least two cases further than one of his neighbors for the
rooks of that side to be able to leave the rather limited "backlines"
space should be hmm, I guess at least
(((max10*10,6*15)/(15*15)+1/23)^2)*((3/5+12/44)^2) < 1.82E -1 (I must say
I'm taking LOTS of chances with that last statement, but I guess it's a
correct upper bound, and it gets us to no more than 1.44E33
possibilities). I THINK a further (34-8)/33 reduction due to the fact
that the two kings can't BOTH be in check could be proved, bringing the
upper bound down to less than 1.13 E 33 - all number crunches have been
done with full precision partials from the previous ones - (well, that's
an almost 10^4 reduction from 10^37, which was a 10^5 reduction on
10^42). I don't think I can do much better.
Indeed I think there are at least 10^28 different legal chessboards with
32 pieces on them. Could YOU prove that?
>
> I think there are 1*3*3*3*3*3*3*1=6561 legal positions per rank,
> corresponding to empty/white pawn/black pawn possibilities.
> plus you'd have to take into account promotion of pawns...
> dividing it up this way does not help simplify the problem.
>
> Tim
Enoch Peserico
en...@dei.unipd.it
1/-1=-1/1 -> a greater number divided by a lesser one = the lesser one
divided by the greater -> negative numbers can't possibly exist
Enoch Peserico
I wrote:
> ... bringing the
> upper bound down to less than 1.13 E 33 - all number crunches have been
> done with full precision partials from the previous ones - (well, that's
> an almost 10^4 reduction from 10^37, which was a 10^5 reduction on
> 10^42). I don't think I can do much better.
That is, if you assume you can distinguish between the rooks and the
knights of the same colour... Otherwise you can get WAY under 10^32...
(though NOT exactly a 1/16 reduction, ALMOST).
graham_laight
In article <321B9B...@lanl.gov>, Adam says...
>
>>
>> Aren't there any mathematicians out there who are a little bit miffed that a
>> simple looking man made game, developed nearly two thousand years ago, is still
>> beyond their wit to resolve?
>>
>
>a few simple rules, carefuly chosen, can give rise to patterns of astounding
>complexity. Chess is just another example of this.
OK then Adam - so can you express chess in terms of equations? Shouldn't be too
hard - and it could be a good first step in resolving the problem of selecting
good moves algorithmically.
>
>> Anyone of normal intelligence can understand anything - if it's explained to them
>> in a straightforward way.
>>
>
>A pleasant fantasy that has nothing to do with the facts. The normal IQ is 100.
>For such people, algebra is at the edge of their reach. Furthermore, many
>things defy straightforward explanation.
Ouch - feel the heat of that flame!
I disagree with Adam PROFOUNDLY here. One always hears people saying, "I'm no
good at maths". I believe that most people have about the same ability to do
maths - it all hangs in the quality of the teaching. Once one has a self image
of being a good mathematician, it tends to re-inforce itself. I think that if
people were given a tool like Mathmatica, and given time and help to learn how
to use it, their confidence would rise enormously.
Oh - and most people in the UK did used to master algebra for their "O" Level
maths before the great decline in UK teaching standards in the 1970s (praise the
Lord that since the early 1990's, people have begun to start thinking about
teaching standards again).
>
>
>> What's wrong with pi? It's the circumference of a circle divided by the diameter.Yes and please, exactly how much is that. Can you answer without using the
>number pi?
>
>>"That imaginary number"? Which one? There's millions ofSlightly more than millions. Uncountably infinite. But I think the writer meant
>that just the concept of i - square root of -1 is difficult for many to comprehend.
>I know of many intelligent people who find this idea utterly confusing. And what
>could be more straight forward an explanation than "i is square root of -1"?
-1 does not have a square root - no wonder people are confused if you're telling
people that it does! All you need to understand about imaginary numbers is that
they are tools used to resolve certain types of equation, Adam.
>
>>The sun? A mass of heavy water under sufficient temperature & pressure to
>> enable nuclear fusion to take place at a slow rate.Actually the nature of the sun is only partly understood even today. Where
>are the neutrinos?
Why ask me? Is this your line when you meet new people at a party - "where do
you suppose the missing neutrinos are?" :-)
>
>> Gravity? Isaac Newton sussed out the rules for its behaviour hundreds of years ago.Actually not. Newton made revolutionary advances in our understanding of gravity
>but he missed a lot - as was pointed out by Einstein. Today there are many open
>questions about the nature of gravity. Newton also was not comfortable with
>imaginary numbers.
You don't need a perfect understanding of gravity to make good use of Newton's
equations!!!
Likewise, you probably don't need a perfect understanding of chess to design
algorithms that can beat the best humans.
>
>It is easy to dismiss problems with a glib comment "Oh that's just an example
>of this or that principle." If one is after real understanding one will find
>that many problems, simple at first blush, defy any simple explanation.
On the contrary - people are ALWAYS doing things which other people believed
were impossible. The people who say that something is impossible tend to think
logically, rather than laterally. It would be nice to see some lateral thinking
applied to the problem of chess move selection - the best chess programs seem
to have got stuck at a certain level (that of Genius 3) for some years now, and
the rate of progress has really slowed down. The problem is that, above a certain
level, the value of good tactics seems to increase only logarithmically, and
positional knowledge and judgement start to count for more. Knowledge based
programs, like CS-Tal, still can't beat the best tactical programs. If mathematical
equations could deliver the equivalent of a game tree, without having to
generate it recursively, there could be a real leap forward in playing ability.
>
>> I'd love to prove you wrong - its just that unfortunately, linear algebra,
>> numerical analysis and discrete mathematics are the subjects I
>> believe are needed to attack the problem. Unfortunately, they were not my strong
>> subjects at university.
>
>Well then, try your hand at this problem ( I hear tell its for 10 year olds )
>- PI is the circumference of a circle divided by its diameter. How does PI
>relate to other numbers? Or in other words, how much is PI? When we try to
>describe PI as a decimal we get an infinite sequence of digits which start
>
>3.1415926...
>
>Many infinite decimals have simple patterns in their digits that allow
>us to glibly summmarize them in a few words - e.g. 3.333333333...
>is described as 3.3 recurring. Find a pattern in the digits of PI
>that would allow us to summarize the sequence.
It's already proven to not exist - yet another example of the triumph of
mathematics.
Now if a mathematician could find the equations that will enable a computer to
beat the Grandmasters, that would be a very sweet and popular victory indeed!!!
Graham
J. P. Hyltin
Graham, Laight wrote:
>
> In article <321B9B...@lanl.gov>, Adam says...[snip]
> >> Aren't there any mathematicians out there who are a little bit miffed that a
> >> simple looking man made game, developed nearly two thousand years ago, is still
> >> beyond their wit to resolve?
> >>
> >
> >I doubt it. A good student of mathematics arrives quickly at the understanding that
> >a few simple rules, carefuly chosen, can give rise to patterns of astounding
> >complexity. Chess is just another example of this.
>
> OK then Adam - so can you express chess in terms of equations? Shouldn't be too
> hard - and it could be a good first step in resolving the problem of selecting
> good moves algorithmically.
I thought I would jump in and make a point by providing my experience with a good
example of a problem with simple rules and a complex solution:
Using the rules of geometric construction, trisect an angle.
Eventually, the solution was to prove it couldn't be done, but an acceptible proof
eluded mathematicians for a few thousand years, until either the 18th or 19th century.
Of course, knowing all this didn't stop myself and my friends in my high school
geometry class from trying, and we learned a lot about Geometry in the process,
and when I was educated enough to understand the proof, I learned even more.
This problem is one of 3 problems that were thought of as "eternal mysteries" (or
something like that), problems that the Greeks (I think, or Romans, or Egyptians)
somehow understood there was no solution, but couldn't prove one way or the other.
One of the others was "squaring a circle", ie, given a line segment that represents
a radius of a circle, construct a square that has the same area using the rules of
geometric construction. I forget the third mystery.
Maybe the maths can help us here. Maybe we can somehow estimate the complexity of
chess as a function of the amount of memory and critical operations necessary for
a computer to play a perfect game once a formulaic algorithm is written. My guess
is we would find that chess is complex beyond any solution that can be executed
within the confines of current computer speed and memory capabilities, but it would
tell us approximately when we would be able to solve the game, ie, by how much
technology must improve in speed and space capacity. Maybe a good start on that
path is the thread regarding the number of possible positions and legal moves in
those positions.
Perhaps even that endeavor is beyond the capacity of we mere humans, but I suspect
the attempt would be quite a learning experience.
Adam Whiteson
Graham, Laight wrote:
>
> I believe that most people have about the same ability to do
> maths - it all hangs in the quality of the teaching.
for everyday things is inadequate to understand most of what is done in
mathematics.
>
> Oh - and most people in the UK did used to master algebra for their "O" Level
> maths before the great decline in UK teaching standards in the 1970s (praise the
> Lord that since the early 1990's, people have begun to start thinking about
> teaching standards again).
Hmmm... Does most of the population in the UK get an O level pass in Mathematics
these days? I remember learning calculus for my O level math and in those days
most of the population did not get an O level in math.
>
> -1 does not have a square root - no wonder people are confused if you're telling
> people that it does! All you need to understand about imaginary numbers is that
> they are tools used to resolve certain types of equation, Adam.
> Actually I find I need to understand a great deal more about imaginary numbers. -1
does not have a square root on the Real number line - it does have a square root
in the Complex plane (actually it has two).
>
> Why ask me? Is this your line when you meet new people at a party - "where do
> you suppose the missing neutrinos are?" :-)
>
I asked you because you implied that the understanding the sun was a simple affair.
The model of the sun as a huge fusion process predicts a certain neutrino flux.
Measurements made here on earth find far fewer neutrinos than the sun "should"
be emitting. This shows that our understanding of how the sun works is seriously
incomplete.
> You don't need a perfect understanding of gravity to make good use of Newton's
> equations!!
This is not the point. Newtons equations are wrong! This was proved
by the Michelson Morely experiment at the end of the last century.
The point of these examples that were brought to your attention by an
earlier poster (I dont recall his name) is that many things that appear
simple are not really so. They only appear simple if one ignores or is
unaware of some of the questions. This author mentioned PI which is
a good example. The pseudo-problem that I posed you was an attempt to
point out that an apparently simple idea like PI can give rise to
very difficult problems. The existence of the irrational numbers
as part of the real number line was not understood until
Cauchy. The string of digits that arises from the attempt to express
PI as a decimal is of such complexity that it cannot be reduced to
any finite sequence of digits.
One could glibly dismiss chess - a Russian master once said "Chess is a
simple game played by moving wooden pieces around on a board". However
if one wishes to defeat a GrandMaster more is needed.
When a problem can be solved simply, this is beautiful and elegant. However,
often it cannot and one who wishes to understand the matter must embrace
the complexity of the problem. One can say "I dont really need to know
that detail to understand what is going on" but a Grand Master takes the
time to master these details and he will crush an opponent who is lazy.
>>> I'd love to prove you wrong - its just that unfortunately, linear algebra,
>>> numerical analysis and discrete mathematics are the subjects I
>>> believe are needed to attack the problem. Unfortunately, they were not my strong
>>> subjects at university.
:)
Being able to write the equation for a problem is only a small part of the
struggle for a solution. The literature in Mathematics is full of equations
for which no one knows the solution. For many equations, mathematicians don't
even know if there IS a solution and are working on the problem of proving
or disproving the mere existence of a solution.
Adam
Chris Whittington
This is a fantastic idea. When you've developed the equation I would
like you to adjust it for the following cases and tell me
immediately:
1. How to get any blonde instantaneously.
2. How to be the next Lenin. I want an equation to tell me what
factors to vary so I can be the next dictator of the world, by
predictable revolutionary activity and adjustments to the price
of sugar.
3. The equation describing the number of mathemeticians and associated
theories sustainable in one bounded space before implosion and
formation of black hole.
4. List continued page 94.
Chris Whittington
Chris Whittington
Graham Laight wrote:
>
> I thought I'd rename the thread in the hope that someone knows something about
> the subject I'm really interested in! If you do, and you don't want to go public,
> you can reach me at Graham...@largotim.co.uk
>
> In article <321261...@netcom.ca>, Komputer says...
> >Claude Chaunier wrote:
> >>
> >> Komputer Korner wrote:
>
> {snip}
>
> >> Why should it be important? Anyway,
>
> Hear hear! If you want to talk about cracking chess with knowledge, you should be
> talking to Chris Whittington. I'd just like to say 2 quick things about that:
>
> * In "Chess Skill In Man And Machine", one of the best books ever written, I
> vaguely remember them saying that a grandmaster has expert knowledge on 50,000
> different positional patterns - so this is what the Whittington brigade should
> be aiming for
No - too many for me :)
From some patterns and then emergent knowledge through search.
I'm not trying to make a one-move analyser - although that woudl be nice.#
>
> * In the CS-Tal games I've played through, apart from the odd brilliant sacrifice,
> CS-Tal seems to play much like any other computer
Yes, that's right - it would be crazy to be 'crazy' all the time.
Most piece sacs lose.
So the program also has to play normal positions.
But it plays normal postions with its evaluation function rather
than its search.
Chris Whittington
>
> >> without promoted pieces your number would be:
> >>
> >> 9x3x3x3x2 x 9x3x3x3x2 = 486 x 486 = 236196
> >>
> >> according to how many black pawns, knights, etc.
> >> and white pawns, knights, etc. there are.
> >> But with promotion there could be 10 black knights
>
> {snip}
>
> >I don't understand your no.'s. in the section w/o promotions.
>
> This is a standard combination calculation. There are 9 different combinations of
> pawn numbers (0-8), three different combinations of rook numbers, three
> combinations of knight numbers, three combination of bishop numbers, and two
> combinations of queen numbers (0 or 1). To get the total numbers of combinations,
> you multiply the individual combinations together. But I agree with Claude - I
> don't think this is a useful number:
>
> * It takes no account of pawn promotion
>
> * It would take more than a table base entry to know how to play all the
> different positions that could arise within a combination of pieces. I think
> that maybe "Chess Skill In Man And Machine" already had it sussed all those
> years ago.
Chris Whittington
Graham Laight wrote:
>
> The following is interesting, but doesn't answer my REAL question - does anyone
> know of any work done by a mathematician in terms of using mathematics to help
> select chess moves without having to generate a game tree???
Apparently not, judging by the lack of response.
Do you know if the universe and all its components are reducable
to explanation by the language of mathematics ?
I would say not.
If you believe in god or things spiritual, I would say definitely
not.
If you consider chaos (butterfly wing flap etc) then I'ld also
say not.
I'ld also go so far as to say that chess is not reducable either (NIM
notwithstanding).
No, the *only* way to solve chess is by application of knowledge
to positions plus search look ahead, and by table-base with limited
piece numbers.
A bit similar to the way humans do it really.
This maths idea is a mickey-mouse dream.
Chris Whittington
graham_laight
In article <84074426...@cpsoft.demon.co.uk>, Chris says...
{snip}
>This is a fantastic idea. When you've developed the equation I would
>like you to adjust it for the following cases and tell me
>immediately:
>
>1. How to get any blonde instantaneously.
>
>2. How to be the next Lenin. I want an equation to tell me what
>factors to vary so I can be the next dictator of the world, by
>predictable revolutionary activity and adjustments to the price
>of sugar.
>
>3. The equation describing the number of mathemeticians and associated
>theories sustainable in one bounded space before implosion and
>formation of black hole.
>
>4. List continued page 94.
>
>Chris Whittington
>
1. You need to be more specific. What does "get" mean here? Is the equation
allowed to instruct you to break the law?
2. Ask Chancellor Kohl - he seems to be making steady progress by applying his
equations! :-)
3. This is not hard to do, given knowledge of the average weight and volume of
said mathematicians and theories.
Shortly after the Wright brothers demonstrated powered flight, an English newspaper
offered stlg1,000 to the first person to fly the English channel. When a comedian
offered stlg1,000,000 to the first person to dig a hole to Australia and call
back by speakerphone, most people sided with the comedian. It was only a matter
of months before the stlg1,000 was claimed.
graham_laight
In article <84080318...@cpsoft.demon.co.uk>, Chris says...
>
>
>Fine, but you can't get away with the argument:
>
>1. In the past everytbody said (A) was impossible, except for
>one person who then did (A),
>
>2. so when I say (B) is possible, and you say (B) is impossible, then
>I'm right because of precedent (1) above.
>
>There are some things that are just not possible or practicable or
>whatever. Solving chess / life / scoring with totty / predicting
>revolutions / predicting the weather over large timescales etc. etc.
>
>Chris Whittington
When I say "solved", I mean able to help a program play better chess than the
best humans. Many people think that, with or without special equations, this
will be achieved within 15 years (based on long term extrapolation). The equations
would be a nice short cut.
At the risk of perpetuating trivia - I have to say I'm not impressed with the
examples the nay-sayers have come up with. Look at Chris's examples above:
Solving chess - he's one of the people trying to do just that!
Life - I refer you to the Economist Annual - "The World In 1996" - some scientists
believe they may have some mathematical equations to explain the creation of the
Universe
Scoring with totty - there are people out there doing that - even here in England!
Predicting Revolutions - I suspect that most revolutions WERE predicted before
they happened. The CIA (and probably our own MI5) try to predict revolutions
Predicting The Weather Over Large Timescales - global warming and cooling has
been shown to follow cycles of 30,000 and 50,000 years depending on the angle
of the earth to the sun, and the distance of the earth from the sun (which varies
in these timescales). We are currently approaching the hottest period in both
cycles.
Come on mathematicians - before Chris and the knowledge folk beat you to being
first to beat the best humans!
Chris Whittington
> >like you to adjust it for the following cases and tell me
> >immediately:
> >
> >1. How to get any blonde instantaneously.
> >
> >2. How to be the next Lenin. I want an equation to tell me what
> >factors to vary so I can be the next dictator of the world, by
> >predictable revolutionary activity and adjustments to the price
> >of sugar.
> >
> >3. The equation describing the number of mathemeticians and associated
> >theories sustainable in one bounded space before implosion and
> >formation of black hole.
> >
> >4. List continued page 94.
> >
> >Chris Whittington
> >
>
> allowed to instruct you to break the law?
>
> 2. Ask Chancellor Kohl - he seems to be making steady progress by applying his
> equations! :-)
>
> 3. This is not hard to do, given knowledge of the average weight and volume of
> said mathematicians and theories.
>
> Shortly after the Wright brothers demonstrated powered flight, an English newspaper
> offered stlg1,000 to the first person to fly the English channel. When a comedian
> offered stlg1,000,000 to the first person to dig a hole to Australia and call
> back by speakerphone, most people sided with the comedian. It was only a matter
> of months before the stlg1,000 was claimed.
Gerry Quinn
In article <4vhan7$f...@lex.zippo.com>, Graham Laight wrote:
>In article <321B9B...@lanl.gov>, Adam says...
>>
>>>
>>> Aren't there any mathematicians out there who are a little bit miffed that a
>>> simple looking man made game, developed nearly two thousand years ago, is
> still
>>> beyond their wit to resolve?
snip
>>
>>Many infinite decimals have simple patterns in their digits that allow
>>us to glibly summmarize them in a few words - e.g. 3.333333333...
>>is described as 3.3 recurring. Find a pattern in the digits of PI
>>that would allow us to summarize the sequence.
>
>It's already proven to not exist - yet another example of the triumph of
>mathematics.
>
>Now if a mathematician could find the equations that will enable a computer to
>beat the Grandmasters, that would be a very sweet and popular victory indeed!!!
>
>Graham
The sequence of digits in Pi can be summarised very easily:
"Expand (circle circumference/diameter) in decimal notation"
The best chess move can be summarised by an almost equally simple equation.
It just gets a bit complicated when you try to expand it. (Of course the
equation represents the tactical solution to chess.)
- Gerry
----------------------------------------------------------
ger...@indigo.ie (Gerry Quinn)
----------------------------------------------------------
Chris Whittington
Graham Laight wrote:
>
> In article <84080318...@cpsoft.demon.co.uk>, Chris says...
>
> >
> >
> >Fine, but you can't get away with the argument:
> >
> >1. In the past everytbody said (A) was impossible, except for
> >one person who then did (A),
> >
> >2. so when I say (B) is possible, and you say (B) is impossible, then
> >I'm right because of precedent (1) above.
> >
> >There are some things that are just not possible or practicable or
> >whatever. Solving chess / life / scoring with totty / predicting
> >revolutions / predicting the weather over large timescales etc. etc.
> >
> >Chris Whittington
>
> best humans. Many people think that, with or without special equations, this
> will be achieved within 15 years (based on long term extrapolation). The equations
> would be a nice short cut.
And some people don't.
>
> At the risk of perpetuating trivia - I have to say I'm not impressed with the
> examples the nay-sayers have come up with. Look at Chris's examples above:
>
> Solving chess - he's one of the people trying to do just that!
According to your redefinition of 'solved', yes. But according
to my definition, eg. a perfect player, no.
>
> Life - I refer you to the Economist Annual - "The World In 1996" - some scientists
> believe they may have some mathematical equations to explain the creation of the
> Universe
Maths is a language. Like other languages it is capable of a partial
and inaccurate expression of reality - but, faced with big issues,
like other languages, it gets lost for words.
Newton came up with equations which do well predicting billiard balls.
Einstein refined them, but still not perfectly.
And nobody has the equations capable of predicting the future, whether
it be chess, the weather, life, girls or whatever. Its too chaotic
and too complex, the only way to tell is to let it play out by life;
and then, the result will just be one of the infinite possibilities.
>
> Scoring with totty - there are people out there doing that - even here in England!
>
The irony seems to have got lost.
> Predicting Revolutions - I suspect that most revolutions WERE predicted before
> they happened. The CIA (and probably our own MI5) try to predict revolutions
>
Really, Russia 1917 ? Predicted ? Not even by Lenin.
Yes the CIA has got a really big computer and lots of equations, and
they screw up really well: Bay of Pigs, Vietnam, Iran, continued page 94.
As for our own MI5, I thought most of them worked for the USSR ?
> Predicting The Weather Over Large Timescales - global warming and cooling has
> been shown to follow cycles of 30,000 and 50,000 years depending on the angle
> of the earth to the sun, and the distance of the earth from the sun (which varies
> in these timescales). We are currently approaching the hottest period in both
> cycles.
Just fart once, apparently this can change the weather in Antartica.
How does any equation and computer deal with this ?
>
> Come on mathematicians - before Chris and the knowledge folk beat you to being
> first to beat the best humans!
Hopefully the sensible ones know there are limits.
Chris Whittington
Simon Read
CW: Chris Whittington <chr...@cpsoft.demon.co.uk>
CW>> 2. How to be the next Lenin. I want an equation to tell me what
CW>> factors to vary so I can be the next dictator of the world, by
CW>> predictable revolutionary activity and adjustments to the price
CW>> of sugar.
--->>
CW> There are some things that are just not possible or practicable or
CW> whatever. [...] predicting revolutions [...]
-->
See "On the Behaviour of Large Groups of People" - Seldon, H. -
Journal of Psychological Simulation, Trantor, G.E. 9840
This is given a more populist treatment in "Foundation",
"Foundation and Empire", "Second Foundation" by Asimov, A.
Personally, I believe that human history is chaotic: small initial
conditions lead to massive differences: it only takes someone's
whim to decide to invade France first instead of Poland. (After all,
those who have made some of the greatest differences to human
history haven't exactly been stable personalitites...) This
would make a great difference to the life of someone later called
General de Gaulle, and would have completely changed his background,
causing him to choose a completely different role in later events.
Ergo, chaos.
Some things, even if they DO have equations to describe them,
are still chaotic and therefore unpredictable.
I was going to give you all a detailed explanation of why this
is intimately connected with the inability to use a single equation
to decide upon which move to make on the chessboard, but I see
that it's all so obvious I'll let you work it out for yourselves.
Simon
Chris Whittington
Quite so.
If atoms, quarks and fundamental constants are
deemed to behave predictably (which, they don't); then a simple
introduction of the Fuhrer should be enough to convince everyone
that the world is not a deterministic place.
The equation you're looking for is:
Fundamental constants + free will = chaos.
Quite nice chaos though.
Chris Whittington
Claude Chaunier
Graham, Laight wrote:
> -1 does not have a square root - no wonder people are confused if you're telling
> people that it does! All you need to understand about imaginary numbers is that
> they are tools used to resolve certain types of equation, Adam.
1/2, -1, square root of 2, pi were also criticized as being only useful
tools
instead of entities like 1, 2, 3. Don't you remember your childhood?
Tim Mirabile
Graham Laight wrote:
>In article <321B9B...@lanl.gov>, Adam says...
>>Well then, try your hand at this problem ( I hear tell its for 10 year olds )
>>- PI is the circumference of a circle divided by its diameter. How does PI
>>relate to other numbers? Or in other words, how much is PI? When we try to
>>describe PI as a decimal we get an infinite sequence of digits which start
>>
>>3.1415926...
>>
>>Many infinite decimals have simple patterns in their digits that allow
>>us to glibly summmarize them in a few words - e.g. 3.333333333...
>>is described as 3.3 recurring. Find a pattern in the digits of PI
>>that would allow us to summarize the sequence.
>
>It's already proven to not exist - yet another example of the triumph of
>mathematics.
(infinity)
__
<
Pi/4 = > -1^n/(2n+1)
<__
n=0
That's Pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...
Not sure it's for 10 year olds, but there it is. I'll leave the glib
summarization to someone else. :)
cma...@ix.netcom.com
Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:
>Fundamental constants + free will = chaos.
Free will is not required. Look at the Mandelbrot set. The only way
to know what 'color' a given (X, Y) point will be is to iterate the
equation until it stops. No math equation will solve this in a single
pass. The 'Chess Tree' is a much more chaotic fractal.
Chris Mayer
Adam Whiteson
Tim Mirabile wrote:
>>
> >>Many infinite decimals have simple patterns in their digits that allow
> >>us to glibly summmarize them in a few words - e.g. 3.333333333...
> >>is described as 3.3 recurring. Find a pattern in the digits of PI
> >>that would allow us to summarize the sequence.
> __
> <
> Pi/4 = > -1^n/(2n+1)
> <__
>
> n=0
>
> That's Pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...
>
> Not sure it's for 10 year olds, but there it is. I'll leave the glib
> summarization to someone else. :)
This is the Taylor series expansion for the arctangent and it does converge
to PI. One could use this to calculate the decimal digits for PI although
this series is not the best practical choice - it converges *very* slowly.
However, this series does not find a pattern in the decimal digits for PI.
If one knew such a pattern then one could predict the nth digit of the PI
decimal without having to calculate the (n-1)th. The point is that the
decimal sequence cannot be simplified.
I too don't think this is a problem for 10 yr olds. Its beyond the reach
of many adults. The original poster had dismissed PI as "math for
10 year olds" and I was just trying to point out that there was more
to it.
Of course PI like sq root(2) is an irrational number. It is not a trivial
matter to show that such quantities are in fact "Real" numbers and that
equations such as "the circumference of a circle divided by its radius" or
"the square root of 2" have solutions.
Adam
graham_laight
In article <84079341...@cpsoft.demon.co.uk>, Chris says...
>
>Graham Laight wrote:
>>
>> The following is interesting, but doesn't answer my REAL question - does anyone
>> know of any work done by a mathematician in terms of using mathematics to help
>> select chess moves without having to generate a game tree???
>
>
>Apparently not, judging by the lack of response.
>
>Do you know if the universe and all its components are reducable
>to explanation by the language of mathematics ?
>
>I would say not.
>
>If you believe in god or things spiritual, I would say definitely
>not.
>
>If you consider chaos (butterfly wing flap etc) then I'ld also
>say not.
>
>I'ld also go so far as to say that chess is not reducable either (NIM
>notwithstanding).
>
>No, the *only* way to solve chess is by application of knowledge
>to positions plus search look ahead, and by table-base with limited
>piece numbers.
>
>A bit similar to the way humans do it really.
>
>This maths idea is a mickey-mouse dream.
>
>Chris Whittington
>
When someone puts sound arguments forward for their case, it displays knowledge.
When someone argues hysterically against an idea, it displays fear. The above
falls into the second category, Chris!
You displayed the same character in the thread about the re-match between DB and
Kasparov.
If this is an indicator of a burning ambition to be the first to kill Grandmasters
by computer, one can but admire it, and wish you well in this quest.
Graham.
graham_laight
In article <84106553...@cpsoft.demon.co.uk>, Chris says...
>> This is given a more populist treatment in "Foundation",
>> "Foundation and Empire", "Second Foundation" by Asimov, A.
>>
>>
>> Personally, I believe that human history is chaotic: small initial
>> conditions lead to massive differences: it only takes someone's
>> whim to decide to invade France first instead of Poland. (After all,
>> those who have made some of the greatest differences to human
>> history haven't exactly been stable personalitites...) This
>> would make a great difference to the life of someone later called
>> General de Gaulle, and would have completely changed his background,
>> causing him to choose a completely different role in later events.
>>
>> Ergo, chaos.
>>
>>
>> Some things, even if they DO have equations to describe them,
>> are still chaotic and therefore unpredictable.
The point is NOT to predict what moves your opponent is going to make, but to
beat them most of the time whatever they do. If General de Gaulle's definition
of "win" was to get into the popular history books, he could have achieved this
whatever Adolf had decided to do. Granted - it's harder to have an exciting
game if your opponent does not make exciting moves.
>>
>> I was going to give you all a detailed explanation of why this
>> is intimately connected with the inability to use a single equation
>> to decide upon which move to make on the chessboard, but I see
>> that it's all so obvious I'll let you work it out for yourselves.
A chess program is a self contained algorithm, so it already IS a single
equation. It just happens to use too much time wasting recursion at the moment.
>
>Quite so.
>
>If atoms, quarks and fundamental constants are
>deemed to behave predictably (which, they don't); then a simple
>introduction of the Fuhrer should be enough to convince everyone
>that the world is not a deterministic place.
1. See above remarks about not needing to know opponents moves
2. Dictators are far more predictable than other politicians. This is why
Margaret Thatcher had to be replaced with John Major - her predictability was
enabling Neil Kinnock to corner her time after time after time, and goad her
into making rash statements.
>
>The equation you're looking for is:
>
>Fundamental constants + free will = chaos.
Actually, this is quite far removed from what I'm looking for, Mr Whittington.
What I really want is some equations that will reduce the need for creating a
game tree in chess. It is difficult to see the contribution the above equation
makes to this requirement.
Graham Laight
Cyber Linguist
In article <4vtreo$a...@dfw-ixnews3.ix.netcom.com> cma...@ix.netcom.com writes:
>
>Free will is not required. Look at the Mandelbrot set. The only way
>to know what 'color' a given (X, Y) point will be is to iterate the
>equation until it stops. No math equation will solve this in a single
>pass. The 'Chess Tree' is a much more chaotic fractal.
>
wouldn't it have to be infinitely complex, as the Mandelbrot set is?
With the 50-move rule, there's a definite upper bound on the number of
moves, and therefore on the size of the tree. It's BIG, true, but not
infinite.
--
Eric Carr <ca...@cs.odu.edu> | http://www.cs.odu.edu/~carr
----------------------------------------------------------------------------
GAT d- s+:+ g++ a23 w C+++ US++ P L+ 3 E--- N+++ K- W M-- V-- t+ 5 R+(*) G++
tv-- b++++ D--- B---- e>++ O++ PS+ PE- Y+ PGP X- DI++ h+ r-- n---- !y>+
Dave Gomboc
In article <4vuh2f$8...@lex.zippo.com>, <Graham Laight> wrote:
>In article <84079341...@cpsoft.demon.co.uk>, Chris says...
>>
>>Do you know if the universe and all its components are reducable
>>to explanation by the language of mathematics ?
>>
>>I would say not.
>>
>>If you believe in god or things spiritual, I would say definitely
>>not.
>>
>>If you consider chaos (butterfly wing flap etc) then I'ld also
>>say not.
>>
>>I'ld also go so far as to say that chess is not reducable either (NIM
>>notwithstanding).
>>
>>No, the *only* way to solve chess is by application of knowledge
>>to positions plus search look ahead, and by table-base with limited
>>piece numbers.
>>
>>A bit similar to the way humans do it really.
>>
>>This maths idea is a mickey-mouse dream.
>>
>>Chris Whittington
>>
>
>When someone puts sound arguments forward for their case, it displays knowledge.
>
>When someone argues hysterically against an idea, it displays fear. The above
>falls into the second category, Chris!
>
>You displayed the same character in the thread about the re-match between DB and
>Kasparov.
>
>If this is an indicator of a burning ambition to be the first to kill Grandmasters
>by computer, one can but admire it, and wish you well in this quest.
>
>Graham.
I think it's unfair of Chris to shrug it off as a "mickey-mouse dream"
as well. There are already certain classes of GO endgames which are
solved exactly by mathematics. The format system has found wins in
positions where 9 dan players cannot. (See Mathematical Go: Chilling
Gets the Last Point. Sorry, I don't have the ISBN number.)
Admittedly this is a small subset of a game which is perhaps more
amenable to mathematical attack than chess, but to utterly reject the
possibility of the same being possible for chess is, IMO, wrong-headed.
--
Dave Gomboc
drgo...@a.stu.athabascau.ca
Padding to force news poster to accept message with lots of quoted
material is below.
..................................................................
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
abcde fghij klmno pqrst uvwxyz abcde fghij klmno pqrst uvwxyz
graham_laight
In article <3223f...@news.cranfield.ac.uk>, Simon says...
>May I suggest the following...
>
>Newsgroup contents = technical discussion + sense of humour.
>
>This might help considerably in extracting value from
>rec.games.chess.computer
>
>Simon
Life is grim and serious, and this newsgroup should reflect that fact. Anyone
who says otherwise obviously disagrees.
Since I am unable to attach a photograph of myself looking suitably austere,
here's a schematic diagram, depicting head, torso, and four main appendages:
\O/
|
/ \
Actually, I'm not all that bad! Just look at all the flames in this thread
directed at me which I've refrained from replying to!
Chris Whittington
Hmmm, thought that was the problem.
There aren't any flames directed at you, just a discussion with
strongly held opinions. There is a difference.
Chris Whittington
Simon Read
CW: In article <84106553...@cpsoft.demon.co.uk>, Chris says...
CW>>
CW>> The equation you're looking for is:
CW>>
CW>> Fundamental constants + free will = chaos.
-->>
GL: Graham Laight
GL> Actually, this is quite far removed from what I'm
GL> looking for, Mr Whittington.
->
Chris Whittington
> >> "Foundation and Empire", "Second Foundation" by Asimov, A.
> >>
> >>
> >> Personally, I believe that human history is chaotic: small initial
> >> conditions lead to massive differences: it only takes someone's
> >> whim to decide to invade France first instead of Poland. (After all,
> >> those who have made some of the greatest differences to human
> >> history haven't exactly been stable personalitites...) This
> >> would make a great difference to the life of someone later called
> >> General de Gaulle, and would have completely changed his background,
> >> causing him to choose a completely different role in later events.
> >>
> >> Ergo, chaos.
> >>
> >>
> >> Some things, even if they DO have equations to describe them,
> >> are still chaotic and therefore unpredictable.
>
> The point is NOT to predict what moves your opponent is going to make, but to
> beat them most of the time whatever they do. If General de Gaulle's definition
> of "win" was to get into the popular history books, he could have achieved this
> whatever Adolf had decided to do. Granted - it's harder to have an exciting
> game if your opponent does not make exciting moves.
>
Point being missed here.
If a bee stung de Gaulles great grandfather at the right moment, there
might have been a world with de Gaulle (or Hitler, or whatever)
The point made is that very small events can create massive fluctuations.
Its a point easy to make with history, but it is also true at
all levels (fractal/chaos etc).
Chess program analogy:
Think of history as one thread in game tree of life. Any one of an
infinite number of other threads could have been the outcome.
No one could generate any equation capable of predicting which outcome
would be the one - it just has to unravel by life.
Likewise the game of chess is so complex (not as complex as life,
but still seriously so) and the numbers involved are so large that
all that can be done is to look ahead N moves (where N is not enough
to get to the end) and try to make a prediction about the path to be
taken. Sometimes the prediction will be 'good enough' and sometimes
not.
If you take the whole game family, you'll find some games that can be
determined, and you'll find some games that can't.
I can't *prove* it, but I am very confident that chess is on the can't
side of the line - and, in that case, an equation isn't going to help.
>
> >>
> >> I was going to give you all a detailed explanation of why this
> >> is intimately connected with the inability to use a single equation
> >> to decide upon which move to make on the chessboard, but I see
> >> that it's all so obvious I'll let you work it out for yourselves.
>
> A chess program is a self contained algorithm, so it already IS a single
> equation. It just happens to use too much time wasting recursion at the moment.
>
No, equations and algorithms are not the same thing.
> >
> >Quite so.
> >
> >If atoms, quarks and fundamental constants are
> >deemed to behave predictably (which, they don't); then a simple
> >introduction of the Fuhrer should be enough to convince everyone
> >that the world is not a deterministic place.
>
> 1. See above remarks about not needing to know opponents moves
>
> 2. Dictators are far more predictable than other politicians. This is why
> Margaret Thatcher had to be replaced with John Major - her predictability was
> enabling Neil Kinnock to corner her time after time after time, and goad her
> into making rash statements.
>
> >
> >The equation you're looking for is:
> >
> >Fundamental constants + free will = chaos.
>
> Actually, this is quite far removed from what I'm looking for, Mr Whittington.
>
> What I really want is some equations that will reduce the need for creating a
> game tree in chess.
There aren't any. There's an algorithm which, given enough time, will
solve the game - but we know that the time isn't available.
> It is difficult to see the contribution the above equation
> makes to this requirement.
Its called irony.
>
> Graham Laight
You are arguing above that there are equations, into which
numbers can be plugged, which will solve problems.
On a macro level or averaging the results, this is true.
We know it will be cold tomorrow in Antartica, but we don't know
the wind direction for next month.
What I am saying is that all these macro level, averaging, equations
break down in the fine detail; that high levels of complexity,
or very small changes in the start conditions will give rise to
massive fluctuations in the final result.
Chess is sufficiently complex and the tree of moves sufficiently
massive to defeat the predictive power of any equation you
care to develop. That's why it's an interesting game.
Chris Whittington
Chris Whittington
Graham Laight wrote:
>
> In article <84079341...@cpsoft.demon.co.uk>, Chris says...
> >
> >Graham Laight wrote:
> >>
> >> The following is interesting, but doesn't answer my REAL question - does anyone
> >> know of any work done by a mathematician in terms of using mathematics to help
> >> select chess moves without having to generate a game tree???
> >
> >
> >
> >Do you know if the universe and all its components are reducable
> >to explanation by the language of mathematics ?
> >
> >I would say not.
> >
> >If you believe in god or things spiritual, I would say definitely
> >not.
> >
> >If you consider chaos (butterfly wing flap etc) then I'ld also
> >say not.
> >
> >I'ld also go so far as to say that chess is not reducable either (NIM
> >notwithstanding).
> >
> >No, the *only* way to solve chess is by application of knowledge
> >to positions plus search look ahead, and by table-base with limited
> >piece numbers.
> >
> >A bit similar to the way humans do it really.
> >
> >This maths idea is a mickey-mouse dream.
> >
> >Chris Whittington
> >
>
> When someone puts sound arguments forward for their case, it displays knowledge.
>
> When someone argues hysterically against an idea, it displays fear. The above
> falls into the second category, Chris!
>
> You displayed the same character in the thread about the re-match between DB and
> Kasparov.
Huh ?
Fear of what, mathematical equations ? Snakes and large hairy spiders
maybe, but I'ld noticed any of these on this thread.
Chris Whittington
Ilias Kastanas
In article <4vbmg4$n...@mark.ucdavis.edu>,
Kevin James Begley <kjbe...@chimi.engr.ucdavis.edu> wrote:
@ppo.com>
@Organization: College of Engineering - University of California - Davis
@Distribution:
@
@GrahamLaight wrote:
@: Kevin,
@
@: Thankyou very much for this post. I'm so glad that someone, somewhere, is
@: prepared to put their oar in the water on this subject - I was beginning to
@: wonder what was wrong with it. Now we can have dialogue instead of monologue.
@
@: What you seem to be saying, Kevin, is that chess belongs to a category of
@: problems which is too difficult to resolve with today's tools - and you
@: ask what a : math program to resolve chess would look like.
@
@Well, I'm not just arguing that it's "too difficult." Such an argument
@would, after all, be immune to rebutal were it not for my concrete
@example of what makes it "too difficult." Matchsticks, which I presume
@has been solved mathematically, I argue, is in another category altogether.
@Why? because, if you construct a database of winning positions for that
@game, I argue that you could determine a set of rules which would allow
@for considerable reduction in the space needed to store these positions.
@In other words, a rule would be found that eliminates 20 positions, and
@another rule found that eliminates 20 more, and the two rules could be
@merged into one rule, and so on until every position is covered by a
@considerably small set of rules.
@
@I argue that this is not the case in chess. But, more than just state
@what my feeling is in this matter, I argue that one cannot reduce the
@size of a simple endgame database by a significant percentage, and if
@this is the case, then certainly, one cannot reduce the entire game
@into a few rules.
@
@Finding mathematical rules for chess is akin to an iterative consensus
@of terms. Consider that if we somehow knew all winning moves for all
@positions, and we somehow could assure that no cycles would result from
@these "winning" moves, and if we had the position & moves stored as
@binary files somewhere, then we could simply solve for a minimum
@coverage of these positions. It might take forever for the algorithm
@to crunch out the equation, but that''s not the point -- the point
@is, in theory, it is equivalent to building a mathematical method.
@The point is, if one cannot obtain significant reduction in space from
@a small set of simple endgames, then one certainly cannot be expected
@to reduce the game itself into any small set of rules.
@
@It seems we are at a standoff until someone can provide data
@on the minimization yeilded by some simple (but unrelated)
@endgames. I would suggest K&R vs K, and K&B&N vs K endgames,
@since they should be unrelated enough, and well enough known.
@If these can in fact be reduced together into a small set of
@equations, then, certainly, there is potential in your idea
@for searching for a mathematical solution. If there is not
@a significant minization yeild, then we can be quite sure
@that any solution will be nearly as complex as entire database
@of positions itself, and therefore, would be, as I suggest it
@is, a complete waste of time.
@
@ Kevin.
@
Endgame databases are perfect chess. I doubt we can aspire to
a full strategy for the game that is likewise. Providing for 40
moves, 20 opponent alternatives per move, already involves 20^40...
and no amount of transpositions, compression or so will cut this down
to something remotely thinkable.
Vukovic has an example of the classical B:h7+ sacrifice in a French
Defense position, its correctness tied to whether the WP at a2 has moved
to a3 or not; White wins in one case and loses in the other.
But a 'mathematical' solution, by principles, rules and computation
coupled with a hefty database, might be possible if the goal is super-
GM performance, say. There might be general rules and guides akin to con-
servation of energy, momentum etc in Physics, Entropy in Stat. Mechanics...
even if not simply expressible or not applicable to all phases.
A precursor is A. Turing, who tried maximizing mobility as compared
to the opponent's. It is actually better than it sounds.
On the other hand, will dedication persist when it transpires that
it is a _drawing_ strategy!? (It should; if general rules exist and
are sufficient, they would be very interesting to know).
Ilias
Ilias Kastanas
In article <321B11...@rdtech.com>,
J. P. Hyltin <JPHy...@rdtech.com> wrote:
>Kenneth Sloan wrote:
>[snip]
>> NIM can be played perfectly without generating *any* of the game tree,
>> much less *all* of it. It turns out that you can perfectly evaluate any
>> NIM position. If it is your turn to move, and the position is LOST -
>> then there is absolutely nothing you can do about it. If it is WON,
>> then you can always make a move which generates a position which is LOST
>> for your opponent - the point is that you can do this without any
>> lookahead whatsoever.[snip]
>
>Thank you for this thread. One of my professors, Dr. Hugh Maynard at the U.
>of Texas at San Antonio, took 2 lecture periods to discuss the application
>of NIM to games and sciences. I thught I had dreamed this, because no one
>I met after college had ever heard of it, even though I have worked on
>several commercial expert system applications.
If you look at John H. Conway's "On Numbers and Games", you
will find a lot about Nim and related matters.
Ilias
Ilias Kastanas
In article <84074426...@cpsoft.demon.co.uk>,
Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:
>
>This is a fantastic idea. When you've developed the equation I would
>like you to adjust it for the following cases and tell me
>immediately:
>
>1. How to get any blonde instantaneously.
Whistle?
OK, OK, ... how about "In my next film..."
>2. How to be the next Lenin. I want an equation to tell me what
>factors to vary so I can be the next dictator of the world, by
>predictable revolutionary activity and adjustments to the price
>of sugar.
I regret I am not at liberty to release this information.
... Sugar? Have you priced armored trains lately?
>3. The equation describing the number of mathemeticians and associated
>theories sustainable in one bounded space before implosion and
>formation of black hole.
Suddenly everything went dark...
Ilias
Simon Read
CW: Chris Whittington <chr...@cpsoft.demon.co.uk>
CW> There aren't any flames directed at you, [...]
CW>
CW> Chris Whittington
CW>
-->
OOooooooooooooh, pleeeeease can I flame him? PLEEEEEASE????
GRRRRRRR THAT MAKES ME SOOOOO ANGRY!
GRRRR HOWLL GNASH!! RIP TEAR CRACK SQUASH!!!
DO YOU REALLY? I MEAN DO YOU REALLY THINK THAT??
GRRRRR THIS MAKES ME SO MAD!!!
YOU'RE SOOOOO STUPID!! ONLY A DUMBFOOL MORON WOULD
HOLD AN OPINION LIKE THAT!!
HOW DARE YOU!!! WHAT A LOAD OF RUBBISH!! YOU CAN'T POSSIBLY
THINK THAT!!!
JUST LISTEN TO WHAT YOU'RE SAYING! GRRRRRRR!!
RIP TEAR MASH GRIND!! GET OUT OF THIS NEWSGROUP!!!
YOU PEOPLE MAKE ME SOOOOO MAD!!!
I hope that makes it clear what I'm saying.
Simon
Chris Whittington
Nope, insufficiently erudite.
Chris Whittington
> Simon
>
CRAIG JOHNSON
In <1996082119...@avernus17.magic.ca> ha...@astral.magic.ca
(Hans Havermann) writes:
>
>Tim Mirabile <t...@mail.htp.com> wrote:
>
>> Items to consider when trying to get the exact number of legal chess
>> positions:
>
>Thank you for your list. There are a few things here I hadn't
explicitly
>considered before.
>
>> And you can't try to tighten your upper bound by calculating how
many of
>> each of these there are and subtracting, because they are not
independent.
>> I think this is enough to show that there is no way to calculate the
>> number of legal positions without checking them all with retrograde
>> analysis, or searching the entire game tree. Sorry guys, this can't
be
>> done with Excel or Mathematica.
>
>Not even Mathematica 3.0? :-)
>
>--
>Nature requires five,
>Custom allows seven,
>Idleness takes nine,
>And wickedness eleven.
I love chess but isn't it but aren't you making it sound a little hard
graham_laight
Best sit down with a nice hot cup of tea, Simon.
You can't foam at the mouth on an empty stomach!
Graham.
Simon wrote:
OOooooooooooooh, pleeeeease can I flame him? PLEEEEEASE????
GRRRRRRR THAT MAKES ME SOOOOO ANGRY!
GRRRR HOWLL GNASH!! RIP TEAR CRACK SQUASH!!!
DO YOU REALLY? I MEAN DO YOU REALLY THINK THAT??
GRRRRR THIS MAKES ME SO MAD!!!
YOU'RE SOOOOO STUPID!! ONLY A DUMBFOOL MORON WOULD
HOLD AN OPINION LIKE THAT!!
HOW DARE YOU!!! WHAT A LOAD OF RUBBISH!! YOU CAN'T POSSIBLY
THINK THAT!!!
JUST LISTEN TO WHAT YOU'RE SAYING! GRRRRRRR!!
RIP TEAR MASH GRIND!! GET OUT OF THIS NEWSGROUP!!!
YOU PEOPLE MAKE ME SOOOOO MAD!!!
I hope that makes it clear what I'm saying.
Simon
In article <3223f...@news.cranfield.ac.uk>, Simon says...
>
Tim Mirabile
ika...@alumnae.caltech.edu (Ilias Kastanas) wrote:
> Vukovic has an example of the classical B:h7+ sacrifice in a French
> Defense position, its correctness tied to whether the WP at a2 has moved
> to a3 or not; White wins in one case and loses in the other.
I'd love to see this, where can I find it? Is it in one of his games?
+----------------------------------------------------------------------+
| Tim Mirabile <t...@mail.htp.com> http://www.angelfire.com/pg9/timm/ |
| TimM on FICS. TheSentinel on FIBS. PGP Key ID: B7CE30D1 |
+----------------------------------------------------------------------+
Simon Read
DG: drgo...@a.stu.athabascau.ca (Dave Gomboc)
DG> Padding to force news poster to accept message with lots of quoted
DG> material is below.
-->
Not necessary, if your newsreader/editor/poster can do the following:
Quote entire document, bung your extra comments on the bottom.
THEN go back into the quoted material, alter it in a very minor
way, then repair it (eg insert a space before one line somewhere
in the middle, then delete it) and the editor will no longer
think that you have pure quoted material, but original stuff.
The news poster will then not have anything to complain about.
HOWEVER, and this constitutes a large "however", I prefer to
quote one or two lines, since the entire previous posting is
still only a mouse-click away.
Simon
Tim Mirabile
Simon Read <s.r...@cranfield.ac.uk> wrote:
>DG: drgo...@a.stu.athabascau.ca (Dave Gomboc)
>DG> Padding to force news poster to accept message with lots of quoted
>DG> material is below.
>Not necessary, if your newsreader/editor/poster can do the following:
>Quote entire document, bung your extra comments on the bottom.
>THEN go back into the quoted material, alter it in a very minor
>way, then repair it (eg insert a space before one line somewhere
>in the middle, then delete it) and the editor will no longer
>think that you have pure quoted material, but original stuff.
>The news poster will then not have anything to complain about.
As I mailed him, the old Netscape used to count all lines with a > in
front as quoted, so simply deleting the >'s in front of blank quoted
lines works well. I still do this out of habit.
>HOWEVER, and this constitutes a large "however", I prefer to
>quote one or two lines, since the entire previous posting is
>still only a mouse-click away.
That depends. On my old news server, it could take a couple of days for
the reply to reach me, and by then the original had been scrolled off.
I know if I really want it, I could go to Deja News, but that's a pain.
But you're right, it's probably best to just quote as little as you need
to comment on.
+----------------------------------------------------------------------+
| Tim Mirabile <t...@mail.htp.com> http://www.angelfire.com/pg9/timm/ |
| TimM on FICS - telnet://fics.onenet.net:5000/ PGP Key ID: B7CE30D1 |
+----------------------------------------------------------------------+
Komputer Korner
Graham, Laight wrote:
> snipped
>
>+----------------------------------------------------------------------+
There is now a team of mathematicians and computer programmers who have
created a special email mailing list and have set up a special web site
to handle this very problem. Email Semaphore Corporation
z...@semaphorecorp.com for more information.
--
Komputer Korner
Dave Gomboc
In article <3229adc2...@snews2.zippo.com>,
Tim Mirabile <t...@mail.htp.com> wrote:
>Simon Read <s.r...@cranfield.ac.uk> wrote:
>>DG: drgo...@a.stu.athabascau.ca (Dave Gomboc)
>>DG> Padding to force news poster to accept message with lots of quoted
>>DG> material is below.
>
>>Not necessary, if your newsreader/editor/poster can do the following:
>
>>Quote entire document, bung your extra comments on the bottom.
>>THEN go back into the quoted material, alter it in a very minor
>>way, then repair it (eg insert a space before one line somewhere
>>in the middle, then delete it) and the editor will no longer
>>think that you have pure quoted material, but original stuff.
>>The news poster will then not have anything to complain about.
>
>As I mailed him, the old Netscape used to count all lines with a > in
>front as quoted, so simply deleting the >'s in front of blank quoted
>lines works well. I still do this out of habit.
I don't use Netscape. It's the machine that handles posting at my
university which gratuitously rejects messages with extensively quoted
material.
--
Dave Gomboc
drgo...@a.stu.athabascau.ca
Don Fong
In article <50i3du$1...@aurora.cs.athabascau.ca>,
Dave Gomboc <drgo...@a.stu.athabascau.ca> wrote:
>>As I mailed him, the old Netscape used to count all lines with a > in
>>front as quoted, so simply deleting the >'s in front of blank quoted
>>lines works well. I still do this out of habit.
>
>I don't use Netscape. It's the machine that handles posting at my
>university which gratuitously rejects messages with extensively quoted
>material.
i have the same "problem". i found that in order to defeat this
feature, it was sufficient to substitute a different quotation character.
--
--- don fong ``i still want the peace dividend''
--