Hi!

I realized that the InCheck function of my chess programm is a bottleneck.
While the tablebased movegeneration seems fast enough, and also MakeMove is
acceptable, InCheck is really slow. Currently I do MakeMove and check the
legality by InCheck. Looking one ply deeper and getting the information
about illegal positions by generating all moves and recognizing a king
capture didn't really show a better performance.
So I ask: Could this be an issue for bitboards?
I have neither thought about nor really looked at bitboards that much, they
just seems difficult to handle.
(And what about move generation when transforming the bitboard informations
into a move list)?

Thanks
-delphi-

Delphi wrote:
Hi!

I realized that the InCheck function of my chess programm is a bottleneck.
While the tablebased movegeneration seems fast enough, and also MakeMove is
acceptable, InCheck is really slow. Currently I do MakeMove and check the
legality by InCheck. Looking one ply deeper and getting the information
about illegal positions by generating all moves and recognizing a king
capture didn't really show a better performance.


This is what I do. IE in _most_ cases, the move you make is perfectly
legal. Which means doing the "in check" test is not necessary. There
are other reasons to do an in check test, of course, but if you only
care about legality, ignore it, make the move, and generate moves at the
next ply. If you capture a king, return "last move was illegal" and you
are done. Since that is rare, the cost is low.


So I ask: Could this be an issue for bitboards?
I have neither thought about nor really looked at bitboards that much, they
just seems difficult to handle.
(And what about move generation when transforming the bitboard informations
into a move list)?

You don't necessarily have to do that. I use bitmaps in Crafty, and I
do turn the moves into a list, because that is more convenient for ordering
them. But there are examples of programs that generate moves one at a
time (chess 4.x, the original bitmap program, did that.)



Thanks
-delphi-



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

Delphi wrote:
----- Original Message -----
From: "Robert Hyatt"
Newsgroups: rec.games.chess.computer
Sent: Wednesday, August 27, 2003 11:13 PM
Subject: Fast InCheck function


Delphi wrote:
Hi!

I realized that the InCheck function of my chess programm is a
bottleneck.
While the tablebased movegeneration seems fast enough, and also MakeMove
is
acceptable, InCheck is really slow. Currently I do MakeMove and check
the
legality by InCheck. Looking one ply deeper and getting the information
about illegal positions by generating all moves and recognizing a king
capture didn't really show a better performance.


This is what I do. IE in _most_ cases, the move you make is perfectly
legal. Which means doing the "in check" test is not necessary. There
are other reasons to do an in check test, of course, but if you only
care about legality, ignore it, make the move, and generate moves at the
next ply. If you capture a king, return "last move was illegal" and you
are done. Since that is rare, the cost is low.

Well, I _do_ one InCheck call at each position:
As I use search extension due to checks, it can't be avoided. Additionally I
will not start
a null-move search when the side to play is in check. And at the leaf nodes,
before
evaluating the position, I have to verify that it is not a mate or
stalemate, which again is done
by InCheck. In my program therefore this InCheck calls are no performance
gain
over the king-capture method, although there are fewer than when in
MakeMove.

OK.. That works fine. What about the q-search? I don't worry about
checks or anything there, so I avoid the in-check testing out there where
the search is _very_ expensive due to the number of q-search nodes.




So I ask: Could this be an issue for bitboards?
I have neither thought about nor really looked at bitboards that much,
they
just seems difficult to handle.
(And what about move generation when transforming the bitboard
informations
into a move list)?

You don't necessarily have to do that. I use bitmaps in Crafty, and I
do turn the moves into a list, because that is more convenient for
ordering
them. But there are examples of programs that generate moves one at a
time (chess 4.x, the original bitmap program, did that.)


I though of my method of move generation with some kind of "preorder":
simple put all moves into a list, captures put to the head, the others put
to the tail.

With bitmaps you can beat this easily. Just don't generate non-captures
until after you generate all the captures and see if any of them are
good enough to try and good enough to cause a cutoff. If not, then you
can generate the non-captures separately, but only when needed. Bitmaps
make it easy to generate only captures...




But I guess, something similar could also be done with bitboards, when
generating (first) only captures,
for example.
So would you say that switching to bitboards will pay off (I know there are
other possible
uses for bitboards) after one has _really_ figured out how they work?

Yes, but it takes time to "think bitmaps". When I converted in 1994,
I made a mental contract with myself to stick with them for at least
three years. The first year was a bit on the difficult side as it is
a different way of thinking. The second year was easier, and by the
time the third year had passed I was sold and could "think bitmaps"
without getting a headache or puking.

I don't think bitmaps are a great leap forward (yet) because we still
depend on 32 bit hardware for the most part. But once you get to a
64 bit machine, bitmap programs take better advantage of the 64 bit
wide registers and datapaths because all 64 bits have "meaning".


Thanks
-delphi-



Thanks
-delphi-



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

But once you get to a
64 bit machine, bitmap programs take better advantage of the 64 bit
wide registers and datapaths because all 64 bits have "meaning".

I think the 'all 64 bits have meaning' argument is pretty silly, just
as the 'data density' you spoke of in the past. For example, a typical
bitboard looks like this:

