Mater

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Mater

Mater,
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 [2]. It was an early pioneering attempt in finding forced checkmates, employing "Artificial Intelligence" rather than "Brute-Force" [3]. 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.


Abstract

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 checkmating combinations 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.'s killer 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].

Namesake

See also

Publications

External Links

References

  1. One of four extant brass astrolabes manufactured by the workshop of Georg Hartmann in Nuremberg in 1537. This one part of the Scientific Instruments Collection of Yale University's Peabody Museum of Natural History, Yale's Hartmann astrolabe.jpg - Wikimedia Commons
  2. George Baylor in All Remembrance of Herbert A. Simon
  3. Max Bramer (1982). Finding Checkmates. Computer & Video Games, Spring 1982, pdf hosted by Mike Watters
  4. George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
  5. Herbert A. Simon, Peter A. Simon (1962). Trial and Error Search in Solving Difficult Problems: Evidence from the Game of Chess. Behavioral Science, Vol. 7, No. 4, pp. 425-429
  6. Allen Newell, N. S. Prasad (1963). IPL-V Chess Position Program. Internal Memo No. 63, Carnegie Mellon University
  7. Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. p. 26
  8. "this (Move ordering) is an attempt to clip unnecessary proliferations in the move tree: if there is a "killing" reply to a checking move, further analysis of that checking move would seem futile" from 4. The Executive and Heuristics of Search in George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
  9. "This is the minimax assumption: namely that the opponent will make his strongest reply at every opportunity. McCarthy.'s killer heuristic (see Kotok, 1962) assumes that a killing reply to one checking move may be a killing reply to other checking moves and thus should be looked at first" from 4. The Executive and Heuristics of Search in George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
  10. Alan Kotok (1962). Artificial Intelligence Project - MIT Computation Center: Memo 41 - A Chess Playing Program. pdf
  11. Reuben Fine (1952). The Middlegame in Chess. McKay
  12. r1bk2nr/p2p1pNp/n2B4/1p1NP2P/6P1/3P1Q2/P1P1K3/q5b1 w - - 0 1 ; Fine 1952, chess/BWTC.PGN at master · wspeirs/chess · GitHub
  13. 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.
  14. r1b2qrk/pp3p1p/4pPpQ/8/8/5N2/P4PPP/3R2KR w - - 0 1 ; Fine 1952, chess/BWTC.PGN at master · wspeirs/chess · GitHub
  15. George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences - Processing Speed
  16. MATER === A simple Mate Searching Program by José Antônio Fabiano Mendes, CCC, January 24, 2001

Up one Level