Programming…..It’s been a while.

My first day back to work, I delved back into the unbeatable tic tac toe computer player in my Clojure implementation.

Having taking a step back from the code, I’ve noticed a few interesting elements about my old implmentation of the minimax algorithm.

The first unnessary complexity that came apparent to me was the amount of small helper methods that existed solely to unpack a complex sequence type data structure.

Two scoring methods, one for the final game state and another used for unfinished game state. Removing the intermediate scoring simplflefy the code.

Finally there was a method that generated multiple game states. Moving the logic under the minimax method reduce some confusion. While the code wasn’t doing what I wanted just yet, but at least I was now in a state to move forward.

I knew I wanted a loop of some type, and every loop needs a terminating condition. So what would be the terminating condition for the minimax.

Well first we have to decide what is it that we ultimately want…

We want the best move that will lead the current player to Victory! Or the very least a draw but never a defeat.

Scoring each possible move and it’s pemutation will allow us to then pick the move with the highest scoring. Which means we need to build a score collection and a move collection. Scoring is done once a game state is over. Now we know our terminating condition

(game-over? board)
(score board)

Should look like something like above.

Now we need to build our moves with their associate scores. We can retrieve our remaining moves which is relatively straightforward. The trickier part is getting the scoring of each of move and the permutation. Not only that but we have to assume that the opponent will also play their best move.

What I don’t know how to clearly do in Clojure is to get the opponent’s best move.

(def board
["X" "X" "-"
"O" "O" "-"
"X" "O" "-"])

{2 99, 5 {2 {8 0}, 8 {2 97}}, 8 {2 {5 0}, 5 98}}

From above, we can see that the collection is returning move 2 as the best move with a score of 99. The tricky part is how to extract the highest scored move from this nested collection.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s