Mateintwo

Home * Engines * Mate-in-two

Dietrich Prinz with Mate-in-two [1] Mate-in-two (Prinz’ program, Robot Chess),

was the very first chess playing program running on a general-purpose computer, developed in 1951 by Dietrich Prinz to solve a restricted set of mate-in-two problems. It ran on a Ferranti Mark 1, the world’s first commercially available general-purpose electronic computer, which was based on the Manchester Mark 1, developed at University of Manchester.

Control Flow

This control flow diagram was given by Prinz, to demonstrate the nested iterative algorithm of the mate search. Each of the four blocks represents one ply [4]:

Entry 1 correspondents to the case of the first move in a turn with all the counters set to their initial value. Entry 2 is the general case of a move following a previous move of this same turn. Exit 3 indicates that a legal move has been found; exit 4 that the position supplied to the turn has been exhausted before such a move has been found.


       ▼  ┌─────◄───────────┐
      1│  │2                │
    ┌────────┐              │
    │  W  1  │              ▲
    └────────┘              │
      3│  │4   No solution  │
       ▼  └─────►           │
       │  ┌─────◄───────────~─────┐
      1│  │2                │     │
    ┌────────┐              │     │
    │  B  1  │              ▲     ▲
    └────────┘              │     │
      3│  │4   Solution     │     │
       ▼  └─────►           │     │
       │  ┌─────◄───────────~─────~─────┐
      1│  │2                │     │     │
    ┌────────┐              │     │     │
    │  W  2  │              ▲     ▲     ▲
    └────────┘              │     │     │
      3│  │4   Avoidable    │     │     │ 
       ▼  └─────►───────────┘     │     │
      1│                          │     │     
    ┌────────┐                    │     │
    │  B  2  │                    ▲     ▲
    └────────┘                    │     │
      3│  │4   Mate               │     │
       │  └─────►─────────────────┘     │
       └────────►───────────────────────┘

Copy-Make

The code of each block is shared, ply-indexing appropriate data structures of the magnetic drum within a copy-make approach. At entry 1 both the piece-list (A-tube) and square-list (B-tube) are copied to the magnetic drum, indexed by ply-index. After initializing piece-list-, direction- and step-counters and generating the first move (if any), those updated counters are saved as state for generating the next move to the drum as well. Then, at entry 2, after determining the current ply index when returning from deeper iterations, the board representation as well the state for generating the next move are restored. Consecutively, after generating the next move, the updated generation state is stored for that level again. Exit 3 increments the ply-index and toggles side to move, and makes the move to update the board accordantly for the next ply level.

Performance

One memory line of the Mark 1 Williams-Kilburn tube main memory had 20 bits, one tube 64 lines. 20 bit instructions had an address and an operator part, indexing an array of consecutive lines was done by modifying the address part of the instruction. Most Mark 1 instructions with line operand and implicit accumulator, such as ‘add’, ‘sub’, ‘xor’, ‘and’, ‘or’, and ‘store’ took about 1 ms. As reported by Prinz, the following mate-in-two position took about 15 minutes to solve with his program:

5Kbk/6pp/6P1/8/8/8/8/7R w - -

Publications

Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium
Dietrich Prinz (1953). The Use of General Computers for Solving Logical Problems, in Bertram Vivian Bowden (editor), Faster Than Thought, a symposium on digital computing machines
Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227