Оптимизация шахматной игры в C

Question

Я делаю простую шахматную игру на C, и я хотел знать об оптимизации, которую я мог бы сделать. В настоящее время у меня есть структура Game, в которой есть текущее состояние игры (Главное меню, Меню паузы, Игра и т. Д.), Поворот, 3 целых числа, которые работают как логические, указатель на доску и указатель на выбранный фрагмент:

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

    ChessColor turn; 
    State state; 

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

Совет имеет 2D массив указателей на куски, игроки и последние перемещаемых штук (для мимоходом):

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

    Player *player1; 
    Player *player2; 

    ChessPiece *lastMovedBlackPiece; 
    ChessPiece *lastMovedWhitePiece; 
} ChessBoard; 

и, наконец, штучных:

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

    //Type 
    Type type; 

    int numberOfMoves; 
} ChessPiece; 

Каждый раз, играть er выбирает кусок, программа вычисляет и показывает действительные ходы выбранного фрагмента, а после перемещения фрагмента программа проверяет, находится ли король врага, или он был мат, проверяя возможные движения фигур (если часть может защитить его, если король может двигаться в другом месте).

Я вижу людей, создающих списки для действительных ходов вместо вычисления каждый раз, но мне нужно будет создать список для каждой части и рассчитать все возможные шаги для игрока, когда изменится поворот? Улучшит ли производительность? Я также видел, что плата была всего лишь массивом, и у нее была бы более высокая производительность?

В принципе, какие возможные оптимизации я могу сделать в своем коде для лучшей производительности?

Код: https://github.com/WalrusNine/chess-game-c

Answer 1

В основном, которые являются возможными оптимизациями я могу сделать в моем коде для улучшения производительности?

Это широкая и глубокая тема. Я написал полностью функциональный шахматный движок в Java (https://github.com/amir650/BlackWidow-Chess), и я могу сказать вам, что вы можете многое сделать.

Сначала читайте: https://chessprogramming.wikispaces.com. Сначала сосредоточьтесь на правильности вашего двигателя. Он справляется с рокировкой, en-passant, check, checkmate, обнаруженной проверкой и т. Д. Не считая этого правильным, производительность не имеет значения!

Далее напишите minimax и функцию оценки - которые служат вашей основной процедурой поиска и измеряют количество плат, которые она может оценить для вас в секунду.

Оттуда, вещи начинают открывать:

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 

Независимо от оптимизации вы делаете, убедитесь, что правильность не регрессирует. Это означает, что написаны достойные модульные тесты.