Chess programming
Author
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
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.
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).
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
#!/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
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]
| | | |
| | | |
| 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]
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.
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.
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.
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?
Author
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
=============================
Andrew Schwartz Moagi
(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:
Then you can do:
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]
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
01111111Then 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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement