An Elegant Negamax With Alpha-Beta Pruning in Clojure
I’ve been reading up on Negamax with Alpha-Beta Pruning and I need to write the following pseudocode in Clojure.
At first I was struggling because I needed to figure out a way to modify a
variable and then break a loop. The code was starting to get ugly and I knew I
was on the wrong course. I realized I need to write it the way someone who
knows clojure would code it. I thought, “What function has short circuiting?”
and I came up with
take-while. That returns a list, but the pseudocode was
just returning a number. I started thinking about what the assignment was
doing and realized that it was just an artifact of the imperative language as
it was trying to find the max value of it’s children. This meant that once I
have the list, I just need to find the max and I’m done. The resulting clojure
code looks like this.
Let’s step through the code.
evaluate-leaf returns a value for the current node. If there is a
node-value, that means it’s a leaf-node (or terminal node if you use the
terminology of the pseudocode) and we can return a value.
In the else clause
- We start with the current node,
- then we get all its children ending up with a list of child nodes.
- We map the negamax function on each of the child nodes in the list. At this
point you may ask, “Doesn’t this defeat the purpose of alpha-beta pruning
because you’re not cutting off the calculation when you find it necessary?”.
The answer is that
mapreturns a lazy sequence, so the elements are not executing the recursion yet.
take-whilewill fetch each element as long as the condition holds. This is when the lazy sequence is realized (i.e. actually gets executed). When this is done, you’ll end up with a list of values.
(cons alpha)adds the alpha value that was passed in because in the pseudocode, we needed to have an initial value when calculating the max.
maxfunction on this list and we’re done.
Note The return value needs to have the sign set by the color in the initial call, i.e.
Note The flaw in this code is that it is not updating the alpha after
checking each child. It does get set when the cousins are calculated. This
means I will need to write a new function that combines the
Just for the record, the clojure code ended up being one line less than the pseudocode.
As a side note, we see
->>. That is just a macro to reduce embedded
parentheses. For example, these two statements are identical.
There is also
-> that works the same way but puts the previous form at the
beginning instead of the end of the argument list. So in this case, these two
statements are equivalent.
Back to the code.