M cmd/perft/main.go +1 -1
@@ 39,7 39,7 @@ func main() {
}
-var perftMoveListCache = [maxDepth]search.FifoMoveList{}
+var perftMoveListCache = [maxDepth]search.MoveList{}
func printPerftResults(p *pos.Position, depth uint) {
M cmd/test_epd_suite/main.go +1 -1
@@ 102,7 102,7 @@ func main() {
log.Printf("Error in line %v: %v", i, err)
continue
}
- legalMoves := new(search.FifoMoveList)
+ legalMoves := new(search.MoveList)
search.GenerateLegalMoves(p, legalMoves)
var moves []pos.Move
for move := legalMoves.Next(); move != pos.NoMove; move = legalMoves.Next() {
M game.go +1 -1
@@ 64,7 64,7 @@ returns checkmate if the color who is in
// todo: this func is a work around
func (this Game) Status() GameState {
- moves := new(search.FifoMoveList)
+ moves := new(search.MoveList)
search.GenerateLegalMoves(this.position, moves)
if moves.Len() == 0 {
M notation/san/san_test.go +1 -1
@@ 37,7 37,7 @@ func TestParseSquare(t *testing.T) {
func TestParseMove(t *testing.T) {
- legalMoves := new(search.FifoMoveList)
+ legalMoves := new(search.MoveList)
var moves []pos.Move
// test: short castling
M position/position.go +10 -11
@@ 112,7 112,6 @@ type Position struct {
pieces [NumberOfColors][NumberOfPieceTypes]PieceList
- // who is in turn?
sideToMove Color
// after a pawn double push this is a possible capture square for an opposite pawn
@@ 285,6 284,10 @@ func (this *Position) move(from, to b.Sq
}
}
+func (this *Position) PieceList(player Color, piece PieceType) *PieceList {
+ return &this.pieces[player][piece]
+}
+
func (this *Position) setPieces(player Color, pieceType PieceType, location ...b.Square) {
for i := range location {
@@ 326,8 329,8 @@ func (this *Position) King(player Color)
return this.pieces[player][King].Pieces[0]
}
-func (this *Position) PieceList(player Color, piece PieceType) *PieceList {
- return &this.pieces[player][piece]
+func (this *Position) EnPassantSquare() b.Square {
+ return this.enPassantSquare
}
func (this *Position) setEnPassantSquare(location b.Square) {
@@ 335,10 338,6 @@ func (this *Position) setEnPassantSquare
this.enPassantSquare = location
}
-func (this *Position) EnPassantSquare() b.Square {
- return this.enPassantSquare
-}
-
/*
func (this *Position) setCastlingRights(color ColorID, castlingRights CastlingOption) {
@@ 527,7 526,7 @@ func (this *Position) String() string {
output := "\nboard:" + pieces[White] + pieces[Black]
output += "\npiece lists:"
for color := range this.pieces {
- output += fmt.Sprintf("\n%s:", color)
+ output += fmt.Sprintf("\n%s:", Color(color))
for pieceType := range this.pieces[color] {
if this.pieces[color][pieceType].Len() > 0 {
output += fmt.Sprintf("\n %s: %s", PieceType(pieceType), this.pieces[color][pieceType])
@@ 535,13 534,13 @@ func (this *Position) String() string {
}
}
output += fmt.Sprintf("\nSide to Move: %s. ", this.sideToMove)
- output += fmt.Sprintf("En Passant b.Square is: %s. ", this.enPassantSquare)
- output += fmt.Sprintf("Halfmove Clock is: %d\n", this.halfmoveClock)
+ output += fmt.Sprintf("En Passant b.Square: %s. ", this.enPassantSquare)
+ output += fmt.Sprintf("Halfmove Clock: %d\n", this.halfmoveClock)
output += fmt.Sprintf("%s\nHash value: %d, Pawn hash value: %d.\n",
this.castlingRights, this.hash, this.pawnHash)
output += fmt.Sprintf("Material White: %d, Black: %d. ",
this.material[White], this.material[Black])
- output += fmt.Sprintf("Position bonus White: %d, Black: %d. ",
+ output += fmt.Sprintf("Position bonus White: %d, Black: %d.\n",
this.positionBonus[White], this.positionBonus[Black])
return output
M search/move_generator.go +127 -12
@@ 31,7 31,7 @@ var (
)
// MVV-LVA
-func GenerateGoodCaptures(p *pos.Position, captures MoveList) {
+func GenerateGoodCaptures(p *pos.Position, captures *MoveList) {
GenerateGoodCapturesCalls++
@@ 112,7 112,7 @@ func GenerateGoodCaptures(p *pos.Positio
}
}
-func GenerateEvenCaptures(p *pos.Position, captures MoveList) {
+func GenerateEvenCaptures(p *pos.Position, captures *MoveList) {
GenerateEvenCapturesCalls++
@@ 179,7 179,7 @@ func GenerateEvenCaptures(p *pos.Positio
}
}
-func GenerateBadCaptures(p *pos.Position, captures MoveList) {
+func GenerateBadCaptures(p *pos.Position, captures *MoveList) {
GenerateBadCapturesCalls++
@@ 218,7 218,7 @@ func GenerateBadCaptures(p *pos.Position
// generates all moves excluding pawn moves
// bug: the king moves first? really?
-func GeneratePieceMoves(p *pos.Position, moves MoveList) {
+func GeneratePieceMoves(p *pos.Position, moves *MoveList) {
// http://www.stmintz.com/ccc/index.php?id=21370
// the other way around gives more cut offs, but not in my program
@@ 249,7 249,7 @@ func GeneratePieceMoves(p *pos.Position,
}
// generate all pawn moves, excluding promotions
-func GeneratePawnMoves(p *pos.Position, moves MoveList) {
+func GeneratePawnMoves(p *pos.Position, moves *MoveList) {
color := p.SideToMove()
pawns := p.PieceList(color, pos.Pawn)
@@ 283,7 283,7 @@ func GeneratePawnMoves(p *pos.Position,
// plain promotions only, no capturing promotions
// BUG: this has to be put into GenerateGoodCaptures() for better move ordering
-func GeneratePawnPromotions(p *pos.Position, moves MoveList) {
+func GeneratePawnPromotions(p *pos.Position, moves *MoveList) {
pawns := p.PieceList(p.SideToMove(), pos.Pawn)
forward := pos.MoveDirection(p.SideToMove())
@@ 301,7 301,7 @@ func GeneratePawnPromotions(p *pos.Posit
}
// todo: moves generated here are legal?
-func GenerateCastlings(position *pos.Position, moves MoveList) {
+func GenerateCastlings(position *pos.Position, moves *MoveList) {
sideToMove := position.SideToMove()
// todo: CASTLING_SHORT|CASTLING_LONG does not work
@@ 464,10 464,11 @@ func InCheckAfterOpponentsMove(p *pos.Po
return chessBid
}
-func GenerateCheckEvasions1(p *pos.Position, checks ChessBid, moves MoveList) {
+func GenerateCheckEvasions1(p *pos.Position, checks ChessBid, moves *MoveList) {
king := p.King(p.SideToMove())
+ // king moves first
for _, direction := range Movements[pos.King].Directions {
switch {
case p.Piece(king+direction) == pos.NoPiece:
@@ 486,6 487,7 @@ func GenerateCheckEvasions1(p *pos.Posit
// try to capture the attacker or block the attack with a piece
// BUG: check if the path of the blocker is blocked
+ // BUG: check if the blocker is pinned
for rayBlock := attack; rayBlock != king; rayBlock += direction {
for blocker := pos.Knight; blocker != pos.King; blocker++ {
ownPieces := p.PieceList(p.SideToMove(), blocker)
@@ 503,7 505,7 @@ func GenerateCheckEvasions1(p *pos.Posit
}
// todo: implement this
-func GenerateCheckEvasions(p *pos.Position, state ChessBid, evasions MoveList) {
+func GenerateCheckEvasions(p *pos.Position, state ChessBid, evasions *MoveList) {
GenerateMoves(p, evasions)
}
@@ 517,9 519,9 @@ func InCheckAfterOwnMove(p *pos.Position
// todo: only for first implementation of GenerateCheckEvasions(), needs
// sane implementation
-var pseudoLegalMoves = new(FifoMoveList)
+var pseudoLegalMoves = new(MoveList)
-func GenerateLegalMoves(p *pos.Position, legalMoves MoveList) {
+func GenerateLegalMoves(p *pos.Position, legalMoves *MoveList) {
pseudoLegalMoves.Empty()
GenerateMoves(p, pseudoLegalMoves)
@@ 535,7 537,7 @@ func GenerateLegalMoves(p *pos.Position,
}
// GenerateMoves generates all pseudo legal moves of a position.
-func GenerateMoves(p *pos.Position, moves MoveList) {
+func GenerateMoves(p *pos.Position, moves *MoveList) {
GeneratePawnPromotions(p, moves)
GenerateGoodCaptures(p, moves)
GenerateEvenCaptures(p, moves)
@@ 549,3 551,116 @@ func GenerateMoves(p *pos.Position, move
func IsValidMove(p pos.Position, move pos.Move) bool {
return false
}
+
+func GeneratePieceCaptures(p *pos.Position, goodCaptures, evenCaptures, badCaptures *MoveList) {
+ // http://www.stmintz.com/ccc/index.php?id=21370
+ // the other way around gives more cut offs, but not in my program
+
+ opponent := pos.Opponent(p.SideToMove())
+ for piece := pos.King; piece != pos.Pawn; piece-- {
+ pieces := p.PieceList(p.SideToMove(), piece)
+ for i := pieces.Max - 1; i >= 0; i-- {
+ start := pieces.Pieces[i]
+
+ if Movements[piece].Repetitions == 1 {
+ for _, direction := range Movements[piece].Directions {
+ if p.Piece(start+direction) != pos.NoPiece &&
+ p.Piece(start+direction) != pos.BorderPiece &&
+ p.Piece(start+direction).Color() == opponent {
+
+ switch value := p.Piece(start+direction).Type() - piece; {
+ case value > 0:
+ goodCaptures.Add(pos.NewMove(start, start+direction),
+ p.Piece(start+direction).Type().SortValue())
+ case value < 0:
+ badCaptures.Add(pos.NewMove(start, start+direction),
+ p.Piece(start+direction).Type().SortValue())
+ case value == 0:
+ evenCaptures.Add(pos.NewMove(start, start+direction),
+ p.Piece(start+direction).Type().SortValue())
+ }
+ }
+ }
+ } else {
+ for _, direction := range Movements[piece].Directions {
+ var square b.Square
+ for square = start + direction; p.Piece(square) == pos.NoPiece; square += direction {
+ }
+ if p.Piece(square) != pos.BorderPiece && p.Piece(square).Color() == opponent {
+ switch value := p.Piece(square).Type() - piece; {
+ case value > 0:
+ goodCaptures.Add(pos.NewMove(start, square),
+ p.Piece(start+direction).Type().SortValue())
+ case value < 0:
+ badCaptures.Add(pos.NewMove(start, square),
+ p.Piece(start+direction).Type().SortValue())
+ case value == 0:
+ evenCaptures.Add(pos.NewMove(start, square),
+ p.Piece(start+direction).Type().SortValue())
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+// generate all pawn captures, excluding promotions
+// todo: capture sort values
+func GeneratePawnCaptures(p *pos.Position, goodCaptures, evenCaptures *MoveList) {
+
+ sideToMove := p.SideToMove()
+ opponent := pos.Opponent(sideToMove)
+ forward := pos.MoveDirection(sideToMove)
+ pawn := pos.NewPiece(sideToMove, pos.Pawn)
+ pawnValue := pos.Pawn.SortValue()
+ // en passant capture
+ if p.EnPassantSquare() != b.NoSquare {
+ enPassantSquare := p.EnPassantSquare()
+ if p.Piece(enPassantSquare-forward+b.Left) == pawn {
+ evenCaptures.Add(pos.NewMove(enPassantSquare-forward+b.Left, enPassantSquare),
+ pawnValue)
+ }
+ if p.Piece(enPassantSquare-forward+b.Right) == pawn {
+ evenCaptures.Add(pos.NewMove(enPassantSquare-forward+b.Right, enPassantSquare),
+ pawnValue)
+ }
+ }
+
+ // pawn captures
+ pawns := p.PieceList(sideToMove, pos.Pawn)
+
+ for i := pawns.Max - 1; i >= 0; i-- {
+ start := pawns.Pieces[i]
+ if b.GetRank(start) == sideToMove.PromotionRank() {
+ // no promotions here, these are handled somewhere else
+ continue
+ }
+ destination := start + forward + b.Left
+ if p.Piece(destination) != pos.NoPiece &&
+ p.Piece(destination) != pos.BorderPiece &&
+ p.Piece(destination).Color() == opponent {
+ switch value := p.Piece(destination).Type() - pos.Pawn; {
+ case value > 0:
+ goodCaptures.Add(pos.NewMove(start, destination),
+ p.Piece(destination).Type().SortValue())
+ case value == 0:
+ evenCaptures.Add(pos.NewMove(start, destination),
+ p.Piece(destination).Type().SortValue())
+ }
+ }
+ destination = start + forward + b.Right
+ if p.Piece(destination) != pos.NoPiece &&
+ p.Piece(destination) != pos.BorderPiece &&
+ p.Piece(destination).Color() == opponent {
+ switch value := p.Piece(destination).Type() - pos.Pawn; {
+ case value > 0:
+ goodCaptures.Add(pos.NewMove(start, destination),
+ p.Piece(destination).Type().SortValue())
+ case value == 0:
+ evenCaptures.Add(pos.NewMove(start, destination),
+ p.Piece(destination).Type().SortValue())
+ }
+ }
+ }
+}
M search/move_generator_perft_test.go +4 -4
@@ 27,7 27,7 @@ func aTestPerftStartingPosition(t *testi
}
p := pos.NewInitialPosition()
- moves := new(FifoMoveList)
+ moves := new(MoveList)
var found, expected uint64
for i := range perftResults {
@@ 62,7 62,7 @@ func aTestPerftGoodTestPosition(t *testi
if err != nil {
panic(err)
}
- moves := new(FifoMoveList)
+ moves := new(MoveList)
var found, expected uint64
for i := range perftResults {
@@ 96,7 96,7 @@ func aTestPerftPromotionBugPosition(t *t
if err != nil {
panic(err)
}
- moves := new(FifoMoveList)
+ moves := new(MoveList)
var found, expected uint64
for i := range perftResults {
@@ 184,7 184,7 @@ func BenchmarkPerftTestA(b *testing.B) {
}
}
-var perftMoveListCache = [10]FifoMoveList{}
+var perftMoveListCache = [10]MoveList{}
// see http://chessprogramming.wikispaces.com/perft
func perft(p *pos.Position, depth int) uint64 {
M search/move_generator_test.go +39 -39
@@ 10,7 10,7 @@ import (
"testing"
)
-func GenerateCaptures(p *pos.Position, captures MoveList) {
+func GenerateCaptures(p *pos.Position, captures *MoveList) {
GenerateGoodCaptures(p, captures)
GenerateEvenCaptures(p, captures)
GenerateBadCaptures(p, captures)
@@ 19,7 19,7 @@ func GenerateCaptures(p *pos.Position, c
type testCase struct {
name string
position *pos.Position
- expected *UnsortedMoveList
+ expected *MoveList
}
// todo: blocker
@@ 31,7 31,7 @@ func TestGeneratePieceMoves(t *testing.T
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetKnights(pos.White, b.A1)
- expected := new(UnsortedMoveList)
+ expected := new(MoveList)
expected.addMovesTo(b.A1, b.C2, b.B3)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 39,7 39,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetKnights(pos.Black, b.D5)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.D5, b.B6, b.C7, b.E7, b.F6, b.F4, b.E3, b.C3, b.B4)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 47,7 47,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetBishops(pos.White, b.H1)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.H1, b.G2, b.F3, b.E4, b.D5, b.C6, b.B7, b.A8)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 55,7 55,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetBishops(pos.Black, b.E4)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.E4, b.F5, b.G6, b.H7, b.F3, b.G2, b.H1,
b.D3, b.C2, b.B1, b.D5, b.C6, b.B7, b.A8)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 64,7 64,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetRooks(pos.White, b.A8)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.A8, b.A7, b.A6, b.A5, b.A4, b.A3, b.A2, b.A1)
expected.addMovesTo(b.A8, b.B8, b.C8, b.D8, b.E8, b.F8, b.G8, b.H8)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 73,7 73,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetRooks(pos.Black, b.B5)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.B5, b.B6, b.B7, b.B8, b.B4, b.B3, b.B2, b.B1)
expected.addMovesTo(b.B5, b.A5, b.C5, b.D5, b.E5, b.F5, b.G5, b.H5)
testSuite = append(testSuite, testCase{name, p, expected})
@@ 82,7 82,7 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetQueens(pos.White, b.H8)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.H8, b.H7, b.H6, b.H5, b.H4, b.H3, b.H2, b.H1)
expected.addMovesTo(b.H8, b.G7, b.F6, b.E5, b.D4, b.C3, b.B2, b.A1)
expected.addMovesTo(b.H8, b.G8, b.F8, b.E8, b.D8, b.C8, b.B8, b.A8)
@@ 92,14 92,14 @@ func TestGeneratePieceMoves(t *testing.T
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetQueens(pos.Black, b.F3)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.addMovesTo(b.F3, b.E4, b.D5, b.C6, b.B7, b.A8, b.G2, b.H1)
expected.addMovesTo(b.F3, b.F4, b.F5, b.F6, b.F7, b.F8, b.F2, b.F1)
expected.addMovesTo(b.F3, b.E2, b.D1, b.G4, b.H5)
expected.addMovesTo(b.F3, b.E3, b.D3, b.C3, b.B3, b.A3, b.G3, b.H3)
testSuite = append(testSuite, testCase{name, p, expected})
- found := new(UnsortedMoveList)
+ found := new(MoveList)
for _, tc := range testSuite {
found.Empty()
GeneratePieceMoves(tc.position, found)
@@ 113,7 113,7 @@ func TestGeneratePieceMoves(t *testing.T
func TestGenerateBishopMoves(t *testing.T) {
- var moves, expectedMoves = new(UnsortedMoveList), new(UnsortedMoveList)
+ var moves, expectedMoves = new(MoveList), new(MoveList)
// test: Move Generator finds the right moves for a bishop.
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
@@ 138,7 138,7 @@ func TestGeneratePawnPushes(t *testing.T
name := "white pawn pushes from initial rank"
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.White, b.A2)
- expected := new(UnsortedMoveList)
+ expected := new(MoveList)
expected.setMoves(pos.NewMove(b.A2, b.A3), pos.NewMove(b.A2, b.A4))
testSuite = append(testSuite, testCase{name, p, expected})
@@ 147,14 147,14 @@ func TestGeneratePawnPushes(t *testing.T
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.Black, b.B7)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.setMoves(pos.NewMove(b.B7, b.B6), pos.NewMove(b.B7, b.B5))
testSuite = append(testSuite, testCase{name, p, expected})
name = "white pawn pushes from non initial square"
p = pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.White, b.D5)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.setMoves(pos.NewMove(b.D5, b.D6))
testSuite = append(testSuite, testCase{name, p, expected})
@@ 162,12 162,12 @@ func TestGeneratePawnPushes(t *testing.T
name = "black pawn pushes from non initial square"
p = pos.NewPosition(pos.Black, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.Black, b.H4)
- expected = new(UnsortedMoveList)
+ expected = new(MoveList)
expected.setMoves(pos.NewMove(b.H4, b.H3))
testSuite = append(testSuite, testCase{name, p, expected})
- found := new(UnsortedMoveList)
+ found := new(MoveList)
for _, tc := range testSuite {
found.Empty()
GeneratePawnMoves(tc.position, found)
@@ 181,7 181,7 @@ func TestGeneratePawnPushes(t *testing.T
func TestGeneratePawnPromotions(t *testing.T) {
- var moves, expectedMoves = new(SortedMoveList), new(SortedMoveList)
+ var moves, expectedMoves = new(MoveList), new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.White, b.A7)
@@ 238,7 238,7 @@ func TestGeneratePawnPromotions(t *testi
}
func TestGeneratePawnCaptures(t *testing.T) {
- var moves, expectedMoves = new(SortedMoveList), new(SortedMoveList)
+ var moves, expectedMoves = new(MoveList), new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
pawn := pos.WhitePawn
p.Set(pawn, b.B3)
@@ 307,7 307,7 @@ func TestGeneratePawnCaptures(t *testing
func TestGenerateCastlings(t *testing.T) {
- var moves, expectedMoves = new(SortedMoveList), new(SortedMoveList)
+ var moves, expectedMoves = new(MoveList), new(MoveList)
// test: no white castling possible
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.CastlingBoth)
p.SetKing(pos.White, b.E1)
@@ 422,7 422,7 @@ func TestGenerateCastlings(t *testing.T)
func TestGenerateEnPassantMoves(t *testing.T) {
- var moves, expectedMoves = new(SortedMoveList), new(SortedMoveList)
+ var moves, expectedMoves = new(MoveList), new(MoveList)
p := pos.NewPosition(pos.Black, b.E3, pos.NoCastling, pos.NoCastling)
pawn := pos.BlackPawn
@@ 460,7 460,7 @@ func TestGenerateNoMovesLeft(t *testing.
p.SetRooks(pos.Black, b.D1)
p.SetKing(pos.White, b.H1)
- moves := new(SortedMoveList)
+ moves := new(MoveList)
GenerateMoves(p, moves)
if moves.Next() == pos.NoMove {
@@ 593,7 593,7 @@ func TestGenerateError1(t *testing.T) {
// this is a position that produced 2 times "f1-h3" in the move list
// reason was that bxb was generated in GoodCaptures(), which is wrong
p, _ := fen.Parse("rn1qkbnr/ppp1pppp/3p4/8/8/6Pb/PPPPPP2/RNBQKBNR w KQkq - 0 1")
- moves := new(FifoMoveList)
+ moves := new(MoveList)
GenerateMoves(p, moves)
found := moves.Len()
expected := int32(21)
@@ 608,7 608,7 @@ func TestMoveOrdering(t *testing.T) {
name string
position *pos.Position
expected []pos.Move
- function func(*pos.Position, MoveList)
+ function func(*pos.Position, *MoveList)
}
var testSuite []testCase
@@ 641,7 641,7 @@ func TestMoveOrdering(t *testing.T) {
testSuite = append(testSuite, testCase{name, p, expected, GenerateGoodCaptures})
for _, tc := range testSuite {
- found := new(FifoMoveList)
+ found := new(MoveList)
tc.function(tc.position, found)
if found.Len() != int32(len(tc.expected)) {
t.Errorf("'%s': found wrong move count %d moves, expected %d.", name, found.Len(), len(expected))
@@ 659,7 659,7 @@ func BenchmarkGenerateMovesStartgame(b *
b.StopTimer()
p := pos.NewInitialPosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
b.StartTimer()
for i := 0; i < b.N; i++ {
GenerateMoves(p, moves)
@@ 671,7 671,7 @@ func BenchmarkGenerateMovesMidgame(b *te
b.StopTimer()
p := pos.NewMidgamePosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
b.StartTimer()
for i := 0; i < b.N; i++ {
GenerateMoves(p, moves)
@@ 683,7 683,7 @@ func BenchmarkGenerateMovesEndgame(b *te
b.StopTimer()
p := pos.NewEndgamePosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
b.StartTimer()
for i := 0; i < b.N; i++ {
GenerateMoves(p, moves)
@@ 695,7 695,7 @@ func BenchmarkGenerateCapturesStartgame(
b.StopTimer()
p := pos.NewInitialPosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
moves.Empty()
b.StartTimer()
for i := 0; i < b.N; i++ {
@@ 708,7 708,7 @@ func BenchmarkGenerateCapturesMidgame(b
b.StopTimer()
p := pos.NewMidgamePosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
b.StartTimer()
for i := 0; i < b.N; i++ {
GenerateCaptures(p, moves)
@@ 720,7 720,7 @@ func BenchmarkGenerateCapturesEndgame(b
b.StopTimer()
p := pos.NewEndgamePosition()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
b.StartTimer()
for i := 0; i < b.N; i++ {
GenerateCaptures(p, moves)
@@ 732,7 732,7 @@ func BenchmarkGenerateCapturesEndgame(b
func BenchmarkGeneratePromotions(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
bt.StartTimer()
for i := 0; i < bt.N; i++ {
GeneratePromotions(b.A7, b.A8, 0, moves)
@@ 759,7 759,7 @@ func BenchmarkGenerateCastlings(bt *test
p.Remove(b.D1)
p.Remove(b.F1)
p.Remove(b.G1)
- moves := new(SortedMoveList)
+ moves := new(MoveList)
bt.StartTimer()
for i := 0; i < bt.N; i++ {
GenerateCastlings(p, moves)
@@ 770,7 770,7 @@ func BenchmarkGenerateCastlings(bt *test
func BenchmarkGenerateQueenMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetQueens(pos.White, b.D5)
bt.StartTimer()
@@ 783,7 783,7 @@ func BenchmarkGenerateQueenMaxMoves(bt *
func BenchmarkGenerateBishopMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetBishops(pos.White, b.D5)
bt.StartTimer()
@@ 796,7 796,7 @@ func BenchmarkGenerateBishopMaxMoves(bt
func BenchmarkGenerateRookMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetRooks(pos.White, b.D5)
bt.StartTimer()
@@ 809,7 809,7 @@ func BenchmarkGenerateRookMaxMoves(bt *t
func BenchmarkGenerateKingMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetKing(pos.White, b.D5)
bt.StartTimer()
@@ 822,7 822,7 @@ func BenchmarkGenerateKingMaxMoves(bt *t
func BenchmarkGenerateKnightMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetKnights(pos.White, b.D5)
bt.StartTimer()
@@ 835,7 835,7 @@ func BenchmarkGenerateKnightMaxMoves(bt
func BenchmarkGeneratePawnMaxMoves(bt *testing.B) {
bt.StopTimer()
- moves := new(SortedMoveList)
+ moves := new(MoveList)
p := pos.NewPosition(pos.White, b.NoSquare, pos.NoCastling, pos.NoCastling)
p.SetPawns(pos.White, b.D2)
p.SetPawns(pos.Black, b.E3, b.C3)
M search/move_list.go +24 -108
@@ 6,111 6,13 @@ import (
"fmt"
)
-type MoveList interface {
- Next() pos.Move
- Add(pos.Move, int32)
- Empty()
- Len() int32
- Sort()
-}
-
-type FifoMoveList struct {
- moves [256]pos.Move
- current, max int32
-}
-
-func (this *FifoMoveList) Add(move pos.Move, dummy int32) {
- max := &this.max
- this.moves[*max] = move
- *max++
-}
-
-func (this *FifoMoveList) Reset() {
- this.current = 0
-}
-
-func (this *FifoMoveList) Empty() {
- this.current, this.max = 0, 0
-}
-
-func (this *FifoMoveList) Sort() {
- return
-}
-
-func (this *FifoMoveList) Len() int32 {
- return this.max
-}
-
-func (this *FifoMoveList) Next() pos.Move {
-
- if this.current == this.max {
- return pos.NoMove
- }
- this.current++
- return this.moves[this.current-1]
-}
-
-// for tests only
-func (this *FifoMoveList) setMoves(moves ...pos.Move) {
- this.Empty()
- max := &this.max
- for i := range moves {
- this.moves[*max] = moves[i]
- *max++
- }
-}
-
-// for tests only
-func (this *FifoMoveList) addMovesTo(from b.Square, destinations ...b.Square) {
-
- for i := range destinations {
- this.moves[this.max] = pos.NewMove(from, destinations[i])
- this.max++
- }
-}
-
-// for tests only
-// bug: both move lists should have the same order, as this list is ordered
-func (this *FifoMoveList) equals(moves *FifoMoveList) bool {
-
- if this.Len() != moves.Len() {
- return false
- }
- var found bool
- for i := int32(0); i < this.Len(); i++ {
- move := this.moves[i]
- found = false
- for j := int32(0); j < moves.Len(); j++ {
- if move == moves.moves[j] {
- found = true
- }
- }
- if !found {
- return false
- }
- }
- return true
-}
-
-func (this *FifoMoveList) String() string {
-
- if this.Len() == 0 {
- return "()"
- }
- output := "("
- for i := int32(0); i < this.Len(); i++ {
- output += fmt.Sprintf("%d: %s, ", i, this.moves[i])
- }
- return output + ")"
-}
-
type EvaluatedMove struct {
Move pos.Move
SortValue int32
}
type UnsortedMoveList struct {
- FifoMoveList
+ MoveList
}
func (this *UnsortedMoveList) equals(moves *UnsortedMoveList) bool {
@@ 135,23 37,23 @@ func (this *UnsortedMoveList) equals(mov
const maxSortedMoves int32 = 5
-type SortedMoveList struct {
+type MoveList struct {
moves [256]EvaluatedMove
max, current int32
}
-func (this *SortedMoveList) Empty() {
+func (this *MoveList) Empty() {
this.max, this.current = 0, 0
}
-func (this *SortedMoveList) Add(move pos.Move, sortValue int32) {
+func (this *MoveList) Add(move pos.Move, sortValue int32) {
max := &this.max
this.moves[*max].Move = move
this.moves[*max].SortValue = sortValue
*max++
}
-func (this *SortedMoveList) Next() pos.Move {
+func (this *MoveList) Next() pos.Move {
if this.current == this.max {
return pos.NoMove
@@ 161,7 63,7 @@ func (this *SortedMoveList) Next() pos.M
}
// insertion sort
-func (this *SortedMoveList) Sort() {
+func (this *MoveList) Sort() {
for i := int32(1); i < this.max; i++ {
pivot := this.moves[i]
@@ 174,11 76,15 @@ func (this *SortedMoveList) Sort() {
}
}
-func (this *SortedMoveList) Len() int32 {
+func (this *MoveList) Len() int32 {
return this.max
}
-func (this *SortedMoveList) String() string {
+func (this *MoveList) Reset() {
+ this.current = 0
+}
+
+func (this *MoveList) String() string {
output := fmt.Sprintf("\nMovelist: #moves: %v\n", this.max)
for i := int32(0); i < this.max; i++ {
output += fmt.Sprintf("[%v: %s(%v)] ",
@@ 188,7 94,7 @@ func (this *SortedMoveList) String() str
}
// for tests only
-func (this *SortedMoveList) setMoves(moves ...pos.Move) {
+func (this *MoveList) setMoves(moves ...pos.Move) {
this.Empty()
max := &this.max
for i := range moves {
@@ 198,8 104,18 @@ func (this *SortedMoveList) setMoves(mov
}
}
+// for tests only
+func (this *MoveList) addMovesTo(from b.Square, destinations ...b.Square) {
+
+ for i := range destinations {
+ this.moves[this.max].Move = pos.NewMove(from, destinations[i])
+ this.moves[this.max].SortValue = 0
+ this.max++
+ }
+}
+
// for tests only, sort values are ignored here
-func (this *SortedMoveList) equals(moves *SortedMoveList) bool {
+func (this *MoveList) equals(moves *MoveList) bool {
if this.Len() != moves.Len() {
return false
M search/move_list_test.go +8 -93
@@ 7,94 7,9 @@ import (
"testing"
)
-func TestFifoMoveList(t *testing.T) {
-
- moves := new(FifoMoveList)
-
- // test: An empty MoveList returns no move.
- move := moves.Next()
- if move != pos.NoMove {
- t.Error(fmt.Sprintf("Expected no move in an empty MoveList, found: %v.", move))
- }
-
- // test: MoveList is returning the right move.
- moves.setMoves(pos.NewMove(b.A3, b.A5))
- move = moves.Next()
- expected := pos.NewMove(b.A3, b.A5)
- if move != expected {
- t.Error(fmt.Sprintf("Expected move %v, found: %v.", expected, move))
- }
-
- // test: MoveList is returning no move when there are no moves left.
- move = moves.Next()
- if move != pos.NoMove {
- t.Error(fmt.Sprintf("Expected no move, found: %v.", move))
- }
-
- // test: MoveList returns moves in the right order.
- moves.Empty()
- move = pos.NewMove(b.A3, b.A5)
- move1 := pos.NewMove(b.G5, b.H5)
- moves.moves[0] = move
- moves.moves[1] = move1
- moves.max = 2
-
- found := moves.Next()
- if found != move {
- t.Error(fmt.Sprintf("Expected %v, found: %v.", found, move1))
- }
-
- found = moves.Next()
- if found != move1 {
- t.Error(fmt.Sprintf("Expected %v, found: %v.", found, move))
- }
+func TestMoveList(t *testing.T) {
- // test: MoveList is returning no move when there are no moves left.
- found = moves.Next()
- if found != pos.NoMove {
- t.Error(fmt.Sprintf("Expected no move, found: %v.", found))
- }
-}
-
-func TestFifoMoveListEquals(t *testing.T) {
-
- moves1 := new(FifoMoveList)
- moves2 := new(FifoMoveList)
-
- // test: Two empty MoveLists are equal.
- if !moves1.equals(moves2) {
- t.Error("Two empty move lists have to be equal, found: unequal.")
- }
-
- // test: MoveLists with different size are unequal.
- moves1.setMoves(pos.NewMove(b.C3, b.C5))
- moves2.setMoves(pos.NewMove(b.C3, b.C4), pos.NewMove(b.C3, b.C5))
- if moves1.equals(moves2) {
- t.Error("pos.Move lists with different sizes are not equal.")
- }
-
- // test: Order of adding Moves does not matter for Equality.
- moves1.Empty()
- moves1.setMoves(pos.NewMove(b.A3, b.A5), pos.NewMove(b.A3, b.A4))
- moves2.Empty()
- moves2.setMoves(pos.NewMove(b.A3, b.A4), pos.NewMove(b.A3, b.A5))
- if !moves1.equals(moves2) {
- t.Errorf("pos.Move lists %+v and %+v are equal, found: unequal.", moves1, moves2)
- }
-
- // test: MoveLists with different moves are unequal.
- moves1.Empty()
- moves1.setMoves(pos.NewMove(b.B3, b.A5), pos.NewMove(b.B3, b.A6))
- moves2.Empty()
- moves2.setMoves(pos.NewMove(b.B3, b.A4), pos.NewMove(b.B3, b.A5))
- if moves1.equals(moves2) {
- t.Errorf("pos.Move lists %+v and %+v are not equal, found: equal.", moves1, moves2)
- }
-}
-
-func TestSortedMoveList(t *testing.T) {
-
- moves := new(SortedMoveList)
+ moves := new(MoveList)
// test: An empty MoveList returns no move.
move := moves.Next()
@@ 145,14 60,14 @@ func TestSortedMoveList(t *testing.T) {
func TestSort(t *testing.T) {
- // moves := new(SortedMoveList)
+ // moves := new(MoveList)
}
-func TestSortedMoveListEquals(t *testing.T) {
+func TestMoveListEquals(t *testing.T) {
- moves1 := new(SortedMoveList)
- moves2 := new(SortedMoveList)
+ moves1 := new(MoveList)
+ moves2 := new(MoveList)
// test: Two empty MoveLists are equal.
if !moves1.equals(moves2) {
@@ 185,9 100,9 @@ func TestSortedMoveListEquals(t *testing
}
}
-func TestSortedMoveListSortValue(t *testing.T) {
+func TestMoveListSortValue(t *testing.T) {
- moves := new(SortedMoveList)
+ moves := new(MoveList)
moves.Empty()
move := pos.NewMove(b.A3, b.A5)
M search/search.go +29 -29
@@ 63,8 63,10 @@ var (
// todo: handle collisions
var AlwaysSave TranspositionTable
-var sortedMoveListCache [MaxDepth + 1]SortedMoveList
-var fifoMoveListCache [MaxDepth + 1]FifoMoveList
+var moveListCache [MaxDepth + 1]MoveList
+var goodCapturesCache [MaxDepth + 1]MoveList
+var evenCapturesCache [MaxDepth + 1]MoveList
+var badCapturesCache [MaxDepth + 1]MoveList
func FindBestMove(position *pos.Position, depthOrTime, flags int32) (pos.Move, int32) {
@@ 132,8 134,9 @@ func negaSearch(position *pos.Position,
}
var hashMove pos.Move
- fifoMoves := &(fifoMoveListCache[depth])
- fifoMoves.Empty()
+
+ moves := &(moveListCache[depth])
+ moves.Empty()
if flags&UseTT != 0 {
@@ 157,11 160,10 @@ func negaSearch(position *pos.Position,
return hashMove, -score
}
if hashMove != pos.NoMove {
- fifoMoves.Add(hashMove, 0)
+ moves.Add(hashMove, 0)
}
}
}
- var moves MoveList = fifoMoves
if depth == 0 {
LeafNodes++
@@ 179,7 181,6 @@ func negaSearch(position *pos.Position,
}
InnerNodes++
- sortedMoves := &(sortedMoveListCache[depth])
sideToMove := position.SideToMove()
nodeType := allNode
bestMove := pos.NoMove
@@ 188,23 189,24 @@ func negaSearch(position *pos.Position,
chessBid := InCheckAfterOpponentsMove(position, lastPly)
if chessBid != NotInCheck {
inCheck = true
- GenerateCheckEvasions(position, chessBid, fifoMoves)
+ GenerateCheckEvasions(position, chessBid, moves)
}
} else {
// in the very first iteration for the first move of the game we have no last played move
inCheck = UnderAttack(position, position.King(sideToMove), pos.Opponent(sideToMove))
if inCheck {
- GenerateLegalMoves(position, fifoMoves)
+ GenerateLegalMoves(position, moves)
}
}
var score int32
+
if inCheck {
//analysis.Set("in check")
NodesInCheckAfterOpponentsMove++
moveMade := false
// todo: use hash move here?
// check evasions
- for move := fifoMoves.Next(); move != pos.NoMove; move = fifoMoves.Next() {
+ for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
// dont evaluate hash move twice
// todo: this makes the search even slower
// probably the cut off comes very soon while evaluating the hash move the 2nd time
@@ 256,6 258,9 @@ func negaSearch(position *pos.Position,
moveMade := false
movesFound := false
firstStage := 0
+ goodCaptures := &(goodCapturesCache[depth])
+ evenCaptures := &(evenCapturesCache[depth])
+ badCaptures := &(badCapturesCache[depth])
if moves.Len() == 0 {
// no move from tt -> skip stage 0
firstStage = 1
@@ 273,35 278,31 @@ func negaSearch(position *pos.Position,
NoCutOffsFromHashMove++
}
NodesStage1++
- moves = sortedMoves
- moves.Empty()
- GeneratePawnPromotions(position, moves)
- if moves.Len() == 0 {
- GenerateGoodCaptures(position, moves)
- } else {
- GenerateGoodCaptures(position, moves)
- moves.Sort()
- }
+ goodCaptures.Empty()
+ evenCaptures.Empty()
+ badCaptures.Empty()
+ GeneratePawnPromotions(position, goodCaptures)
+ GeneratePieceCaptures(position, goodCaptures, evenCaptures, badCaptures)
+ GeneratePawnCaptures(position, goodCaptures, evenCaptures)
+ goodCaptures.Sort()
+ moves = goodCaptures
case 2:
NodesStage2++
- moves = fifoMoves
- moves.Empty()
- GenerateEvenCaptures(position, fifoMoves)
- moves = fifoMoves
+ evenCaptures.Sort()
+ moves = evenCaptures
case 3:
NodesStage3++
- moves = fifoMoves
- moves.Empty()
- GenerateBadCaptures(position, moves)
+ badCaptures.Sort()
+ moves = badCaptures
case 4:
NodesStage4++
- moves = sortedMoves
+ moves = &(moveListCache[depth])
moves.Empty()
GeneratePieceMoves(position, moves)
moves.Sort()
case 5:
NodesStage5++
- moves = sortedMoves
+ moves = &(moveListCache[depth])
moves.Empty()
GeneratePawnMoves(position, moves)
GenerateCastlings(position, moves)
@@ 344,7 345,6 @@ func negaSearch(position *pos.Position,
move.Destination() == oldEnPassantSquare {
if IsCheck(position, sideToMove) {
NodesInCheckAfterOwnMove++
- //--logger.Printf("player %v is in check after own move -> take back move and try next move", sideToMove)
position.UnmakeMove(uMove)
continue
}
M ui/text/textui.go +1 -1
@@ 36,7 36,7 @@ func ReadMoveFromUser(position *pos.Posi
err := errors.New("")
- legalMoves := new(search.FifoMoveList)
+ legalMoves := new(search.MoveList)
search.GenerateLegalMoves(position, legalMoves)
for err != nil {