Datastructures in computer chess
Gustav Grundin
very little about computer chess programming specifics. For this
reason I come to you with some questions. Today let's start with the
basics - Board Representation.
Is there a concensus among the authors of computer chess
programs on which datastructures are optimal for representing the
board? I've studied the crafty-style representation (as it is
presented in the movegen, make and unmake routines). It seems clearly
obviuous that this representation is superior in several ways to
the naive way of just storing the board in a 64-byte array, with the
values of the piece occupying each square.
When computer chess people talk in terms of representing the
chessboard by 64-bit arrays, I assume that, what they are talking
about is something simlar to the crafty way. Is this correct?
I've also read about programs, for instance KnightCap (I think it
was KnightCap but I'm not entirely sure), who
store the ChessBoard in some sort of AttacksTo[32] array for each
square on the board. This array has, as far as I can understand, a
specific bit set under the condition that the individual piece which
corresponds to that bit is attacking that particular square. Have I
understood this method correctly?
I fail to see how, in any obious way, this datastructure could be
used to generate moves. Is it possibly, that this datastructure is
just a complement to the crafty-representation? I do understand that
it would have some use in the evaluation function in answering
questions such as which player controls a given square.
Are there other approaches to board representation than those that I
have mentioned above?
I hope there is still room in this forum for discusions not regarding
who said or did not say what when.
Gustav Grundin
Royal Institute of Technology
Sweden
Paul Onstad
> Are there other approaches to board representation than those that I
> have mentioned above?
>
> I hope there is still room in this forum for discusions not regarding
> who said or did not say what when.
<Amen>
My comment does not address a board for a chess playing program but for move
making... There is still something to be said for the 64 sq. matrix. If
position searching is to be a feature, the matrix--or something easily
translatable to the matrix--would still seem necessary.
My implementation is pretty simple--just ordinals for piece and side per
square plus a Boolean for "virtual pawn" (en passant). I regret somewhat I
did not take everything down to the bit level for compression as many
indexes by board position often end up in memory or on disk and can be quite
sizable if all moves of many games are indexed. As it is, when indexing is
necessary, I often compute a two byte hash and store that.
-Paul
Gustav Grundin
> position searching is to be a feature, the matrix--or something easily
> translatable to the matrix--would still seem necessary.
Why, in a position searching situation, is it necessary to have a 64
sq. matrix?
Gunnar Andersson
If you have never implemented the alpha-beta algorithm (or some
variation thereof), I think you should try the mailbox representation
first. Rotated bitboards etc are powerful but very ambitious for a
first chess program - and you'll probably start off with a pretty
simple evaluation function anyway.
Disclaimer: It's been ten years since I wrote a chess program but I
have since created one of the top 5 (probably #3) Othello programs in
the world. This program uses mailbox representation but evaluation
functions in Othello are quite different from those in chess.
My $0.02...
/ Gunnar
Gustav Grundin
> variation thereof), I think you should try the mailbox representation
> first. Rotated bitboards etc are powerful but very ambitious for a
> first chess program - and you'll probably start off with a pretty
> simple evaluation function anyway.
I have not yet implemented my search algoritm (which will be some
variant of alpha-beta), but I have already implemented move
generation by rotated bitboards. I still have a mailbox
representation to be able to make and unmake moves in a simple manner
(this will eventually dissapear), while I go on to studies of
diffrent types of search algoritms.
Its just that I don't feel like leaving the movegeneration/make and
unmake routines until I'm confident that I've implemented them in the
way which is considered to be the best.
Anders Thulin
Gustav Grundin <d98...@nada.kth.se> wrote:
>Its just that I don't feel like leaving the movegeneration/make and
>unmake routines until I'm confident that I've implemented them in the
>way which is considered to be the best.
You may implement 'the best' move generation methods, and then go on
and make some other decision (in the scoring function or in hash
table) that makes the whole question of best move generation
moot.
From one point of view, the bitboard methods of move generation as
used in Crafty are flawed, as there's a pretty elaborate conversion
between data formats involved: moves as bitboards are converted to
moves as move records. It seems a good method should not introduce
such a drastic data format conversion: it takes time.
However, keeping pre-generated moves record lists around carries a
cost in memory, and indirectly in terms of paging behaviour of the
application: making move generation faster might cause the entire
application to slow down, if you're close to stepping on the process
working set limits. Are you? Do you know? When can you decide?
What criteria are you using to decide, and when? Speed of move
generation alone? Or speed of final application? Amount of memory
used? Or just the opinion of others? Personally, I'd use a very, very
simple method until the entire application was working, and then
decide what parts of it need to be spent time on.
So far, it seems that user interface design leads. Code neatness
and clarity comes in second place. But that's just my opinion.
--
Anders Thulin Anders....@telia.se 013-23 55 32
Telia ProSoft AB, Teknikringen 6, S-583 30 Linkoping, Sweden
Gustav Grundin
> and make some other decision (in the scoring function or in hash
> table) that makes the whole question of best move generation
> moot.
This is definitely a possibility, and this is the reason why I would
like to hear from people who have already constructed complete chess
engines. It would be intresting to hear their views on which
approaches pose which restrictions or complications in the process of
making effective evaluation and search-functions.
> From one point of view, the bitboard methods of move generation as
> used in Crafty are flawed, as there's a pretty elaborate conversion
> between data formats involved: moves as bitboards are converted to
> moves as move records. It seems a good method should not introduce
> such a drastic data format conversion: it takes time.
I still haven't heard of a more efficient alternative to this
approach. Yes, the conversion takes time, but this cost in time is
definitely less than the cost of generating moves the "naive" way.
Perhaps there is an efficient algoritm for say rookmovegeneration,
that does not involve bitboards? In that case I would certainly be
thrilled to hear about it.
> However, keeping pre-generated moves record lists around carries a
> cost in memory, and indirectly in terms of paging behaviour of the
> application: making move generation faster might cause the entire
> application to slow down, if you're close to stepping on the process
> working set limits. Are you? Do you know? When can you decide?
The system i I will be running on during this period of development
has 512 MB of RAM. I do not feel that the precalculated movelists
(approximately 500 K in size) are of an uncontrollable size.
> What criteria are you using to decide, and when? Speed of move
> generation alone? Or speed of final application? Amount of memory
> used? Or just the opinion of others? Personally, I'd use a very, very
> simple method until the entire application was working, and then
> decide what parts of it need to be spent time on.
Naturally there are a lot of factors which have impact on the
programs playing strenght. Still there is no question about the fact
that movegeneration is one of the routines which will be executed the
most number of times during a search. Fast move generation must in
the end, be an important factor. Allthough this factor of course is
less significant than for instance getting a high rate of cut-offs
during the search.
> So far, it seems that user interface design leads. Code neatness
> and clarity comes in second place. But that's just my opinion.
To me, user interface is nothing, chess playing strength on the
other hand - is everything
bruce moreland
>Are there other approaches to board representation than those that I
>have mentioned above?
>
>I hope there is still room in this forum for discusions not regarding
>who said or did not say what when.
>
>Gustav Grundin
>Royal Institute of Technology
>Sweden
There are many ways to do it, and it is possible to write a strong
program that uses any of them. I think that a large reason why people
spend so much time on board representation and move generation is that
it is the first thing they have to do, but the strength of a program
comes from many other places than just that.
A naive way of storing the board is as a 12 x 12 array, the 8 x 8
board sits in the midde of this, and the 2-square border is used to
detect pieces moving off the board.
There is the method that isn't called "0x88" anywhere else, but is
called "0x88" here, which involves a board that is 8 ranks by 16
files, the real board is the left-most half of this. The extra
squares don't serve any purpose other than to create an extra bit in
the middle of the square index value, which is used to detect
off-board conditions. I don't want to go into it too much, but the
basic idea is that if you have an index into the real board, and you
add a value to it that corresponds to the movement of any chess piece,
if the resulting new index AND'd with 0x88 is non-zero, you are off
the board, either left-right, top-bottom, or both.
There is also the move table method, which involves a large table of
pseudo-legal moves, which contain pointers into whatever board
data-structure you use (which can most simply be an 8 x 8 array).
With this method, move generation is a matter of processing the right
part of this table.
Lots of ways to do it. Some might be better than others. Even if one
is demonstrably better at generating moves, the others may give you
advantages that you can make use of elsewhere in the program.
bruce
Mike Leahy - Bookup
bruce moreland wrote:
Bookup uses a 10x10 array with the 'real' 8x8 board in the middle.
As a knight tries to move off the 'right' edge by two squares, it lands on
the 'left'
edge and vice versa. If a knight tries to go off the front or back of the
board it's
just caught by range checking.
Bookup stores the board and move/enpassant/castling rights in a 33 byte
array
with a halfbyte per square. Now that computers are speedy, version 2.0 may
start using compression.
> [snip]
> bruce
Mike Leahy
"The Database Man!" http://www.bookup.com
Paul Onstad
Check the ECO thread in rgc.misc. ..Couple of questions for you.
-Paul
Urban Koistinen
>I've also read about programs, for instance KnightCap (I think it
>was KnightCap but I'm not entirely sure), who
>store the ChessBoard in some sort of AttacksTo[32] array for each
>square on the board. This array has, as far as I can understand, a
>specific bit set under the condition that the individual piece which
>corresponds to that bit is attacking that particular square. Have I
>understood this method correctly?
Yes, I think so.
>I fail to see how, in any obious way, this datastructure could be
>used to generate moves. Is it possibly, that this datastructure is
>just a complement to the crafty-representation? I do understand that
>it would have some use in the evaluation function in answering
>questions such as which player controls a given square.
It is earlier than the rotated bitboard method by at least a few years.
It is very good for generating captures.
With minimax that is often all that is needed.
For generating the other moves, mailbox is fine and if you don't
need to generate captures the mailbox code gets faster.
A datastructure with position of the pieces and promotion status
of the pawns is needed too.
>Are there other approaches to board representation than those that I
>have mentioned above?
Plenty.
>Royal Institute of Technology
>Sweden
That is where I did most of my chess programming.
If you would care to do some endgame tablebase programming,
I'd be happy to help with algorithms. (to improve the state of the art)
Urban Koistinen - m10...@abc.se