Rotated bitboards - experiment and result
Robert Hyatt
-->
-->Arasan, my Windows chess program, currently maintains a database
-->in the board structure that holds, for each square, a list (compacted
-->in bit form) of pieces attacking the square. This is updated on
-->every move. The incremental update is fast (typically around 5%
-->of total search time). However, one defect of this approach is that
-->it currently doesn't handle "stacked" attackers (e.g. White rooks
-->on a1 and a2 attacking black pawn on a6). This causes some "en prise"
-->and "attack gain" calculations involving this info to be incorrect.
-->There is some special-case capture extension code in the search module
-->which partially corrects for this problem, but the problem is still
-->there.
-->
-->I have experimented over the past month or so with putting the
-->rotated bitboard attack generation code from Crafty into Arasan.
-->I have used the "old", non-compacted, non-assembly attack code,
-->because it's easier to program. Even this wasn't exactly easy,
-->because Arasan has a different board representation (square 0
-->is a8 on the chessboard, not a1 as in Crafty) and the bitmap
-->class uses the opposite bit numbering from Crafty.
-->
-->The results were rather disappointing. Tree sizes went down about 20%,
-->which I attribute to better move ordering and more precise capture
-->extension behavior, due to the more accurate attack estimation code.
-->But nodes/sec. decreased by more than 50%, so there is no net gain.
-->
-->One of the problems here is that Arasan was built with incremental
-->attack updating, so it assumes in a lot of places that querying attack
-->info is basically free. E.g. center control in the scoring module
-->is computed by finding which pieces "attack" the center. The King
-->safety code also uses the attack info.
You should probably move this to a simple array query anyway, since this
is a "first order" evaluation that is independent of anything but the
particular piece you are evaluating. Simply do the computation at the
root, stuff the result in an array of 64 ints, and fetch in eval.
-->
-->I notice in looking at Crafty's scoring function that it doesn't call
-->AttacksTo, Swap or EnPrise, which is probably why it's reasonably
-->fast. These functions are fast using bitboards, but they are a long
-->way from free.
-->
-->So at this point I could proceed to put in the better bitmap code
-->(e.g. use the "compact" attacks plus assembly bits), but I am afraid
-->that even with that installed, I will have to jettison the attack
-->queries from my scoring function to get reasonably fast, which I am
-->reluctant to do.
One note. Crafty (many months ago) was an incremental program too, but
the makemove cost was high. As I first moved to the "compute attacks
on the fly with rotated bitboards" it slowed crafty down a lot. However,
I had the "feeling" that it would work and decided that the incremental
days were "history". It took a couple of months to get things clean
enough. Back then Crafty was searching 5-7K nodes per second. Now it's
up to 25-30K. A *lot* of work, and a *lot* of analyzing "is this worth
the cost, or do I toss it out?"
-->
-->Comments and suggestions are welcome. I think this is an interesting
-->illustration of how interrelated the various parts of a chess program
-->typically are.
-->
-->--Jon
-->
-->--
-->Jon Dart
-->jd...@netcom.com
-->--
-->Eugene V. Debs for President!
There are a few calls to Swap() and the attack functions in evaluate, but
as you mentioned, when you see their cost there rather than buried in the
makemove code, you can more readily assess the cost vs the gain and decide
whether or not it's attractive. With incremental update, you *have* to eat
the cost, then you use it as much as possible to ammortize the cost over
lots of things. Without incremental updating, you will choose to not do
some things, although you note I still do mobility and the like.
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Jon Dart
Arasan, my Windows chess program, currently maintains a database
I have experimented over the past month or so with putting the
rotated bitboard attack generation code from Crafty into Arasan.
I have used the "old", non-compacted, non-assembly attack code,
because it's easier to program. Even this wasn't exactly easy,
because Arasan has a different board representation (square 0
is a8 on the chessboard, not a1 as in Crafty) and the bitmap
class uses the opposite bit numbering from Crafty.
The results were rather disappointing. Tree sizes went down about 20%,
which I attribute to better move ordering and more precise capture
extension behavior, due to the more accurate attack estimation code.
But nodes/sec. decreased by more than 50%, so there is no net gain.
One of the problems here is that Arasan was built with incremental
attack updating, so it assumes in a lot of places that querying attack
info is basically free. E.g. center control in the scoring module
is computed by finding which pieces "attack" the center. The King
safety code also uses the attack info.
I notice in looking at Crafty's scoring function that it doesn't call
AttacksTo, Swap or EnPrise, which is probably why it's reasonably
fast. These functions are fast using bitboards, but they are a long
way from free.
So at this point I could proceed to put in the better bitmap code
(e.g. use the "compact" attacks plus assembly bits), but I am afraid
that even with that installed, I will have to jettison the attack
queries from my scoring function to get reasonably fast, which I am
reluctant to do.
Comments and suggestions are welcome. I think this is an interesting
illustration of how interrelated the various parts of a chess program
typically are.
--Jon
--
Jon Dart
jd...@netcom.com
Jon Dart
>In article <jdartDn...@netcom.com>, Jon Dart <jd...@netcom.com> wrote:
>-->
>-->attack updating, so it assumes in a lot of places that querying attack
>-->info is basically free. E.g. center control in the scoring module
>-->is computed by finding which pieces "attack" the center. The King
>-->safety code also uses the attack info.
>
>You should probably move this to a simple array query anyway, since this
>is a "first order" evaluation that is independent of anything but the
>particular piece you are evaluating. Simply do the computation at the
>root, stuff the result in an array of 64 ints, and fetch in eval.
>
counted as contributing to center control only if it actually "attacks"
a center square, meaning it's not blocked by another piece.
Similary, king safety currently considers how many squares near the king
are attacked by enemy pieces. Crafty's code is simpler and seems to
mainly consist of looking at the king's "pawn cover".
It may well be that I'm doing more than necessary in the scoring function.
Certainly I can make it go faster by removing scoring terms or doing
something cheaper and faster. I'll try doing that, but there's a
tradeoff here between fast and accurate.
>-->that even with that installed, I will have to jettison the attack
>-->queries from my scoring function to get reasonably fast, which I am
>-->reluctant to do.
>
>One note. Crafty (many months ago) was an incremental program too, but
>the makemove cost was high. As I first moved to the "compute attacks
>on the fly with rotated bitboards" it slowed crafty down a lot. However,
>I had the "feeling" that it would work and decided that the incremental
>days were "history". It took a couple of months to get things clean
>enough. Back then Crafty was searching 5-7K nodes per second. Now it's
>up to 25-30K. A *lot* of work, and a *lot* of analyzing "is this worth
>the cost, or do I toss it out?"
>
I'm not suggesting that Crafty do things differently. I'm only pointing
out some non-obvious (to me) tradeoffs that have been made in its
design. They clearly work, and work quite well. However, I can imagine
a quite different set of choices also working.
Currently I'm going to keep two versions of my program for a while, one
with on the fly bitboard attack generation and one with incremental
attack generation. I'll put some speedups in the scoring function and
try to eliminate calls to Attacksto() in other places. I suspect this
will benefit both versions. If these changes also make the non-
incremental version the fastest, then I can switch to that approach.
--Jon
--
Jon Dart
jd...@netcom.com
Bruce Moreland
>
>
>Arasan, my Windows chess program,
Everyone, or every amateur at least, should get an account for their program
on ICC or FICS or wherever, make an interface that will allow automatic play
on that server, and let loose. If you have Windows '95 and a PPP connection
you are in business. Other configurations also work, but I know for a fact
that it is easy to get up and running with this configuration.
I have three instances of Ferret running on ICC. The full-blast one hasn't
been running lately, but two of them that have been wimped-down by forcing
them to use less time per move have played 6000 games between them in the
last 16 days.
This is good for me, perhaps I can go through the games, most of which were
sent to me automatically via email, and find mistakes, but I am also amusing
the humans that hang out on the chess server.
It also tells you approximately where you stack up compared to other
programs.
bruce