the best alternative for the minimising player. Beta is associated with min nodes and represents the maximum score that the minimising player is assured of i.e.the best alternative for the maximising player. Alpha is associated with the max nodes and represents the minimum score that the maximising player is assured of i.e.MiniMaxImproved addresses this by adding the depth to maximising evaluations and taking depth away from minimising evaluations, this has the effect of making wins which can be achieved in fewer moves and loses which can be achieved in the most moves more favourable.īelow are demonstrations of a victory not being seized immediately where the vanilla algorithm is being used (left gif) and the improved version that takes the win immediately where the improved algorithm is being used (right gif).Īlpha-Beta optimises the Minimax algorithm by not evaluating a node's children when at least one possibility has been found that proves the node to be worse than a previously examined move, this is known as pruning. The vanilla MiniMax algorithm's heuristic function sometimes results in a slower victory or a faster loss due to the heuristic not taking into account how many moves it would take to realise a certain configuration.
the branching factor of the game tree) and d is the maximum depth of the tree, this inefficiency is addressed with the Alpha-Beta optimisation.
This implementation also explores every possible board configuration it can, even when it is redundant to do so resulting in a time complexity of O(b^d) where b is how many legal moves there are from a board configuration (i.e. In the vanilla implementation of MiniMax ( MiniMax.java) the evaluation function returns a heuristic value for terminal nodes and nodes at the predetermined maximum search depth but the heuristic only takes into account winning, losing and draw configurations returning +10 for winning configurations, -10 for losing and 0 for a draw which slightly hinders the performance of the algorithm in terms of time to win, this is addressed in MiniMaxImproved. The Minimax algorithm uses backtracking to recursively find the next best move by assigning a value to each board configuration and evaluating each of these configurations using a heuristic evaluation function. Below are examples of varying game sizes.
However, boards of size 4x4 (or larger) have a maximum search depth over 6 have very poor performance when using the vanilla MiniMax algorithm making them essentially unplayable, this is addressed with Alpha-Beta pruning. Varying board sizes can be played by changing the BOARD_WIDTH constant in the Board class. The game GUI is implemented using JavaFX and follows a Model-View-Controller (MVC) structure where the Board and Tile classes comprise the Model and the TicTacToe class comprises the View and Controller.
0 kommentar(er)
