HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Connect Four: Bitboard checking algorithm

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
connectcheckingfouralgorithmbitboard

Problem

I'm rather new to Clojure and so I decided to program a Connect Four for fun and learning.

The code below is a Clojure implementation of this bitboard algorithm.

The whole code can be found here: https://gist.github.com/3639220

What I'm unsure about are the functions (insert) and (bit-check-board):

(defn insert
  "Inserts symbol for given player (either 1 or 2) at specified x and
   calls bit-insert for corresponding bitboard."
  [boards x player-num]
  (let [y (get-y (boards 0) x)]
    (if (= player-num 1) ; TODO: improve
      (vector
       (assoc-in (boards 0) [y x] (player player-num))
       (bit-insert (boards 1) (- 5 y) x)
       (boards 2))
      (vector
       (assoc-in (boards 0) [y x] (player player-num))
       (boards 1)
       (bit-insert (boards 2) (- 5 y) x)))))

(defn bit-check-board ; TODO: improve
  "Checks whether given bitboard is a win."
  [bitboard]
  (let [diag1 (bit-and bitboard (bit-shift-right bitboard 6))
        hori  (bit-and bitboard (bit-shift-right bitboard 7))
        diag2 (bit-and bitboard (bit-shift-right bitboard 8))
        vert  (bit-and bitboard (bit-shift-right bitboard 1))]
    (bit-or (bit-and diag1 (bit-shift-right diag1 (* 2 6)))
            (bit-and hori  (bit-shift-right hori  (* 2 7)))
            (bit-and diag2 (bit-shift-right diag2 (* 2 8)))
            (bit-and vert  (bit-shift-right vert  (* 2 1))))))


  • insert: Is there a better way to somehow make function calls depend on some test?



  • bit-check-board: A lot of similar lines where just one number (and one variable name) is different.

Solution

The bit-check-board can be indeed improved. This is what I got by just joining together common parts, even though I guess it could be further improved:

(defn check [c x]
  (bit-and c (bit-shift-right c x)))

(defn bit-check-board
  "Checks whether given bitboard is a win."
  [bitboard]
  (let [positions [6 7 8 1]
        coords (mapv (partial check bitboard) positions)]
    (apply bit-or (map check coords (map #(* 2 %) positions)))))


Also, you can reduce the repetition in the insert function by better modularize the code and use higher order functions with a pre-calculated transformation table:

(defn insert* [board x y]
  (bit-insert board (- 5 y) x))

(defn get-transforms [num]
  (if (= 1 num)
    [identity insert* identity]
    [identity identity insert*]))

(defn insert
  "Inserts symbol for given player (either 1 or 2) at specified x and
   calls bit-insert for corresponding bitboard."
  [boards x player-num]
  (let [y (get-y (boards 0) x)
        board0 (assoc-in (boards 0) [y x] (player player-num))
        transfv (get-transforms player-num)]
    (mapv [board0 (boards 1) (boards 2)] transv)))


If you're on Clojure < 1.4 than you have to change (mapv ...) in (vector (map ...))

Code Snippets

(defn check [c x]
  (bit-and c (bit-shift-right c x)))

(defn bit-check-board
  "Checks whether given bitboard is a win."
  [bitboard]
  (let [positions [6 7 8 1]
        coords (mapv (partial check bitboard) positions)]
    (apply bit-or (map check coords (map #(* 2 %) positions)))))
(defn insert* [board x y]
  (bit-insert board (- 5 y) x))

(defn get-transforms [num]
  (if (= 1 num)
    [identity insert* identity]
    [identity identity insert*]))

(defn insert
  "Inserts symbol for given player (either 1 or 2) at specified x and
   calls bit-insert for corresponding bitboard."
  [boards x player-num]
  (let [y (get-y (boards 0) x)
        board0 (assoc-in (boards 0) [y x] (player player-num))
        transfv (get-transforms player-num)]
    (mapv [board0 (boards 1) (boards 2)] transv)))

Context

StackExchange Code Review Q#15378, answer score: 2

Revisions (0)

No revisions yet.