Posts tagged artificial intelligence

Generating Moves

Part of the How to Program a Chess Engine in Lisp series.

This post will cover basic game state and move generation.

The Chess Move

Part of the How to Program a Chess Engine in Lisp series.

This post will cover the following tasks, in preparation for generating chess moves:

• A macro for conveniently encoding fields in a fixnum integer
• An efficient encoding of a chess move
• Basic game state

FEN - Forsyth-Edwards Notation

Part of the How to Program a Chess Engine in Lisp series.

Now that we have pieces and a board, we need a convenient way of setting pieces on the board in specific positions. We’ll use this, not only for the initial position of a game, but also to configure a board with specific game scenarios for testing and debugging.

The standard way to do this is to use FEN, or Forsyth-Edwards Notation: [Wikipedia] [Chess Programming Wiki]

Here is the source for fen.rkt

The Chess Board

Part of the How to Program a Chess Engine in Lisp series.

One of the most significant design decisions for a chess engine is how to model the chess board. I think the most competitive engines use a bitboard representation; however, for our purposes, a mailbox representation is more intuitive and easy to visualize. In particular, we will use a 10 x 12 board.

Here is the source for board.rkt

The Chess Piece

Part of the How to Program a Chess Engine in Lisp series.

Donald Knuth is credited with the statement:

…We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

Chess programming is most assuredly in the 3%! Our challenge in this series will be to strike a reasonable balance between efficiency and clarity. Our first opportunity to that end is the chess piece.

Here is the source for piece.rkt

Last updated 2024–11–29 18:48

Table of Contents

1. The Chess Piece
2. The Chess Board
3. FEN - Forsyth-Edwards Notation
4. The Chess Move
5. Move Generation

Introduction

Programming a competent chess engine in lisp has been a goal of mine for some time. I finally did so in 2021, and it was a lot of fun! My new goal is to rewrite the code in a step by step way that emphasizes clarity, and to present it as a clear tutorial for writing a chess engine, and as a general Racket tutorial.

Someone on the Julia Slack mentioned this interview with Peter Norvig on the Gradient Dissent podcast.

• The 4th edition of Peter’s book, “Artificial Intelligence: A Modern Approach” was released earlier this year.

• When asked, “Do you think that Python will continue to be the main programming language for ML for the next decade?”, Peter replied, “Looking at where we are today, I guess I would be happier if Julia was the main language” ! (40:34)