Extracts from the report of a project done by Y.P.K. Teoh in 2000-1
This project attempts to emulate human thought by using artificial intelligence to annotate chess games.
The annotation module comprises of two logical phases. The first phase involves intensive computation on the search-tree of chess positions and reveals the short-term, tactical points. The second phase is more of a black art: the program tries to recognise strategic points by comparing the game with the program's bank of special cases.
We can enhance the performance of the program in two ways. Firstly, a more powerful processor will compute deeper into the search-tree; secondly a more comprehensive collection of special-cases will better mimic human experience. The challenge remains to integrate and translate these diverse results into a form intelligible to the human reader.
The project has successfully implemented a program that produces remarkably good chess annotations, making use of both 'brute-force' search-tree techniques and other intuitive methods. The results obtained are encouraging and suggest that a similar framework can be applied to a program that plays chess.
Table of Contents
- 1. The Annotation Process
- 1.1 Project Scope
- 1.2 Previous Work on Chess Computing
- 1.3 Human Intelligence in the Annotation Process
- 1.4 Components of the Annotation Process
- 1.5 Using Crafty as a Platform
- 2. During-Game Analysis
- 2.1 Search Tree Analysis
- 2.2 Sieving Out Points of Interest
- 2.3 Obviousness of a Move
- 2.4 Identifying Good and Bad Moves
- 2.5 Miscellaneous Comments from Position Scores
- 3. Post-Game Analysis
- 3.1 Identifying Trends Relating Material
- 3.2 Identifying Trends Using Chessmap Analysis
- 3.3 Identifying Trends Using Piece History
- 3.4 Analysing Position Scores with Benefit of Hindsight
- 4. Implementation
- 4.1 Coding Scheme
- 4.2 Formatting the Output
- 5. Discussion and Conclusion
Future Exploration and Development
Many aspects of this project have been simplified to save on computational costs. Some of these are worth exploring and refining in theory, so that they can be implemented in practice when the hardware permits.
Fitting the Annotation Model into a Generic Chess Engine
As described in section 1.5, 'annotate.c' makes use of two other Crafty modules, 'iterate.c' and 'evaluate.c'. The modified tests in 'evaluate.c' are incorporated into 'annotate.c', so the program can function without 'evaluate.c'. The program, however, still needs an engine module, which must be able to do the following things:
The depth-weighted unobviousness score x* (described in section 2.3) is an attractive alternative to the plain unobviousness score x, because it offers discrimination to depth-wise unobviousness. The extra d5 and d7 terms require additional computation of the Crafty engine, which slows down the performance. We can extract the d3, d5, d7 and d9 terms in the same pass, although this requires low-level modification to the engine code
- The algorithm used to construct the chessmaps (described in section 3.2) is a simplified version. The original version devised by Kieran Greer takes into account some subtle factors. For example, when calculating which side controls a square, the computer bears in mind the relative values of the pieces attacking the square, as well as any ensuing capture sequence. The full algorithm is complex, but the information encoded in the chessmaps is richer and more meaningful.
- Intensive studies of chess theory have made an exact science of the opening and endgame. There are books on openings that analyse all playable variations up to 20 moves deep. Likewise, computers have been used to generate endgame databases. (Presently, there are databases that can play flawlessly any endgame with five pieces or less.) By incorporating such opening books and endgame databases into the annotation module, the program can generate comments that are more precise; it will also save computation time by not having to generate opening and endgame comments from scratch.
- All the thresholds in the annotation module have been set arbitrarily. A set of thresholds that optimally produce sensible and balanced annotations can only be derived by trial and error.
- Instead of deriving the thresholds by experimentation, we can leave them as variables; this offers customisability to the user. For example, the user can have direct control over the frequency of diagrams, the minimal unobviousness under which all comments are suppressed, etc.
- The during-game phase currently expands the search tree to a depth of nine plies. As an estimate, the computer needs to search at least 13 plies to emulate a seasoned chess player; the world's best players would start taking notice if the computer can search 19 plies. Crafty is in theory capable of calculations to such depths, although the time required will be unfeasibly long.
- Where it is easy to apply technology to upgrade the during-game phase, the development of the post-game phase is less straightforward. Advancement in the special cases can come in the form of quantity or quality. It is easy to build up the number of special cases in annotate.c. Firstly, if it is all right to repeat the comment in the annotation, then a flag bit should be reserved in each 'Annotation' record to reflect if the corresponding move is affected. However, if the comment cannot be repeated, then an index x should be reserved so that its affected move can be stored in the appropriate slot of the 'strategic_comment' array.
A chess program with an engine that does all the above will be able to support the annotation module, after a modest amount of code adjustments.
- Assign a score to any position, using heuristic evaluation functions.
- Execute a search tree analysis, of a specified depth, on a given position.
- Apply a minimax (or variant) algorithm to return the five moves that yield the highest scores, as well as the score of the actual move played in the game.
- Return the main line of each of the six moves.
The Annotation Model as a Framework
The annotation model serves as a framework for future developments. In future, more powerful processors will emerge to boost the computers' performance in the search tree analysis. Historically, most of the advancements in chess computing have been made here; computers will (if not already) surpass humans in brute-force calculations. Therefore isolating the search tree analysis from the special case analysis makes it easy to apply our strengths.
The computer's aptitude in hardcore calculation relieves humans of the jobs that require precision. We can harness the computer's exactness in commentating other sports: the gracefulness of an ice-skater's 'spin-up' may be a function of the roundness of the circle traced out by the arms; the co-ordination of a team of synchronised swimmers can be measured exactly rather than impressionistically.
The main challenge is to emulate the aspect of human intelligence that is less exact in nature - the post-game analysis. It is especially difficult to quantify emotions like psychology and pressure, and as of now human editing of the annotations is still necessary. Newell, Shaw and Simon, three pioneer researchers on artificial intelligence, said: "If one could devise a successful chess machine, one would seem to have penetrated to the core of human intellectual endeavour."
Shortcomings of the Project
The program has a reasonably big collection of tests for special cases. The difficulty in processing these test results is to integrate them as seamlessly as a human, so that they are suitable for human consumption. The program has difficulty co-ordinating such vastly diverse findings even though it has perfectly capable faculties with which to collect them. Analogously, even the human mind is prone to lapses under severe conditions - paradoxes and optical illusions are some examples where the human mind makes fallacious deductions and perceives artefacts.
The art of chess annotation has much scope for creativity. Like a poem or song, which has technical features that can be assessed exactly (like rhyme and rhythm), there are also merits that must be felt. The program is far from being able to feel, and is certainly not ready to inject wit and humour into its annotations. The most glaring shortcoming of this project (and most others on artificial intelligence) is its inadequacy in replacing the human's capacity for spontaneity. For that reason, chess columnists who annotate for a living have little to fear for the time being.
Ultimately the performance of this artificial intelligence project has to be measured against the human mind. The program branches search trees to a depth of 9 plies, and compares positions with its collection of 150 special cases. An experienced annotator can easily evaluate more than 13 plies and consider thousands of special cases. In this perspective, there is much distance to make up.
A convincing validation of the project's success would be a Turing Test. If a chess columnist generates a piece of annotation and publishes it as his own work without alerting his ardent readers, then that would be evidence of success. However, even if the novice reader is able to gain insights into the game after reading it, then that will also be success in its own right.
A natural conclusion to draw from this project is that computers, being able to use the dual-ideology approach (section 1.2) to annotate chess games, should have comparable results in playing chess. The 'feeling' ideology of chess programming has been forsaken due to its lack of success compared to the 'number-crunching' ideology. However, a marriage of the two might open up a new dimension of computer chess playing.
Players dislike playing computers that never make unsound sacrifices - they like to call a bluff occasionally. Modern chess programs mostly run on the 'number-crunching' framework, and its logic is exact and absolute. By adding a 'feeling' component, we can make the computer exhibit "fuzzy logic." The moves played might no longer be the strongest but at least they will be more human. As such, chess should not be such an exact science - if it were, humans would merely be playing an elaborate form of solitaire.
The dual-ideology approach to annotating chess may well be generalised to applications beyond chess computing. (After all, the pioneers in A.I. had similar intentions when they chose chess as one of the primary fields of research.) We have briefly discussed the parallelisms between the appreciation of chess and other humanly pursuits, and we may one day grasp the very inner workings of human intellect. As the former World Chess Champion, Garry Kasparov said: "If a computer can beat the World Champion, a computer can read the best books in the world, can write the best plays, and can know everything about history and literature and people."
- Rook trapped by friendly king
- Rook centred on the board
- Rook on open file
- Rook on half-opened file
- Rook supporting friendly passed pawn
- Rook blockading enemy passed pawn
- Rook on 7th rank
- Rook on 7th rank hemming in opponent's king
- Rooks connected on 7th rank
- Knight on an outpost
- Knight on an undefended outpost
- Knight on an outpost unopposed by
- Knight blockading enemy's central pawn
- Knight blockading friendly central pawn
- Queen centred on the board
- Queen-rook battery on the 7th rank
- Queen is strong
- Queen is offside from rest of the action
- Bishop trapped by enemy pawns
- Bishop centred on the board
- Bishop is mobile
- Bishop blockading enemy's central pawn
- Bishop blockading friendly central pawn
- Bishop with friendly pawns on same
- Bishop fianchettoed
- General Positional Comments
- First rank cleared for movement of major pieces
- Weak back rank
- Blocked centre pawn
- Passed pawn
- Passed pawn blockaded by enemy
- Connected passed pawns
- Connected and advanced passed pawns
(beyond 5th rank)
- Isolated pawn
- Isolated pawn on a half-opened file
- Weak pawn / very weak pawn
- Doubled pawns
- Doubled passed pawns
- Candidate passed pawn
- Hidden passed pawn
- Kingside pawn defect
- Queenside pawn defect
- Pawn majority on either wing
- Pawn advance weakens square
- Single bishop v single knight
- Unopposed bishops pair
- Bishops pair v knights pair
- Bishops pair exploiting extra pawn
against knights pair
- Bishop exploiting extra pawn against
- Knight preferred to bishop
- Bishop preferred to knight
- Drawn rooks endgame
- Weak kingside light-coloured squares
- Weak queenside light-coloured squares
- Weak central light-coloured squares
- Weak kingside dark-coloured squares
- Weak queenside dark-coloured squares
- Weak central dark-coloured squares
- Concentration on the kingside defensive zone
- Concentration on the queenside offensive zone
- Concentration on the kingside defensive zone
- Concentration on the queenside offensive zone
- Series of defensive moves
- Series of offensive moves
- Switch flank to the kingside
- Switch flank to the queenside
- Move pins a knight
- Move unpins a pinned knight
- Knight on a knight tour to a destination square
- Knight forks two or more enemy pieces
- Knight manoeuvres to attempt to fork
- Bishop is inactive
- Bishop is suddenly active
- Bishop has hidden potential
- Bishop realises hidden potential
- Bishop pins enemy knight
- Useful light-coloured bishop prevented from being exchanged
- Useful dark-coloured bishop prevented from being exchanged
- Rook is inactive
- Rook is suddenly active
- Rook has hidden potential
- Rook realises hidden potential
- Rook pins enemy knight
Back to the Computers and Chess page.
Updated June 2001