Optimizing Chess Game in C

Question

I'm making a simple chess game in C and I wanted to know about the optimizations I could make to it. Currently, I have a struct Game that has the current state of the game (Main Menu, Pause Menu, Playing etc), the turn, 3 integers that work as booleans, pointer to a board and pointer to the selected piece:

typedef struct game{
    ChessBoard *board;
    ChessPiece *selectedPiece;

    ChessColor turn;
    State state;

    //Booleans
    int inGame;
    int checkmate;
    int check;
}Game;

The Board has a 2D array of pointers to pieces, the players and the last moved pieces (for en passant):

typedef struct chessboard{
    ChessPiece *pieces[8][8];

    Player *player1;
    Player *player2;

    ChessPiece *lastMovedBlackPiece;
    ChessPiece *lastMovedWhitePiece;
} ChessBoard;

And finally the piece:

typedef struct chesspiece{
    //Properties
    int x;
    int y;
    ChessColor color;

    //Type
    Type type;

    int numberOfMoves;
} ChessPiece;

Each time the player selects a piece, the program calculates and shows the valid moves of the selected piece, and after moving a piece the program verifies whether the enemy king is in check or it was checkmate by checking the possible moves of the pieces (if a piece can protect him, if the king can move elsewhere).

I see people creating lists for valid moves instead of calculating every time, but I'd have to create a list for every piece and calculate all the possible moves for a player when the turn changes? Would that improve the performance? I also saw the board being just an array, would that have greater performance as well?

Basically, which are the possible optimizations I can do in my code for better performance?

The code: https://github.com/WalrusNine/chess-game-c

It's difficult to suggest improvements to your code without seeing it. — PM 77-1, Apr 04 '15 at 23:58
@PM I was thinking about general, known-optimizations for chess games, as I did no optimization at all, and there are some parts of my code that really (really) need a change haha, but anyways: https://github.com/WalrusNine/chess-game-c After the code is better I'm planning on giving it to some friends to help them learn a bit of games in C. It's using Allegro btw — WalrusNine, Apr 05 '15 at 00:05
@PM Are there any well known tips that could help me? If it's still too broad, I'd like to know about the two questions I asked (lists of possible moves vs calculate every time and array of pieces instead of 2D array). Or would you recommend another site? — WalrusNine, Apr 05 '15 at 00:12
you might want to look at the min/max algorithms and alpha/beta pruning algorithms. BTW: the code would be a LOT more readable if you eliminated the typedef modifiers on the struct definitions (the preferred method is to not use typedef's as they just clutter/obscure the code, clutter the compiler namespace, and can be very misleading to the human reader.) — user3629249, Apr 05 '15 at 02:36
I browsed the code for main,.c and game.c . in C, the returned value from malloc() (and family of functions) should not be cast. The returned value from malloc() and family should always be checked (!= NULL) to assure the operation was successful — user3629249, Apr 05 '15 at 02:43
when calling scanf() and family, always check the returned value (not the parameter value) to assure the operation was successful. The user could easily overrun the input buffers, place a length limiter on the conversion parameters to avoid the overrun problem. — user3629249, Apr 05 '15 at 02:45
in this function: 'void InitializeBoard(ChessBoard *board){' if board is NULL, the initialization is skipped, however, there is no effort to recover from this error, nor is the error information propagated back to the caller/rest of the game. — user3629249, Apr 05 '15 at 02:54
@user3629249 I still have to take AI classes so I'm leaving the AI part for later xD. But man these programming tips are awesome, is there a site or a book that cover these details and helps improving the code? Anyways I'll improve the code in the areas you pointed out, thanks! — WalrusNine, Apr 05 '15 at 03:03
Guys... The program should be optimised by chess algorithms. Doing those little things will never work. In particular, you might want to look at alpha-beta, PVS, pruning etc. — ABCD, Apr 05 '15 at 11:26
Whatever else you do, [*do this*](http://stackoverflow.com/a/378024/23771). You might find, for example, 50% or more of your time going into `malloc` and `free`. If you find that (but not before), there's a simple fix. (It will speed you up by a factor of 1 over 1 minus the fraction of time it takes.) Other things also could have simple fixes. — Mike Dunlavey, Apr 06 '15 at 17:42

score 1 · Accepted Answer · answered Apr 06 '15 at 16:49

Basically, which are the possible optimizations I can do in my code for better performance?

This is a broad and deep topic. I've written a fully functional chess engine in Java (https://github.com/amir650/BlackWidow-Chess) and I can tell you, there are a lot of things you can do.

Start by reading: https://chessprogramming.wikispaces.com. First focus on the correctness of your engine. Does it handle castling, en-passant, check, checkmate, discovered check, etc. Without getting this correct, performance doesn't matter!

Next write a minimax and evaluation function - which serve as your basic search procedure, and measure the number of boards it can evaluate for you per second.

From there, things start to open up:

1) Alpha Beta Pruning
2) Board representation (bit-board vs array)
3) Null Move Heuristic
4) DB for opening
5) DB end engame
6) Transposition tables
7) ..it goes on

Whatever optimizations you do, make sure correctness does not regress. This means having decent unit tests written.

Optimizing Chess Game in C

1 Answers1