EntelectChallenge/2014-PacMan-TestHarness — pull request #18 by bhaeussermann (2014-06-24 19:59:07+00:00)
Title: Perft values

Added project to generate Perft-values based on the rules implemented in the test harness. The intent is to help validate that the rules are implemented correctly (and stay that way with any future changes).
See http://phpbb-entelect100k.rhcloud.com/viewtopic.php?f=2&t=27

The new console application probes exactly which moves are allowed by the test harness starting at the initial board up to 20 turns into the game. It does this by closely emulating the Run() method of the Game class by using the same helper-methods of the helper-classes. If the application runs to completion without errors, then all Perft values up to 20 turns are correct. Otherwise, if an error in the rules is detected, the application will terminate with an error stating the computed and expected Perft values.

The development of the Perft-generator helped identify two bugs that were previously not known. This illustrates that the technique is effective.
The fixes to these bugs are included in this change-set, namely:
- MazeValidator.GetPossibleMoves(): The code allowed the players to eat each other in the respawn zone (Perft value for depth 6 was computed as 2304 instead of 2296).
- TurnMarshaller.ProcessMove(): It is possible that a player drops a pill and eats the opponent's pill all in the same turn. TurnMarshaller did not take this possibility into account. The effect of this was that the player would still have a poison pill left, even though a poison pill was dropped (this bug was exposed when the Perft value for depth 12 came out as 1357411 instead of 1357407; the player still had a poison pill after exiting the respawn zone, and hence more possible moves).

Perft-value generation becomes exponentially slow with increasing depths (and this program is slow mainly because the board is copied at every level of recursion). I have managed to compute and verify Perft values up to depth 14 at this stage. Currently investigating techniques to speed up the computation.