README
¶
bitboard
This library aims to implement a flexible system for storing state in games played on 8×8 grids. It does not implement game mechanics.
Bitboards
Bitboards are bitmaps representing the positions of a certain type of piece (player/piece combination) on a game board. They are a compact way to store state in games like chess, checkers, and Reversi.
For example, we could use the following bitboard to represent the positions of White's pawns after White opens with 1. e4.
8 | 0 0 0 0 0 0 0 0
7 | 0 0 0 0 0 0 0 0
6 | 0 0 0 0 0 0 0 0
5 | 0 0 0 0 0 0 0 0
4 | 0 0 0 0 1 0 0 0
3 | 0 0 0 0 0 0 0 0
2 | 1 1 1 1 0 1 1 1
1 | 0 0 0 0 0 0 0 0
---------------
a b c d e f g h
Because an 8×8 grid has 64 squares, we can represent all the positions of a particular type using a single 64-bit integer. Of course, we can also represent smaller boards using the same technique.
For more information on bitboards, check out the Chess Programming Wiki.
Example
package main
import "github.com/benwebber/bitboard"
func main() {
b := bitboard.NewChessBoard()
b.PrettyPrint()
}
Documentation
¶
Overview ¶
Package bitboard implements 8x8 bitboards for games like chess, checkers, Reversi, and Othello.
Utility functions for the bitboard library.
Index ¶
- func AlgebraicToBit(p string, files int) int
- func AlgebraicToCartesian(p string, files int) (int, int)
- func BitToAlgebraic(p int, files int) string
- func BitToCartesian(p int, files int) (int, int)
- func CartesianToAlgebraic(x int, y int, files int) string
- func CartesianToBit(x int, y int, files int) int
- func ClearBit(i *uint64, p int)
- func FlipDiagonalA1H8(i uint64) uint64
- func FlipDiagonalA8H1(i uint64) uint64
- func FlipHorizontal(i uint64) uint64
- func FlipVertical(i uint64) uint64
- func GetBit(i *uint64, p int) int
- func IsBitSet(i uint64, p int) bool
- func PopCount(i uint64) int
- func Rotate180(i uint64) uint64
- func Rotate270(i uint64) uint64
- func Rotate90(i uint64) uint64
- func SetBit(i *uint64, p int)
- func ToggleBit(i *uint64, p int)
- func Union(i ...uint64) uint64
- type Bitboard
- func (b *Bitboard) AlgebraicToBit(p string) int
- func (b *Bitboard) AlgebraicToCartesian(p string) (int, int)
- func (b *Bitboard) BitToAlgebraic(p int) string
- func (b *Bitboard) BitToCartesian(p int) (int, int)
- func (b *Bitboard) CartesianToAlgebraic(x int, y int) string
- func (b *Bitboard) CartesianToBit(x int, y int) int
- func (b *Bitboard) GetBitmapIndex(p int) int
- func (b *Bitboard) MovePieceAlgebraic(m int, p1 string, p2 string)
- func (b *Bitboard) MovePieceBit(m int, p1 int, p2 int)
- func (b *Bitboard) MovePieceCartesian(m int, x1 int, y1 int, x2 int, y2 int)
- func (b *Bitboard) PlacePieceAlgebraic(m int, p string)
- func (b *Bitboard) PlacePieceBit(m int, p int)
- func (b *Bitboard) PlacePieceCartesian(m int, x int, y int)
- func (b *Bitboard) PrettyPrint()
- func (b *Bitboard) RemovePieceAlgebraic(m int, p string)
- func (b *Bitboard) RemovePieceBit(m int, p int)
- func (b *Bitboard) RemovePieceCartesian(m int, x int, y int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AlgebraicToBit ¶
Convert coordinates in algebraic notation to an integer bit position.
func AlgebraicToCartesian ¶
Convert coordinates in algebraic notation to Cartesian coordinates.
func BitToAlgebraic ¶
Convert an integer bit position to coordiantes in algebraic notation.
func BitToCartesian ¶
Convert an integer bit position to Cartesian coordinates.
func CartesianToAlgebraic ¶
Convert Cartesian coordinates to coordinates in algebraic notation.
func CartesianToBit ¶
Convert Cartesian coordinates to an integer bit position.
func FlipDiagonalA1H8 ¶
Flip a bitboard about the diagonal A1-H8.
func FlipDiagonalA8H1 ¶
func FlipHorizontal ¶
Flip a bitboard horizontally about the centre files.
func FlipVertical ¶
Flip a bitboard vertically about the centre ranks.
func PopCount ¶
PopCount calculates the population count (Hamming weight) of an integer using a divide-and-conquer approach.
See <http://en.wikipedia.org/wiki/Hamming_weight> for a complete description of this implementation.
Types ¶
type Bitboard ¶
type Bitboard struct {
Bitmaps []uint64 // Bitmaps for each colour/piece combination
Symbols []string // Symbols representing each colour/piece combination
Occupied uint64 // Union of all bitmaps (occupied squares)
Ranks int // Number of rows
Files int // Number of columns
}
A Bitboard represents game state.
We use a little-endian mapping of bits to rank-and-file coordinates. For an 8x8 board, this mapping looks like:
8 | 56 57 58 59 60 61 62 63
7 | 48 49 50 51 52 53 54 55
6 | 40 41 42 43 44 45 46 47
5 | 32 33 34 35 36 37 38 39
4 | 24 25 26 27 28 29 30 31
3 | 16 17 18 19 20 21 22 23
2 | 8 9 10 11 12 13 14 15
1 | 0 1 2 3 4 5 6 7
-------------------------
a b c d e f g h
Coordinates ¶
We will define three sets of coordinates for interacting with the Bitboard:
- bit positions
- alegraic notation
- Cartesian (x, y) coordinates
For example, the following positions are equivalent on an 8x8 board:
| Bit | Algebraic | Cartesian | |-----|-----------|-----------| | 0 | a1 | (0, 0) | | 22 | g3 | (6, 2) | | 28 | e4 | (4, 4) | | 35 | d5 | (3, 4) |
Construct a new Bitboard using New. There are also convenience functions for constructing bitboards for specific games.
func NewCheckersBoard ¶
func NewCheckersBoard() *Bitboard
NewCheckersBoard is a convenience function for constructing a new checkers (English draughts) board.
func NewChessBoard ¶
func NewChessBoard() *Bitboard
NewChessBoard is a convenience function for constructing a new chess board.
func NewConnectFourBoard ¶
func NewConnectFourBoard() *Bitboard
NewConnectFourBoard is a convenience function for constructing a new Connect Four board.
func NewOthelloBoard ¶
func NewOthelloBoard() *Bitboard
NewOthelloBoard is a convenience function for constructing a new Othello board.
Othello differs from Reversi only in starting position.
func NewReversiBoard ¶
func NewReversiBoard() *Bitboard
NewReversiBoard is a convenience function for constructing a new Reversi board.
func NewTicTacToeBoard ¶
func NewTicTacToeBoard() *Bitboard
NewTicTacToeBoard is a convenience function for constructing a new Tic-Tac-Toe board.
func (*Bitboard) AlgebraicToBit ¶
Convert coordinates in algebraic notation to an integer bit position. Wrap AlgebraicToBit to automatically pass in number of files.
func (*Bitboard) AlgebraicToCartesian ¶
Convert coordinates in algebraic notiton to Cartesian coordinates. Wrap AlgebraicToCartesian to automatically pass in number of files.
func (*Bitboard) BitToAlgebraic ¶
Convert an integer bit position to coordiantes in algebraic notation. Wrap BitToAlgebraic to automatically pass in number of files.
func (*Bitboard) BitToCartesian ¶
Convert an integer bit position to Cartesian coordinates. Wrap BitToCartesian to automatically pass in number of files.
func (*Bitboard) CartesianToAlgebraic ¶
Convert Cartesian coordinates to coordinates in algebraic notation. Wrap CartesianToAlgebraic to automatically pass in number of files.
func (*Bitboard) CartesianToBit ¶
Convert Cartesian coordinates to an integer bit position. Wrap CartesianToBit to automatically pass in number of files.
func (*Bitboard) GetBitmapIndex ¶
GetBitmapIndex returns the array index of the bitmap including a particular square.
func (*Bitboard) MovePieceAlgebraic ¶
Move a piece from algebraic position p1 to p2.
func (*Bitboard) MovePieceBit ¶
Move a piece from bit position p1 to p2.
func (*Bitboard) MovePieceCartesian ¶
Move a piece using Cartesian coordinates.
func (*Bitboard) PlacePieceAlgebraic ¶
Place the piece at algebraic coordinate p.
func (*Bitboard) PlacePieceBit ¶
Place the piece at bit position p.
func (*Bitboard) PlacePieceCartesian ¶
Place the piece at Cartesian coordinates (x, y).
func (*Bitboard) PrettyPrint ¶
func (b *Bitboard) PrettyPrint()
PrettyPrint pretty-prints a Bitboard using the symbols for each colour/piece combination. Empty squares are represented by periods.
func (*Bitboard) RemovePieceAlgebraic ¶
Remove the piece at algebraic coordinate p.
func (*Bitboard) RemovePieceBit ¶
Remove the piece at bit position p.
Source Files