Implementing a Minimax Algorithm in Clojure - conditional function with multiple recursive calls

Question

This question and another question of mine sort of merged into one after I figured a few things out, so I revised this question.

What I'm trying to accomplish with my function is outlined below.

Iterate over all of the spots. If it's open, select the spot with the current player's symbol.
If this move causes the game to be won and it's the computer player's turn, add a key-value pair of the spot (an integer) and the score of the spot (an integer, 1 in this case) to the scored-spots hash-map.
Recurse and call this same function, passing it the new scored-spots hash-map, the board with the move just made removed, the same player, and the same symbol.
If however, the game has not been won, proceed to the next conditional statement and check that.
Proceed with the next conditional statements in the same way, just with different scores (a win with the computer's turn is 1, a win with the human's turn is -1, a tie is 0).
If none of the conditional statements evaluate to true, recurse anyway (the scored-spots hash-map won't be any different in this case).

Here's the code I tried, but this isn't returning the values I'm expecting.

Note:
board is a hash-map like this: {0 "0", 1 "1", 2 "2"} (spot location - spot value)
sym is a symbol, like "X" or "O"
current-player is a keyword, like :computer or :human
scored-spots is a hash-map like this: {}

(defn score-spots [board sym current-player scored-spots]
  (for [spot (keys board)]
    (if (some #(= % (.toString spot)) (filter #(not= "O" %) (filter #(not= "X" %) (vals board))))
      (let [board (assoc board spot sym)]
        (cond
          (and (game-won board) (= current-player :computer))
            (score-spots board sym current-player (assoc scored-spots spot 1))
          (and (game-won board) (= current-player :human))
            (score-spots board sym current-player (assoc scored-spots spot -1))
          (game-tied board)
            (score-spots board (switch-symbol sym) (switch-player current-player) (assoc scored-spots spot 0))
          :else
            (score-spots board (switch-symbol sym) (switch-player current-player) scored-spots)))
  scored-spots))))

What I'm expecting as a return value is a hash-map with each open spot scored. For example, {1 0, 4 1, 5 -1, 6 -1, 8 0}.

Instead, if I pass it this board:
{1 "X" 2 "X" 3 "O" 4 "4" 5 "5" 6 "6" 7 "7" 8 "X" 9 "O"},
I get a return value with a large list of hash-maps.

i was gonna suggest you can just hardcode it but then realized you mentioned it in your blog. lol — user789327
What about find the spots (if any) which can make X win in next turn and put O there as the first step? Also, personally I would try to code this using core.logic — Ankur

bostonou bostonou · Accepted Answer · 2012-11-13T18:25:53

I'm relatively new to Clojure and FP in general. Whenever I think about recursion, I always try to first think if it is an opportunity for map and/or reduce.

In this case, you're trying to score each spot. Each spot collected together is a board. So if I can score each spot and then collect them together, I can accomplish the task at hand. In reduce terms, I can do something to an item (the spot) in a collection, and then merge that value into a single value (the board - technically only the spots without "X" or "O" for the code below).

Here's my rewrite:

(defn score-spot [scored-spot current-player board]
  (let [[spot score] scored-spot]
    (cond
      (and (game-won board) (= current-player :computer)) {spot 1}
      (and (game-won board) (= current-player :human)) {spot -1} 
      (game-tied board)  {spot 0}
      :else {spot score})))

(defn score-board [board current-player]
  (let [spots-to-score (filter #(and (not= "X" (second %))
                                     (not= "O" (second %))) board)]
    (reduce #(into %1 (score-spot %2 current-player board)) {} spots-to-score)))

This would give your result of e.g. {1 0, 4 1, 5 -1, 6 -1, 8 0}

Edit:

Regarding the need to recur, you're basically wanting to use mutual recursion. For that, you can use declare to forward declare functions and then use trampoline (here's a quick tutorial) for the actual recursion.

Implementing a Minimax Algorithm in Clojure - conditional function with multiple recursive calls

1 Answers