HAL

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * HAL

HAL 9000 [1]

HAL, (Heuristic Associative Linear-algorithm, HAL-9000, HAL9000)
an open source chess program by Stephen F. Wheeler, also dubbed HAL-9000 as pun of HAL 9000, the fictional character in Arthur C. Clarke's Space Odyssey series, first appearing in 2001: A Space Odyssey [2] [3]. HAL was written in Turbo Pascal to run under the MS-DOS command line, and was part of Wheeler's Ph.D. research during the late 80s and early 90s, specifically on linear symbolic problem-solving systems and natural language processing.

Header

[4]

*                                                                  *)
(********************************************************************)
(*                                                                  *)
(*                             H A L                                *)
(*                                                                  *)
(*             Heuristic Associative Linear-algorithm               *)
(*             -         -           -                              *)
(*                                                                  *)
(*==================================================================*)
(*                                                                  *)
(*                  C H E S S   P R O G R A M   3                   *)
(*                  -           -               -                   *)
(********************************************************************)
(*                                                                  *)
(*------------------------------------------------------------------*)
(*                                                                  *)
(* Author:  Stephen F. Wheeler, Ph.D.   A.I. Computer Scientist     *)
(*                                                                  *)
(* Language:  Turbo Pascal v6.0                                     *)
(*                                                                  *)
(*------------------------------------------------------------------*)
(*                                                                  *)
(*                                                                  *)
(* Date Written:                September 8, 1990                   *)
(*                                                                  *)
(* Date of Last Revision:       May 25, 2010                        *)
(*                                                                  *)
(* Revisions in This Version:                                       *)
(*                                                                  *)
(* 1)  In Move_Selector Procedure set -INF and +INF for             *) 
(*     re-searches for failed-low and failed-high when Level is < 3.*)
(*                                                       05/15/10   *)
(*                                                                  *)
(* 2)  In EVAL Procedure decremented level variable at P^.LX by 1   *)
(*     and stored it in an LX variable when level of play was < 3.  *)
(*     This corrected the missed checkmate declaration when playing *)
(*     at skill levels 1 and 2.                                     *)                          
(*                                                       05/25/10   *)
(*                                                                  *)
(*                                                                  *)
(*------------------------------------------------------------------*)
(*                  C P 3 V 8 . 9 . 9 . 7 . 2                       *)
(*------------------------------------------------------------------*)
(*                                                                  *)
(*==================================================================*)
(*                                                                  *)
(*        C O M P U T E R   C H E S S   A U T O M A T O N           *)
(*                                                                  *)
(*    THIS PROGRAM UTILIZES THE ITERATIVE-DEEPENING NEGAMAX         *)
(*    FAILSOFT ALPHA-BETA SEARCH ALGORITHM WITH QUIESCENCE, THE     *)
(*    KILLER HEURISTIC AND REFUTATION TABLES.                       *)
(*                                                                  *)
(*==================================================================*)
(*                                                                  *)
(********************************************************************)

Description

User Interface

HAL has a command line interface, and supports an interactive English dialogue between the opponent and itself to receive and report its moves and to receive directives, such as skill level. The directives are given to HAL in the form of English sentences, which can be rather free-form in structure, and will even allow for slight misspellings in certain situations. HAL utilizes the long algebraic notation [5] [6].

Board Representation

HAL's board is represented by an incremental updated 8x8 board, a two-dimensional array of board cells, and a piece-list as array of piece cells indexed by side (1..2) and man index 1..16.

Search

The search algorithm is pure alpha-beta implemented as recursive negamax with fail-soft bounds inside the iterative deepening framework with aspiration windows. Move ordering is improved by the refutation table based on the triangular PV-table, and a sophisticated killer heuristic with up to four killers per ply. Selectivity is due to check extensions and depth limited quiescence search.

Evaluation

Evaluation considers material balance, a material exchange heuristic, and positional heuristic terms for development, king attack, defence, threats, mobility, advancement, captures and checks.

See also

Postings

External Links

References

  1. The famous red eye of HAL 9000, the fictional character in Arthur C. Clarke's Space Odyssey series. Image by Cryteria, October 1, 2010, Wikimedia Commons
  2. Murray Campbell (1997). "An Enjoyable Game": How HAL Plays Chess. in David G. Stork (ed.), Hal's Legacy - 2001's Computer as Dream and Reality. MIT-Press, pdf
  3. An interesting link by Steven Edwards, CCC, March 29, 2004
  4. HAL 9000 by Master Om, Rybka Forum, June 10, 2010 (Download)
  5. HAL-9000.zip/HALDOC.DOC
  6. HAL-9000.zip/CP3.pas

Up one level