Implementation for a minimax game engine.
A Minimax game is any turn-based two player game where the objective of one player is to maximize the evaluation score while the opponent tries to minimize it. Examples of such games include Chess, Go, TicTacToe, Connect Four, etc.
In this crate, there is a generic implementation of the minimax game-playing engine that can be used for any such games. The minimax algorithm is notorious for being slow so we speed it up using a pruning method called Alpha-Beta pruning.
The minimax algorithm under-the-hood tries to simulate every possible "best" gameplays from either sides and based on the results, recommends a move that should be played to best improve the winning chances of the player to move.
There is a caveat, in that, the minimax algorithm is too slow (since it explores the search space almost uncleverly). One optimization is that of pruning the search space by the means of a clever approach in which we "rule out gameplay sequences which the opponent won't definitely let us improve in." This is achieved by a technique called Alpha-Beta pruning.
The crate provides concrete implementations for TicTacToe, (note: other games are in works).
TicTacToe::get_best_move(depth, player) method to compute the best move in this position for this player.
To use a pre-written driver:
To write a driver yourself:
use ; use *; let mut ttt = create_game; ttt.print_board; // The first argument takes a reference to the move position. // The structure of the board is like [[0, 1, 2], [3, 4, 5], [6, 7, 8]]. // The second argument governs who plays this move; // true means the first player, false means the second. ttt.play; ttt.play; ttt.print_board; // The first argument is the depth to explore. // The higher the depth, the more the time it takes to compute // the best move and that the chances of it being the best move increase. // The lower the depth, the faster it takes to compute but the less // the likelihood of being the best move. // The second argument governs who plays this move; // true means the first player, false means the second. let best = ttt.get_best_move; ttt.play; ttt.print_board;
To use the engine for a completely new minimax game (e.g. chess):
use ; /// Define the Chess structure. // Implement any basic methods on Chess. // This should ideally allow us to work with // Chess at a very low level. // You'll likely need to have a new struct // that represents a move in Chess. // Implement all the higher level // methods on Chess. This should ideally // be compositions of the basic methods // in the default impl of Chess. // Once Strategy is implemented for Chess, the Minimax engine should be ready to use! // Make sure there is a create_game in the default impl for Chess. // Then create a game with parameters as necessary. let mut chessboard = create_game let search_depth: i64 = 6; // Play arbitrary number of moves depending on how've you defined it in the default impl. chessboard.play; let best_move: ChessMove = chessboard.get_best_move; chessboard.play; chessboard.print_board;
I enjoyed creating this and is one of my first excursions in Rust. If you found this library useful or maybe just cool, consider awarding a star.
Please create an issue.
All pull requests are welcome!