Archived

This topic is now archived and is closed to further replies.

Druzzer007

Chess programming

Recommended Posts

I want to do a chess program using java, but for efficiency''s sake i want it to be independent on the windows platform, but my big question is should i use polymorphism for piece designing and what search algorithm should i use and why? ============================= Andrew Schwartz Moagi

Share this post


Link to post
Share on other sites
quote:
Original post by Druzzer007
I want to do a chess program using java,


Probably a poor choice. Chess programs need all the performance they can get, and C or C++ are better ways to get it.

quote:

but for efficiency''s sake i want it to be independent on the windows platform,


That doesn''t make any sense.

quote:

but my big question is should i use polymorphism for piece designing and what search algorithm should i use and why?


That''s at least two questions. To the first one: no, you should not use polymorphism for piece design. The very basic operations of finding the possible moves for a piece or determining if a piece attacks a particular square are called so many times that an indirection would kill performance. To the second question: use alpha-beta. Why? Because it''s good, easy to implement, well understood and well documented.

Share this post


Link to post
Share on other sites
I agree with alvaro. Ask yourself if you want this to be a good program, or if it''s just a pure hobby and you don''t care how good it is. If you don''t care how good it is, then use java and all the polymorphism you want. If you care about how fast it is, and how well it plays, then I''d recommend using C or C++. As for the search algorithm, if you''ve never done anything like this before, implement minmax first, then after you have that working use alphabeta (it''s only a handful of extra lines of code).

Share this post


Link to post
Share on other sites
I agree, I wouldn''t use java, but i found a really neat module on CPAN for chess programming in Perl. Since that''s my favorite language, I was very excited to download a copy, it is fairly is to use.

#!/usr/bin/perl
use warnings;
use strict; # this has to be in place
use GD::chess; # I think that this is the name, you may have # to put something else here

# now, you create a hash to hold all the stuff
%hash -> GD::chess;
# then you do stuff with the module

The offical documetation is on CPAN. You may not want to use Perl, but I found that it was pretty fun. You could use OpenGL for graphics ( and ploymorphism? ), I''m not really sure cause I''m fairly new to OpenGL. I do know that you can use object-oriented Perl for ploymorphism, and it''s just as good as C/C++ ( in my opinion ). Programming this type of game in Perl or Java is actually a fairly good idea if you want to put the game on a website.

Like I said you may not want to use Perl, but I think that it is a fun language to play around with, and if the game is ment to be a fun thing, then Perl is the Langauge. At least fgo to CPAN and check it out

Share this post


Link to post
Share on other sites
BTW, I would consider using A* for pathfinding, because a chess baord is a grid, and A* is based on that idea. If chess piece A is going to move to node B, then you look for any other pieces, and then move the piece after you check.
| | | |
| | | |
| A | O | B |
| | | |
| | | |
|_____________|______________|______________|
This would demonstarte say, a pawn at A moving to node B. O is an object in the way, say a knight. You then use an A* algorithm to compute this. You may want to implement a collision detection algorithm as well. Hope this helps. ( BTW, there is also a VERY good A* pathfinding module on CPAN as well )

Edit: The diagram didn't turn out fair well, the three bars after the fist one in each row are supposed to be even with the ones on the bottom rows, and O is supposed to be in the second "square" and B is supposed to be in the last one. It looked fine until I posted the reply

[edited by - neo88 on October 13, 2003 3:07:45 PM]

Share this post


Link to post
Share on other sites
Sorry, neo88, but that doesn''t have much to do with chess. While I have used a path finding algorithm to figure out if a king can stop a passed pawn in pawn-only endgames, your suggestion will not help Druzzer007 get started with a working chess program.

Share this post


Link to post
Share on other sites
Two things.

1. There is zero reason to use OpenGL to write graphics for a chess program, and there is zero reason to even write a GUI for a chess program. You can write a console application and add in support for either the Winboard or UCI protocol (or both), and it will run in any number of GUIs which do tons of cool stuff. You can connect your program to the internet and play against people and other programs for instance, and the GUI does it all for you. Your program just has to support a few commands and the GUI does all of the magic. Winboard is pretty much supported by any GUI I know of. There are good free ones too. There are over 200 freely available chess programs that support the Winboard protocol, and you can play them against your program. Implementing all of this stuff in addition to writing a chess program is just plain stupid.

