The game using MiniMax algorithm
The game involves two players taking turns selecting numbers from an n-element vector. Each player can choose either the first or the last number from the vector on their turn. The game continues until all numbers have been chosen. The objective for each player is to maximize the sum of the numbers they collect. The player who achieves the highest sum wins the game.
For example n = 4, consider the vector [2, 0, 3, 1]. The optimal gameplay for the starting player would be to select [2, 3], leaving the second player with [0, 1] or [1, 0].
Implemented are three different players against whom the MinMax player plays:
Random Agent: The Random Agent makes decisions randomly without considering any specific strategy. It simply chooses a move randomly from the available options. This agent can be unpredictable and may not always make optimal decisions. However, it can sometimes introduce an element of surprise into the game, which might be advantageous in certain situations.
Greedy Agent: The Greedy Agent follows a simple strategy of always choosing the move that maximizes its immediate gain without considering the long-term consequences. It typically selects the option that appears most favorable at each step without considering future moves or opponent strategies. While this approach can lead to quick gains in the short term, it may not always result in the best overall outcome.
Ninja Agent: The Ninja Agent is a more sophisticated player that employs a combination of defensive and opportunistic strategies. It evaluates potential moves based on their immediate benefits as well as their impact on future gameplay. The Ninja Agent aims to minimize risks while capitalizing on opportunities, often adopting a more adaptive and strategic approach compared to the Random and Greedy Agents. This agent is more likely to anticipate opponent moves and adjust its strategy accordingly, making it a formidable opponent in many scenarios.
test.py Unit tests have been conducted to verify whether the algorithm has been implemented correctly. The algorithm passed all tests successfully.
- Głębokość - Depth
- Średni czas - Mean time
- Średnia suma punktów - Mean sum of points
- Odchylenie standardowe - Standard deviation
Depth: Indicates how far the algorithm goes in analyzing the game tree. Mean time: Measures the dispersion of data around the average score. Mean sum of points: The average value of points collected by the algorithm during the game. Standard deviation: The average time it takes for the algorithm to make a move in the game.
-
MinMaxAgent vs RandomAgent
-
MinMaxAgent vs GreedyAgent
-
MinMaxAgent vs NinjaAgent
-
MinMaxAgent vs MinMaxAgent(15)
Depth: The depth of the state tree, which is a parameter of the Minimax algorithm, has a significant impact on the results obtained by the agent in various situations. With increasing depth of the tree, i.e., the number of levels at which the algorithm considers possible moves, the agent can make more thoughtful decisions, potentially leading to better game results. However, the impact of the tree depth is not straightforward and may depend on many factors, such as the opponent's strategy, the complexity of the game, and even randomness or random elements in the game.
Mean time: The game execution time may also depend on the opponent's strategy. If the opponent makes quick decisions or has lower computational complexity, the game execution time may be shorter. On the other hand, more advanced opponent strategies may require longer computation time by the MinMaxAgent.
Mean sum of points: The results obtained by the MinMaxAgent tend to decrease as the opponent's difficulty increases. If the opponent is more sophisticated or employs a more optimal strategy, the MinMaxAgent may struggle to achieve high point sums.
Standard Deviation: The stability of MinMaxAgent's results may also depend on the opponent's strategy. If the opponent is more predictable or employs similar strategies in different games, the standard deviation of MinMaxAgent's results may be lower. On the other hand, more diverse opponent strategies may lead to greater variability in results.
-
Test for tree depth 2 MinMaxAgent vs RandomAgent
-
Test for tree depth 15 MinMaxAgent vs RandomAgent
-
Test for tree depth 2 MinMaxAgent vs GreedyAgent
-
Test for tree deptha 15 MinMaxAgent vs GreedyAgent
-
Test for tree depth 2 MinMaxAgent vs NinjaAgent
-
Test for tree depth 15 MinMaxAgent vs NinjaAgent
-
Test for tree depth 2 MinMaxAgent vs MinMaxAgent(15)
-
Test for tree depth 15 MinMaxAgent vs MinMaxAgent(15)
The distribution of point sums obtained by the MinMaxAgent for tree depths 2 and 15 can be approximated as a normal distribution, specifically a binomial distribution, as the random variable is discrete rather than continuous. For both tree depths, the majority of results cluster around the mean value, and deviations from this value become increasingly rare, which aligns with the characteristics of a distribution approaching normality.
If the histogram of point sums for one of the agents is shifted towards higher values and has a smaller spread than the histogram for the other agent, we can consider that agent to be better. This implies that the agent achieves higher average scores and is more effective in maximizing the sum of points.