murphyj / scarlsen-chess-engine Goto Github PK

#Scarlsen - Scala Chess Engine

Named after the current number one Magnus Carlsen - no affiliation

##Scope: Long term project to write a Chess Engine in Scala

##Goal

"To build a chess engine in Scala using the foundations and principles of chess engine theory that's been built up over the last 40 years or so. Also, partially an opportunity for me to try out Scala as a language and see how truly efficient it is in the domain of highly CPU intensive operations"

##Resources

StackOverflow Thread

Chess Programming Wiki

Chess Programming Part 1 - Getting Started

Chess Programming Part 2 - Data Structures

Chess Programming Part 3 - Move Generation

Chess Programming Part 4 - Basic Search

Chess Programming Part 5 - Advanced Search

Chess Programming Part 6 - Evaluation Functions

Alpha Beta Search

Game Search

Louis Kessler Chess Links

Book: Chess Skill in Man and Machine - By Peter W. Frey

##What I need to cover

• A way to store a representation of the Game Board in memory
• Rules on determining legal moves
• Technique to choose a move among all legal possibilities
• Ways of comparing moves so it makes an intelligent choice
• User interface

###Board Representation

• 64-bit Bitboards

• Piece centric notation

• 1 bitboard represents each piece type AND colour

• General Bitboard Techniques

• General Setwise Operations

  • Important to understand Set Theory, Union, Exclusive Or,

• Population Count

• BitScan

• Flipping Mirroring and Rotating

  • Transposition tables
    • How to create an efficient transposition hash?
      • Generate 12x64 N-bit random numbers (where the transposition table has 2^N entries) and store them in a table. Each random number is associated with a given piece on a given square (i.e., black rook on H4, etc.) An empty square is represented by a null word.
    • Start with a null hash key.
    • Scan the board; when you encounter a piece, XOR its random number to the current hash key. Repeat until the entire board has been examined.
    • Fill Algorithms

###Pattern and Attacks

• Pawn Pattern and Properties

• Knight Pattern

• King Pattern

• Sliding Piece Attacks including rotated and magic bitboards

• Square Attacked By

• X-ray Attacks

• Checks and Pinned Pieces

• Design Principles

• Move Generation Issues

• Bitboard aspects on move generation and static exchange evaluation (SEE).

• Bitboard Serialization

• Pieces versus Directions

• DirGolem

• SEE - The Swap Algorithm

• Attack and Defend Maps

• Miscellaneous

• Backtracking - Eight Queens puzzle with Bitboards

• De Bruijn Sequence Generator

• Quad-Bitboards

• Traversing Subsets of a Set