Josh Hayden: Added the evaluation methods and made the NoOpponentCornersPlayer. This method worked best out of all the ones I tested. It beat spacesControlled as well as weighting corners and edges or just corners every time. Minimax using this evaluation method, with a depth of 2, beat random 80% of the time.
Tim Marotta: Added the MinimaxTranspositionPlayer. This transposition table takes more time than a regular minimax on a 4x4 board each set to look ahead to depth at 4, but always wins against a regular minimax agent. Against a random agent, transposition table minimax wins 90% of the time.
Tea Mdevadze: Added the AlphaBetaPruning. AlphaBetaPruning is version of Minimax that is more efficient. It was tested on 8x8 board it takes almost 10 times less than regular minimax. It wins over random and greedy agents, it wins as many games as minimax when compared to it.
John Hunter: Pair programmed with Tim on the Transposition Table. Also implemented the MinimaxRandomPlayer, which is a mix of the RandomPlayer and the standard MinimaxPlayer. The randomness of this agent disrupts the plans of deterministic minimax agents who expect their oppoenent to make optimal moves. This player has been demonstrated to reduce time significantly, which would be especially helpful in time-bank gameplay. Currently the improvement of gameplay is uncomfirmed do to issues with the compare_players function. A possible improvement for this agent is a quiescence hueristic, which could help the agent choose when to make a random move at the least risky times.
Addition vs Base Minimax Analysis: To see for sure which additions actually improved our agent we ran them all against the base Minimax algorithm for 100 games. For all of the additions besides the MinimaxRandomPlayer we found that the agent tied with base Minimax, winning 50 games and losing 50 games, random lost slightly more, winning 42 games, tying 5, and losing 53. Of these algorithms, AB pruning and Minimax random were faster than the base Minimax, with AB pruning taking about .2 less seconds a game, nearly cutting the time to play a game in half. Transposition table took slightly longer than minimax, an extra .03 seconds per game, and the NoOpponentCornersPlayer took just under .1 extra seconds per game. From this we belive AB pruning is our most effective addition, as it is significantly faster while breaking even with our base Minimax.
CombinedPlayer Analysis: For our combined player we just used AB pruning with the NoOpponentCorners evaluation metric. We also added in the legendary "Sneaky Move", if no moves have been made our agent waits 3 seconds, forfeiting the turn. This means that our agent effectively always goes second, giving it a slight competitive advantage. We found that this combined agent beat all the other individual agents besides NoOpponentCorners. Our theory is that since CombinedPlayer is just NoOpponentCornersPlayer with more depth, perhaps CombinedPlayer's obsession with preventing the opponent from getting a corner might backfire and eventually lead to a loss. If not facing the exact same evaluation metric the CombinedPlayer method with depth 4 seems to be the most effective.