Chess AI

This individual chess AI project was completed over the course of two months in the summer of 2014. It is Universal Chess Interface compliant, and can be used either as a command line executable or with a UCI front-end.

The primary goal was to apply my theoretical knowledge of AI in a more practical manner. The program generates a tree of possible moves from a given internal board state and then uses the min-max algorithm to find the best possible move. The board position scores can be based upon values given in an XML file, or default values for pieces and controlled squares may be used.

One unexpected challenge of the project was optimization. The program generates a tree of all possible moves to a specified depth, which requires exponentially increasing time with each additional level of depth. When I ran the first tests, the program would take two to three minutes to generate a search tree three moves deep. This was approximately the speed and depth of a novice human, and unacceptably slow. The primary performance gains were derived from redesigning the data structures and reducing the number of heap allocations.

The full source code and an installer for a third party UCI front-end can be found at this link.

The following code snippet is the method for min-max scoring:

std::vector<Move> MinMaxNode::bestMoves()
{
    std::vector<Move> goodMoves;
    float bestScore = m_boardState.m_whiteToMove ? highestChildScore() : lowestChildScore();
    for (unsigned int childIndex = 0; childIndex < m_children.size(); childIndex++)
    {
        if (m_boardState.m_whiteToMove ? m_children[childIndex]->m_highestScore == bestScore : m_children[childIndex]->m_lowestScore == bestScore)
        {
            goodMoves.push_back(m_children[childIndex]->m_moveToTransform);
        }
    }
    return goodMoves;
}