lucidtaz/minimax

MiniMax engine for game decision making

minimax's Issues

Parameter interface strictness

The Decision interface prescribes an apply method receiving a GameState parameter, which is itself also an interface. This makes sense from an interface standpoint, but it constrains an implementer that applies strict static analysis.

The reason is that a concrete MyDecision wants a concrete MyGameState as a parameter, in order to actually do something useful such as filling a field on the board. However, since the interface prescribes a GameState parameter, this is not possible without agitating static analysis tools. (Such as phpstan with a high enough strictness level.)

Conceptually this could be solved by templating in languages that support it. In PHP however we need to look to other solutions. Perhaps a concrete Decision can already take its original concrete GameState via the constructor so that the interface does not need to know about it? Since Decisions are constructed by concrete GameStates, this keeps all concreteness at the implementer's side.

Cyclic dependency between GameState and Decision

Currently GameState knows about Decision and vice versa. This is not really good design and should be eliminated. When solved, it will make the program easier to reason about. Also, it doesn't force a bad practice onto interface implementers.

GameState's knowledge lies in GameState::getDecisions(): Decision[] and Decision's knowledge lies in Decision::apply(GameState): GameState.

One possible solution is to move apply from Decision to GameState. It could also help to think about extracting a Board class from GameState and making only that known to Decision. However, care should be taken to keep the interface as simple as needed.

Create build matrix with different dependency versions

See tip number 7 on https://blog.martinhujer.cz/17-tips-for-using-composer-efficiently/

Optimization

There are at least three logical optimizations possible, which should be implemented in order to 1) search a broader space (more game support), or 2) be able to search deeper (harder difficulty).

The optimizations are:

• Alpha/beta pruning. Stop evaluating hopeless subtrees.
• Remember/cache the decision subtrees to re-use them when deciding a next move. It's probably best to let the GameState decide on a cache key, and offer a caching interface to the implementer. As long as the cache is isolated per Engine object, the cache should be usable like that. A global cache would need some additional work for the cache key, since a GameState may be evaluated from multiple player's perspectives.
• Eliminate symmetry, for example in Reversi the start state has four options but they are all equivalent because of the symmetrical start layout.

Extract Board class

The code could become a lot cleaner by extracting a Board class from the TicTacToe example GameState class. The example will be easier to understand, and it might even have a positive impact on the tests readability.