Determining valid moves for a chess game

Gareth H

I am making a simple chess game in my spare time. I have been thinking of the best way to check whether or not a move is valid for a certain piece. Each "board square" has an index: 0 to 64. I have decided that when the player wants to make a move, I'll build a list of indexes that that piece can move to, and check whether or not the new position is in that list. So, does anyone know of a better/easier way of checking the above?, i thought I'd post here before i crack on and see if anyone had any other ideas than me - thinking out of the box and all that. Cheers.

Regards, Gareth. (FKA gareth111)

enginco

http://code.msdn.microsoft.com/cshuochess/Release/ProjectReleases.aspx?ReleaseId=1261[^] it seems like a simple code but I couldn't examine.

Gareth H

enginço, I don't want a complete game, as i want to learn, not copy. Also, the code looks horrible to say the least...

Regards, Gareth. (FKA gareth111)

Luc Pattyn

Hi Gareth, there are many ways to generate and store chess moves, I tried some of them. The most popular nowadays has the following characteristics: - use BOARD (a uint, that's unsigned int 64-bit) as the fundamental data type, and let each bit represent one square. - use as many BOARD items as you see fit, e.g. one to indicate the position of all white pieces, one to indicate the position of all white rooks, etc. - apply bitwise operators all the time: hence pieces=kings|queens|rooks|bishops|knights|pawns - for move generation, try to use shifts, e.g. if wrooks is a BOARD indicating the position of white rooks, then they could move one to the left by shifting left by one, except of course for rooks in the "a" file; so it would look like wrooksLeft1=(wrooks & notAFile) << 1 - doing it this way, you can get very compact code, and avoid a lot of conditional branches and bugs. - you have to work iteratively for long moves, so rookLeft7 does not make sense, you must iterate with rookLeft1 since you have to detect occupied squares. - you can't check yourself; the easiest way to avoid that is make your king behave as a queen, then as a knight, and see whether it can capture a corresponding piece of the opposing color. - and of course a lot of BOARD items can be precalculated and stored in some tables. In my estimate it takes around a thousand lines of code to generate all moves correctly, including castling, double pawn move, and en-passant. Hope this helps. :)

Luc Pattyn [Forum Guidelines] [My Articles]

Voting for dummies? No thanks. X|

modified on Monday, July 28, 2008 10:44 AM

GuyThiebaut

I don't play chess however... What I would do is use an OOP design approach. The board can be an object that contains information relating to which piece is where. I would have each type of piece as an object, as well, that has methods associated with it. Each method can then return a valid or invalid move and fire an event that the board object could then act on if the method returns a valid move.

Continuous effort - not strength or intelligence - is the key to unlocking our potential.(Winston Churchill)

Luc Pattyn

Hi Guy, that is all pretty nice, but computer chess is about performance. You simply cannot afford to waste cycles on calling virtual methods and the like if the strength of your computer game is all that matters. You really have to make the best use of the number of CPU cycles you are allowed. So OOP is fine for the GUI part of a chess game, but not for the chess engine itself. That is assuming the end goal is a chess playing program; for pure validation and visualization, every approach is fine, and then of course OOP is recommended. :)

Luc Pattyn [Forum Guidelines] [My Articles]

Voting for dummies? No thanks. X|

GuyThiebaut

Thanks - I appreciate that as I sometimes forget that the object interface provided is not necessarily the fastest or most efficent way to do things. Coming from a very heavily procedural background, and having been seduced by OOP, I can sometimes assume that OOP will solve everything. :)