Possible chess knights movements using minimax algorithm

In high school, my Artificial Intelligence course gave me an assignment: a two-player game around one chess piece, the knight, on a 4×4 board. One player is human, the other is the computer, and nobody may step on a square that either player has already visited. The computer had to choose its moves with the minimax algorithm. I first worked out all possible moves by hand, then built a working version and developed it in Ruby.

In this article, I’ll explain the basics:

• how the knight moves
• basic information about A.I.
• the beast called recursion
• what is the minimax algorithm
• loading the starting game grid
• generating the movement tree
• printing for visibility
• making basic moves

The theory part

I will start with the essential theory. If you already know it, skip to the next chapter.

---

How does a chess knight move?

If you have ever played chess, you know that the knight can be a powerful and dangerous piece. Of all chess pieces, it moves in the most unusual way: two squares horizontally and one square vertically, or two squares vertically and one square horizontally. So, if the knight has space, it can move to 8 different squares from its current position.

This L-shaped jump is the knight’s move, and the knight can jump over other pieces. Knight legal moves drop near the edges: on an 8×8 board, a knight has 8 moves from each of the 16 central squares but only 2 from a corner. On our 4×4 board, it has 4 from the central squares, 3 from the other edge squares and 2 from a corner. In code, all knight movements come from eight offsets plus a check that the square is on the board, as in find_valid_movement below.

Basic information about Artificial Intelligence

Artificial means made by people. Intelligence is harder to define. My definition for IT: Artificial Intelligence is the ability of non-living things to think, learn, analyze and then act on the information or situation in front of them.

Films are full of clever AI robots, but in 2015 real robotics looked different. A robot first has to learn, and people learn from results: you touch fire, it burns you, and you don’t touch it again. A robot feels no pain, so A.I. needs data to base its decisions on.

Why am I telling you all this? To play against you, the computer has to know how to react to your moves and pick the best one, so we programmers write the rules that guide it. A hand-written program is not self-thinking, true, but the computer opponents in your favorite FPS game also follow written rules and still act like humans. My knight-computer needed rules too, and the assignment required the minimax algorithm for its decision-making.

---

Few words about recursion

Recursion is a programming technique in which a function calls itself. The idea is simple, the implementation less so: a function that never stops calling itself ends in Ruby’s “stack level too deep” error (SystemStackError). You need to know the next step and, above all, where the function stops. For me, the stopping condition was the hardest part when I was learning LISP.

Example factorial function:

def fact(n)  
  if n > 1
    n * fact(n - 1)
    # puts n

    # In theory, that puts is only executed when deepest level -1 of recursion is reached,
    # that is, when fact returns 1 and steps back.
    # In this example it would break recursion because fact works on returned values, puts returns nil
  else
    1
  end
end

The check on n decides whether this call is the stopping point or the function calls itself again with (n – 1). Recursion goes down to the deepest level you allow, then climbs back level by level, returning each value to the level above: fact(5) returns 120. When a simple loop can do the job, use the loop.

---

What is the minimax algorithm?

The minimax algorithm picks the move that is best for the computer, assuming you also play your best: max wants the final score high, min wants it low, and each side picks the move that leaves the opponent the weakest best reply. In short, the computer plays its best to stop you from winning. To choose a route through the tree, minimax needs a tree of all* possible moves.

*All possible moves fit here because this game is short. In chess they don’t: Claude Shannon estimated in 1950 that chess has about 10^120 possible variations, so chess programs grow the tree as they search, stop at a set depth and score those positions with an evaluation function.

The game code (the game rules) generates the tree; that part is not the algorithm itself. During generation, though, the algorithm sets the first node’s state (min or max), and each deeper level gets the opposite state.

Example:

If the first node’s state is min, the next level must be max, then min again, and so on.

The tree is generated depth first. At an end node, where the player to move has no free square left, the algorithm sets the rank (0/1) from the state: min gets 1, max gets 0. A player who cannot move loses, so 1 means max wins and 0 means min wins. As the recursion steps back up, the algorithm checks whether every child has a rank. If so, the parent takes the highest child rank if it is a max node and the lowest if it is a min node. If a child has no rank yet, generation goes deeper into it and the process repeats.

Example:

Let’s do this step by step:

• The algorithm finds the end nodes (H, F, E) and sets their ranks by state: min=1, max=0.
• On the E branch, the algorithm moves back to C and takes the maximum of its children’s ranks: [1].max is 1.
• At A, node B has no rank yet, so the algorithm works it out.
• H is 1, so G must be 1 too, because it has only one child ([1].max).
• F is 0. D is a min node, so [0, 1].min makes D 0.
• Now we can get B, which is 0 because D is 0 too ([0].max).
• Finally, A has children B and C, so [0, 1].min is 0.

When all that is done, the first node’s rank (0 or 1) tells you who wins if both sides play their best. Here A is 0, so min wins by moving to B, and the same comparison gives the computer its best move in each position. Two ranks suffice because this game ends only in a win or a loss. Since 1 is the best a max node can get, it could stop checking its children once one returns 1 (and a min node once one returns 0): a simple case of alpha-beta pruning.

