PSChess – A Chess Engine in PostScript

March 2023

Here is a quick overview about the making and inner working of PSChess.

GitHub repo: https://github.com/nst/PSChess

See also my remarks about programming in PostScript.

Motivation

To what extend can we execute arbitrary code on a printer?
How to implement a chess engine in PostScript?
Can you play chess against your printer?

Usage

You can use PSChess in GhostScript with the following arguments:

$ gs -DNOSAFER -dBATCH -dNOPAUSE -sDEVICE=pdfwrite -sOutputFile="%d.pdf" main.ps

The user plays by entering moves like d2d4.

The output is produced on both the console and PDF documents.

Console output:

r...r...        black h8 e8
pppkb.Q.        320
..bqp...
...p..Np        P...............
...B.Pn.        npp.............
..P...PB
PP.NP..P        -
..KR...R        white turn

PDF output:

Limitations

human plays white, computer plays black
pawns convert into queens only

Project Status

The project can be broken down in five steps:

draw a chess board
implement a user interface so that user can move pieces
implement chess game rules and logic
implement an algorithm so that the computer can play
run the program on a printer, prompting user for the next move

All 4 first steps are done. You can play chess against GhostScript, a PostScript interpreter.

Step 5 is not complete yet. I've already validated the practicaly feasibility of an interactive PostScript game running on a printer with PSTicTacTow. However, a chess game is far more bigger and demanding. There is probably important optimizations to be made and further tests to be carried out before playing PSChess against an actual printer.

Program Structure

PSChess code is structured in three files:

logic_board.ps  - data structure and primitives to deal with the board
logic_chess.ps  - chess rules, evaluation function, min-max algorithm
drawing.ps      - draw chess board and game state

And three consumers of these basic layers:

main.ps         - user input
tests_logic.ps  - unit tests
tests_visual.ps - visual tests to check possible moves

Or in a software layer diagram:

The Board

The board is represented by a PostScript string:

(\
rnbqkbnr\
pppppppp\
........\
........\
........\
........\
PPPPPPPP\
RNBQKBNR\
)

Pieces are moved with the putinterval instruction. Moving black pawn from a7 to a6 is:

board 16 (p) putinterval
board  8 (.) putinterval

The game state is kept in a dictionary. It mostly consist in the board, the current player and the captured pieces.

Pieces Moves

Pieces moves are encoded with their offsets, postive and negative. A moving procedure implements capture rules and ensures that pieces cannot go off the board.

/DirectionsForPiece
<<
    /N -8 def
    /E  1 def
    /S  8 def
    /W -1 def

    (P) [N N N add N W add N E add]
    (p) [S S S add S E add  S W add]
    (n) [N N E add add
         E N E add add
         E S E add add
         S S E add add
         S S W add add
         W S W add add
         W N W add add
         N N W add add]
    (b) [N E add S E add S W add N W add]
    (r) [N E S W]
    (q) [N E S W N E add S E add S W add N W add]
    (k) [N E S W N E add S E add S W add N W add]
    (.) []
>> def

Document UI

In addition to the text UI, PSChess will show a page after each and every move.

When it will be working on an actual printer, a page will be printed after each and every move.

Drawing

All pieces are drawn in a vector format on a 20x20 grid.

/PiecesPathsDict
<<
    /m { moveto } bind def
    /l { lineto } bind def

    /p { newpath SQUARE_SIZE 2 div SQUARE_SIZE 2 div 4 0 360 arc closepath }

    /r { newpath 5 15 m 7 15 l 7 13 l 9 13 l 9 15 l 11 15 l 11 13 l 13 13 l
         13 15 l 15 15 l 15 11 l 13 10 l 13 3 l 7 3 l 7 10 l 5 11 l 5 15 l
         closepath }

    /n { newpath 12 15 m 14 3 l 6 3 l 10 9 l 6 9 l closepath }

    /b { newpath 14 3 m 12 10 l 10 12 3 -30 30 arc
        10 12 l 10 12 3 80 210 arc 8 10 l 6 3 l closepath }

    /q { newpath 4 12 m 8 10 l 10 15 l 12 10 l 16 12 l 12 3 l 8 3 l closepath }

    /k { newpath 8 3 m 5 9 l 9 9 l 9 11 l 7 11 l 7 13 l 9 13 l 9 15 l 11 15 l
        11 13 l 13 13 l 13 11 l 11 11 l 11 9 l 15 9 l 12 3 l closepath }

    /. {}
>> def

Evaluation Function

Each board configuration can be evaluated. High positives values indicate that the configuration is best for white. Conversely, low negative values indicate that configuration is best for black.

PSChess implements the simplified evaluation function from Tomasz Michniewski.

In short, all pieces have an intrinsic value + a positional value, depending on where they stand on the board.

Intrinsic values:

P = 100
N = 320 # knight
B = 330
R = 500
Q = 900
K = 20000

Positional value of white knights:

-50,-40,-30,-30,-30,-30,-40,-50,
-40,-20,  0,  0,  0,  0,-20,-40,
-30,  0, 10, 15, 15, 10,  0,-30,
-30,  5, 15, 20, 20, 15,  5,-30,
-30,  0, 15, 20, 20, 15,  0,-30,
-30,  5, 10, 15, 15, 10,  5,-30,
-40,-20,  0,  5,  5,  0,-20,-40,
-50,-40,-30,-30,-30,-30,-40,-50,

So, a white knight on a2 is worth 320 - 20 = 300 points.

When computer plays, it considers all his possible moves, and plays the move that will minimize the best human answer to his move (min-max algorithm).

Visual Tests

Running the tests_visual.ps file contains a sample chessboard, iterates through all squares and output PDF files representing all possible moves.