Ostrich was the first chess program to compete on a parallel system (ACM 1982). It used eight Data General computers with each screen displaying the parallel computations taking place [2] .
Monty: Maybe David helped Ben on the second one. The second one was held in Chicago, where the Northwestern team lived. Ben had it in his own backyard, so to speak. The second tournament then was a big success, and the third tournament I was back involved in organizing as well. For a number of years, Mittman and I organized these tournaments together. I started competing myself in the Boston tournament, the third tournament.
Q: With Ostrich?
Monty: With Ostrich. Ostrich was not a bad program. It never quite reached the top, but it was not bad. Ben and I organized tournaments year after year. David Levy got involved with some. We organized the ACM tournaments yearly, and in addition we organized world championships every third year. This went on pretty consistently right up until the time that Kasparov played the computer. They’re still having these tournaments, but my interest as a scientist sort of was fulfilled when Kasparov lost to the computer. As a scientist, I would say that that was the end of the experiment.
A win in the following last round game would have given Ostrich a tie for first place in the 1st World Computer Championship. Unfortunately, the program missed the winning move, 35. Rxh6+, as finding it required a search depth of 19-ply, which was beyond its capabilities. It also missed another winning move, 39. Bf5, which required an 11-ply search.
Ostrich, developed by Monty Newborn, was the first chess program to compete on a parallel system. It used eight Data General computers with each screen displaying the parallel computations taking place. Through the 1970s and 1980s, Ostrich competed in five world championships, coming close to winning in 1974.
The early Ostrich did not yet perform iterative deepening, instead the search was controlled by various parameters, such as fan-out or maximum number of moves played at each level with {F1, ..., F10}, two depth parameters Dmin and Dmax, average move time and total time. Dmin determines the minimal depth to the horizon. If depth is still less Dmax, positions either resulting from tactical moves, or with the presence of en prise pieces were extended. Initial guesses of the parameters based on time control were adapted during the course of the game considering time usage and various statistics .
Gamma-Algorithm
The Gamma-algorithm caused certain futile nodes to be considered leaves:
Determine material score at current node P[i]
Compare the score with the material score of the P[best] that follows by making the best move M[best] found so far at node P[i-3]
If the score of P[i] implies that the move sequence of M[1], M[2], M[3] is worse than the move M[best] then stop searching at node P[i]
Processing at the leaf nodes includes the usual evaluation terms dominated by material, but also path-dependent terms by the move sequence from the root to this node, such as bonus for castling or penalties for tempo wasting moves, i.e. moving a piece to a square in two moves to which it could move in one, too early queen moves in the opening, etc.. The static evaluation function consists of thirteen subroutines each corresponding to a basic chess heuristic [15]:
Material. The subroutine which computes the difference between White's and Black's material the greatest single value to the overall scoring function. The pieces have their conventional values.
Material ratio term, which computes whether an even exchange of material has occurred between the top node of the tree and the bottom position being evaluated; a bonus goes to the side ahead in material.
Board control, which is intended to increase one's own mobility and restrict one's opponent's. There is a small bonus for each square controlled, centre squares and squares near the enemy king have the greatest score. 'Control' is defined as the ability of the piece in question to capture a hypothetical enemy piece on that square.
Tempi. Moving the same piece twice in the opening, moving a king or rook before castling, moving a piece back to its immediately previous position and moving to a square in two moves when it could be done in one, all attract penalties.
Early queen moves. These attract a penalty before the eighth move of the game; by which time most minor pieces are developed and the king has castled.
Pawn structure. Advancement of pawns is encouraged and doubled pawns penalised.
King safety. To guard against king-side pressure on the part of the opponent the program encourages its own pieces in its own king-sector.
Passed pawns. The goal is to encourage the advancement and queening of pawns along with trading off the opponent's passed pawns before they become too advanced. A passed pawn receives credit according to its advancement.
Ostrich 81, originally developed by George Arnold and Monroe Newborn at Columbia University in 1971, has participated in seven ACM tournaments and two world championships. Its best result was a second place finish in the 1972 ACM tournament. Ostrich 81 won 3 out of 4 points in qualifying play for this tournament among the three Canadian programs this August.
Ostrich 81 is written in assembly language and requires 32k word of memory to execute. A book of about 1,000 lines helps with the first few moves, when the program leaves the book, various strategies guide its play for the next dozen moves or so. The program carries out an iteratively deepening and variable depth search examining about 20,000 nodes per three minute move. During the last few years, two of Montreal's better chess players, Ilan Vardi and Frank Wang, have helped with the openings.
^ Description 1975 based on Chapter X. Ostrich: A Description of a Chess-Playing Program. in Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y.
a chess program originally developed by George Arnold and Monroe Newborn at Columbia University in 1971, and subsequently by Newborn at McGill University since 1975 [1].
Ostrich was the first chess program to compete on a parallel system (ACM 1982). It used eight Data General computers with each screen displaying the parallel computations taking place [2] .
Table of Contents
Etymology
The program was named Ostrich because of its cowardly "head in the sand when in a crisis" style of play [4] [5].Tournament Play
Ostrich had its debut at ACM 1972 with its best result of a second place finisher. It played the first five World Computer Chess Championships, the WCCC 1974 in Stockholm, the WCCC 1977 in Toronto, the WCCC 1980 in Linz, the WCCC 1983 in New York City, and the WCCC 1986 in Cologne, and 15 ACM North American Computer Chess Championships until ACM 1987, including the ACM 1983 which was simultaneously the Fourth WCCC.Photos & Games
1972
Quote from Oral History of Monty Newborn [8] :
Q: With Ostrich?
Monty: With Ostrich. Ostrich was not a bad program. It never quite reached the top, but it was not bad. Ben and I organized tournaments year after year. David Levy got involved with some. We organized the ACM tournaments yearly, and in addition we organized world championships every third year. This went on pretty consistently right up until the time that Kasparov played the computer. They’re still having these tournaments, but my interest as a scientist sort of was fulfilled when Kasparov lost to the computer. As a scientist, I would say that that was the end of the experiment.
WCCC 1974
Quote from Canadian Chess [9] [10]:ACM 1979
ACM 1982
Description 1975
Ostrich ran on a Data General SuperNOVA computer, and was written in Supernova assembly language [13] [14].Data Structures
Ostrich had a plane 8x8 board with positive and negative numbers for white and black pieces respectively, and zero for empty squares, further a piece list, and multiple other incremental updated data, such as attack and defend maps, a change list, a list of pinned pieces, and pieces en prise. The move list for move generation is shared and controlled by indices kept on the ply-stack recursively.Search
Ostrich searched a tree of variable-length move sequences using Shannon's Type B strategy supplemented by the alpha-beta algorithm. Strict legal move generation, move ordering, re-ordering and plausibility analysis took huge effort, especially at or near the root.Search Control
The early Ostrich did not yet perform iterative deepening, instead the search was controlled by various parameters, such as fan-out or maximum number of moves played at each level with {F1, ..., F10}, two depth parameters Dmin and Dmax, average move time and total time. Dmin determines the minimal depth to the horizon. If depth is still less Dmax, positions either resulting from tactical moves, or with the presence of en prise pieces were extended. Initial guesses of the parameters based on time control were adapted during the course of the game considering time usage and various statistics .Gamma-Algorithm
The Gamma-algorithm caused certain futile nodes to be considered leaves:P[i-3] : M[best] -> P[best] ... : M[1] -> P[i-2] : M[2] -> P[i-1] : M[3] -> P[i]Evaluation
Processing at the leaf nodes includes the usual evaluation terms dominated by material, but also path-dependent terms by the move sequence from the root to this node, such as bonus for castling or penalties for tempo wasting moves, i.e. moving a piece to a square in two moves to which it could move in one, too early queen moves in the opening, etc.. The static evaluation function consists of thirteen subroutines each corresponding to a basic chess heuristic [15]:Description 1981
Ostrich's parallel search was elaborated by Monroe Newborn [16] , and a brief description of Ostrich 81 is available from the ACM 1980 tournament booklet [17] :Ostrich 81 is written in assembly language and requires 32k word of memory to execute. A book of about 1,000 lines helps with the first few moves, when the program leaves the book, various strategies guide its play for the next dozen moves or so. The program carries out an iteratively deepening and variable depth search examining about 20,000 nodes per three minute move. During the last few years, two of Montreal's better chess players, Ilan Vardi and Frank Wang, have helped with the openings.
See also
Publications
Chapter X. Ostrich: A Description of a Chess-Playing Program
Forum Posts
External Links
Chess Program
Misc
References
What links here?
Up one level