seriot.ch

About | Projects | Trail

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.

[2024-11-07] 2 minutes video presented in a rump session at Black Alps cyber-security conference: postscript_1024.m4v

Motivation

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:

You can also play directly in GhostView with:

  1. in main.ps, set USE_GHOSTVIEW to true
  2. gv -scale=2 - (mind the trailing dash)
  3. in GhostView console, type (main.ps) run

Limitations

Project Status

The project can be broken down in five steps:

  1. draw a chess board
  2. implement a user interface so that user can move pieces
  3. implement chess game rules and logic
  4. implement an algorithm so that the computer can play
  5. 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 PSTicTacToe. However, a chess game is far more bigger and demanding. There are 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:

+----------------+
| main.ps        |
+----------------+----------------+-----------------+
| drawing.ps     | logic_tests.ps | visual_tests.ps |
+----------------+----------------+-----------------+
|                  logic_chess.ps                   |
+---------------------------------------------------+
|                  logic_board.ps                   |
+---------------------------------------------------+

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 get 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.

On an actual printer, a page will be printed after each 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.