Older Version
Newer Version
GerdIsenberg
Oct 14, 2016
**[[Home]] * [[Engines]] * Mate-in-two**
|| [[image:DietrichPrinz.jpg width="337" height="282" link="http://www.computerhistory.org/chess/full_record.php?iid=stl-431e1a07d45c1&mainImage=1"]] ||~ || **Mate-in-two** (Prinz' program, Robot Chess),
was the very first chess playing program running on a general-purpose computer, developed in [[Timeline#1951|1951]] by [[Dietrich Prinz]] to solve a restricted set of [[https://en.wikipedia.org/wiki/Chess_problem#Types_of_problem|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 [[https://en.wikipedia.org/wiki/Manchester_Mark_1|Manchester Mark 1]], developed at [[University of Manchester]]. ||
|| [[Dietrich Prinz]] with Mate-in-two <ref>[[Dietrich Prinz|Dr. Dietrich Prinz]] loading chess program into a [[Ferranti Mark 1|Ferranti Mark I]] computer, 1955, Courtesy of [[https://en.wikipedia.org/wiki/Getty_Images|Hulton-Deutsch Collection]]/[[https://en.wikipedia.org/wiki/Corbis|CORBIS]], [[http://www.computerhistory.org/chess/main.php?sec=thm-42b86c2029762&sel=thm-42b86c4252f72#%7CDietrich|Dietrich Prinz]] from [[http://www.computerhistory.org/chess/index.php|History of Computer Chess]], [[The Computer History Museum]]</ref> ||~ ||^ || ||~ ||^ ||
[[toc]]
=Description=
The program was described by Prinz in 1952 <ref>[[Dietrich Prinz]] (**1952**). //Robot Chess//. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]]</ref>. It already introduced a [[Piece-Lists|piece-list]] in conjunction with a embedded [[Mailbox|mailbox board representation]], albeit 10*10, since a knight move was composed of two single step moves. [[Move Generation|Move generation]] was done keeping a [[Ply|ply]]-indexed [[Array|array]] of piece-list-index, [[Direction|direction]]- and step-counter. [[Legal Move|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|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 [[Checkmate|checkmake]] and [[Stalemate|stalemate]], and [[Castling|castling]], [[Pawn Push#DoublePush|double pawn push]], [[En passant|en passant]] and [[Promotions|promotions]] were not implemented <ref>[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index21|Chess programs: Prinz]] from [[Alex Bell]] (**1972**). //[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm|Games Playing with Computers]]//. [[https://en.wikipedia.org/wiki/Allen_%26_Unwin|Allen & Unwin]], ISBN-13: 978-0080212227</ref> .
==Control Flow==
This [[https://en.wikipedia.org/wiki/Control_flow_diagram|control flow diagram]] was given by Prinz, to demonstrate the nested [[Iteration|iterative algorithm]] of the [[Mate Search|mate search]]. Each of the four blocks represents one [[Ply|ply]] <ref>[[Dietrich Prinz]] (**1952**). //Robot Chess//. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]]</ref>:
|| {{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.}} ||
[[code]]
▼ ┌─────◄───────────┐
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 │ │
│ └─────►─────────────────┘ │
└────────►───────────────────────┘
[[code]]
==Copy-Make==
The code of each block is shared, ply-indexing appropriate data structures of the magnetic drum within a [[Copy-Make|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|side to move]], and [[Make Move|makes the move]] to update the board accordantly for the next ply level.
=Performance=
One memory line of the Mark 1 [[https://en.wikipedia.org/wiki/Williams_tube|Williams-Kilburn tube]] main [[Memory|memory]] had 20 [[Bit|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:
> [[image:http://webchess.freehostia.com/diag/chessdiag.php?fen=5Kbk/6pp/6P1/8/8/8/8/7R%20w%20-%20-&size=medium&coord=yes&cap=no&stm=yes&fb=no&theme=classic&color1=E3CEAA&color2=635147&color3=000000 caption="5Kbk/6pp/6P1/8/8/8/8/7R w - -"]]
=See also=
* [[El Ajedrecista]] by [[Leonardo Torres y Quevedo]]
* [[History|History of Computer Chess]]
* [[Mater]]
* [[Tihamér Nemes#Machine|Nemes' Chess Machine]] by [[Tihamér Nemes]]
=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 [[https://en.wikipedia.org/wiki/B._V._Bowden,_Baron_Bowden|Bertram Vivian Bowden]] (editor), [[http://www.computinghistory.org.uk/cgi-bin/sitewise.pl?act=det&p=10719|Faster Than Thought]], a symposium on digital computing machines
* [[Alex Bell]] (**1972**). //[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm|Games Playing with Computers]]//. [[https://en.wikipedia.org/wiki/Allen_%26_Unwin|Allen & Unwin]], ISBN-13: 978-0080212227
=External Links=
* [[https://en.wikipedia.org/wiki/First_video_game#1947.E2.80.931958:_Chess|First video game - 1947–1958: Chess, from Wikipedia]]
* [[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index21|Chess programs: Prinz]] from [[Alex Bell]] (**1972**). //[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm|Games Playing with Computers]]//. [[https://en.wikipedia.org/wiki/Allen_%26_Unwin|Allen & Unwin]], ISBN-13: 978-0080212227
* [[http://www.computer50.org/kgill/mark1/sale.html|Ferranti Mark 1 Sales Literature]] (d) PROBLEMS OF LOGICAL STRUCTURE, August 1952, from [[http://www.computer50.org/|Computer 50 - The University of Manchester Celebrates the Birth of the Modern Computer]]
* [[http://www.macalester.edu/psychology/whathap/ubnrp/intelligence05/MMhistory.html|The “Modern” History of Artificial Intelligence and Programs]] from [[http://www.macalester.edu/academics/psychology/whathap/ubnrp/intelligence05/index.html|Neuroscience Of Intelligence]]
* [[http://chesspuzzles.com/mate-in-two|Mate in Two Problem | Chess Puzzles!]]
=References=
<references />
=What links here?=
[[include page="Mate-in-two" component="backlinks" limit="20" ]]
**[[Engines|Up one level]]**