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.
Last updated 2024–11–06 18:00
Table of Contents
- The Chess Piece
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.
|
#lang iracket/lang #:require racket
(require "../advent.rkt")
|
Day 8 involves navigating binary trees, and modular arithmetic, but I’m getting ahead of myself. Here is our test input:
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)
|
#lang iracket/lang #:require racket
(require "../advent.rkt")
|
Day 7 involves simulating a card game. Our input looks like:
...
8J833 494
6AJT8 318
AA4QQ 125
62KK6 876
7A7QK 241
...
The left side is our card
hand. The right side is our bid
amount. As always, we begin with parsing. For our purposes of illustration, I’ll skip the first 20 hands to get to a more interesting one with a J:
|
#lang iracket/lang #:require racket
(require "../advent.rkt")
|
Day 5 involves a typical Advent of Code scenario where Part 1 is easy, and a naive modification to Part 1 to get Part 2 is easy; however, the naive Part 2 solution will take far too long to run! :)
After solving Part 1 to get a star, I re-implemented the code to solve Part 2, and then Part 1 was simply making the Part 1 input conform to what Part 2 needed, and call Part 2.
The “trick” for Part 2 was to process the seed ranges as ranges, and not attempt to convert the seed ranges into lists of individual seeds.
|
#lang iracket/lang #:require racket
(require "../advent.rkt")
|
I always enjoy recursive list processing in Racket :) Here’s our input today:
Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
|
#lang iracket/lang #:require racket
(require "../advent.rkt" threading)
|
Day 3 involves some two dimensional analysis, so we’ll use complex numbers as a convenient two dimensional index:
|
#lang iracket/lang #:require racket
(require "../advent.rkt" threading)
|
Our data today is as follows:
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
For today’s task, I found it helpful to make use of the parallel-combine
combinator from Hanson & Sussman’s “Software Design for Flexibility”. This combinator applies f
and g
to the input, in parallel, and combines their output using h
. Pictorially, it looks like this:
Day 1
For part 1, we’re given data as follows (Note: in both data examples, intraline spaces are only for emphasis):
1 abc 2
pqr 3 stu 8 vwx
a 1 b2c3d4e 5 f
treb 7 uchet
The task is to find the first and last numeric digit in each line, e.g. 1
and 2
, concatenate them together, e.g. 12
, and then sum all of those values.
It appears upgrading my Anaconda Python distribution killed my Emacs, so I figured I’d try upgrading to the latest version to see if that fixed things. It did :)
Since upgrading Emacs to 29.1 no longer required the manual configuration changes I had to make when upgrading to 28.2, I’ll document the procedure I used on MacOS Ventura 13.6.1