00000000
00000000
00000000
00000000
00000000
00001000
00000000
00000000

They're good at moving zeroes, yes

--
GCP

"Robert Hyatt" schrieb im Newsbeitrag
...
Delphi wrote:
----- Original Message -----
From: "Robert Hyatt"
Newsgroups: rec.games.chess.computer
Sent: Wednesday, August 27, 2003 11:13 PM
Subject: Fast InCheck function


Delphi wrote:
Hi!

I realized that the InCheck function of my chess programm is a
bottleneck.
While the tablebased movegeneration seems fast enough, and also
MakeMove
is
acceptable, InCheck is really slow. Currently I do MakeMove and check
the
legality by InCheck. Looking one ply deeper and getting the
information
about illegal positions by generating all moves and recognizing a
king
capture didn't really show a better performance.


This is what I do. IE in _most_ cases, the move you make is perfectly
legal. Which means doing the "in check" test is not necessary. There
are other reasons to do an in check test, of course, but if you only
care about legality, ignore it, make the move, and generate moves at
the
next ply. If you capture a king, return "last move was illegal" and
you
are done. Since that is rare, the cost is low.

Well, I _do_ one InCheck call at each position:
As I use search extension due to checks, it can't be avoided.
Additionally I
will not start
a null-move search when the side to play is in check. And at the leaf
nodes,
before
evaluating the position, I have to verify that it is not a mate or
stalemate, which again is done
by InCheck. In my program therefore this InCheck calls are no
performance
gain
over the king-capture method, although there are fewer than when in
MakeMove.

OK.. That works fine. What about the q-search? I don't worry about
checks or anything there, so I avoid the in-check testing out there where
the search is _very_ expensive due to the number of q-search nodes.



My q-search is very simple, as I didn't find a good way to reduce the number
of nodes searched there.
I consider only some captures there, so as in the other search part InCheck
is called in MakeMove
and of course again in the leaf nodes. Did you mean that by avoiding the
in-check testing?




So I ask: Could this be an issue for bitboards?
I have neither thought about nor really looked at bitboards that
much,
they
just seems difficult to handle.
(And what about move generation when transforming the bitboard
informations
into a move list)?

You don't necessarily have to do that. I use bitmaps in Crafty, and I
do turn the moves into a list, because that is more convenient for
ordering
them. But there are examples of programs that generate moves one at a
time (chess 4.x, the original bitmap program, did that.)


I though of my method of move generation with some kind of "preorder":
simple put all moves into a list, captures put to the head, the others
put
to the tail.

With bitmaps you can beat this easily. Just don't generate non-captures
until after you generate all the captures and see if any of them are
good enough to try and good enough to cause a cutoff. If not, then you
can generate the non-captures separately, but only when needed. Bitmaps
make it easy to generate only captures...



And how to deal with moves from the TT, which should be searched before
captures,
but should be pseudo-legal in that position?
Asked differently: Is it fast to verify with bitmaps, if a certain move is
pseudo-legal in a certain position?




But I guess, something similar could also be done with bitboards, when
generating (first) only captures,
for example.
So would you say that switching to bitboards will pay off (I know there
are
other possible
uses for bitboards) after one has _really_ figured out how they work?

Yes, but it takes time to "think bitmaps". When I converted in 1994,
I made a mental contract with myself to stick with them for at least
three years. The first year was a bit on the difficult side as it is
a different way of thinking. The second year was easier, and by the
time the third year had passed I was sold and could "think bitmaps"
without getting a headache or puking.


Well, that might just be my problem: Time!
However, getting interested in bitmaps more and more :-)


I don't think bitmaps are a great leap forward (yet) because we still
depend on 32 bit hardware for the most part. But once you get to a
64 bit machine, bitmap programs take better advantage of the 64 bit
wide registers and datapaths because all 64 bits have "meaning".


Thanks
-delphi-



Thanks
-delphi-



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

Delphi wrote:
"Robert Hyatt" schrieb im Newsbeitrag
...
Delphi wrote:
----- Original Message -----
From: "Robert Hyatt"
Newsgroups: rec.games.chess.computer
Sent: Wednesday, August 27, 2003 11:13 PM
Subject: Fast InCheck function


Delphi wrote:
Hi!

I realized that the InCheck function of my chess programm is a
bottleneck.
While the tablebased movegeneration seems fast enough, and also
MakeMove
is
acceptable, InCheck is really slow. Currently I do MakeMove and check
the
legality by InCheck. Looking one ply deeper and getting the
information
about illegal positions by generating all moves and recognizing a
king
capture didn't really show a better performance.


This is what I do. IE in _most_ cases, the move you make is perfectly
legal. Which means doing the "in check" test is not necessary. There
are other reasons to do an in check test, of course, but if you only
care about legality, ignore it, make the move, and generate moves at
the
next ply. If you capture a king, return "last move was illegal" and
you
are done. Since that is rare, the cost is low.

