Board representation 0x88 or bitboard.
RohiT
I'm a beginner chess programmer and want some advise for my chess
engine. As I have relatively very less experience ( I have only read
the many helpful articles on the web as well as posts on this group) I
would like to know which board representation would be easier for me
to comprehend with Bitboards or 0x88. My main aim first is to make a
functional chess engine. If there are any other board representation
schemes which may be usefule please let me know.
Thanks in advance
Simon Krahnke
Take 0x88. It's very easy to understand and implement and is sufficient
for a functional chess engine. For your first engine, concentrate on the
search algorithm, the evaluation function, the transposition table, the
interface.
You might want to change to rotated bitboards later, if you need to
improve. It's more efficient at move generation and thing like SEE.
mfg, simon .... l
Roman Hartmann
"RohiT" <rox...@gmail.com> schrieb im Newsbeitrag
news:4dcb455b.04100...@posting.google.com...
Hi,
I started some time ago writing a chess engine too. Although I did
understand how bitboards work back then when I started I decided to start
with something simpler than bitboards. I choosed an 10x12 array for my
internal board representation. Making a working movegenerator was relatively
easy with this approach but the resulting move generator isn't the fastest
one around, of course. My move generator is now about as fast (perft) as the
one from crafty on a 32-bit CPU (on a 64-bit CPU this would be different, of
course). 10x12 is easy to understand and might be a good start for a
beginner, although most people are using either 0x88 or bitboard
representation.
If you are interested in the 10x12 board representation just google for the
file minimax.c. With the hep of this file you should get an idea how your
board representation could look like (just take care not to look at sources
of other chess engines too closely).
Roman
RohiT
> internal board representation. Making a working movegenerator was relatively
> easy with this approach but the resulting move generator isn't the fastest
> one around, of course. My move generator is now about as fast (perft) as the
> one from crafty on a 32-bit CPU (on a 64-bit CPU this would be different, of
> course). 10x12 is easy to understand and might be a good start for a
> beginner, although most people are using either 0x88 or bitboard
> representation.
Thanks for the advice. I was just wondering how do you make a move
generator for any such representation which uses a 2-D array. The one
which seemed obvious to me was to scan each of the columns or rows one
by one checking for pieces, if a piece is found in a particular cell
generate all the legal moves for it. This isn't too complicated (I
guess) but is there some other way which is more efficient for this
representaion?
Thanks
Rohit
Roman Hartmann
Well, the board representation isn't really 2d but rather an int array with
120 elements. There are 120 fields because there are two rows added at the
bottom and top and one on each side of the board. This makes it easier to
detect if your moves are valid or not and you don't have to to worry about
array overruns as no (non valid) moves will produce a buffer overflow.
The square A1 could now be adressed with board[21] and H8 with board[98].
The pieces have usually integer values K: 6, Q: 5, R: 4, B: 3, N: 2, P: 1.
The black pieces have the same but negative values. The rows at the bottom
and at the top get a value to show that they don't belong to the board
anymore i.e. 100. If one of the moves leads to a field with this value you
know this is not a valid move. The different pieces have now different
offsets (numbers you can add to the current square to reach the target
square). For the knight valid offsets are 19, -19, 12, -12, 8, -8, 21, -21.
King: 1, -1, 10, -10, 9, -9, 11, -11.
The white pieces can move if the target field is either empty (i.e has the
value 0) or if it has a negative value (means that a black piece is on that
field). The black pieces can move to a specific target square if the field
is either empty or when the value is above 0 and not 100 (would be the
border).
The easiest approach now is to loop through your board and when you find a
piece, generate the valid moves (no moves allowed that leave or bring your
king into check) and store them in a list. That should get you started or at
least give you an idea how it works.
Hope that clears things a bit up
cheers
Roman
Simon Krahnke
> The easiest approach now is to loop through your board and when you find a
> piece, generate the valid moves (no moves allowed that leave or bring your
> king into check) and store them in a list. That should get you started or at
> least give you an idea how it works.
Testing for putting (or leaving) the king in check is easier done while
searching. You do the move on the board, recurse only if legal, undo the
move. The test is executed not once per move generated, but once per
move searched.
mfg, simon .... l
Roman Hartmann
"Simon Krahnke" <over...@gmx.li> schrieb im Newsbeitrag
news:878yalo...@xts.gnuu.de...
That seems to be the faster approach, of course. Still it's very nice to
have a legal move generator instead of a pseudo legal move generator.As an
example you instantly know when you run out of moves and don't have to test
the legalitity of your moves after doing them on the internal board. While
you spend more time in makemovelist(..) you need less time in domove(..).
If the movegenerator gives back zero (assuming the function gives back the
number of valid moves) you know it's either mate or stalemate. That way the
function can be used in a very simple way also in search.
if(makemovelist(&p, list) == 0 && imschach(&p) == TRUE)
printf("\nMatt");
if(makemovelist(&p, list) == 0 && imschach(&p) == FALSE)
printf("\nPatt");
My move generator generates only legal moves and isn't that slow at all. But
I will test also a pseudo legal move generator (and also add a piece list
for testing purposes) just to see if that speeds things up a bit.
mfg
Roman
Alexander Belov
says move leads to valid position and has beta cutoff you don't need
to check validity of the rest.
"Roman Hartmann" <rhar...@bluewin.ch> wrote in message
news:41638654$1...@news.bluewin.ch...
Simon Krahnke
> Nice feature of pseudo legal move generator is that if tranposition table
> says move leads to valid position and has beta cutoff you don't need
> to check validity of the rest.
The transposition table is not relevant here, it's alpha-beta that does
the cut which makes the difference between moves generated and moves
Simon Krahnke
>> Testing for putting (or leaving) the king in check is easier done while
>> searching. You do the move on the board, recurse only if legal, undo the
>> move. The test is executed not once per move generated, but once per
>> move searched.
>
> That seems to be the faster approach, of course. Still it's very nice to
> have a legal move generator instead of a pseudo legal move generator.
But these nice-to-haves usually happen in sections, where performance
doesn't matter. It's better to optimize for use in top-performance
sections like the search.
> As an example you instantly know when you run out of moves and don't
> have to test the legalitity of your moves after doing them on the
> internal board. While you spend more time in makemovelist(..) you need
> less time in domove(..). If the movegenerator gives back zero
> (assuming the function gives back the number of valid moves) you know
> it's either mate or stalemate. That way the function can be used in a
> very simple way also in search.
I can just count each move searched, and if I didn't search any, it mate
or stalemate. Actually, I don't need to count, I just check my
bestValue, and if it's still -INFINITY I know I didn't search any.
> if(makemovelist(&p, list) == 0 && imschach(&p) == TRUE)
> printf("\nMatt");
> if(makemovelist(&p, list) == 0 && imschach(&p) == FALSE)
> printf("\nPatt");
Du machst es dir ja einfach, alles auf deutsch zu schreiben. :-)
| if(!makemovelist(&p, list) puts (imschach(&p) ? "\nMatt" : "\nPatt");
> My move generator generates only legal moves and isn't that slow at all.
How do you do that? You actually have to do the move on board, to be
able to check, don't you?
> But I will test also a pseudo legal move generator (and also add a
> piece list for testing purposes) just to see if that speeds things up
> a bit.
Should do, tell me.
mfg, simon .... l
RohiT
> cheers
> Roman
Thanks a ton
Cheers
RohiT
Roman Hartmann
> * Roman Hartmann <rhar...@bluewin.ch> (07:46) schrieb:
>
> >> Testing for putting (or leaving) the king in check is easier done while
> >> searching. You do the move on the board, recurse only if legal, undo
the
> >> move. The test is executed not once per move generated, but once per
> >> move searched.
> >
> > That seems to be the faster approach, of course. Still it's very nice to
> > have a legal move generator instead of a pseudo legal move generator.
>
> But these nice-to-haves usually happen in sections, where performance
> doesn't matter. It's better to optimize for use in top-performance
> sections like the search.
In certain positions when only a few legal moves are left legal move
generators seems to have an advantage. In the end the performance of the
move generator isn't that important anyway. Still I try to make it as fast
as possible as this gives me some extra time I can spend evaluating the
moves properly.
> > As an example you instantly know when you run out of moves and don't
> > have to test the legalitity of your moves after doing them on the
> > internal board. While you spend more time in makemovelist(..) you need
> > less time in domove(..). If the movegenerator gives back zero
> > (assuming the function gives back the number of valid moves) you know
> > it's either mate or stalemate. That way the function can be used in a
> > very simple way also in search.
>
> I can just count each move searched, and if I didn't search any, it mate
> or stalemate. Actually, I don't need to count, I just check my
> bestValue, and if it's still -INFINITY I know I didn't search any.
My search is still quite simple (pure alpha-beta). I'm still working on the
move generator mainly.
> > if(makemovelist(&p, list) == 0 && imschach(&p) == TRUE)
> > printf("\nMatt");
> > if(makemovelist(&p, list) == 0 && imschach(&p) == FALSE)
> > printf("\nPatt");
>
> Du machst es dir ja einfach, alles auf deutsch zu schreiben. :-)
Die meisten meiner Funktionen haben zwar englische Namen aber da ich auch
eine Funktion incheck(..) habe und nicht eine incheck2(..) Funktion
einführen wollte, habe ich sie halt imschach(..) getauft. Bei mittlerweile
mehr als 35 verschiedenen Funktionen und über 4000 Zeilen Code wird es halt
langsam auch etwas unübersichtlich. Prägnante Namen helfen da schon ganz
gut, nicht den Überblick zu verlieren :)
> | if(!makemovelist(&p, list) puts (imschach(&p) ? "\nMatt" : "\nPatt");
I try to keep the source as simple as possible (means the code is sometimes
a bit longwinded). But then my version is probably easier to read at 2AM and
the output of the compiler should be the same (not in this case because of
printf/puts) :)
> > My move generator generates only legal moves and isn't that slow at all.
>
> How do you do that? You actually have to do the move on board, to be
> able to check, don't you?
I do have a stripped down domove for this task. The move is made and then
checked if the king is attacked by an opp. piece. But this simplified domove
doesn't have to update any castling flags or promotion flags and the call to
that function is therefore not very timeconsuming. But of course time sums
up as I have to call it everytime a move is generated. I will change the
code to act a bit more clever soon as I'm now checking now every move if the
king gets into check even when the king is sheltered by pawns as an example.
Adding a list with pinned pieces might help, I guess.
> > But I will test also a pseudo legal move generator (and also add a
> > piece list for testing purposes) just to see if that speeds things up
> > a bit.
>
> Should do, tell me.
I removed all the testmove functions from the movegenerator to test it.
There is a 3x (over 15Mn/s now on my AMD XP 3200+) speedup from the initial
position with the pseudo legal move generator now but when the position
get's closed (and the king get's into check often) it slows down quite a bit
by all the move/undomoves that have to be done before the king get's either
out of check or there are no moves left and the king is mated. Maybe I
shouldn't do incheck tests but rather just let the king getting captured and
then cut off this leaf and --nodes.
In some positions (especially in blocked positions) the move generating
process with the pseudo legal move generator is now much much slower than it
was before. Additionally the values from perft 4 upwards are a bit off by
now. This is probably because the program is made to deal with lists of
legal moves in the first place and now it has to deal with lists of pseudo
legal moves and some tests are not yet made properly on them, obviously. But
I will recreate my movegenerator/domove/undomove functions (and adjust the
data structure) to deal with that properly and will give it another try
soon.
mfg Roman
> mfg, simon .... l
Simon Krahnke
> I removed all the testmove functions from the movegenerator to test it.
> There is a 3x (over 15Mn/s now on my AMD XP 3200+) speedup from the initial
> position with the pseudo legal move generator now
3x? Wow.
> but when the position get's closed (and the king get's into check
> often) it slows down quite a bit by all the move/undomoves that have
> to be done before the king get's either out of check or there are no
> moves left and the king is mated.
So they are getting slower than with legal move generation because of
the more expensive doMove() and the other move dealing code inside the
search.
> Maybe I shouldn't do incheck tests but rather just let the king
> getting captured and then cut off this leaf and --nodes.
We had a short thread about this. Every time I generate a capture, I
look if the captured piece is a king. If so, I return a special value.
I've been told, this is not optimal because of the conditional code on
every generated capture.
mfg, simon .... l