CAPS
[ Spherical Cap [1] CAPS, (Chess as Problem Solving, CAPS-II)
Hans Berliner’s experimental chess program which was subject of his 1974 Ph.D. thesis Chess as Problem Solving: The Development of a Tactics Analyser at Carnegie Mellon University [2], further eloborated at the Advances in Computer Chess 1 conference [3], and, along with B*, in a Panel on Computer Game Playing [4]. CAPS is a selective, knowledge driven depth-first alpha-beta searcher in the domain of chess tactics. A position is represented as vector of 1040 words of information, including the list of generated pseudo-legal moves, kept on a stack of up to 20 ply.
CAPS-II
CAPS-II was tested on many middle-game chess tactics problems from standard textbooks on chess. It played a few complete games of chess. In both these modes it ran with a maximum depth of 10 ply. CAPS-II did not do too well in the games, since it had little positional knowledge, and more importantly the tactics mechanisms were still not completed, causing it to make occasional blunders which would wipe out whatever good it had achieved earlier. However, it did quite well on the tactics problems such as Reinfeld’s Win at Chess [5].
Refutation Description
While visiting a node, CAPS determines attack information, and whether pieces are completely or partial en prise or overprotected, are pinned, or may be source of a discovered attack, and further collects a so called Refutation Description of expandable sets ( bitboards and piece-sets) of moving and captured pieces, their source- and target squares, and appropriate paths of sliding pieces involved, associated with the full qualified moves (piece, from, to, captured piece if any) along the current search line. The description of the six sets of the Refutation Description is given from the Advances in Computer Chess 1 paper [6]:
- RPCS -
is a bit-vector which has bits representing names of pieces. The name bit <code>of the piece that moved to produce this node is set in this vector.
- RSQS -
is a bit-vector with bits representing squares on the board. The bit corresponding to the destination square of the move that produced this node is set in RSQS.
- RPATH -
is a bit-vector with bits representing squares on the board. The bit for any square across which a sliding piece moved in making the made move is set in RPATH. If the move was a non-capture pawn move, then all squares over which it passed including the destination also have bits set for them.
- RTGTS -
is a bit-vector with bits representing names of targets. A comparison is made of BEST for this node with BEST one ply previously. Any squares which are now named as containing material targets, but were not mentioned in the previous BEST, have bits set for the name of the piece on this square to indicate that this threat was created by the last move.
- TGTSQS -
is a bit-vector with bits representing squares on the board. For any RTGTS detected as above, bits are set in TGTSQS for the corresponding squares.
- TPATH -
is a bit-vector with bits representing squares on the board. For any TGTSQS detected as above, if a piece that has an ATTACKING function on this square is a sliding piece, then all the intervening squares have bits set for them in TPATH.
Causality Facility
While classical depth-first searchers may perform the killer heuristic, or may analyze the backed-up principal variation for refutations, i.e. to move or defend any captured piece, or capture or pin any capturer, or block the path of any moving piece, CAPS’ refutation description allows for much more complete understanding of a set of consequences, not only restricted to the PV. The Causality Facility interprets the refutation descriptions and tries to determine tactical causes and goals to control a set of move generators for possible goal transitions, and allows pruning of large sub-trees. The facility may further execute a null move to determine whether a suspected move was responsible for a bad position or not.
Method of Analogies
Once a move was determined as in fact bad, it is possible to posit a Lemma along with its environment of the refutation description — this being knowledge that a certain move will be bad as long as the described environment does not change. With this knowledge, any proposed move may be looked up in the Lemma file and if it has been previously cataloged, the program may determine if the current position contains any essential changes from the Lemma environment which might make the move succeed. It is important to note that should it be decided to try the move, and should it again fail, that it would now be possible to generalize the Lemma to include the union of the two environments, thus making it stronger. In a somewhat similar way, it is possible to generalize about the movements of a single piece, if more than one Lemma exists with respect to its moves. Lemmas are also posited about winning moves. Whenever a move is suggested at some future point in the search, the lemma file is first examined to determine if a lemma exists about this move and if the partial board description matches. If so, the result of the move is assumed known and the search can be foregone. A similar system has been described by Georgy Adelson-Velsky, Vladimir Arlazarov and Mikhail Donskoy [7] [8].
Quotes
Hans Berliner on CAPS-II in his Oral History, March 2005 [9]:
See also
Publications
- Hans Berliner (1973). Some Necessary Conditions for a Master Chess Program. 3. IJCAI 1973
- Hans Berliner (1974). Chess as Problem Solving: The Development of a Tactics Analyser. Ph.D. thesis, Carnegie Mellon University
- Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program. Advances in Computer Chess 1
- Hans Berliner, Richard Greenblatt, Jacques Pitrat, Arthur Samuel, David Slate (1977). Panel on Computer Game Playing. 975-982 5. IJCAI 1977, pdf
- Editor (1979). Chess Ratings from Problem Solving. Personal Computing, Vol. 3, No. 12, pp. 77 » Chess Problems, Compositions and Studies
Forum Posts
- Re: Method of Analogies?? by Steven J. Edwards, CCC, May 29, 1998
- Re: Symbolic: Status Report 2007.04.25 by Steven Edwards, CCC, April 26, 2007 » Symbolic
External Links
Caps
- Caps (disambiguation) from Wikipedia
- CAPS entreprise - many-core programming
- Caps lock from Wikipedia
- Calcyphosin (CAPS gene) from Wikipedia
- Computer Animation Production System - Wikipedia
- Java Caps from Wikipedia » Java
- Problem solving from Wikipedia
Cap
References
- ↑ An example of a spherical cap by Pbroks13, October 2008, Spherical cap from Wikipedia
- ↑ Hans Berliner (1974). Chess as Problem Solving: The Development of a Tactics Analyser. Ph.D. thesis, Carnegie Mellon University
- ↑ Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program. Advances in Computer Chess 1
- ↑ Hans Berliner, Richard Greenblatt, Jacques Pitrat, Arthur Samuel, David Slate (1977). Panel on Computer Game Playing. 975-982 5. IJCAI 1977, pdf
- ↑ Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program. Advances in Computer Chess 1
- ↑ Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program. Advances in Computer Chess 1
- ↑ Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium pp. 129-135
- ↑ Method of Analogies?? by Bruce Cleaver, CCC, May 29, 1998
- ↑ Oral History of Hans Berliner, Interviewed by: Gardner Hendrie, Recorded: March 7, 2005, The Computer History Museum, pdf, pp. 25.