Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
I just read an article about the minimax algorithm. When you design the algorithm, you assume that your opponent is a perfect player, i.e. it plays optimally.
Let's consider the game of chess. What happens if the opponent plays irrationally or sub-optimally? Do you still have a guarantee that you are going to win?
What happens if the opponent plays irrationally or sub-optimally? Do you still have a guarantee that you are going to win?
If your search is deep enough to guarantee optimal play in all cases, then yes. Optimal play is such that the opponent's decision causes least impact to your agent. In fact, if the opponent makes a mistake, often that can make the search easier/faster, and the agent will win more convincingly.
What it may mean is that optimisations you may have taken - e.g. pruning game tree segments that lead to non-optimal decisions by either player - might not be as useful. This might impact decision time if you keep some partial game tree or cache branch evaluations between moves to help speed up the agent.
Actual optimal agents for games as complex as chess are not possible. In these games, you will not have a truly optimal agent, but approximately optimal. You will be relying on some heuristic to guide the minimax search when it cannot force an end game win. If the opponent manages to control play into a state where the heuristics are not accurate, they could cause minimax search to fail and misdirect your agent into making mistakes.
A combination of effects is also possible if you have implemented a tree caching mechanism for performance improvements and made the system playable by limiting planning time - e.g. you limit computer search time to 3 seconds max - an irrational opponent may cause your agent's performance to degrade to the point where it too starts to make mistakes. Whether or not this is enough for a smart opponent to take advantage of it and beat an agent which is capable of otherwise playing a "perfect" game depends on details of the game, and how narrow the agent's measure of "perfect" is.
An extreme case might be an agent that has memorised a single perfect game (by scoring high heuristics for any state on a single tarjectory through the game that has been pre-calculated for perfect moves by both players), and has poor heuristics otherwise - once state moves away from what it can evaluate directly, the agent will be limited by how well it can search for completed game wins, and can easily be manipulated by a more generally smart opponent into a losing position that is beyond the depth of its search.
In practice, well-coded agents will not suffer too much from this effect. If you make a mistake, or try a random probably bad move in an attempt to confuse the agent when playing against Stockfish, you will lose.
