This page is based on the description of Mater by George Baylor and Herbert Simon, 1966, A chess mating combinations program[4]:
The program reported here is not a complete chess player; it does not play games. Rather, it is a chess analyst limited to searching for checkmatingcombinations in positions containing tactical possibilities. A combination in chess is a series of forcing moves with sacrifice that ends with an objective advantage for the active side. A checkmating combination, then, is a combination in which that objective advantage is checkmate. Thus the program described here - dubbed MATER - given a position, proceeds by generating that class of forcing moves that put the enemy King in check or threaten mate in one move, and then by analyzing first those moves that appear most promising.
History
The original mating combination program, as conceived by Herbert Simon and his son Peter Simon in 1962 [5], was a hand simulation setting forth a strategy of search. It discovered mating combinations in 52 of the 129 positions collected in Fine's chapter of the mating attack from The Middlegame in Chess. Newell's and Prasad's IPL program [6], which could set up a chessboard, recorded positions, generated and made moves and testing their legality, was base of Mater I and in 1964 the revised Mater II programs. According to Monroe Newborn, Mater was ported to Fortran and incorporated into Cooper-Kozdrowicki program by Dennis Cooper and Ed Kozdrowicki[7]:
MATER is written by George Baylor and Simon in FORTRAN. It is able to search to great depths for checkmates. MATER is presently part of the Cooper-Kozdrowicki program. While MATER is an interesting program in its own right, the opportunity to checkmate one's opponent plays a relatively small computational part of the game of chess, and its inclusion in the Cooper-Kozdrowicki program does not seem to add measurably to the program's strength.
Mater I
Only check giving moves were generated in Mater I for the attacking side and check evasions for the defending side, for each ply level put into a try-list. For the attacker, the list is ordered by the fewest-reply heuristic, highest priority goes to moves with the fewest number of legal replies, while checking moves with more than four legal replies are pruned entirely. Ties are broken by giving priority to double checks and then to checks with no capturing replies. Search only continues down a particular path so long as the opponent's mobility is on the decline, which implies a maximum search depth of 9 plies. The defender's side considers captures in MVV/LVA order first, followed by king moves and interpositions. In A chess mating combinations program, the beta-cutoff was mentioned as "killing reply" [8], also with a footnote [9] on McCarthy.'skiller heuristic referring Alan Kotok's 1962 paper [10], covering alpha-beta. Reuben Fine's position from The Middlegame in Chess served as one example of Mater's ability [11][12].
Mater II
At its first level of search, Mater II also generates moves threatening mate in one. After generation and trying checking moves without success, but triggered after collecting useful informations of "nearly" mate with only one legal reply, Mater II considers none checking moves which put additional pressure to the enemy king's sector, that is moves which directly or indirectly (x-ray) attack squares around the king. In this respect it resembles what Adriaan de Groot has called a "sample variation" [13], a kind of trial balloon sent up for the express purpose of gathering information to direct subsequent investigations. A further condition to finally add the move into the try-list is that after the move is internally made followed by a defender's null move, the resulting position is mate in one. Now, the defender's move ordering heuristic needs to prefer moves that defend the mating square. Fine's diagram 97 [14] was given as example of the abilities of Mater II.
Board Representation
Mater was written in IPL V with its primary data structure of a list, and kept lists with a header (name) and attribute-value pairs for each square and piece to represent the board, where values for piece and square attributes are addresses (cells) of lists again, yielding in an extensive network of relations among squares and pieces:
Name
Attribut
Value
H1
Man on square
M8
North
H2
West
G1
WNW
F2
NW
G2
NNW
G3
...
...
...
M8
Man on what square
H1
Type of man
Rook
Color of man
White
Move directions
list of directions
Capture directions
list of directions
...
...
...
Move Generation
In A chess mating combinations program, Baylor and Simon further elaborate on move generation, with two tacks, corresponding to a one-many or many-one approach. In trying to find all checking moves, one could either radiate out from the enemy king, and for each square, search for a piece that can get there and check (one-many), or converge from the squares along the move directions of each attacking piece onto the enemy king's square (many-one). If there are many pieces on the board, the former tends to be more effective, if few, the latter.
Processing Speed
Mater was written in an interpretive language IPL, without any attempts to provide a special machine-language representation for primitive board manipulation. The most difficult mates, requiring the examination of about 100 positions, were achieved in about 3 minutes on an IBM 7090[15].
^Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam, advisor Géza Révész; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6.
a chess mating combinations program, developed in the mid 60s by George Baylor and Herbert Simon, which was subject of Baylor's Masters thesis at Carnegie Mellon University [1]. It was an early pioneering attempt in finding forced checkmates, employing "Artificial Intelligence" rather than "Brute-Force" [2]. Only moves which either put the enemy king in check (Mater I), or threaten mate in one (Mater II) were generated for the attacking side, searching those moves first which leave the minimum number of defensive replies, to eventually reduce the defender's mobility to zero.
Table of Contents
Abstract
This page is based on the description of Mater by George Baylor and Herbert Simon, 1966, A chess mating combinations program [4]:History
The original mating combination program, as conceived by Herbert Simon and his son Peter Simon in 1962 [5], was a hand simulation setting forth a strategy of search. It discovered mating combinations in 52 of the 129 positions collected in Fine's chapter of the mating attack from The Middlegame in Chess. Newell's and Prasad's IPL program [6], which could set up a chessboard, recorded positions, generated and made moves and testing their legality, was base of Mater I and in 1964 the revised Mater II programs. According to Monroe Newborn, Mater was ported to Fortran and incorporated into Cooper-Kozdrowicki program by Dennis Cooper and Ed Kozdrowicki [7]:Mater I
Mater II
Board Representation
Mater was written in IPL V with its primary data structure of a list, and kept lists with a header (name) and attribute-value pairs for each square and piece to represent the board, where values for piece and square attributes are addresses (cells) of lists again, yielding in an extensive network of relations among squares and pieces:Move Generation
In A chess mating combinations program, Baylor and Simon further elaborate on move generation, with two tacks, corresponding to a one-many or many-one approach. In trying to find all checking moves, one could either radiate out from the enemy king, and for each square, search for a piece that can get there and check (one-many), or converge from the squares along the move directions of each attacking piece onto the enemy king's square (many-one). If there are many pieces on the board, the former tends to be more effective, if few, the latter.Processing Speed
Mater was written in an interpretive language IPL, without any attempts to provide a special machine-language representation for primitive board manipulation. The most difficult mates, requiring the examination of about 100 positions, were achieved in about 3 minutes on an IBM 7090 [15].Namesake
See also
Publications
External Links
References
What links here?
Up one Level