Alen Shapiro

From Chessprogramming wiki
Jump to: navigation, search

Home * People * Alen Shapiro

Alen David Shapiro,
a British computer scientist, who as student of Donald Michie at Department of Machine Intelligence at University of Edinburgh researched on decision tree algorithms and decision tree learning applied to chess. Alen Shapiro and Tim Niblett, another of Michie's students, adopted Ross Quinlan's Iterative Dichotomiser 3 (ID3) algorithm for processing complex data [1] for other employment at the chessboard, while they overcame [2] its disadvantage that it yielded massively unwieldy and incomprehensible decision-rules with structured induction, an interactive regime for generating machine-executable decision rules and configuring them into transparent concept-hierarchies. Niblett and Shapiro tested ID3 on the endgame of KPK, and found that decision trees generated by the algorithm 100% accurate.


In 1979/80, Alen Shapiro worked with Ivan Bratko and Zdenek Zdrahal on Pattern Recognition applied to Chess. In fact they used Bitboards, called cellular 8x8 arrays, to implement their Cellular logic processing emulator for chess (CLESS) [3] . CLESS used three kinds of instructions to recognize simple and more complex chess patterns:

  1. bitwise boolean operations without any interactions between squares
  2. shifts as expand instructions
  3. fill-like propagation instructions, internally using the first two kinds of instructions and conditions in loops

Chess Endgames

Quote by Maarten van Emden in I remember Donald Michie [4]:

In 1980 I spent another summer in Edinburgh as a guest of Donald Michie. Since the low point of 1975, thanks to assiduous and inventive joint pursuit of funding possibilities by Donald and Jean, the Machine Intelligence Research Unit was alive with work focused on chess endgames. There were students, including Tim Niblett and Alen Shapiro. Danny Kopec was there, perhaps formally as a student, but de facto as the resident chess consultant. Ivan Bratko visited frequently. Alen was the administrator of the dream computing environment of that time: a small PDP-11 running Unix. 

Structured Induction

from computer chess: Information from [5][6]:

In addition to purely factual discoveries, computer programs could help the chess expert fill the gaps of which codified chess knowledge is now seen mainly to consist. Knowledge-directed programs can support his endeavours to outline the missing framework and by semi-automatic generation of descriptions from expert-supplied examples to fill empty slots in the framework as it takes shape. Using a technique of Alen Shapiro and Timothy Niblett known as 'structured induction', Shapiro was able to generate a complete human-readable codification for adjudicating positions in the king-pawn–king-rook ending (pawn's side to move, pawn on a7) where none pre-existed. A side benefit subsequently extracted from this phenomenon was endowment of the program with the ability to document its own adjudications on demand with explanatory notes.
In the above-mentioned work the induction process was fuelled by hand-supplied examples. In some other cases success has been reported where the examples have been quarried by the program itself from large pre-computed databases. A recent de novo synthesis of knowledge in clinical cardiology by Ivan Bratko and colleagues employed just such an alternation between
 (i) exhaustive derivation of brute facts from a logical model and
 (ii) induction from these of an operational theory.
Sparked initially by the chess work, application is beginning to place emphasis on factual compilations as raw materials for automating the codification of new knowledge as a commercial product. The need to better understand the cognitive invariants with which the designer of codification languages must now come to terms is also leading to closer involvement of professional students of mind. 

Structured Induction Expert System [7]

AI as Sport

Quote by John McCarthy from AI as Sport [8][9]:

Besides AI work aimed at tournament play, particular aspects of the game have illuminated the intellectual mechanisms involved. Barbara Liskov demonstrated that what chess books teach about how to win certain endgames is not a program but more like a predicate comparing two positions to see if one is an improvement on the other. Such qualitative comparisons are an important feature of human intelligence and are needed for AI. Donald Michie, Ivan Bratko, Alen Shapiro, David Wilkins, and others have also used chess as a Drosophila to study intelligence. Newborn ignores this work, because it is not oriented to tournament play. 

Selected Publications

[10] [11]

External Links


  1. Ross Quinlan (1986). Induction of Decision Trees. Machine Learning, Vol. 1, No. 1
  2. D. Michie CV
  3. Zdenek Zdráhal, Ivan Bratko, Alen Shapiro (1981). Recognition of Complex Patterns Using Cellular Arrays. The Computer Journal, Vol. 24, No. 3, pp. 263-270
  4. I remember Donald Michie (1923 – 2007) « A Programmers Place by Maarten van Emden, June 12, 2009
  5. Title: Chess End-Game - King+Rook versus King+Pawn on a7
  6. Mario Marchand and Mostefa Golea (1993). A Constructive Algorithm for Neural Decision Lists. University of Ottawa, from World Congress on Neural Networks: Proceedings of the 1993 Annual Meeting of the International Neural Network Society, vol. 3, pp. 560-563, Hillsdale, NJ: Erlbaum Associates. pdf
  7. Alen Shapiro (1987). Structured Induction in Expert Systems. Turing Institute Press in association with Addison-Wesley Publishing Company, Workingham, UK. ISBN 0-201-178133
  8. John McCarthy (1997). AI as Sport. Science, Vol. 276
  9. AI as Sport by John McCarthy
  10. ICGA Reference Database (pdf)
  11. dblp: Alen Shapiro
  12. UCI Machine Learning Repository: Chess (King-Rook vs. King-Pawn) Data Set
  13. Dap Hartmann (1988). Alen D. Shapiro: Structured Induction in Expert Systems. ICCA Journal, Vol. 11, No. 4
  14. Dheeru Dua, Efi Karra Taniskidou (2017). UCI Machine Learning Repository. University of California, Irvine, School of Information and Computer Science

Up one level