Ostrich

Home * Engines * Ostrich

Ostrich

Ostrich (The Ostrich),
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 . 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 .

Etymology

The program was named Ostrich because of its cowardly "head in the sand when in a crisis" style of play .

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

Ostrich under development at Columbia University Computer Lab, George Arnold

Quote from Oral History of Monty Newborn  :

 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. 

WCCC 1974

Quote from Canadian Chess :

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. 

[Event "WCCC 1974"]
[Site "Stockholm, Sweden"]
[Date "1974.08.08"]
[Round "4"]
[White "Ostrich"]
[Black "Kaissa"]
[Result "0-1"]

1.Nf3 e6 2.d4 Nf6 3.Bg5 d5 4.e3 Be7 5.Nc3 Bb4 6.Bxf6 Bxc3+ 7.bxc3 Qxf6
8.Bd3 c5 9.O-O O-O 10.Qd2 Nc6 11.dxc5 Qe7 12.c4 dxc4 13.Bxc4 Qxc5 14.Qd3 
Rd8 15.Qe4 b5 16.Bd3 f5 17.Qh4 e5 18.e4 f4 19.Rfe1 Bb7 20.Ng5 h6 21.Ne6 
Qb6 22.Nxd8 Rxd8 23.a4 b4 24.Bc4+ Kh8 25.Rad1 Nd4 26.Rc1 Bc6 27.c3 bxc3 
28.Rxc3 Bxa4 29.Qe7 Nc6 30.Qf7 Qc5 31.Rd3 Nd4 32.Bd5 Bb5 33.Rh3 Ne2+ 
34.Kh1 Qxf2 35.Rd1 Qb6 36.Rb1 Rc8 37.Be6 Rd8 38.Qg6 Qb7 39.Qf5 Qc7 
40.Rh4 Nd4 41.Qh3 Nxe6 42.Qxe6 Bd3 43.Rg1 Bc4 44.Qf5 Be2 45.Ra1 a5 
46.Qg6 a4 47.Re1 Bc4 48.Ra1 a3 49.Rb1 Qd6 50.Qxd6 Rxd6 51.Rh3 a2 52.Rc1 
Rd4 53.Rhc3 Rxe4 54.Ra1 Rd4 55.Rxc4 Rxc4 56.g3 f3 57.h3 Rc2 58.Rd1 Rd2 
59.Rc1 e4 60.g4 e3 61.Kg1 e2 62.Kf2 Rd1 63.Rc8+ Kh7 64.Kxf3 e1=Q 
65.Rc2 Rd3+ 66.Kf4 g5+ 67.Kf5 Rf3# 0-1

ACM 1979

ACM 1979, Round 4, Monroe Newborn standing, Tony Marsland, Ostrich 80 - Awit 1/2-1/2

[Event "ACM 1979"]
[Site "Detroit USA"]
[Date "1979.10.30"]
[Round "4"]
[White "Ostrich 80"]
[Black "Awit"]
[Result "1/2-1/2"]

