To do

TODO Rewrite to use integers instead of bitvectors

It seems I have not chosen the best way to represent the bits of a bitboard. It seems that bitwise operations are only defined on integers, not on bitvectors, as I initially thought. There is a noticable speed difference between my implementation with bitvectors and a possible implementation with integers and bitwise operations. This can be shown as follows:


(use-modules (srfi srfi-19))

(define-syntax time
  (syntax-rules ()
    [(time expr expr* ...)
     (begin
       (define start-time (current-time time-monotonic))
       expr
       expr* ...
       (define end-time (current-time time-monotonic))
       (let* ([diff (time-difference end-time start-time)]
              [elapsed-ns (+ (/ (time-nanosecond diff) 1e9)
                             (time-second diff))])
         (display (format #t "~fs~%" elapsed-ns))))]))


(define (binary-bit-vector-operation bv1 bv2 proc)
  (define (iter bit-list1 bit-list2)
    (cond [(or (null? bit-list1) (null? bit-list2)) '()]
          [else (cons (proc (car bit-list1)
                            (car bit-list2))
                      (iter (cdr bit-list1)
                            (cdr bit-list2)))]))
  (list->bitvector
   (iter (bitvector->list bv1)
         (bitvector->list bv2))))


(time
 (let ([bv1 #*10101010]
       [bv2 #*01010101])
   (do ([i 1 (+ i 1)])
       ([> i 1000000])
     (binary-bit-vector-operation
      bv1
      bv2
      (lambda (b1 b2)
        (and b1 b2))))))

1.308778s
#t


(use-modules (srfi srfi-19))

(define-syntax time
  (syntax-rules ()
    [(time expr expr* ...)
     (begin
       (define start-time (current-time time-monotonic))
       expr
       expr* ...
       (define end-time (current-time time-monotonic))
       (let* ([diff (time-difference end-time start-time)]
              [elapsed-ns (+ (/ (time-nanosecond diff) 1e9)
                             (time-second diff))])
         (display (format #t "~fs~%" elapsed-ns))))]))


(time
 (let ([int1 #b10101010]
       [int2 #b01010101])
   (do ([i 1 (+ i 1)])
       ([> i 1000000])
     (logand int1 int2))))

0.004594s
#t

While my implementation using bitvectors is simpler for arbitrary procedures on bitboards, there might be a need to rewrite the bit board code to use integers in the future. Other bit board implementations seem to use integers to represent the bits, so maybe for most use cases one does not need more complex operations. Implementing more complex operations in Guile itself might again lead to a slowdown.

On such a rewrite, one consideration would be which bitwise operations library to use. There are the following options:

Here are some notes on equivalent operations for operations on bitvectors, when using integers to represent the bits of a bit board:

AND: ???
OR: ???
NOT: ???
XOR: addition and discarding the leading bit or overflowing bit

Implementation ideas

Here will ideas for an implementation using integers be collected.

Value of a single bit

I could simply use logical and operation to and the integer with 2^n where n is the number or id of the square on the chess board.

Checking for any bit being 1

Simply check whether the number is greater than 0.

Checking for all bits being 1

Is the number equal to 2^63 - 1?

Checking for all bits being 0

Is the number equal to 0?

Valid number Check

Check whether the number is positive.
Check whether the number is less than or equal to 2^n where n is the number of squares in the bit

Keeping more general operations availble

One can use logical and to get the value of single bits at the same position and then use logical operations on those to implement general procedures. The operation can still be an argument to make a higher order, more generic procedure. Instead of iterating through a bit vector, one can iterate through the bits of an integer this way.

Position	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
Value	128	64	32	16	8	4	2	1
Integer 1	0	0	1	1	0	1	1	0
Integer 2	0	1	1	0	1	1	1	0
Operation	AND	AND	AND	AND	AND	AND	AND	AND
Result	0	0	1	0	0	1	1	0
Result value	0*128	0*64	1*32	0*16	0*8	1*4	1*2	0*1

Then one can simply return the resulting integer, if the rest of the code has the proper abstractions.

Timing after refactoring to integer usage

Timings show, that the code using integers instead of bitvectors is slower for generic operations, but is faster for the primitive operations and, or and such:


(use-modules
 ;; SRFI 19: monotonic timing
 (srfi srfi-19)
 ;; SRFI 60: procedures for treating integers as bits
 (srfi srfi-60))

(define-syntax time
  (syntax-rules ()
    [(time expr expr* ...)
     (begin
       (define start-time (current-time time-monotonic))
       expr
       expr* ...
       (define end-time (current-time time-monotonic))
       (let* ([diff (time-difference end-time start-time)]
              [elapsed-ns (+ (/ (time-nanosecond diff) 1e9)
                             (time-second diff))])
         (display (format #f "~fs~%" elapsed-ns))))]))

(define-public val-of-bit-pos
  (λ (bit-pos)
    (expt 2 bit-pos)))

(define-public bit-mask-of-pos
  (λ (pos)
    (val-of-bit-pos pos)))

(define-public get-bit-value-at-pos
  (λ (int pos)
    "This procedure interprets 1 as true and 0 as false."
    (if (= (bitwise-and int (bit-mask-of-pos pos)) 0)
        0
        1)))

(define-public generic-binary-bit-integer-operation
  (λ (int1 int2 proc)
    (let ([max-len (max (integer-length int1) (integer-length int2))])
      (let iter ([pos 0] [result 0])
        (cond
         [(< pos max-len)
          ;; We can AND the integers with a bit mask, which only has a 1 at the position, which we
          ;; are interested in. If the bit of the integer at the position we are interested in is a
          ;; 1, then the AND operation will return an integer not equal 0. Otherwise, if the bit in
          ;; the integer is 0 instead, the AND operation will return 0 as well, because no other
          ;; bits are 1 in both the integer and the bit mask.
          (let ([bit1 (get-bit-value-at-pos int1 pos)]
                [bit2 (get-bit-value-at-pos int2 pos)])
            (iter (+ pos 1)
                  (proc result pos bit1 bit2)))]
         [else result])))))

(define example-reimplement-bitwise-and
  (λ (prev-res pos bit1 bit2)
    (+ prev-res
       (* (if (= (+ bit1 bit2) 2)
              1
              0)
          (val-of-bit-pos pos)))))

(time
 (let ([int1 #b10101010]
       [int2 #b01010101])
   (do ([i 1 (+ i 1)])
       ([> i 1000000])
     (generic-binary-bit-integer-operation
      int1
      int2
      example-reimplement-bitwise-and))))

(time
 (let ([int1 #b10101010]
       [int2 #b01010101])
   (do ([i 1 (+ i 1)])
       ([> i 1000000])
     (logand int1 int2))))

4.375609s
0.004535s

Since usage of the generic procedure is probably not likely or only needed in few cases when dealing with bit board logic, I intend to implement the bit board logic in terms of integers.

todo.org 8.0 KB History Raw