From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Genie

Genie in Legoland [1]

an early chess program written by Herbert D. Raymond. Genie played the ACM 1971, with wins vs. Schach and Coko III and losses from Chess 3.5 and the runner up play-off from Tech. Genie ran on a SDS 940 [2] , Scientific Data Systems' first machine to support the Berkeley Timesharing System [3] [4] , created by the University of California, Berkeley as part of their Project Genie that ran between 1964 and 1965 as smaller counterpart to MIT's Project MAC.

Genie was a Shannon Type B program with a width of three or four moves, written in Quick Systems Programming Language (QSPL), which was also used for the Community Memory, the first public computerized bulletin board system.


Unknown Raymond Genie vs Schach ACM 1971.jpg

Genie vs Schach [5], Herbert D. Raymond (left?) and Rolf C. Smith? [6], ACM 1971 [7]

[Event "ACM 1971"]
[Site "Chicago USA"]
[Date "1971.08.02"]
[Round "1"]
[White "Genie"]
[Black "Schach"]
[Result "1-0"]

1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O b5 6.Bb3 Nxe4 7.Na3 Bxa3 8.bxa3 d5
9.Re1 Bg4 10.Re3 Bxf3 11.Rxf3 O-O 12.Rf5 g6 13.Rf3 Qd6 14.d3 Nf6 15.Bg5 Ng4
16.Rg3 Nxf2 17.Kxf2 Qxa3 18.Bc1 Qc5+ 19.Kf3 e4+ 20.dxe4 dxe4+ 21.Ke2 Nd4+ 
22.Kf1 Kh8 23.Rg5 Nf5 24.Qd7 Qd6 25.Qxf5 Qd1+ 26.Kf2 e3+ 27.Bxe3 Qxa1 
28.Qe5+ Qxe5 29.Rxe5 Rad8 30.Bc5 Rg8 31.Rd5 Rge8 32.Rxd8 Rxd8 33.Bxf7 Rd2+ 
34.Ke3 Rd7 35.Bd4+ Rxd4 36.Kxd4 c6 37.g4 g5 38.Kc5 h6 39.Kxc6 Kh7 40.c4 1-0


From ACM 1971 Computer Chess Programs (Panel) [8]

This chess-playing program was written in Quick Systems Programming Language (QSPL), a language developed for the SDS 940. Although the code generated by this compiler is rather inefficient, it was decided to use this high level language rather than suffer through assembly level coding. This choice was made considering requirements for rapid program development, ease of maintenance, flexibility, and understandable documentation. The program runs under a time sharing system using a teletype for man-machine communication. The program accepts Postal Chess Notation as input and responds likewise. Additionally, it will print the board when requested and ask for a piece selection for pawn promotion. The user interface also allows for player color selection. The program itself has been developed, so far, in two stages as defined below. Stage one of program development consisted of writing the legal chess support routines and a one move lookahead algorithm for machine move selection. A very blunt approach was taken to create the legal move generators. Upon call to one of the piece move generators (pawn, knight, bishop, rook, queen, king) with an (x, y) board position as input, all legal moves for that type of piece in that position are listed in a table. These move generators use only the current board position (from a table), except for the pawn and king move generators which also refer to the game (move record) table to extract information for en passant captures and castling.
Two other routines, for check and mate, complete the legal move machinery. These latter routines test for check and mate using an input of the color to be tested for those conditions and returning true or false answers.
An opponent's move is checked for legality by taking the (x, y)-from position and calling on the correct piece routine. All legal moves from that position with that piece are checked against the (x, y)-to position of the opponent's move. If no match is found, the move is illegal and a new move is requested (an error message is typed also). If the move matches, then the check routine is called to determine if the opponent has attempted to move into check or has failed to move out of a check. If true, once again an illegal move is signaled. The check and mate routines are then called using the machine's color as an input to advise of check or mate. Legal chess by the opponent thus being assured, it is the machine's turn to play. The machine starts its move selection by scanning the board and generating every move for each of its pieces using the piece move generators. Moves into check are immediately eliminated using the check routine. Then, each of the possible moves is rated by adding values for check on opponent, piece captured, control of center, mobility, development, other king attacks, own king defense, promotion, attacks, and immediate replies. All except the last two are based on that move being evaluated and the current board position. Replies and attacks consist of using the move generators to list every possible reply and every possible second move in a row (two machine moves with no intervening opponent move).
These moves are rated only on the basis of pieces captured (or attacked) and control of the board center. Their values are summed and applied to the rating value of the basic move. A move which checkmates the opponent is tested for first and if found, immediately receives the highest possible rating value and no other rating calculations are made. This first stage program was experimented with to optimize the play by changing piece values, position values, and other variable parameters; recognizing that the program only looked ahead one move. The second stage of program development consisted of adding a recursive routine to look ahead, using the same rating criteria, as far as a set depth and using a set width of move selection. A minimax or alpha-beta algorithm was employed in hopes of getting sufficient cut-offs to be able to increase look-ahead efficiency. No dynamic changes to the width and depth were incorporated. This second stage of development created the program as it exists today. Unfortunately, the combination of a 1.75 microsecond cycle time and the inefficient code generated by the compiler allow only a three or four move look-ahead with a width of three or four without exceeding time constraints. The program does, however, play a quite reasonable game of chess. Immediate future effort will consist of the addition of more sophistication to the move tree machinery; probably in the areas of dynamic width and depth changes and recognition of double moves where one would do. Also, the application of different heuristics to opening, middle, and end games could easily be implemented. 

See also

External Links


Up one Level