1.e4 c5 2.Nf3 d6 3.Bb5+ Nc6 4.O-O Bd7 5.Nc3 Nf6 6.d4 a6 7.Bxc6 Bxc6 8.Be3 Qb6
9.b3 Nxe4 10.Nxe4 Bxe4 11.c3 Qc6 12.Qe2 O-O-O 13.Ng5 Bg6 14.Nf3 Bh5 15.Bg5 Kd7
16.Rad1 Bxf3 17.gxf3 cxd4 18.cxd4 Qd5 19.f4 h6 20.Bh4 g5 21.fxg5 hxg5 22.Bg3 Rc8
23.Rd3 Bg7 24.Rfd1 e6 25.Qe3 b5 26.f4 f6 27.fxg5 Rc2 28.R1d2 Rc1+ 29.Be1 Qxg5+
30.Qxg5 fxg5 31.Re3 Ke7 32.Kg2 g4 33.Ree2 Bf6 34.Bg3 Bg5 35.Rd3 d5 36.a4 bxa4
37.bxa4 Ra1 38.Be5 Rg8 39.Kg3 Bh6 40.Kh4 Rxa4 41.Rg2 a5 42.Rxg4 Rf8 43.Kh5 Bc1
44.Rg7+ Rf7 45.Bd6+ Kxd6 46.Rxf7 Rc4 47.Kg6 Rc2 48.h4 a4 49.Rff3 a3 50.Rb3 a2
51.Rb6+ Kc7 52.Ra6 Kb7 53.Ra4 Kb6 54.Rf6 Kb5 55.Ra8 Be3 56.Rxe6 Bxd4 57.Rb8+ Ka5
58.Ra8+ Kb5 59.Rb8+ Kc4 60.Rc6+ Kd3 61.Rb3+ Bc3 62.Ra6 Rg2+ 63.Kh5 Kc4 64.Rba3 
a1=Q 65.R6a4+ Kd3 66.Rxa1 Bxa1 67.Rxa1 Rg8 68.Rd1+ Ke4 69.Re1+ Kf5 70.Rf1+ Ke4 
71.Re1+ Kf4 72.Rd1 Ke5 73.Re1+ Kd6 74.Rd1 Ke5 75.Re1+ Kd6 76.Rd1 Ke5 1/2-1/2

ACM 1982

ACM 1982, Parallel Computer Chess Machine Ostrich

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. 

Description 1975

Ostrich ran on a Data General SuperNOVA computer, and was written in Supernova assembly language .

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:

1. Determine material score at current node P[i]
2. 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]
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]

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 :

• 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.
• Castling.
• 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.
• Blocking central pawns. 'Clogging' a position is penalised.
• Development of pieces. Rapid development is encouraged by giving a penalty to unmoved minor pieces or central pawns.
• Central pawns. These carry a bonus
• 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.

Description 1981

Ostrich's parallel search was elaborated by Monroe Newborn , and a brief description of Ostrich 81 is available from the ACM 1980 tournament booklet  :

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. 

See also

• The Ostrich from Evaluation Overlap by Mark Watkins

Publications

• Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. ISBN 0-125-17250-8.

Chapter X. Ostrich: A Description of a Chess-Playing Program

• Jean E. Hayes, David Levy (1976). The world computer chess championship, Stockholm 1974. University Press (Edinburgh) ISBN 0852242859
• Monroe Newborn (1979). Ostrich IV meets the Black Knight. Personal Computing, Vol. 3, No. 10, pp. 74 » ACM 1978, Black Knight
• Monroe Newborn (1982). OSTRICH/P - a parallel search chess program, SOCS-82.3. McGill University, School of Computer Science, Montreal
• Monroe Newborn (1985). A Parallel Search Chess Program. Proceedings of the ACM Annual Conference, pp. 272-277. Denver, Co.
• Monroe Newborn (1988). Unsynchronized Iterative Deepening Parallel Alpha-Beta Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI, Vol. 10, No. 5, pp. 687-694. ISSN 0162-8828.

Forum Posts

• Re: Ostrich... by Robert Hyatt, rgcc, July 29, 1998
• OSTRICH-KAISSA, Stockholm 1974 by José Antônio Fabiano Mendes, CCC, March 01, 2000 » WCCC 1974

External Links

Chess Program

• Ostrich's ICGA Tournaments
• Computer Chess and Canada by David Cohen, 2005

Misc

• Ostrich from Wikipedia
• Ostriches, Ostrich Pictures, Ostrich Facts - National Geographic
• Ostrich | San Diego Zoo Animals
• Ostrich (disambiguation) from Wikipedia
• Ostrich algorithm from Wikipedia
• Ostrich effect from Wikipedia
• Ostrich head in sand › Dr Karl's Great Moments In Science (ABC Science)
• Why ostriches DON'T bury their heads in the sand... and the surprising truths behind other great animal myths by David Thomas, May 15, 2008, Mail Online

References

Up one level