Monday 14 April 2014

Game logic

During a job interview a few years ago I was asked how I would go about implementing a simple game of noughts and crosses.

I was fine with defining the objects, but when it came to the logic for determining when someone had won I found myself overthinking the situation, considering pre-loading the system with won states and using some kind of map lookup, or navigating the game state with some kind of tree of neighbouring cells based on the last move and following a backtracking algorithm.

In the case of Noughts and crosses there are only 8 possible winning combinations per player, with each combination involving checking the state of 3 positions on the playing grid.

A brute force approach would be to check every possibility until finding a win or running out of possibilities.

A more elegant solution would only consider the combinations that involve the most recently played move. This would introduce a requirement of being able to determine which winning states are related to the new move's grid position.

* Footnote: The interview was so long ago that I don't recall the company - or the interview.  I found this post awaiting publication so have updated the wording accordingly.

No comments:

Post a Comment