Board Types in '08

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
jshriver
Posts: 1105
Joined: Wed Mar 08, 2006 8:41 pm
Location: Morgantown, WV, USA
Contact:

Board Types in '08

Post by jshriver » Sat Jun 28, 2008 5:20 am

What are the common board types now adays? Last time I was researching this bitboards and 0x88 where the big ones. Some new engines were using 0x88, but bitboards always seemed popular.

Now that 64bit CPU's are common place has bitboard taken over or are both still pretty popular. Perhaps something else has come out that I'm not aware.

Any info is appreciated :)

Dann Corbit
Posts: 9505
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Board Types in '08

Post by Dann Corbit » Sat Jun 28, 2008 6:14 am

jshriver wrote:What are the common board types now adays? Last time I was researching this bitboards and 0x88 where the big ones. Some new engines were using 0x88, but bitboards always seemed popular.

Now that 64bit CPU's are common place has bitboard taken over or are both still pretty popular. Perhaps something else has come out that I'm not aware.

Any info is appreciated :)
Popularity of board representations waxes and wanes. When Crafty did well at Jakarta, Bitboard was all the rage. Then some 0x88 engines started to dominate and lots of people wrote 0x88 engines. Now, Rybka is bitboard and so Bitboard is more popular again. I think that now that we have 64 bit CPUs, the bitboard programs are really starting to reap the benefit.

The most popular board representations are still 0x88 (or similar array types) and bitboard. However, bitboard has had an interesting renaisance with lots of different generation methods.

You might like to examine the chess programming wiki:
http://chessprogramming.wikispaces.com/

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Board Types in '08

Post by bob » Sun Jun 29, 2008 1:10 am

jshriver wrote:What are the common board types now adays? Last time I was researching this bitboards and 0x88 where the big ones. Some new engines were using 0x88, but bitboards always seemed popular.

Now that 64bit CPU's are common place has bitboard taken over or are both still pretty popular. Perhaps something else has come out that I'm not aware.

Any info is appreciated :)
Depends on who you listen to. I think bitboards are the way to go. Vincent will tell you they are "hell slow". Yet they don't seem to hurt my speed, nor Glaurung's, nor Rybka's, etc...

They make good sense on 64 bit machines due to data density. But they have a steep learning curve...

User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 10:08 am
Location: Klein-Gerau, Germany
Contact:

Re: Board Types in '08

Post by smrf » Sun Jun 29, 2008 5:33 am

SMIRF is using a flat approach where pieces at the same time are members of a color specific double linked list, having bit encoded gait specific properties.

User avatar
hgm
Posts: 23155
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Board Types in '08

Post by hgm » Sun Jun 29, 2008 6:44 am

All my engines use 0x88-type array boards, but I once designed an alternative format for allowing faster generation of attack maps, and a table driven SEE. Never implemented or tested it, though.

The idea was to represent the board as sets of files, ranks , diagonals and anti-diagonals. (So you would actually have quadruple redundancy, like in rotated bitboards.) Each square could be represented by 4 bits (i.e. a nybble), so that one 32-bit word would contain info on 8 squares.

Some 8x8 tables, indexed by square, would tell which 4 rays (in the 4 different directions) would go through each square. On MakeMove / UnMake the 4 rays going through from-square and to-square would be updated, by masking out the old contents, and ORing in a new one, the masks coming from other 8x8 tables.

The encoding of the square contents could be different for diagonals and orthogonals, and designed such that information relavant for some purposes was encoded in just a subset of the bits. E.g. one bit indicating if the quare was occupied, another bit that the piece there could move along the ray (so referring to different pieces in the diagonals and the orthogonals), one to indicate color, one to indicate if it was a slider.

Magic-bitboard-like techniques could be applied to the individual rays, to extract the relevant bits and pack them into a small index, to be used in tables that would give attack sets (encoded as the number of pieces of a certain type that could go to a certain square on the ray). The attack sets could then again be used as index in tables that would tell you the SEE fr that square.

User avatar
jshriver
Posts: 1105
Joined: Wed Mar 08, 2006 8:41 pm
Location: Morgantown, WV, USA
Contact:

Re: Board Types in '08

Post by jshriver » Tue Jul 01, 2008 1:31 am

bob wrote: They make good sense on 64 bit machines due to data density. But they have a steep learning curve...


Well said, I've working off/on for to long now and just can't understand bitboards that well, even though they are the route I'd like to take.

I started learning toward 0x88 because the stagnation of progress was impeding my desire to keep on.

At this point though I don't care if I write a super-great engine. If it can play legal moves and beat me, I will consider my task accomplished lol.

I think a big part of it, is that chess programming is a lot different than chess playing. Meaning when I play chess I have certain methods to go about doing it in mentally. So originally I was going to do a simple board[][]. Then piece movements, attacks, etc still map out to a single object that correlates to the real board and how (at least my brain) works.

Oh well, hopefully someday :)

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Board Types in '08

Post by bob » Wed Jul 02, 2008 8:20 pm

jshriver wrote:
bob wrote: They make good sense on 64 bit machines due to data density. But they have a steep learning curve...


Well said, I've working off/on for to long now and just can't understand bitboards that well, even though they are the route I'd like to take.

I started learning toward 0x88 because the stagnation of progress was impeding my desire to keep on.

At this point though I don't care if I write a super-great engine. If it can play legal moves and beat me, I will consider my task accomplished lol.

I think a big part of it, is that chess programming is a lot different than chess playing. Meaning when I play chess I have certain methods to go about doing it in mentally. So originally I was going to do a simple board[][]. Then piece movements, attacks, etc still map out to a single object that correlates to the real board and how (at least my brain) works.

Oh well, hopefully someday :)
Certainly playing and writing a program to play are two completely different tasks. Hard to say which is harder, but clearly the more you know about chess, the better your engine will play... It is (IMHO) harder to teach someone something than it is to learn it for yourself. So "teaching" a computer to play chess is an interesting task...

Post Reply