https://seriot.ch/projects/pschess.html

seriot.ch

About | Projects | Trail

PSChess - A Chess Engine in PostScript

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:

[pschess]

Limitations

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

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 agaist GhostScript, a
PostScript interpreter.

I've started working on step 5 (see Programming in PostScript but I'm
not totally sure yet about the actuably feasibility.

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:

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

[pschess]