Arena - a free GUI that supports both Winboard and UCI chess engines, play on the net, engine vs. engine tournaments, and more.

Winboard - a free GUI that supports the Winboard protocol, and comes with full source code. Supports engine-engine games and can play on the net. Hasn''t been updated in a while, but it''s still good. Works on linux too.

Winboard forum - from here you can get over 200 free Winboard engines and UCI engines. Use the little drop box in the top right corner that says, "Select Engine".

WBEC - This is Leo''s site. He runs a huge computer chess tournament. You can look at his rating list to see which programs are the strongest, and there is a drop box similar to the one on the Winboard forum that will lead you to info pages where you can find out about them and download them.

2. A* has no use in a chess program. There are plenty of clever ways to do things much faster than using A*. If you use the right data structures, you''d be suprised how many things you can do almost instantly, or at least use lazy evaluation so you only have to call that slow algorithm a small percentage of the time. For instance, there is no need to use any path finding algorithm to determine if a king can stop a passed pawn, as alvaro mentioned.

Share this post


Link to post
Share on other sites
quote:
Original post by Russell
For instance, there is no need to use any path finding algorithm to determine if a king can stop a passed pawn, as alvaro mentioned.


And can I hear what your solution is?

Share this post


Link to post
Share on other sites
well am having trouble choosing what language i can use here since i fairly know C but i really wanted to use an object oriented language so i think i will have to consider C++(which i know the basics), but my choice of java was based on the fact that later i will put it on the net and make it a network game but your ideas guys are all reasonable so if you can help me with the choice(between C and C++) i''ll be very happy.

=============================
Andrew Schwartz Moagi

Share this post


Link to post
Share on other sites
(In response to alvaro...)

Most chess programs use one of two main board representations.

1. An 0x88-like system (link, read the section titled "A Bonus").
2. Bitboards (link).

If you use bitboards, you can have an array of precomputed bitboards, where each bitboard represents "the square of the pawn" that the king must be in to stop the passed pawn from promoting. For instance:

Bitboard blackPawnPromoteSquare[64];

blackPawnPromoteSquare[E4] would like like:

00000000
00000000
00000000
00000000
01110111
01111111
01111111
01111111


Then you can do:

if (blackPawnPromoteSquare[E4] & whiteKingSquare)
{
// white king can stop black pawn
}


1 table lookup, 1 AND, and you're done.

One of the main advantages to an 0x88-like system is that square relationships are not ambiguous. If you used a 64-element array for your board, where a1=0, b1=1, ..., a2=8, etc. then square relationships will be ambiguous. For instance, if you subtract h1 - a1, you get 7. If you subract a2 - b1, you also get 7. So an offset of 7 can mean different things. This is not the case if you use an 8x16 board (or other similar board representations). Your board would look like this, where X means you don't use this part of the board.

--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX

You only actually use the left half of the board. This means a row is 16 elements wide. Now let's look at things. h1 - a1 = 7, but a2 - b1 now equals 15, not 7. This means that if we subtract two squares, the relationship will always be unique. So the square relationship of "down one and right one" is always 15. This allows you to do some very cool things using a lookup table. One very common use is to speed up attack detection a great deal. Usually, you would have to scan all over the board to see if any piece attacks a square (maybe you want to know if you left your king in check, which is illegal). You can speed that up a lot by creating a table that you give the offset of two squares. For instance, you know that an offset of, say, 33 (up two and right one, like a knight moves) can never be attacked by a bishop, because a bishop doesn't move that way, so if you want to know if a bishop on b1 can possibly attack c3, you can do a lookup in table and the table will tell you "no", and you don't have to do any scanning at all.

You can do something similar to detect whether a king can stop a passed pawn. Just compute the square difference of the king and the pawn, put it in your lookup table and it might tell you "no, the king cannot catch it" or, "yes the king can catch it", or maybe it will say, "i can't tell from this offset, you'll have to search". The point is, the vast majority of the time, the table will give you the answer immediately. You might still have to search in some cases, but doing that slow search around the board 5% of the time is a lot better than 100% of the time.