Minimum Knight Moves: Use Breadth-First Search

Minimax needs an opponent. The minimum knight moves puzzle (LeetCode problem 1197) asks for the fewest moves a lone knight needs to reach a square. There is nothing to minimize or maximize, so it is a shortest-path problem, and breadth-first search (BFS) solves it: the first time BFS reaches the target, it has found the shortest route. We ran this Ruby version for an 8×8 board:

KNIGHT_MOVES = [[-2, -1], [-1, -2], [1, -2], [2, -1],
                [-2, 1], [-1, 2], [1, 2], [2, 1]]

# Breadth-first search: the first time we reach the target is the shortest path
def minimum_knight_moves(from, to, size = 8)
  distance = { from => 0 }
  queue = [from]
  until queue.empty?
    x, y = queue.shift
    return distance[[x, y]] if [x, y] == to
    KNIGHT_MOVES.each do |dx, dy|
      square = [x + dx, y + dy]
      next unless square.all? { |c| c.between?(0, size - 1) }
      next if distance.key?(square)
      distance[square] = distance[[x, y]] + 1
      queue << square
    end
  end
  nil
end

puts minimum_knight_moves([0, 0], [7, 7]) # => 6
puts minimum_knight_moves([0, 0], [1, 1]) # => 4

From one corner to the opposite corner takes 6 moves; the square diagonally next to a corner takes 4.

---

The programming part

For this blog post, I’ll use a reduced and cleaner version of the code from the actual game. The program consists of 3 files:

• main.rb which will launch this simple application.
• grid.rb for Grid class and manipulations with grid.
• tree.rb for Tree class that will generate a tree and implement minimax algorithm.

---

Main

main.rb builds the starting grid, generates the tree and prints it. The comments explain each step.

class Main  
  # Some constants for easier use
  PLAYER_1 = 0
  PLAYER_2 = 1

  CURRENT_POSITION = 0
  CURRENT_X = 1
  CURRENT_Y = 2

  # Creates some default 4x4 game grid with 2D arrays
  def make_grid
    grid = [
      [0, 1, 0, 0],
      [0, 4, 0, 0],
      [0, 0, 3, 0],
      [0, 0, 2, 0]
    ]

    # Players location [player_info1, player_info2] where player_info[index, x, y], last even and odd values from grid
    players = [[3, 2, 2], [4, 1, 1]]

    # Creates first game grid
    grid_object = Grid.new(grid, players[PLAYER_1], players[PLAYER_2])
    # Prints out starting grid
    print_grid(grid_object.grid)
    # Generates tree
    tree_object = Tree.new.generate(grid_object.grid, players[PLAYER_1], players[PLAYER_2])
    # Prints full tree
    print_tree(tree_object)
  end

  private
  # Helper printing methods, fugly.
  def print_grid(grid, right = '  ')
    grid.each do |i|
      val = ''
      i.each do |j|
        val = val + "[#{j > 0 ? j.to_s.rjust(2, ' ') : '  '}] "
      end
      puts "#{right}#{val}"
    end
    puts "#{right}-------------------"
    ''
  end

  def print_tree(tree_object, right = '  ')
    if(tree_object)
      print_grid(tree_object.grid, right)
      right = right + '  '
      tree_object.moves.each do |node|
        print_tree(node, right)
      end
    end
  end
end

# Game initializer
require_relative 'tree'  
require_relative 'grid'

Main.new.make_grid

---

Grid

grid.rb holds one position: its grid, moves, state and rank.

class Grid < Main  
  # So we access from outside
  attr_accessor :grid, :moves, :state, :rank

  # Sets default values for object
  def initialize(grid_array, player1_info, player2_info)
    # Needs to_s and eval because for some reason Ruby keeps it by reference even if I dup or clone
    @grid = eval(grid_array.to_s)
    # Will hold all possible moves based on current grid
    @moves = []
    # State - min/max
    @state = ''
    # Rank - 0/1
    @rank = -1

    # Sets both player locations on grid, player_info = [index, x, y]
    @players = [player1_info, player2_info]
    set_player_coords(player1_info)
    set_player_coords(player2_info)
  end

  # Helper methods
  # Get player info - [index, x, y]
  def player_info(player)
    @players[player]
  end

  # Finds who's move it is
  def current_player
    @players[PLAYER_1][CURRENT_POSITION] < @players[PLAYER_2][CURRENT_POSITION] ? PLAYER_1 : PLAYER_2
  end

  # Changes current players info
  def current_player_set(array)
    @players[current_player] = array
  end

  # Finds current players index
  def current_index
    @players[current_player][CURRENT_POSITION]
  end

  # Finds current players x
  def current_x
    @players[current_player][CURRENT_X]
  end

  # Finds current players y
  def current_y
    @players[current_player][CURRENT_Y]
  end

  # Determines best next move for computer
  def find_best_way
    if @state == 'max'
      way = moves.max{ |a, b| a.rank <=> b.rank }
    elsif @state == 'min'
      way = moves.min{ |a, b| a.rank <=> b.rank }
    end
  end

  # Sets state based on previous state
  def set_state(prev_state)
    if prev_state == 'max'
      @state = 'min'
    elsif prev_state == 'min'
      @state = 'max'
    end
  end

  # Sets rank based on current state
  def set_rank
    ranks = @moves.collect{ |x| x.rank }
    if @state == 'max'
      @rank = ranks.max
    elsif @state == 'min'
      @rank = ranks.min
    end
  end

  # Finds all possible moves from current move in specific grid
  def self.find_valid_movement(grid, x, y)
    valid_coordinates = [
      [-2,-1],[-1,-2],[ 1,-2],[ 2,-1],
      [-2, 1],[-1, 2],[ 1, 2],[ 2, 1]
    ]
    move_to = []

    valid_coordinates.each do |array|
      x_coordinate = array[0] + x
      y_coordinate = array[1] + y
      next if outside_area?(x_coordinate, y_coordinate)
      move_to << [x_coordinate, y_coordinate] if grid[x_coordinate][y_coordinate] == 0
    end

    move_to
  end

  # Helper method to check coords
  def self.outside_area?(x, y)
    x < 0 || y < 0 || x > 3 || y > 3
  end

  private

  def set_player_coords(player_array)
    position = player_array[CURRENT_POSITION]
    x = player_array[CURRENT_X]
    y = player_array[CURRENT_Y]

    @grid[x][y] = position
  end