Well, I _do_ one InCheck call at each position:
As I use search extension due to checks, it can't be avoided.
Additionally I
will not start
a null-move search when the side to play is in check. And at the leaf
nodes,
before
evaluating the position, I have to verify that it is not a mate or
stalemate, which again is done
by InCheck. In my program therefore this InCheck calls are no
performance
gain
over the king-capture method, although there are fewer than when in
MakeMove.

OK.. That works fine. What about the q-search? I don't worry about
checks or anything there, so I avoid the in-check testing out there where
the search is _very_ expensive due to the number of q-search nodes.



My q-search is very simple, as I didn't find a good way to reduce the number
of nodes searched there.
I consider only some captures there, so as in the other search part InCheck
is called in MakeMove
and of course again in the leaf nodes. Did you mean that by avoiding the
in-check testing?

In the q-search I _never_ do an "in check" test. If you use the same
MakeMove() in the normal and quiescence searches, then it sounds like
you do in-check everywhere..




So I ask: Could this be an issue for bitboards?
I have neither thought about nor really looked at bitboards that
much,
they
just seems difficult to handle.
(And what about move generation when transforming the bitboard
informations
into a move list)?

You don't necessarily have to do that. I use bitmaps in Crafty, and I
do turn the moves into a list, because that is more convenient for
ordering
them. But there are examples of programs that generate moves one at a
time (chess 4.x, the original bitmap program, did that.)


I though of my method of move generation with some kind of "preorder":
simple put all moves into a list, captures put to the head, the others
put
to the tail.

With bitmaps you can beat this easily. Just don't generate non-captures
until after you generate all the captures and see if any of them are
good enough to try and good enough to cause a cutoff. If not, then you
can generate the non-captures separately, but only when needed. Bitmaps
make it easy to generate only captures...



And how to deal with moves from the TT, which should be searched before
captures,

Search them _before_ you generate any moves. Testing for legality (pseudo-
legality actually) is easy. Make sure the moving piece is on the from
square, the captured piece is on the to square, etc...


but should be pseudo-legal in that position?
Asked differently: Is it fast to verify with bitmaps, if a certain move is
pseudo-legal in a certain position?

Yes, although it is fast without bitmaps also...




But I guess, something similar could also be done with bitboards, when
generating (first) only captures,
for example.
So would you say that switching to bitboards will pay off (I know there
are
other possible
uses for bitboards) after one has _really_ figured out how they work?

Yes, but it takes time to "think bitmaps". When I converted in 1994,
I made a mental contract with myself to stick with them for at least
three years. The first year was a bit on the difficult side as it is
a different way of thinking. The second year was easier, and by the
time the third year had passed I was sold and could "think bitmaps"
without getting a headache or puking.


Well, that might just be my problem: Time!
However, getting interested in bitmaps more and more :-)


I don't think bitmaps are a great leap forward (yet) because we still
depend on 32 bit hardware for the most part. But once you get to a
64 bit machine, bitmap programs take better advantage of the 64 bit
wide registers and datapaths because all 64 bits have "meaning".


Thanks
-delphi-



Thanks
-delphi-



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

I think the 'all 64 bits have meaning' argument is pretty silly, just
as the 'data density' you spoke of in the past. For example, a typical
bitboard looks like this:

00000000
00000000
00000000
00000000
00000000
00001000
00000000
00000000

They're good at moving zeroes, yes


Sorry, but you miss the point. _every_ "zero" is _important_. Each
one represents an empty square. Or don't you care which squares are
empty?

zeroes are _not_ unimportant data when they each have specific
meaning.

My point is about efficiency of representation.

You are saying:

'There is no rook on a1. There is no rook on a2. There is no rook on a3.
There is no rook on a4. There is no rook on a5. There is no rook on a7.
There is no rook on a8. There is no rook on b1. ... [and so on]'

I prefer to say:

'There's a rook on a6.'

--
GCP

However, when thinking about check testing before, I discarded the idea of
doing it "incrementally",
as it seemed too complicated and also not very fast (I though, there were
too many cases
of ranks/files/diagonals getting opened or closed, "rays" getting cut and
so
on).

You only need to look at rays that can actually bear on your king.

If you find a certain case too difficult to deal with, just call
the old incheck routine at that point. As long as the majority of
cases is handled the quick way, you'll be fine.

--
GCP

Gian-Carlo Pascutto wrote:
I think the 'all 64 bits have meaning' argument is pretty silly, just
as the 'data density' you spoke of in the past. For example, a typical
bitboard looks like this:

00000000
00000000
00000000
00000000
00000000
00001000
00000000
00000000

They're good at moving zeroes, yes


Sorry, but you miss the point. _every_ "zero" is _important_. Each
one represents an empty square. Or don't you care which squares are
empty?

zeroes are _not_ unimportant data when they each have specific
meaning.

My point is about efficiency of representation.

You are saying:

'There is no rook on a1. There is no rook on a2. There is no rook on a3.
There is no rook on a4. There is no rook on a5. There is no rook on a7.
There is no rook on a8. There is no rook on b1. ... [and so on]'

I prefer to say:

'There's a rook on a6.'

--
GCP


except there is _no_ usable representation of the board that does
that.



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

except there is _no_ usable representation of the board that does
that.

....that you know of

--
GCP