How to write in C# a chess like game?

Question

I have a question. I want to write a chess like program applying the rules as follows:

• It should have just a king and a queen on one side and the other side should have just a king.
• The first side should mate the second side with the lowest number of moves possible.

I want to know your thoughts about how to make this project. For example I want to know about which way of writing code is easier (object oriented or structured, ...) (I have a little information about object oriented) and can say me about writing its algorithm? For example from where I should begin to write the codes?

Answer 1

Take a look at this SO question (Programming a chess AI).

From the answers to that question, I think this C# Chess Game Starter Kit would be a good start, but I would also look at the other articles referenced as well for some interesting history/information.

Answer 2

The good news here is that your problem is quite restricted in scope, as you only have three pieces to contend with. You're not really implementing a game so much here, as solving a logical puzzle. I'd approach it like this:

1. Figure out how to represent the three pieces in a simple way. You really don't need a UI here (other than for testing), since you're just trying to solve a puzzle. The simplest way is probably a simple Row,Column position for each of the three pieces.

2. If you haven't written an object-oriented program before, you'll probably want to stick with a procedural model and simply define variables for the data you'll need to represent. The problem scope is small, so you can get away with this. If you have some OOP experience, you can split up the problem appropriately, though you probably won't need any inheritance relationships.

3. Write the code for generating possible moves and determine whether a given move makes any sense at all. A legal King move is any move that does not check the King. Most queen moves should be permissible, but you probably also want to exclude moves that would allow the enemy King to take the Queen.

4. Now you need to determine a strategy for how to put together a sequence of moves that will solve the puzzle. If you need to find the true optimal solution (not merely a good solution), you may need to do a brute-force search. This may be feasible for this problem. You'll probably want to perform a depth-first search (if you don't know what this means, that's your first topic to research), as once you find a possible solution, that limits the depth at which all other solutions must be considered.

5. If you can get brute force functional and need to make things faster, consider if there are moves you can prove will have no benefit. If so, you can exclude these moves immediately from your search, saving on the number of branches you need to consider. You can also work to optimize your evaluation functions, as a faster evaluation is very beneficial when you are doing billions of them. Finally, you might come up with some heuristics to evaluate which of the branches to try first. The faster you can converge to a 'good' solution, the less cases you need to consider to find the optimal solution.

---

One side note I realized is that the problem is very different if you assume that the enemy King is trying to avoid checkmate. The simple depth-first pruning only works if you are allowed to move the enemy King in the way that best checkmates it. If the enemy King is attempting to avoid checkmate, that complicates the problem, as you have conflicting optimization goals (you want it to occur in as few moves as possible, yet your enemy King wants to postpone as long as possible.) You might be limited to characterizing a range of possibilities (say, 3 moves best case if King is perfectly cooperative, 8 moves best worst-case if King is perfectly evasive.)

Answer 3

This is the simplest possible example of an endgame database. There are less than 64^3 = 262144 positions, so you can easily store the score of each position. In this case, we can define the score as the number of moves to checkmate, for a winning position; or 255 for a drawn position. Here is an outline:

1. Set all scores to 255.
2. Look for all checkmate positions, and score them as 0.
3. Set depth = 1.
4. For each drawn position (score=255), see if a move exists into a won position (more precisely, see if a move exists into a position from which all of the opponent's moves are losing.) If so, set its score to depth.
5. If no new position was found in step 4, you're done.
6. Increment depth, and go to Step 4.

Now you have a 250k table that you can save to disk (not that it should take many seconds to generate it from scratch). If space is important, you can reduce this significantly by various tricks. Wikipedia has a nice article on all this -- seach for "Endgame tablebase".

Answer 4

A poster here suggest that Stockfish would be a good start, but it is a C++ project, whereas you are asking for C#.

The solution depends on your requirement. If you are interested in "just make it work", you could complete the project without writing more than 200 lines of code. You could embed an open source C# project, and ask the engine to report you the number of moves to mate. If the open source project is UCI supported, the following command will do the job:

go mate x

where x is the number of moves to mate.

However, if you need to do the thinking yourself. You will need to choose between efficient bitboard or object-oriented representation. Bitboard is a much better representation, it is very fast but harder to program. All chess engines use bitboard. In your project, represenation efficiency is not too much of concern, so you could choose OO represenation.