25,161
edits
Changes
Created page with "'''Home * Engines * Ostrich''' FILE:Afrikanischer Strauss Portrait.jpg|border|right|thumb|Ostrich <ref>Photo by [http://de.wikipedia.org/wiki/Benutzer:-do..."
'''[[Main Page|Home]] * [[Engines]] * Ostrich'''
[[FILE:Afrikanischer Strauss Portrait.jpg|border|right|thumb|Ostrich <ref>Photo by [http://de.wikipedia.org/wiki/Benutzer:-donald- A. Kniesel], September 03, 2004, [https://en.wikipedia.org/wiki/Ostrich Ostrich from Wikipedia]</ref> ]]
'''Ostrich''' (The Ostrich),<br/>
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 <ref>[https://en.wikipedia.org/wiki/Monty_Newborn Monty Newborn from Wikipedia]</ref>. Ostrich was the first chess program to compete on a [[Parallel Search|parallel system]] ([[ACM 1982]]). It used eight [[Nova|Data General]] computers with each screen displaying the parallel computations taking place <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63 Eight screen terminal of computer chess machine Ostrich at the 13th ACM North American Computer Chess Championship in Dallas, Texas], Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref> .
=Etymology=
The program was named Ostrich because of its cowardly "[https://en.wikipedia.org/wiki/Ostrich_effect head in the sand when in a crisis]" style of play <ref>[http://www.abc.net.au/science/articles/2006/11/02/1777947.htm Ostrich head in sand › Dr Karl's Great Moments In Science (ABC Science)]</ref> <ref>[http://www.dailymail.co.uk/news/article-566719/Why-ostriches-DONT-bury-heads-sand--surprising-truths-great-animal-myths.html 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, [https://en.wikipedia.org/wiki/Mail_Online Mail Online]</ref>.
=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 Championship|World Computer Chess Championships]], the [[WCCC 1974]] in [https://en.wikipedia.org/wiki/Stockholm Stockholm], the [[WCCC 1977]] in [https://en.wikipedia.org/wiki/Toronto Toronto], the [[WCCC 1980]] in [https://en.wikipedia.org/wiki/Linz Linz], the [[WCCC 1983]] in [https://en.wikipedia.org/wiki/New_York_City New York City], and the [[WCCC 1986]] in [https://en.wikipedia.org/wiki/Cologne Cologne], and '''15''' [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]] until [[ACM 1987]], including the [[ACM 1983]] which was simultaneously the Fourth WCCC.
=Photos & Games=
==1972==
[[FILE:3-1.Arnold.Columbia_University_Computer_Lab.Ostrich.1972.102645382.NEWBORN.jpg|none|border|text-bottom|640px|link=http://www.computerhistory.org/chess/full_record.php?iid=stl-430b9bbe4451b]]
Ostrich under development at [[Columbia University]] Computer Lab, [[George Arnold]] <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-430b9bbe4451b Ostrich chess program under development at Columbia University Computer Lab], Photographer [[Monroe Newborn]], 1972, [[The Computer History Museum]]</ref> <ref>[http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/ archive.computerhistory.org - /resources/still-image/Chess_temporary/still-image/]</ref>
Quote from ''Oral History of Monty Newborn'' <ref>[http://archive.computerhistory.org/projects/chess/related_materials/oral-history/newborn.oral_history.2005.102630783/newborn.oral_history_transcript.2005.102630783.pdf Oral History of Monty Newborn] (pdf) with [http://museums.wikia.com/wiki/Dag_Spicer Dag Spicer], © 2005 [[The Computer History Museum]]</ref> :
Monty: Maybe [[David Levy|David]] helped [[Ben Mittman|Ben]] on the [[ACM 1971|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 [[ACM 1972|third tournament]] I was back involved in organizing as well. For a number of years, [[Ben Mittman|Mittman]] and I organized these tournaments together. I started competing myself in the Boston tournament, the third tournament.
Q: With Ostrich?<br/>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.
<span id="OstrichKaissa"></span>
==WCCC 1974==
Quote from ''Canadian Chess'' <ref>[http://www.canadianchess.info/canadianchesshistory/CanadianChessBiographiesN.html#NEWBORN Canadian Chess - Monroe (Monty) Newborn]</ref> <ref>[http://www.stmintz.com/ccc/index.php?id=99672 OSTRICH-KAISSA, Stockholm 1974] by [[José Antônio Fabiano Mendes]], [[CCC]], March 01, 2000</ref>:
A win in the following last round game would have given Ostrich a tie for first place in the [[WCCC 1974|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.
<pre>
[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
</pre>
==ACM 1979==
[[FILE:4-3_and_3-1.Game_Room.ACM_NACCC_10.Detriot.1979.102645341.NEWBORN.jpg|none|border|text-bottom|640px|link=http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/]]
[[ACM 1979]], Round 4, [[Monroe Newborn]] standing, [[Tony Marsland]], Ostrich 80 - [[Awit]] 1/2-1/2 <ref>[http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/ Photo] Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref>
<pre>
[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
</pre>
==ACM 1982==
[[FILE:3-1.Eight_screen_termimal_OSTRICH.ACM_NACCC_13.Dallas.1982.102645425.NEWBORN.lg.jpg|none|border|text-bottom|481px|link=http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63]]
[[ACM 1982]], Parallel Computer Chess Machine Ostrich <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63 Eight screen terminal of computer chess machine Ostrich at the 13th ACM North American Computer Chess Championship in Dallas, Texas], Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref>
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 [[Nova#SuperNOVA|Data General SuperNOVA]] computer, and was written in [https://en.wikipedia.org/wiki/Data_General_Nova#Assembly_language_examples Supernova] [[Assembly|assembly language]] <ref>Description 1975 based on Chapter X. ''Ostrich: A Description of a Chess-Playing Program''. in [[Monroe Newborn]] ('''1975'''). ''Computer Chess''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], New York, N.Y.</ref> <ref>A description of Ostrich is given in [[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref>.
==Data Structures==
Ostrich had a plane [[8x8 Board|8x8 board]] with positive and negative numbers for white and black [[Pieces|pieces]] respectively, and zero for empty squares, further a [[Piece-Lists|piece list]], and multiple other [[Incremental Updates|incremental updated data]], such as [[Attack and Defend Maps|attack and defend maps]], a change list, a list of [[Pin|pinned pieces]], and pieces [[En prise|en prise]]. The [[Move List|move list]] for move generation is shared and controlled by indices kept on the [[Stack#SearchStack|ply-stack]] recursively.
==Search==
Ostrich [[Search|searched]] a [[Search Tree|tree]] of variable-length move sequences using [[Type B Strategy|Shannon's Type B strategy]] supplemented by the [[Alpha-Beta|alpha-beta algorithm]]. Strict [[Move Generation#Legal|legal move generation]], [[Move Ordering|move ordering]], re-ordering and plausibility analysis took huge effort, especially at or near the [[Root|root]].
===Search Control===
The early Ostrich did not yet perform [[Iterative Deepening|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|depth]] parameters Dmin and Dmax, average move time and total time. Dmin determines the minimal depth to the [[Horizon Node|horizon]]. If depth is still less Dmax, positions either resulting from [[Tactical Moves|tactical moves]], or with the presence of en prise pieces were [[Extensions|extended]]. Initial guesses of the parameters based on [[Time Management|time control]] were adapted during the course of the [[Chess Game|game]] considering time usage and various [[Search Statistics|statistics]] .
<span id="GammaAlgorithm"></span>
===Gamma-Algorithm===
The '''Gamma-algorithm''' caused certain [[Futility Pruning|futile nodes]] to be considered [[Leaf Node|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]
<pre>
P[i-3] : M[best] -> P[best] ...
: M[1] -> P[i-2] : M[2] -> P[i-1] : M[3] -> P[i]
</pre>
==Evaluation==
Processing at the [[Leaf Node|leaf nodes]] includes the usual [[Evaluation|evaluation]] terms dominated by [[Material|material]], but also [[Path-Dependency|path-dependent]] terms by the move sequence from the root to this node, such as bonus for [[Castling|castling]] or penalties for [[Tempo|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 <ref>from [[Evaluation Overlap]] by [[Mark Watkins]]</ref>:
* [[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 [[Point Value|values]].
* Material ratio term, which computes whether an even exchange of material has occurred between the [[Root|top node]] of the tree and the bottom position being evaluated; a bonus goes to the side ahead in material.
* [[Castling]].
* [[Square Control|Board control]], which is intended to increase one's own [[Mobility|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.
* [[Tempo|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.
* [[Development|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.
* [[Development#Eval Considerations|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.
* [[Pawn Center|Central pawns]]. These carry a bonus
* [[Pawn Structure|Pawn structure]]. Advancement of pawns is encouraged and doubled pawns penalised.
* [[King Safety|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 Pawn|Passed pawns]]. The goal is to encourage the advancement and [[Promotions|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|parallel search]] was elaborated by [[Monroe Newborn]] <ref>[[Monroe Newborn]] ('''1982'''). ''OSTRICH/P - a parallel search chess program, SOCS-82.3''. [[McGill University]], School of Computer Science, Montreal</ref> , and a brief description of Ostrich 81 is available from the [[ACM 1980]] tournament booklet <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6cdeeb The Eleventh ACM's North American Computer Chess Championship], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3.1980_11th_ACM_NACCC/The_Eleventh_ACMs_North_American_Computer_Chess_Championship.1980.062303015.sm.pdf pdf] from [[The Computer History Museum]]</ref> :
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 [[ACM 1972|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|assembly language]] and requires 32k word of [[Memory|memory]] to execute. A [[Opening Book|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 [[Iterative Deepening|iteratively deepening]] and variable depth search examining about 20,000 nodes per three minute move. During the last few years, two of [https://en.wikipedia.org/wiki/Montreal Montreal's] better chess players, [[Ilan Vardi]] and [[Frank Wang]], have helped with the [[Opening|openings]].
=See also=
* [[Various Classifications#Bird|Bird]]
* [[Evaluation Overlap#Ostrich|The Ostrich]] from [[Evaluation Overlap]] by [[Mark Watkins]]
=Publications=
* [[Monroe Newborn]] ('''1975'''). ''Computer Chess''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], New York, N.Y. ISBN 0-125-17250-8.
: Chapter X. Ostrich: A Description of a Chess-Playing Program
* [[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859
* [[Monroe Newborn]] ('''1979'''). ''Ostrich IV meets the Black Knight''. [[Personal Computing#3_10|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=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a8d292d71a40a0c4 Re: Ostrich...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], July 29, 1998
* [https://www.stmintz.com/ccc/index.php?id=99672 OSTRICH-KAISSA, Stockholm 1974] by [[José Antônio Fabiano Mendes]], [[CCC]], March 01, 2000 » [[WCCC 1974]]
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=45 Ostrich's ICGA Tournaments]
* [http://web.archive.org/web/20091026180259/http://geocities.com/rookknightrook/ChessArticlesDavidCohen.htm#A0507 Computer Chess and Canada] by [http://web.archive.org/web/20091026180259/http://geocities.com/rookknightrook/ChessArticlesDavidCohen.htm David Cohen], 2005
* [http://www.computerhistory.org/chess/search.php?more=&submitted=1&keywords=Ostrich&x=30&y=3&all=all&item_document=item_document&item_moving_image=item_moving_image&item_artifact=item_artifact&item_still_image=item_still_image&item_oral_history=item_oral_history&item_software=item_software# Search Ostrich] from [[The Computer History Museum]]
==Misc==
* [https://en.wikipedia.org/wiki/Ostrich Ostrich from Wikipedia]
* [http://animals.nationalgeographic.com/animals/birds/ostrich/ Ostriches, Ostrich Pictures, Ostrich Facts] - [https://en.wikipedia.org/wiki/National_Geographic_Society National Geographic]
* [http://animals.sandiegozoo.org/animals/ostrich Ostrich] | [https://en.wikipedia.org/wiki/San_Diego_Zoo San Diego Zoo] Animals
* [https://en.wikipedia.org/wiki/Ostrich_%28disambiguation%29 Ostrich (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Ostrich_algorithm Ostrich algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Ostrich_effect Ostrich effect from Wikipedia]
* [http://www.abc.net.au/science/articles/2006/11/02/1777947.htm Ostrich head in sand › Dr Karl's Great Moments In Science (ABC Science)]
* [http://www.dailymail.co.uk/news/article-566719/Why-ostriches-DONT-bury-heads-sand--surprising-truths-great-animal-myths.html 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, [https://en.wikipedia.org/wiki/Mail_Online Mail Online]
=References=
<references />
'''[[Engines|Up one level]]'''
[[FILE:Afrikanischer Strauss Portrait.jpg|border|right|thumb|Ostrich <ref>Photo by [http://de.wikipedia.org/wiki/Benutzer:-donald- A. Kniesel], September 03, 2004, [https://en.wikipedia.org/wiki/Ostrich Ostrich from Wikipedia]</ref> ]]
'''Ostrich''' (The Ostrich),<br/>
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 <ref>[https://en.wikipedia.org/wiki/Monty_Newborn Monty Newborn from Wikipedia]</ref>. Ostrich was the first chess program to compete on a [[Parallel Search|parallel system]] ([[ACM 1982]]). It used eight [[Nova|Data General]] computers with each screen displaying the parallel computations taking place <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63 Eight screen terminal of computer chess machine Ostrich at the 13th ACM North American Computer Chess Championship in Dallas, Texas], Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref> .
=Etymology=
The program was named Ostrich because of its cowardly "[https://en.wikipedia.org/wiki/Ostrich_effect head in the sand when in a crisis]" style of play <ref>[http://www.abc.net.au/science/articles/2006/11/02/1777947.htm Ostrich head in sand › Dr Karl's Great Moments In Science (ABC Science)]</ref> <ref>[http://www.dailymail.co.uk/news/article-566719/Why-ostriches-DONT-bury-heads-sand--surprising-truths-great-animal-myths.html 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, [https://en.wikipedia.org/wiki/Mail_Online Mail Online]</ref>.
=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 Championship|World Computer Chess Championships]], the [[WCCC 1974]] in [https://en.wikipedia.org/wiki/Stockholm Stockholm], the [[WCCC 1977]] in [https://en.wikipedia.org/wiki/Toronto Toronto], the [[WCCC 1980]] in [https://en.wikipedia.org/wiki/Linz Linz], the [[WCCC 1983]] in [https://en.wikipedia.org/wiki/New_York_City New York City], and the [[WCCC 1986]] in [https://en.wikipedia.org/wiki/Cologne Cologne], and '''15''' [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]] until [[ACM 1987]], including the [[ACM 1983]] which was simultaneously the Fourth WCCC.
=Photos & Games=
==1972==
[[FILE:3-1.Arnold.Columbia_University_Computer_Lab.Ostrich.1972.102645382.NEWBORN.jpg|none|border|text-bottom|640px|link=http://www.computerhistory.org/chess/full_record.php?iid=stl-430b9bbe4451b]]
Ostrich under development at [[Columbia University]] Computer Lab, [[George Arnold]] <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-430b9bbe4451b Ostrich chess program under development at Columbia University Computer Lab], Photographer [[Monroe Newborn]], 1972, [[The Computer History Museum]]</ref> <ref>[http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/ archive.computerhistory.org - /resources/still-image/Chess_temporary/still-image/]</ref>
Quote from ''Oral History of Monty Newborn'' <ref>[http://archive.computerhistory.org/projects/chess/related_materials/oral-history/newborn.oral_history.2005.102630783/newborn.oral_history_transcript.2005.102630783.pdf Oral History of Monty Newborn] (pdf) with [http://museums.wikia.com/wiki/Dag_Spicer Dag Spicer], © 2005 [[The Computer History Museum]]</ref> :
Monty: Maybe [[David Levy|David]] helped [[Ben Mittman|Ben]] on the [[ACM 1971|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 [[ACM 1972|third tournament]] I was back involved in organizing as well. For a number of years, [[Ben Mittman|Mittman]] and I organized these tournaments together. I started competing myself in the Boston tournament, the third tournament.
Q: With Ostrich?<br/>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.
<span id="OstrichKaissa"></span>
==WCCC 1974==
Quote from ''Canadian Chess'' <ref>[http://www.canadianchess.info/canadianchesshistory/CanadianChessBiographiesN.html#NEWBORN Canadian Chess - Monroe (Monty) Newborn]</ref> <ref>[http://www.stmintz.com/ccc/index.php?id=99672 OSTRICH-KAISSA, Stockholm 1974] by [[José Antônio Fabiano Mendes]], [[CCC]], March 01, 2000</ref>:
A win in the following last round game would have given Ostrich a tie for first place in the [[WCCC 1974|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.
<pre>
[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
</pre>
==ACM 1979==
[[FILE:4-3_and_3-1.Game_Room.ACM_NACCC_10.Detriot.1979.102645341.NEWBORN.jpg|none|border|text-bottom|640px|link=http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/]]
[[ACM 1979]], Round 4, [[Monroe Newborn]] standing, [[Tony Marsland]], Ostrich 80 - [[Awit]] 1/2-1/2 <ref>[http://archive.computerhistory.org/resources/still-image/Chess_temporary/still-image/ Photo] Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref>
<pre>
[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
</pre>
==ACM 1982==
[[FILE:3-1.Eight_screen_termimal_OSTRICH.ACM_NACCC_13.Dallas.1982.102645425.NEWBORN.lg.jpg|none|border|text-bottom|481px|link=http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63]]
[[ACM 1982]], Parallel Computer Chess Machine Ostrich <ref>[http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc19ea63 Eight screen terminal of computer chess machine Ostrich at the 13th ACM North American Computer Chess Championship in Dallas, Texas], Gift of [[Monroe Newborn]], [[The Computer History Museum]]</ref>
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 [[Nova#SuperNOVA|Data General SuperNOVA]] computer, and was written in [https://en.wikipedia.org/wiki/Data_General_Nova#Assembly_language_examples Supernova] [[Assembly|assembly language]] <ref>Description 1975 based on Chapter X. ''Ostrich: A Description of a Chess-Playing Program''. in [[Monroe Newborn]] ('''1975'''). ''Computer Chess''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], New York, N.Y.</ref> <ref>A description of Ostrich is given in [[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref>.
==Data Structures==
Ostrich had a plane [[8x8 Board|8x8 board]] with positive and negative numbers for white and black [[Pieces|pieces]] respectively, and zero for empty squares, further a [[Piece-Lists|piece list]], and multiple other [[Incremental Updates|incremental updated data]], such as [[Attack and Defend Maps|attack and defend maps]], a change list, a list of [[Pin|pinned pieces]], and pieces [[En prise|en prise]]. The [[Move List|move list]] for move generation is shared and controlled by indices kept on the [[Stack#SearchStack|ply-stack]] recursively.
==Search==
Ostrich [[Search|searched]] a [[Search Tree|tree]] of variable-length move sequences using [[Type B Strategy|Shannon's Type B strategy]] supplemented by the [[Alpha-Beta|alpha-beta algorithm]]. Strict [[Move Generation#Legal|legal move generation]], [[Move Ordering|move ordering]], re-ordering and plausibility analysis took huge effort, especially at or near the [[Root|root]].
===Search Control===
The early Ostrich did not yet perform [[Iterative Deepening|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|depth]] parameters Dmin and Dmax, average move time and total time. Dmin determines the minimal depth to the [[Horizon Node|horizon]]. If depth is still less Dmax, positions either resulting from [[Tactical Moves|tactical moves]], or with the presence of en prise pieces were [[Extensions|extended]]. Initial guesses of the parameters based on [[Time Management|time control]] were adapted during the course of the [[Chess Game|game]] considering time usage and various [[Search Statistics|statistics]] .
<span id="GammaAlgorithm"></span>
===Gamma-Algorithm===
The '''Gamma-algorithm''' caused certain [[Futility Pruning|futile nodes]] to be considered [[Leaf Node|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]
<pre>
P[i-3] : M[best] -> P[best] ...
: M[1] -> P[i-2] : M[2] -> P[i-1] : M[3] -> P[i]
</pre>
==Evaluation==
Processing at the [[Leaf Node|leaf nodes]] includes the usual [[Evaluation|evaluation]] terms dominated by [[Material|material]], but also [[Path-Dependency|path-dependent]] terms by the move sequence from the root to this node, such as bonus for [[Castling|castling]] or penalties for [[Tempo|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 <ref>from [[Evaluation Overlap]] by [[Mark Watkins]]</ref>:
* [[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 [[Point Value|values]].
* Material ratio term, which computes whether an even exchange of material has occurred between the [[Root|top node]] of the tree and the bottom position being evaluated; a bonus goes to the side ahead in material.
* [[Castling]].
* [[Square Control|Board control]], which is intended to increase one's own [[Mobility|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.
* [[Tempo|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.
* [[Development|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.
* [[Development#Eval Considerations|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.
* [[Pawn Center|Central pawns]]. These carry a bonus
* [[Pawn Structure|Pawn structure]]. Advancement of pawns is encouraged and doubled pawns penalised.
* [[King Safety|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 Pawn|Passed pawns]]. The goal is to encourage the advancement and [[Promotions|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|parallel search]] was elaborated by [[Monroe Newborn]] <ref>[[Monroe Newborn]] ('''1982'''). ''OSTRICH/P - a parallel search chess program, SOCS-82.3''. [[McGill University]], School of Computer Science, Montreal</ref> , and a brief description of Ostrich 81 is available from the [[ACM 1980]] tournament booklet <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6cdeeb The Eleventh ACM's North American Computer Chess Championship], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3.1980_11th_ACM_NACCC/The_Eleventh_ACMs_North_American_Computer_Chess_Championship.1980.062303015.sm.pdf pdf] from [[The Computer History Museum]]</ref> :
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 [[ACM 1972|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|assembly language]] and requires 32k word of [[Memory|memory]] to execute. A [[Opening Book|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 [[Iterative Deepening|iteratively deepening]] and variable depth search examining about 20,000 nodes per three minute move. During the last few years, two of [https://en.wikipedia.org/wiki/Montreal Montreal's] better chess players, [[Ilan Vardi]] and [[Frank Wang]], have helped with the [[Opening|openings]].
=See also=
* [[Various Classifications#Bird|Bird]]
* [[Evaluation Overlap#Ostrich|The Ostrich]] from [[Evaluation Overlap]] by [[Mark Watkins]]
=Publications=
* [[Monroe Newborn]] ('''1975'''). ''Computer Chess''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], New York, N.Y. ISBN 0-125-17250-8.
: Chapter X. Ostrich: A Description of a Chess-Playing Program
* [[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859
* [[Monroe Newborn]] ('''1979'''). ''Ostrich IV meets the Black Knight''. [[Personal Computing#3_10|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=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a8d292d71a40a0c4 Re: Ostrich...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], July 29, 1998
* [https://www.stmintz.com/ccc/index.php?id=99672 OSTRICH-KAISSA, Stockholm 1974] by [[José Antônio Fabiano Mendes]], [[CCC]], March 01, 2000 » [[WCCC 1974]]
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=45 Ostrich's ICGA Tournaments]
* [http://web.archive.org/web/20091026180259/http://geocities.com/rookknightrook/ChessArticlesDavidCohen.htm#A0507 Computer Chess and Canada] by [http://web.archive.org/web/20091026180259/http://geocities.com/rookknightrook/ChessArticlesDavidCohen.htm David Cohen], 2005
* [http://www.computerhistory.org/chess/search.php?more=&submitted=1&keywords=Ostrich&x=30&y=3&all=all&item_document=item_document&item_moving_image=item_moving_image&item_artifact=item_artifact&item_still_image=item_still_image&item_oral_history=item_oral_history&item_software=item_software# Search Ostrich] from [[The Computer History Museum]]
==Misc==
* [https://en.wikipedia.org/wiki/Ostrich Ostrich from Wikipedia]
* [http://animals.nationalgeographic.com/animals/birds/ostrich/ Ostriches, Ostrich Pictures, Ostrich Facts] - [https://en.wikipedia.org/wiki/National_Geographic_Society National Geographic]
* [http://animals.sandiegozoo.org/animals/ostrich Ostrich] | [https://en.wikipedia.org/wiki/San_Diego_Zoo San Diego Zoo] Animals
* [https://en.wikipedia.org/wiki/Ostrich_%28disambiguation%29 Ostrich (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Ostrich_algorithm Ostrich algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Ostrich_effect Ostrich effect from Wikipedia]
* [http://www.abc.net.au/science/articles/2006/11/02/1777947.htm Ostrich head in sand › Dr Karl's Great Moments In Science (ABC Science)]
* [http://www.dailymail.co.uk/news/article-566719/Why-ostriches-DONT-bury-heads-sand--surprising-truths-great-animal-myths.html 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, [https://en.wikipedia.org/wiki/Mail_Online Mail Online]
=References=
<references />
'''[[Engines|Up one level]]'''
