54 views

Skip to first unread message

Sep 23, 1993, 2:39:03 AM9/23/93

to

I've been thinking about chess programming for over a decade now, and

although this may seem short in comparison to some of the gurus in

this field (Bob Hyatt comes to mind), I have managed to come up with

and implement a few good ideas. The last time I sat down and wrote a

chess program, however, was almost 8 years ago.

although this may seem short in comparison to some of the gurus in

this field (Bob Hyatt comes to mind), I have managed to come up with

and implement a few good ideas. The last time I sat down and wrote a

chess program, however, was almost 8 years ago.

I've come up with one idea in particular that I hoped to incorporate

in a future program. True to the traditions of chess programmers I

kept this idea a secret so that I could trounce everybody else who

didn't employ my improvement. It has become clear to me that I won't

have the time to write a chess program any time soon, and that keeping

such algorithms secret harms the advance of the field.

So here it is. I'd be interested to hear if this algorithm has already

been used in some form, whether anyone considers it too inefficient to

be included in an evaluation function, or if its just absolute crap.

Input: A chess position and a piece whose mobility is to be analyzed.

Output: A 8x8 matrix specifying how many moves it would take to reach

a particular square. Squares that cannot be reached would have some

constant <= 0 indicating that they cannot be reached. (The square that

a piece stands on is not automatically reached. This can occurr when a

piece cannot move at all.)

It is easy to envision a use for the output of this algorithm, I hope,

so I won't discuss the applications here.

The Algorithm: The squares of a chess board are viewed as nodes in a

graph. Since there are 64 squares, an adjacency matrix for this graph

would be 64x64. We can precompute the adjacency matrix on an empty

board for all sorts of pieces (pawns are a little different than other

pieces in that their adjacency matrix changes in strange way on a

non-empty board. Sigh). Also, if we use a bit matrix, we can rather

easily modify the adjacency matrix for a piece to reflect the presence

of friendly and unfriendly pawns/pieces on certain squares, the

presence of an unsafe square (i.e. you move here and you'll lose all

sorts of material), pinning squares (your piece is pinned here), etc.,

by ANDing in a precomputed bitmask for that condition and square.

Once we have an adjacency matrix for the (position, piece) pair, we

proceed to take powers of the 64x64 boolean matrix (AND instead of *,

OR instead of + :-). At the n+1st power we note which entries have

changed from 0 (can't be reached) to 1 (can be reached) from the nth

power. The path length of n+1 is then recorded for those entries in a

64x64 integer array of some sort. We halt when the n+1st power is the

same as the nth power; no more changes will occurr (proof left to the

reader :-).

NOTE: If you simply want to know which squares can be reached, you can

compute the 64th power (ridiculous upper bound) quickly by the usual

divide and conquer technique.

In order to contruct the 8x8 path length Output matrix, we map the row

corresponding to the piece's current square to the 8x8 matrix, where

each of the 64 entries in the row corresponds to one of the 64

"squares" in the 8x8 matrix.

NOTE: The 64x64 path length matrix contains quite a bit of

information, and could be used to select things like optimal squares,

critical squares, etc.

Conclusion: Certainly this is an algorithm that can benefit from any

and all code bumming and tweaks.

Some obvious benefits are that it will allow you to easily detect bad

bishops, bad knights, and how the control of one important square can

alter the mobility of your oponents forces. Of course there are many

potential non-intuitive benifits.

Thanks for reading all the way to the end (you must be uterly mad),

PS ispell is busted on this system. sorry

Sep 24, 1993, 6:47:05 AM9/24/93

to

In article <KAP1.93Se...@carol.math.binghamton.edu>

ka...@carol.math.binghamton.edu (Dietrich Kappe) writes:

[...]

>Output: A 8x8 matrix [...]

>The Algorithm: The squares of a chess board are viewed as nodes in a

>graph. [...]

>Once we have an adjacency matrix for the (position, piece) pair, we

>proceed to take powers of the 64x64 boolean matrix (AND instead of *,

>OR instead of + :-). [...]

ka...@carol.math.binghamton.edu (Dietrich Kappe) writes:

[...]

>Output: A 8x8 matrix [...]

>The Algorithm: The squares of a chess board are viewed as nodes in a

>Once we have an adjacency matrix for the (position, piece) pair, we

>proceed to take powers of the 64x64 boolean matrix (AND instead of *,

This all sounds very like some suggestions made in a paper to

one of the first "Computer Chess" conferences, at Oxford 1975. As I

recall, Atkin and Hartston [yes, *the* Hartston] were proposing to

reduce chess to some inverse functional on a 57-dimensional space

[the precise jargon and number escapes me], but the solution was

progressing very slowly. Chatting to Hartston afterwards, I found

that the main obstacle was that they couldn't invert 57x57 matrices

because it would take longer than the age of the universe [they were

Pure mathematicians, trying to do it by Cramer's rule]. I told him

about Gaussian elimination, and he went away *very* happy. Haven't

heard much about it since ....

Incidentally, while I'm here: BBC2, with Hartston, Francine

Stock, etc., is still offering better coverage of [both] WC matches

than Channel 4, but C4 is definitely improving, and Carol Vorderman

now knows enough about chess to ask sensible questions.

--

Andy Walker, Maths Dept., Nott'm Univ., UK.

a...@maths.nott.ac.uk

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu