Minimax AI

[ghost]

The AI should be completely redesigned to use the minimax algorithm, via a game simulator, this will be the final goal of the AI subsystem.

[ghost]

Implementing this, requires implementing several subparts:

• The AI itself, which will call the Lua API in order to generate a game plan. This can also be implemented in the form of an AI generator, which will be the case in the minimax approach, where we'll generate all possible AI moves, rather than some priority based static one.
• The Game Simulator, which will replace all the Lua API functions with its own, such that no calls are actually made to the game, but rather to the simulator, which will act exactly as the game would. I.e. when dropping a minion, this has to be reflected by the corresponding getcards call. (Chances will be handled with multiple simulation outputs).
• The plan generator, which will hook all game changing Lua API functions, and make an action list from calls to them. Such that we can record, a game plan, from an AI. This will be used in conjunction with the Game Simulator.
• The plan executor, which will take a game plan in, and execute it, in a humanlike way. With delays, mousing over minions alike.
• The simulator verifier, which will compare the actual output game state, after running a plan, with the simulators expected output, and log any differences for correction of the simulator.
• The board evaluator, which will take in a board configuration, and return its greatness (value), such that different game plans can be compared against each other. This will be required to implement the minimax approach. Evaluating a boards greatness will be the real task here, and will be heuristic.

[ghost]

The simulator will likely need to have card specific code and information, to get the simulation correct. Having the simulator will also allow the AI API to support reverting operations, which may help implementing some features.

The board evaluator will be based upon external configuration variable, which can be set by user, or via evolutionary algorithms. (The last approach may take quite some time).

[felixhao28]

I don't think so.

Minimax algorithm bases on expectations on opponents' move. You need to first calculate probabilities of the decks they may be using and then calculate probabilities of the cards they may be holding. Such calculation is exponential. In addition, the search depth of minimax represents the turns yet to come. You have to calculate the probability of every top-decks.

[jamesford42]

I think Minimax would be performed on all possible actions available to be done for you, on a SINGLE TURN. Eg, to answer the question : how do i spend my x mana crystals most efficiently this turn / what is the best order to play my current cards in. Looking any farther ahead than the current turn is, as you said, exponentially more complicated.

[felixhao28]

@jamesford42 If we just want to optimize the current turn's play, Minimax is not needed. A slightly pruned DFS (or even a DP algorithm) can deal with that efficiently. Minimax is powerful because it evaluates the opponent's possible counter plays (and your response to that and so on). If we only consider the current turn, then we are talking about the same thing: not using Minimax. However it is possible to mimic Minimax behaviors by manually maintaining a "play-around card list", including most AOE spells and popular tech cards, and by using bigger cards first to reserve small cards as "fillers" to be used later (e.g. a six-drop is usually better than a five-drop and a one-drop on turn six).