Attempting to test drive minimax

One of the reason I struggle with minimax is that it’s a difficult to test drive.
I like to first do the smallest thing possible that would get me started and make me feel like I’m doing something of value.

I outlined a rough idea of what I want from the minimax algorithm. The first simplest thing to test is the scoring of a final board game state.
10 for a win, -10 for a lost and 0 for a draw.

(describe "final-score"
(it "scores 10 for a winning move"
(should= 10 (score winning-board "X")))
(it "scores 0 for a draw game"
(should= 0 (score drawn-board "X")))
(it "scores -10 for a lost game for player X"
(should= -10 (score lost-board "X"))))

The second part is to have a test that will force to generate possible game states. I’ve achieved that by scoring an incomplete game. This means that the inter-score function needs to make potential moves on a board to get the board into a final state which it can score.

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

A simple board to test is a board with only one move remaining, this involves no loop and we should return only one possible board from this.

["X" "X" "X"
"O" "O" "X"
"X" "O" "O"])

So the inter-score will return a 10 as the next possible move will always be a win.

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

We assume that the opponent will pick the best move to win, so this will mean player “X” will lose

Final board

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

The game is over so the inter-score, scores the final game state from player “X” perspective, returning -10.

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

(describe "scores possible move"
(it "scores incomplete winning board"
(should= 10 (inter-score possible-winning-board "X")))
(it "scores incomplete losing board"
(should= -10 (inter-score possible-losing-board "X")))

;currently failing
(it "scores incomplete drawn board"
(should= 0 (inter-score possible-drawn-board "X"))))
(defn score-multiple [boards mark]
(score (first boards) mark))

(defn current-mark [moves-left]
(if(even? (count moves-left))
"O"
"X"))

(defn generate-possible-boards [board mark]
(let [open-spots (board-logic/remaining-moves board)]
(for [open-spot open-spots]
(board-logic/make-move board open-spot mark))))

(defn inter-score [board mark]
(if (board-logic/game-over? board)
(score board mark)
(score-multiple (generate-possible-boards board mark) mark)))

To get the currently failing state to pass I imagine I will have to have a loop and a way to switch players, so that a full game is played. Then I can score that completed game.

To be continue

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