Mobility Measure: Proposed Algorithm
Dietrich Kappe
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
Dr A. N. Walker
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