Mate-in-two

From Chessprogramming wiki
Jump to: navigation, search

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.

Description

The program was described by Prinz in 1952 [2]. It already introduced a piece-list in conjunction with a embedded mailbox board representation, albeit 10*10, since a knight move was composed of two single step moves. Move generation was done keeping a ply-indexed array of piece-list-index, direction- and step-counter. Legal move detection was implemented somewhat inefficient - the king not to move was treated as a super-piece, and with the same technique as used in move generation, the board was scanned from the king's square looping over all directions and steps, to look whether an appropriate opponent piece to move may capture. The iterative search process took up to four plies 0, 1, 2, 3. A mate in 2 was found, if after a ply-0-move, all ply-1-moves could be replied by at least one mate-in-one move, that is leave no legal moves at ply-3. There was no distinction between checkmake and stalemate, and castling, double pawn push, en passant and promotions were not implemented [3] .

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

See also

Publications

External Links

References

  1. Dr. Dietrich Prinz loading chess program into a Ferranti Mark I computer, 1955, Courtesy of Hulton-Deutsch Collection/CORBIS, Dietrich Prinz from History of Computer Chess, The Computer History Museum
  2. Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium
  3. Chess programs: Prinz from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
  4. Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium

Up one level