This week at the Recurse Center I took my ghess chess engine and implemented a MiniMax algorithm to give it some sort of AI. There are a number of steps to creating a chess engine

  1. Represent the board
  2. Validate the moves
  3. Search for valid moves
  4. Evaluate positions
  5. Choose a move to play

I more or less knocked out the first few steps before arriving at RC; and it’s the fifth step that really challenged me, whereas validating the moves was an exercise in basic math and searching for valid moves revolves around sound and redundant tests. It was appropriate, I decided, to implement minimax, a recursive algorithm, at the Recurse center.

Before, however, I had to evaluate positions. My initial reaction was to evaluate a move, which might make sense when deciding what move to take for us humans. I quickly found out, however, that computers don’t care what the move is, they care about how the board looks afterward (or better yet, after any number of moves). While this leads to some pretty funny, in a bad way, moves, it makes implementing minimax much easier.

Evaluation

First of all evaluation for a zero-sum game like chess takes into account that the two players are on opposite sides of the same coin: Max on one side, and Mini on the other. That is to say, an evaluated board will give a negative score for Black advantage and positive score for White advantage. The scoring algorithm, hopefully, will give a solid 0 to the opening position, seeing as how things are pret-ty even steven in a zero-sum game.

Edit:

Evaluation was neat to play around with, but MiniMax is performed best when deepest. As MiniMax traverses the tree, each depth increases the amount of calls exponentionally and anything like the checks below becomes more of a hinderance (in terms of speed, or computer power) than a boon. So sticking with simple material advantage in centipwans was the most efficient. The faster each move, search, and evaluation, the farther the possible depth in shorter amount of time.

Resuming original post

For evaluation, which isn’t evident, I leaned on some basic chess knowledge I’ve learned over the years, mostly thanks to Nimzowitsch’s elements. That is, simple positional givens (some of which escape my ability to evaluate), such as:

  1. Passed Pawns
  2. Outpost Knights
  3. Rooks on the Seventh Rank
  4. Open Files
  5. Pawn Chains
  6. Tempo

Otherwise, the pieces themselves, as traditionally scores 1 for Pawn 3 for Knight and Bishop, 5 for Rooks, and 9 for Queen, offer simple ways of evaluating a players position on the board. I declare +10 for every white pawn, and -10 for every black pawn.

One of the more subtle ideas I tried to implement in my evaluation, is the notion of tension. I wrote a func (b *Board) Tension() map[int]int method whose job is similar to a simple Search for Valid move method: it finds all the valid moves, but instead of returning a list of valid moves, it returns a map. The keys are coordinates on the bitmap holding the chess position, and the values are the weight of attack on that square. So for every black piece attacking a certain square, that square gets -1, and visaversa for white. Now the sum of this, as with the evaluation more generally, will be 0 on the opening. The board’s initial position’s tension looks like this:

Total Tension:  0
|-1||-1||-2||-2||-1||-2||-1||-1|8:
|-1||-1||-1||-4||-4||-1||-1||-1|7:
|-2||-2||-3||-2||-2||-3||-2||-2|6:
| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|5:
| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|4:
| 2|| 2|| 3|| 2|| 2|| 3|| 2|| 2|3:
| 1|| 1|| 1|| 4|| 4|| 1|| 1|| 1|2:
| 1|| 1|| 2|| 2|| 1|| 2|| 1|| 1|1:
: a:: b:: c:: d:: e:: f:: g:: h:

MiniMax

The MiniMax algorithm is essentially a depth first search algorithm which goes down the tree of possible moves (which in Chess quickly get’s large) in what we call a ply. A ply is half a move. For example, 1. e4 e5 is one move, two plies. Instead of looking for the best possible move, the minimax will look for the opponent (mini’s) best possible move, and itself (max) choose the move which gives the least best move to mini. This involves searching down the tree recursively to the terminal positions (which are feasible reached for tic tac toe but quite out my puny computer’s reach for chess) and comes up with the relevant score and the move that got there. Because chess is so, well, large in possibilities, I define the terminal point myself; currently a depth of 3 ply can take around 2 seconds to determine a move, while 4 ply will take 4 minutes.

Preconditions

The code itself is pretty short, but it includes three parts:

  1. A State struct to keep track of the initial move that got us to a position and the score of that position:
  2. A function for getting all possible states, GetPossibleStates() and setting, if empty, that move that got us there
  3. Two functions, Min() and Max() for getting the Maximum and the Minimum State in a list of States

With those three things, I could finally implement a Minimax algorithm:

func MiniMax(depth, terminal int, s State) (State, error) {
    if depth == 0 {
        // Check opening dictionary
        openState, err := DictionaryAttack(s)
        if err == nil {
            return openState, nil
        }
    }
    // Stop at terminal depth
    if depth == terminal { // that is, 2 ply
        //fmt.Println("Depth ", depth, s)
        return s, nil
    }

    states, err := GetPossibleStates(s)
    if err != nil {
        return s, err
    }

    var bestState State
    var bestStates States
    for _, state := range states {
        bestState, err = MiniMax(depth+1, terminal, state)
        if err != nil {
            return bestState, err
        }
        bestStates = append(bestStates, bestState)
    }
    if len(bestStates) < 1 {
        return s, nil
    }
    even := (depth % 2) == 0
    if even {
        // If is White Player Return Maximum
        return Max(bestStates), nil
    } // Otherwise Return Minimum
    return Min(bestStates), nil
}

This function is always called with 0 as depth, and then recursively it calls itself and adds to 0 until it reaches the likewise defined terminal depth.

This is the minimun requirement working code for MiniMax; to improve it, see my repo for it’s final form. Namely, it needs AlphaBeta Pruning.

Especially for an opening move, the minimax algorithms shows some weakness (both in time and quality of a decision); the solution is to construct a map of opening positions and, if the depth is still 0, first check for a predefined response. My AI will open with the classic 1. e4.

Result

Edit:

The prototype ghess, deployed on heroku, has three difficulties, easy 3, medium 4, and hard 5 depth. It’s not perfect, but *ghess can be a brutal and uncompromising opponent.

Resuming original post

My first game against a depth 3:

|Move:  35     Turn: w
|Check: true Castle: ----
|Mate:  true Score: 0-1

| ||░||♖||░||♚||░|| ||░|1:
|░|| ||░|| ||░|| ||░||♖|2:
|♟||░|| ||░|| ||░|| ||░|3:
|░|| ||░||♗||░|| ||░|| |4:
| ||░|| ||░|| ||░|| ||░|5:
|░|| ||░|| ||░||♘||♗|| |6:
|♙||♙|| ||♔|| ||♙||♙||♙|7:
|░|| ||░|| ||░|| ||░|| |8:
:h::g::f::e::d::c::b::a:

Game Over:
0-1

Now, it looks pretty bad for white, but for some of the game they weren’t playing half bad – it’ll improve. Note the unicode colors on this blog are not correct, it’s white who looses.