Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How should I represent a chess bitboard in clojure?

What are some of the possible ways of representing a chess bitboard in Clojure (/Java)?

http://pages.cs.wisc.edu/~psilord/blog/data/chess-pages/rep.html

I need to be able to access individual bits and also perform bitwise operations.

I thought of using java.lang.Long but this causes issues with 1x10^63 because of the signage. I'm also not sure how I would access bits at a specific index?

I also looked at BitSet, but I need a fixed length ideally.

like image 322
DanS Avatar asked Apr 27 '12 08:04

DanS


2 Answers

There's no reason you can't use a straight long. The problem, as you've noted, is that java's (and therefore clojure's) long is signed, allowing only 63 bits for positive numbers

Java, by default, allows arithmetic overflow without error. Clojure, by default, doesn't allow arithmetic overflow without error (see *unchecked-math* flag). It adds extra checking around arithmetic operations and casts, so, for instance, (byte 128) will cause an exception. Since clojure v1.3.0 there are functions like (unchecked-byte) which is equivalent to the java functionality....

(unchecked-byte 128)
;=> -128 ; 2s-complement of 10000000
(unchecked-byte 2r10000001)
;=> -127 ; 2s-complement of 10000001

There are a whole raft of unchecked-* operations available (see clojuredocs).

If you use a straight long and the unchecked-* operations you are mostly there, and then you can use the bit-* operations to twiddle/check bits.

Finally storing your chessboard in an atom makes sense, and you then update it with (swap! chessboard fn args)

(updated 15/02/13 with slightly more idiomatic swap! calls)

e.g.

(inc Long/MAX_VALUE) ; java.lang.ArithmeticException

(unchecked-inc Long/MAX_VALUE) ; wraps.
-9223372036854775808

(def chessboard (atom 0))
@chessboard
;=> 0
(bit-test @chessboard 1)
;=> false
(swap! chessboard bit-flip 1)
;=> 2
(bit-test @chessboard 1)
;=> true
@chessboard
;=> 2
(reset! chessboard 0)
;=> 0
(swap! chessboard bit-flip 63)
;=> -9223372036854775808 
(bit-test @chessboard 63)
;=> true 
like image 86
sw1nn Avatar answered Nov 03 '22 02:11

sw1nn


=> (def chessboard (byte-array 8))
#'user/chessboard

=> (vec chessboard)
[0 0 0 0 0 0 0 0]

=> (for [row (range 8)] (aset-byte chessboard row (rand-int 8)))
(3 0 6 6 2 3 6 7)

=> (bigint chessboard)
216179404987106823N

=> (defn bigint-to-array
 [bi]
 (.toByteArray (biginteger bi)))

=> (vec (bigint-to-array 216179404987106823N))
[3 0 6 6 2 3 6 7]

Clojure supports most functions you need this way. Like all clojure numbers, clojure.lang.BigInt supports binary operations (bit-and etc.). On a byte-array you can use all methods from java.util.Arrays (search, fill, sort).

Take care that the bigint fn coerces to clojure.lang.BigInt, and the biginteger fn coerces to a java.math.BigInteger. If you want to use the methods of java.math.BigInteger, you need to coerce your bigint or byte-array through biginteger.

like image 28
NielsK Avatar answered Nov 03 '22 02:11

NielsK