If any of this doesn't make sense just ask me to explain more. I kind of rushed through it all because I need to get ready for work, but I'll have all evening to explain more thoroughly if you have any questions.

[edited by - Russell on October 14, 2003 1:47:34 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Druzzer007
well am having trouble choosing what language i can use here since i fairly know C but i really wanted to use an object oriented language so i think i will have to consider C++(which i know the basics), but my choice of java was based on the fact that later i will put it on the net and make it a network game but your ideas guys are all reasonable so if you can help me with the choice(between C and C++) i''ll be very happy.

=============================
Andrew Schwartz Moagi


If you want to put it on the net, then you should make your program a console (text mode) program and have it support the Winboard or UCI protocols. The Winboard protocol will allow your program to play on internet chess servers, and the GUI does all of the work for you. C or C++ are both good choices. There are a lot of open source programs written in C, and some in C++, and you can find a handful written in Java or VB. If you use C or C++, you''ll be able to get a lot more help, at least from my experience. Some people ask questions sometimes about "how do I do this in Delphi?" or some other less common language, and most of the time the person gets responses like, "well in C you''d do it like this...". Plus like I said there are a bunch of open source programs in C that you can look at and learn from. You really don''t need to know that much of C++ to write a chess program. A chess program should be fast, and you shouldn''t make it any more complicated than it needs to be (it will be complicated enough already), so don''t mess with polymorphism or any of the OOP stuff. If you want to make classes to ensure the validity of your data or something, that''s fine. Computer chess is a problem that has been studied for many, many decades, and there are well established ways of doing a lot of things, so using a lot of OOP stuff to arrive at the correct way of doing things really isn''t necessary. Just keep things simple.

Share this post


Link to post
Share on other sites
quote:
Original post by Russell
(In response to alvaro...)

Most chess programs use one of two main board representations.

1. An 0x88-like system (link, read the section titled "A Bonus").
2. Bitboards (link).


I know. I have used them both.

quote:

If you use bitboards, you can have an array of precomputed bitboards, where each bitboard represents "the square of the pawn" that the king must be in to stop the passed pawn from promoting.
...



That is all nice and dandy, and I use it. The problem here is that this only works if there is nothing preventing the king from advancing towards the enemy pawn. In some difficult endings, especially pawn-only endings, there are situations where there are obstacles, like your own pawns, squares attacked by enemy pawns and the enemy king. It is possible to improve your static evaluation for those situations by using a path-finding algorithm that accounts for those obstacles. Whether this approach is worth the effort or not is a matter for discussion, but I have actually used it in a relatively strong program. I also penalize weak pawns for being close to the enemy king, with distance computed using the same method.

Share this post


Link to post
Share on other sites
Ah, I see what you''re doing. A lot of people would say that''s a job for the search. I guess you and I are in the minority, because I like for my evaluation function to be as accurate as possible, so I try to evaluate these kinds of things statically as well.

If you''re using bitboards, there is are some interesting and little know algorithms that will do floodfilling and pathfinding kind of operations pretty efficiently, which might be useful for this kind of situation. The basic idea is that you do some shifting and ANDing of the bitboard to generate attacks, and you can do floodfills that "go around" squares that you specify.

As an example, you could generate attacks by floodfilling a "white rooks" bitboard in one direction, and passing in "empty squares" as the squares that are okay to fill through. Consider the following code:


typedef unsigned __int64 Bitboard;
Bitboard UpAttacks (Bitboard b, Bitboard c)
{
b |= (b << 8) & c;
c &= (c << 8);
b |= (b << 16) & c;
c &= (c << 16);
b |= (b << 32) & c;
return b << 8;
}


If you had the bitboard that represented "all white rooks", and a bitboard that represented "empty squares", you could generate attacks in the upward direction by:

Bitboard upRookAttacks = UpAttacks(whiteRooks, emptySquares);

Or you could generate rook and queen attacks by:

Bitboard upRookAttacks = UpAttacks(whiteRooks|whiteQueens, emptySquares);

You can do similar fills left, right, down, and diagonally in all directions. For just generating attacks in one direction this isn''t particularly efficient. You can combine the UpAttacks() with DownAttacks() and the other directions to write a RookAttacks() function:


Bitboard RookAttacks (Bitboard rooks, Bitboard empty)
{
return UpAttacks(rooks, emtpy) | DownAttacks(rooks, empty) |
LeftAttacks(rooks, empty) | RightAttacks(rooks, empty);
}


Then it becomes trivial to find out which squares a rook can move to in 2 moves. Just do someting like:

Bitboard in1Move = RookAttacks(rooks, empty);
Bitboard in1Moves = RookAttacks(in1Move, empty);


Here''s some more code to play around with (below). ''b'' is usually the piece bitboard (whitePawns, blackRooks, etc.) although it could be anything that you want to generate attacks in some direction from. ''c'' is generally the squares you want to allow filling through, which is usually "empty squares". Sometimes you might want to generate a bitboard that is "safe empty squares" and you could use that to see if a king can reach a passed pawn, or whatever. This code assumes a1=0, b1=1, a2=8, etc.


// ----------

// Pawn moves

// ----------

bitboard WhitePawnAttacks (bitboard b)
{
return ((b << 7) & 0x7F7F7F7F7F7F7F7F) |
((b << 9) & 0xFEFEFEFEFEFEFEFE);
}

bitboard BlackPawnAttacks (bitboard b)
{
return ((b >> 7) & 0xFEFEFEFEFEFEFEFE) |
((b >> 9) & 0x7F7F7F7F7F7F7F7F);
}

bitboard WhitePawnNonAttacks (bitboard b, bitboard c)
{
b |= (b << 8) & c;
c &= (c << 8);
return b |= ((b & 0x0000000000FF0000) << 16) & c;
}

bitboard BlackPawnNonAttacks (bitboard b, bitboard c)
{
b |= (b >> 8) & c;
c &= (c >> 8);
return b |= ((b & 0x0000FF0000000000) >> 16) & c;
}

// ------------

// King Attacks

// ------------


bitboard KingAttacks (bitboard b)
{
bitboard c = b;
b |= (b >> 1) & 0x7F7F7F7F7F7F7F7F;
b |= (b << 1) & 0xFEFEFEFEFEFEFEFE;
b |= b << 8;
b |= b >> 8;
return b ^ c;
}

// --------------

// Knight Attacks

// --------------


bitboard KnightAttacks (bitboard b)
{
bitboard c = b;
b ^= c;
b |= (c >> 17) & 0x7F7F7F7F7F7F7F7F;
b |= (c << 15) & 0x7F7F7F7F7F7F7F7F;
b |= (c >> 15) & 0xFEFEFEFEFEFEFEFE;
b |= (c << 17) & 0xFEFEFEFEFEFEFEFE;
b |= (c >> 10) & 0x3F3F3F3F3F3F3F3F;
b |= (c << 6) & 0x3F3F3F3F3F3F3F3F;
b |= (c >> 6) & 0xFCFCFCFCFCFCFCFC;
b |= (c << 10) & 0xFCFCFCFCFCFCFCFC;
return b;
}

// ---------------------

// Rank and file attacks

// ---------------------


bitboard UpAttacks (bitboard b, bitboard c)
{
b |= (b << 8) & c;
c &= (c << 8);
b |= (b << 16) & c;
c &= (c << 16);
b |= (b << 32) & c;
return b << 8;
}

bitboard DownAttacks (bitboard b, bitboard c)
{
b |= (b >> 8) & c;
c &= (c >> 8);
b |= (b >> 16) & c;
c &= (c >> 16);
b |= (b >> 32) & c;
return b >> 8;
}

bitboard LeftAttacks (bitboard b, bitboard c)
{
c &= 0x7F7F7F7F7F7F7F7F;
b |= (b >> 1) & c;
c &= (c >> 1);
b |= (b >> 2) & c;
c &= (c >> 2);
b |= (b >> 4) & c;
c &= (c >> 4);
return (b >> 1) & 0x7F7F7F7F7F7F7F7F;
}

bitboard RightAttacks (bitboard b, bitboard c)
{
c &= 0xFEFEFEFEFEFEFEFE;
b |= (b << 1) & c;
c &= (c << 1);
b |= (b << 2) & c;
c &= (c << 2);
b |= (b << 4) & c;
c &= (c << 4);
return (b << 1) & 0xFEFEFEFEFEFEFEFE;
}

bitboard RankFileAttacks (bitboard b, bitboard c)
{
return UpAttacks(b,c) |
DownAttacks(b,c) |
LeftAttacks(b,c) |
RightAttacks(b,c);
}

// ----------------

// Diagonal attacks

// ----------------


bitboard DownLeftAttacks (bitboard b, bitboard c)
{
c &= 0x7F7F7F7F7F7F7F7F;
b |= (b >> 9) & c;
c &= (c >> 9);
b |= (b >> 18) & c;
c &= (c >> 18);
b |= (b >> 27) & c;
c &= (c >> 27);
return (b >> 9) & 0x7F7F7F7F7F7F7F7F;
}

bitboard UpLeftAttacks (bitboard b, bitboard c)
{
c &= 0x7F7F7F7F7F7F7F7F;
b |= (b << 7) & c;
c &= (c << 7);
b |= (b << 14) & c;
c &= (c << 14);
b |= (b << 21) & c;
c &= (c << 21);
return (b << 7) & 0x7F7F7F7F7F7F7F7F;
}

bitboard DownRightAttacks (bitboard b, bitboard c)
{
c &= 0xFEFEFEFEFEFEFEFE;
b |= (b >> 7) & c;
c &= (c >> 7);
b |= (b >> 14) & c;
c &= (c >> 14);
b |= (b >> 21) & c;
c &= (c >> 21);
return (b >> 7) & 0xFEFEFEFEFEFEFEFE;
}

bitboard UpRightAttacks (bitboard b, bitboard c)
{
c &= 0xFEFEFEFEFEFEFEFE;
b |= (b << 9) & c;
c &= (c << 9);
b |= (b << 18) & c;

c &= (c << 18);
b |= (b << 27) & c;
c &= (c << 27);
return (b << 9) & 0xFEFEFEFEFEFEFEFE;
}

bitboard DiagonalAttacks (bitboard b, bitboard c)
{
return DownLeftAttacks(b,c) |
UpLeftAttacks(b,c) |
DownRightAttacks(b,c)|
UpRightAttacks(b,c);
}

Share this post


Link to post
Share on other sites
So as you guys have mentioned how does this 88-like system handle the middle game tactics,as to my understanding, the branching factor here is a little bit higher and does this not have significant effect on the perfomance of the program. And generally what are the ratings(FIDE) the programs done using this system generally accumulate.

=============================
Andrew Schwartz Moagi

[edited by - Druzzer007 on October 14, 2003 5:52:13 PM]

[edited by - Druzzer007 on October 14, 2003 5:53:55 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Russell

typedef unsigned __int64 Bitboard;
Bitboard UpAttacks (Bitboard b, Bitboard c)
{
b |= (b << 8) & c;
c &= (c << 8);
b |= (b << 16) & c;
c &= (c << 16);
b |= (b << 32) & c;
return b << 8;
}






That is the coolest thing ever. In exchange, I'll share with you a little trick that I think might be useful. I don't like writing every function twice, once for white and once for black. This past weekend I came up with the following neat C++ solution:
      
enum Color{White,Black};

template <Color c>
struct ColorTraits;

template <>
struct ColorTraits<White>{
static const Color Enemy = Black;
static u64 forward(u64 x){ return x<<8; }
static u64 backwards(u64 x){ return x>>8; }
static const Piece Pawn = WhitePawn;
static const Piece Night = WhiteNight;
//...

};

template <>
struct ColorTraits<Black>{
static const Color Enemy = White;
static u64 forward(u64 x){ return x>>8; }
static u64 back(u64 x){ return x<<8; }
static const Piece Pawn = BlackPawn;
static const Piece Knight = BlackKnight;
//...

};

template <Color c>
u64 passed_pawns(){
u64 obstacles = bitboard[ColorTraits<ColorTraits<c>::Enemy>::Pawn];
obstacles = ColorTraits<c>::back(obstacles);
obstacles |= Left(obstacles) | Right(obstacles); // Left and Right have obvious definitions

obstacles |= ColorTraits<c>::back(obstacles);
obstacles |=
ColorTraits<c>::back(
ColorTraits<c>::back(obstacles));
obstacles |=
ColorTraits<c>::back(
ColorTraits<c>::back(
ColorTraits<c>::back(
ColorTraits<c>::back(obstacles))));
return bitboard[ColorTraits<c>::Pawn] & ~obstacles;
}

I think the ColorTraits template is pretty neat. I also discovered that my compiler (g++-3.2) does not optimize the four concatenated calls to `back' properly, so I provided a function `back4' that rotates 32 places. Other than that, the assembly code looks very good.



[edited by - Alvaro on October 14, 2003 6:13:05 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Druzzer007
So as you guys have mentioned how does this 88-like system handle the middle game tactics,as to my understanding, the branching factor here is a little bit higher and does this not have significant effect on the perfomance of the program. And generally what are the ratings(FIDE) the programs done using this system generally accumulate.


You can write a good program using any board representation. Different board representations give you different things for "free" (meaning, they do some things very quickly). They each have their own advantages. Pick the one that makes the most sense to you and learn all about the advantages of that system, and you'll be fine.

I have discovered over time that pretty much anything I can do in one board representation, I can do in another just as efficiently. The hard part is learning how to use the tools that each system provides to acheive what you want to achieve. For instance, thinking in terms of bitboards is quite different from using an 0x88 system.

IMO, the board representation that will get you the most bang for your buck is a 12x16 board. This allows you to use the 0x88 trick, and scanning the board is more efficient. When you scan an 0x88 board (8x16), you typically do something like this:

1. Is this square on the board (uses the 0x88 trick)
2. Is this square empty
3. If it's empty, generate a move (or whatever), else stop scanning.

Using a 12x16 board, you can still use the 0x88 trick, but it really isn't necessary. Now you can just do:

1. Is the square empty?
2. If it's empty, generate a move (or whatever), else stop scanning.

If a square is off the board, it won't be "empty" (it will be "invalid" or whatever you want to set it to). It's not a huge difference, but it's better if you do a lot of scanning of the board. The 8x8 board is in the middle of the 12x16 board. It will look like this (X means "off the board"):


XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX


I use bitboards however, because I think they offer a little more once you really learn how to use them. If you're starting out though, use something simple. You'll have plenty of other stuff to learn. It seems like you're picking up on things pretty fast though, so you should do well.

[edited by - Russell on October 14, 2003 6:33:43 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by alvaro
That is the coolest thing ever.
I thought so too when I first saw it I'll warn you though, that it's not the fastest code on 32-bit hardware for doing simple attacks. Rotated bitboards are way faster (unless you can make it work using MMX or something, which I know one person did). You really need to do something like floodfilling where you can fill the entire board in a handful of iterations (as opposed to doing recursive scanning all over the board). It also might be worth it if you want to know something like "how many squares can this rook move to in N moves?".

quote:

In exchange, I'll share with you a little trick that I think might be useful. I don't like writing every function twice, once for white and once for black. This past weekend I came up with the following neat C++ solution:
         
enum Color{White,Black};

template <Color c>
struct ColorTraits;

template <>
struct ColorTraits<White>{
static const Color Enemy = Black;
static u64 forward(u64 x){ return x<<8; }
static u64 backwards(u64 x){ return x>>8; }
static const Piece Pawn = WhitePawn;
static const Piece Night = WhiteNight;
//...

};

template <>
struct ColorTraits<Black>{
static const Color Enemy = White;
static u64 forward(u64 x){ return x>>8; }
static u64 back(u64 x){ return x<<8; }
static const Piece Pawn = BlackPawn;
static const Piece Knight = BlackKnight;
//...

};

template <Color c>
u64 passed_pawns(){
u64 obstacles = bitboard[ColorTraits<ColorTraits<c>::Enemy>::Pawn];
obstacles = ColorTraits<c>::back(obstacles);
obstacles |= Left(obstacles) | Right(obstacles); // Left and Right have obvious definitions

obstacles |= ColorTraits<c>::back(obstacles);
obstacles |=
ColorTraits<c>::back(
ColorTraits<c>::back(obstacles));
obstacles |=
ColorTraits<c>::back(
ColorTraits<c>::back(
ColorTraits<c>::back(
ColorTraits<c>::back(obstacles))));
return bitboard[ColorTraits<c>::Pawn] & ~obstacles;
}

I think the ColorTraits template is pretty neat. I also discovered that my compiler (g++-3.2) does not optimize the four concatenated calls to `back' properly, so I provided a function `back4' that rotates 32 places. Other than that, the assembly code looks very good.

Very cool and elegant! I'll play with it when I get home from work.



[edited by - Russell on October 14, 2003 6:40:26 PM]

Share this post


Link to post
Share on other sites
Would I be correct in assuming that bitboards will be used in the overwhelming majority of implementations once 64-bit cpu''s (ie. AMD x86-64) become commonplace? It would seem to me that bitboards will receive a HUGE boost in performance once we get 64-bit cpu''s.

Share this post


Link to post
Share on other sites
quote:
Original post by Optikal
Would I be correct in assuming that bitboards will be used in the overwhelming majority of implementations once 64-bit cpu''s (ie. AMD x86-64) become commonplace? It would seem to me that bitboards will receive a HUGE boost in performance once we get 64-bit cpu''s.
It depends upon what kind of program we''re talking about. I doubt you will see many commercial engines go to this in the near future, because their goal is to make money, and most people still have 32-bit machines. It will take a while before 64-bit machines are the majority. Already there are a lot of amateur programs that are using bitboards.

On 32-bit hardware, bitboards tend to "break even" with other approaches. The hope is that they will receive a bigger speed boost on 64-bit hardware, but some people have reported that their non-bitboard programs are almost twice as fast on an Opteron when compared to an Athlon at the same GHz. Common sense would tell us that a bitboard program would benefit even more.

It''s kind of up in the air until the 64-bit stuff becomes more mainstream, the price comes down, and they get all of the other stuff in order (operating systems, compilers, etc.).

Share this post


Link to post
Share on other sites
quote:
ColorTraits


Just out of curiosity (I''m not that experienced with the details of templates), how fast would your ColorTraits approach perform compared to other approaches? And what does it convert to? Does it do an if statement under the hood or a table lookup or a function pointer, or what? Like I said, I''m not all that familiar with how the compiler translates these kind of templated things.

Share this post


Link to post
Share on other sites
quote:

Just out of curiosity (I'm not that experienced with the details of templates), how fast would your ColorTraits approach perform compared to other approaches? And what does it convert to? Does it do an if statement under the hood or a table lookup or a function pointer, or what? Like I said, I'm not all that familiar with how the compiler translates these kind of templated things.



Templates are evaluated in compile time, which means that there is no overhead whatsoever. The effect is that now I can call the functions passed_pawns<White>() and passed_pawns<Black>(), they would do the right thing, they are as efficient as if they had been coded separately, but I only had to write one function.

[edited by - Alvaro on October 14, 2003 9:02:01 PM]

Share this post


Link to post
Share on other sites
I know that if you do passed_pawns(), that will be the same as if you did WhitePassedPawns(), but what if you did:


Color c = GetColorToMove();
Bitboard passedPawns = passed_pawns;


I don''t see how that could be a compile time decision. If you do passed_pawns(), you still need an if statement or something to determine whether to call passed_pawns() or passed_pawns(), right?

Share this post


Link to post
Share on other sites
quote:
Original post by Russell
I know that if you do passed_pawns<White>(), that will be the same as if you did WhitePassedPawns(), but what if you did:


Color c = GetColorToMove();
Bitboard passedPawns = passed_pawns;


I don''t see how that could be a compile time decision. If you do passed_pawns<White>(), you still need an if statement or something to determine whether to call passed_pawns<White>() or passed_pawns<Black>(), right?


You can''t compile that code, as c''s value cannot be decided in compile time. But that is an unlikely use of those functions. Typically, you would need to detect all passed pawns at the evaluation function, regardless of whose turn it is.

At least in the checkers and chess programs that I have written in the past, I end up having tons of duplicated code that could have been avoided with this method.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hey Guys i really love this and i have been looking for something like this for a week, i want you guys to help me get started on a very simple chess game using C could you please paste the code here so that we can discuss it, thanks!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Russell
Two things.

1. There is zero reason to use OpenGL to write graphics for a chess program

Share this post


Link to post
Share on other sites