end

---

Tree

tree.rb builds the tree recursively and sets the ranks on the way back up. generate passes ‘max’ to set_state, which flips it, so the root actually gets the min state.

class Tree < Main  
  # Generates tree from given grid and locations, first state is max, returns full tree
  def generate(grid, player_1, player_2)
    new_grid_object = Grid.new(grid, player_1, player_2)
    new_grid_object.set_state('max')
    generate_moves(new_grid_object)
    new_grid_object
  end

  # Recursive function
  def generate_moves(grid_object)
    # Finds all possible moves based on current grid
    move_to = Grid.find_valid_movement(grid_object.grid, grid_object.current_x, grid_object.current_y)

    # Iterates through all possible next moves
    move_to.each_index do |i|
      # Determines where to put next move based if next_position is odd or not
      next_position = grid_object.current_index+2
      new_player_info = [next_position, move_to[i][0], move_to[i][1]]
      player_1 = next_position.odd? ? new_player_info : grid_object.player_info(PLAYER_1)
      player_2 = next_position.odd? ? grid_object.player_info(PLAYER_2) : new_player_info

      # Creates new grid based on new moves
      new_grid_object = Grid.new(grid_object.grid, player_1, player_2)
      # Adds new grid to old grids moves array
      grid_object.moves << new_grid_object
      # Sets new grids state based on previous state
      new_grid_object.set_state(grid_object.state)
      # Goes deeper in recursion with newly created grid
      generate_moves(new_grid_object)
      # When recursion has come back (reached deepest level), old grid gets rank based on childs it has
      grid_object.set_rank
    end

    # When reached deepest level of tree, sets rank based on state
    set_last_rank(grid_object) if move_to.empty?
  end

  private

  def set_last_rank(grid_object)
    if grid_object.state == 'min'
      grid_object.rank = 1
    else grid_object.state == 'max'
      grid_object.rank = 0
    end
  end
end

---

Launching tree generator

Save the three files in one folder and run ruby main.rb. It prints the starting grid, then every position in the tree, indented by depth. The numbers show the order of moves: odd for one player, even for the other.

---

How to play?

This example isn’t fully playable: it lacks the game loop and input handling. The full code, a little messier and undocumented, is on the GitHub page.

---

What Has Changed Since 2015

The tutorial above is kept as written in 2015. Its code uses only core Ruby and no gems, and in October 2026 we reran it with the system Ruby on a Mac: it builds the same tree. If Ruby reports a syntax error near an if after copying, replace the non-breaking spaces before it. The grid.rb comment about Ruby keeping the grid “by reference even if I dup or clone” has a simple cause: dup and clone make shallow copies, so the inner rows stay shared. Today you would write grid_array.map(&:dup) instead of eval; see our post on Ruby arrays.

Minimax chess engines prune the tree with alpha-beta, which skips branches that cannot change the result and still returns the move plain minimax would choose. With ideal move ordering, it can search about twice as deep for the same effort. Stockfish still searches this way (principal variation search), but its evaluation is now a neural network: NNUE arrived in 2020, and Stockfish 16.1 removed the hand-written evaluation in February 2024. DeepMind’s AlphaZero (2017) replaced alpha-beta with Monte Carlo tree search guided by a neural network trained through self-play. Its paper reports 80 thousand positions searched per second against 70 million for Stockfish, and AlphaZero still won their match. For a 4×4 knight game, plain minimax over the whole 43-position tree is still enough.

 

See more examples of the AI Services and Integration we provide.

 

Diatom Enterprises is a software development company headquartered in Riga, in business since 2004. Contact us if you need help with AI Development Services and integrations.

---