Focusing back on the chess engine in order to get a chess web service up and running...
Alrighty, I'm back on the chess engine I think. I got sidetracked a bit with some other ideas, some of which I'll be hanging onto through the weekend, but the chess engine is definitely a priority. I had figured the entire process would be a bit easier than it is. I've always played chess and it is easy for a human player to quickly and easily validate moves. We are adept enough that you miss the nuances of how a computer has to play chess and the shear amount of thought that is involved. For an example you can examine the process of validating a move...
- Is the destination square valid for the piece that is being played? Note moving the piece means changing the underlying data structure to note the change. This could also mean removing pieces from the board, which happens to be very important for the next step.
- Does the move result in a Check of the moving side? You have to validate the move and remove any pieces because if you don't, the piece that would be removed may still be forcing a Check on the King. You might be moving out of Check. If you already updated your board, but you just moved yourself into check, then the move wasn't valid. Now what do you do?
- Does the move result in a Check for the opponent side? This is the last check you do and the results here determine the status message sent back to each of the clients. Whether or not the status message is going to be Check or ValidMove in the case of my engine.
- Do you generate moves at this point and also validate a CheckMate? There is such a thing as a CheckMate, an impossible to get out of position. But before this happens most good players will retire having known they've lost several moves before the end. Or should the engine be as simplified as possible and leave retiring up to the remote player when they've realized that they've lost?
It just seems that having a throw away board might be easier than trying to keep the memory usage of the application low by using a sparse mapping collection. Most commercial chess engines use a special structure called a BitBoard. These are fairly neat, since they are 64 bits long and represent a single detail about the game board. Many of them at a time are required in order to play a game and execute all of your algorithms. The interesting features of bit boards are the transformations that are possible to not only validate moves, but also generate all possible moves for a piece. Being stored in longs, means they don't take up very much space and can be used as scratch-pads during various portions of the move process. After all, they can be easily thrown away if things go south.
I'm not sure I really want to change my entire engine over to using bit boards, but there are certain things that make sense to convert over. Being able to use a throw away structure representing blocked board locations might really simplify the current logic I have for handling the above 4 steps. I'll keep putting thought into the process, and should be done fairly soon. Hopefully we have some chess aficionados willing to put effort into some chess AI and take the service architecture for a spin to give some feedback.