grandmaster level chess ai using python - Part 1: Outlining the Rough Design

By
Inspired by AlphaGo, I am starting to work on building a basic chess computer using Python.

I will design this chess computer based off of first principles.  I will try not to consult any online guides.  I won't use any libraries and will only rely on basic data structures and algorithms to build it.

 The first iteration of this chess computer will work by brute force alongside a simple heuristic algorithm.  After the first iteration is complete, I will try to improve on it.

 My goal here is to create a grandmaster level chess ai (elo > 2500).  I think the key to creating a very strong chess ai is the combination of the tree search and the heuristic algorithm.

Below is a rough outline of how I will design this engine.  This design will compute N moves into the future, and then use a simple scoring method to choose the best moves out of the future states.

Chess set design
  • A 2D 8x8 matrix to represent all the spaces on the chess board.
  • letters to represent the different chess pieces, also rules around how they can move, and value of each piece
    • pawn = 'p'
      • movement: 1 or 2 squares up the board
      • value: 1
    • rook = 'r'
      • movement: vertically or horizontally up the board
      • value: 5
    • knight = 'k'
      • movement: two squares left or right + one square up down OR two squares up down + one square left right
      • value: 3
    • bishop = 'b'
      • movement: diagonal
      • value: 3
    • king = 'ki'
      • movement: up down left right 1 square
      • value: 100 (basically a number arbitrarily high enough that the chess engine will never think that it is a good idea to lose this piece)
    • queen = 'q'
      • movement: up down left right or diagonal
      • value: 9
  • Prefix to each piece to represent whether it is black or white (b or w)

Program design
  • Chess board
    • init() function creates the chess board data structure and places all the chess pieces at their starting positions
  • Rules
    • logic to enforce the rules of the game
      • how the pieces move
      • castling
      • etc.
  • AI Engine
    • Component 1: Tree Search
      • Running process that calculates into the future and stores the best move in a data structure, along with its projected score
      • Given the current position, computer all possible future board states up to N moves into the future.  Store all these future states into an array
        • Minimax algorithm:
          • when it is your turn, you want to maximum the your odds of winning
          • when it is your opponents turn, he wants to maximize his odds of winning.
    • Component 2: Position Evaluator, Heuristic Algorithm
      • some sort of heuristic to evaluate each chess position
        • such as sum of pieces on the board
        • can use a model, such as a neural network to evaluate positions quickly and accurately. 
          • train it on millions of chess games.  
          • use this as training data: http://www.ficsgames.org/download.html
    • Prioritization
      • We need to prune out fruitless searches in order to optimize this chess computer.  Here are some ideas to weed out fruitless moves
        • The chess computer assumes that its opponent and will choose a reasonable good move (minimax algorithm)
        • Heuristic component (position evaluator) of the Chess AI will reduce the search space by narrow down to a few possible moves
          • Heuristic algorithm based off a neural network trained off of millions of games can also reduce the depth required for the search.  This is because the algorithm is trained against the outcome of the game, so basically you are using heuristics to see far further into the future than what is capable from the brute force tree search.
        • Use a chess opening database for initial moves
        • alpha beta pruning

 Now I will attempt to build this and see how it performs.  After that, I will review and optimize its performance.

Comments

Post a Comment

Popular posts from this blog

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

By
Image
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 o...
Read more

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