Ruby and recursion - find out all possible chess knights movements using minimax algorithm

The article starts from a high school assignment to build a two-person game on a 4x4 chessboard with a knight, where a human plays against the computer and neither side can step on a square already used. It explains the basic ideas behind knight movement, recursion, and minimax, then connects them to the problem of choosing the computer’s move.

The programming section describes three Ruby files for the grid, the tree, and the launcher. The code creates the starting grid, generates all valid knight moves recursively, builds a move tree, assigns min/max states and ranks, and uses those ranks to decide the best next move for the computer.

Reading notes

#

• A high school assignment asked for a two-person chess-based game on a 4x4 field, with human and computer players who cannot revisit the same square.
• The article covers knight movement, basic AI ideas, recursion, minimax, grid loading, movement tree generation, printing, and basic moves.
• The knight moves in an L shape, two squares in one direction and one square in the other, giving up to eight possible destinations.
• AI is presented as a way for non-living things to think, learn, analyze, and act from information and situation.
• The computer needs programmed rules to react to player moves and choose a best move.
• Recursion is described as a function calling itself, with a stopping condition needed to avoid infinite loops and stack errors.
• The example notes that recursion goes to the deepest level and then returns values back up the chain.
• Minimax is described as minimizing the risk of losing by building a tree of possible moves and evaluating the tree from min and max states.
• The tree is generated by code, and the algorithm assigns alternating min/max states by level.
• End nodes get ranks of 0 or 1 depending on state, then parent nodes use child ranks to compute their own rank.
• The program is split into main.rb, grid.rb, and tree.rb.
• The grid code creates a 4x4 array, stores player locations, prints the grid, and prints the tree for visibility.
• The tree code stores grid, moves, state, and rank, finds the current player, and computes the best next move from child ranks.
• Valid knight moves are checked against board boundaries and empty squares.
• The tree generator creates a new grid object, sets the initial state to max, recursively generates moves, and sets ranks when recursion returns.
• The post says the example is not fully playable and points to a GitHub repository for the full code.