grandmaster level chess AI using python - Part 2 (the code)

By
In continuation of part 1, I will now building my chess AI in python.  As mentioned before, my goal is to create a chess AI at the Grandmaster level (elo > 2500)

Here is the code for the chess AI.
https://github.com/luweizhang/chess_ai

 Key components of the chess game / AI:
  • Python Classes:
    • ChessGame
      • instantiates the chessboard and pieces
      • keeps track of whose turn it is
    • RulesEnforcer
      • Logic for how all the pieces move, castling
        • Makes sure you cant make illegal moves
        • Used in the chess AI to generation possible positions
    • ChessAi
      • Tree generator
        • generates the tree of position moves
      • Position Evaluator
        • evaluates the quality of chess positions
      • Minimax
        • Determines the optimum move from the chess tree
    • ChessDB
      • Opening database


 Explanation of the tree generator:

 The tree generator component of the chess AI generates the possible future board positions based on the possible moves that the pieces can make.  At any given position, there are on average 20 possible moves that can be made in chess.

 Image result for chess ai
The above illustrates a chess tree.  Possible moves are generated from the current position to create hypothetical future states.

Explanation of the evaluation function

 I would say that this is the intuitive component of the chess AI.  Given an 8x8 chess position, the evaluation function with determine between a move is good or not by assigning it a numerical score.   A negative score means that black is winning, a positive score means that white is winning.
Image result for brains
This component of the AI is the most important because it is the one that can be optimized.


 Explanation of the minimax algorithm:

The minimax algorithm essentially tries to find the optimal move from a tree of moves.   Starting from the leaves of the tree, you want to backwards calculate back to the optimal move by alternating between min() and max() (hence the name, minimax).

When it is your turn, you want to optimize for your outcome, therefore you want to calculate the max() position score.

When it is your opponents turn, he wants to minimize your outcome, therefore it calculates the min() position score.

Image result for explanation of minimax

The guide below explains minimax very well:
http://web.cs.ucla.edu/~rosen/161/notes/minimax.html

Comments

Post a Comment

Popular posts from this blog

building a chess ai - part 4: learning an evaluation function using deep learning (keras)

By
Image
Note: this post is still in progress. Below I will discuss approaches for training a deep learning chess game and the results of my implementation. Approach 1: Train against the outcome of the game *y* is the outcome of the game (1 is win for white, 0 is loss for white, .5 is draw) We want to learn a function * f(p)* that can approximate this. *p*  is the chess position (8x8 chess board), actually is an 8x8x12 = 768 dimensional vector (since there are 12 pieces)      8x8x6  = 384 dimensional vector with positive values for squares with a white piece and negative values for squares with a black piece.  (Using 64 x 12 introduces too many degrees of freedom) The goal is to try to learn a function * f(p)* that can predict the winner of the game * y* given a chess position * p* . The model: Dataset: http://www.ficsgames.org/download.html millions of high quality games played by grand masters or international masters Objective/Loss Function...
Read more

Brief intro to recurrent neural networks

By
Image
Note: This post is meant to be a brief and intuitive summary of recurrent neural networks.   I have adapted this material from the Coursera deep learning course.  The value I hope to add here is that I have attempted to summarize the information in a way that is easy (hopefully) to understand, and can be used as reference or refresher material for the future. Part 1: Recurrent Neural Networks: Recurrent neural networks are a class of neural networks where the nodes/neurons form a directed graph along a sequence.  They are very effective at tasks such as Natural Language Processing because they have a "memory," in other words they can receive context from previous inputs.  They can take in input one at a time, and can pass information from one node to the next via hidden activation layers.  This information serves as the "memory" or "context" layer of the network, which can be used in conjunction as more new input is being processed. RNN Cell: ...
Read more