Difference between revisions of "Coko"

From Chessprogramming wiki
Jump to: navigation, search
Line 2: Line 2:
 
'''[[Main Page|Home]] * [[Engines]] * Coko'''
 
'''[[Main Page|Home]] * [[Engines]] * Coko'''
  
'''Coko''',
+
'''Coko''', (COKO III)
 
a chess program by [[Dennis Cooper]] and [[Ed Kozdrowicki]] which competed the first four [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]], [[ACM 1970]], [[ACM 1971]], [[ACM 1972]] ('''Coko III''') and [[ACM 1972]] ('''Coko IV'''). Coko, the Cooper-Kozdrowicki chess program was written in [[Fortran]] as a highly selective tree searcher in the spirit of a [[Type B Strategy|Shannon Type B]] program using a tree pruning system (TPS) consists of a set of commands designed for programming heuristic tree searches <ref>[[Ed Kozdrowicki|Edward W. Kozdrowicki]] ('''1968'''). ''[[http:''portal.acm.org/citation.cfm?id=810637&dl=GUIDE&coll=GUIDE&CFID=85270894&CFTOKEN=84258946|An adaptive tree pruning system: A language for programming heuristic tree searches]]''. Proceedings of the 1968 23rd ACM national conference</ref>.  
 
a chess program by [[Dennis Cooper]] and [[Ed Kozdrowicki]] which competed the first four [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]], [[ACM 1970]], [[ACM 1971]], [[ACM 1972]] ('''Coko III''') and [[ACM 1972]] ('''Coko IV'''). Coko, the Cooper-Kozdrowicki chess program was written in [[Fortran]] as a highly selective tree searcher in the spirit of a [[Type B Strategy|Shannon Type B]] program using a tree pruning system (TPS) consists of a set of commands designed for programming heuristic tree searches <ref>[[Ed Kozdrowicki|Edward W. Kozdrowicki]] ('''1968'''). ''[[http:''portal.acm.org/citation.cfm?id=810637&dl=GUIDE&coll=GUIDE&CFID=85270894&CFTOKEN=84258946|An adaptive tree pruning system: A language for programming heuristic tree searches]]''. Proceedings of the 1968 23rd ACM national conference</ref>.  
  
 
=Descriptions=
 
=Descriptions=
==No Alpha-Beta==
+
==Abstract==
 +
COKO III: The Cooper-Koz Chess Program, [[ACM#Communications|Communications of the ACM]], Vol. 16, 7 <ref>[[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[https://www.semanticscholar.org/paper/COKO-III%3A-The-Cooper-Koz-Chess-Program-Kozdrowicki-Cooper/8ca0c0f08ba564883b96f6126e2c0c3745fe31e7 COKO III: The Cooper-Koz Chess Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 16, 7</ref>
 +
 
 +
COKO III is a chess player written entirely in Fortran. On the [[IBM 360|IBM 360-65]], COKO III plays a minimal chess game at the rate of .2 sec cpu time per move, with a level close to lower chess club play. A selective tree searching procedure controlled by tactical chess logistics allows a deployment of multiple minimal game calculations to achieve some optimal move selection. The tree searching algorithms are the heart of COKO's effectiveness, yet they are conceptually simple. In addition, an interesting phenomenon called a tree searching catastrophe has plagued COKO's entire development just as it troubles a human player. Standard exponential growth is curbed to a large extent by the definition and trimming of the Fisher set. A clear distinction between tree pruning and selective tree searching is also made. Representation of the chess environment is described along with a strategical preanalysis procedure that maps the Lasker regions. Specific chess algorithms are described which could be used as a command structure by anyone desiring to do some chess program experimentation. A comparison is made of some mysterious actions of human players and COKO III. 
 +
 
 +
==Board Representation==
 +
Figure 2 from ''COKO III: The Cooper-Koz Chess Program'' covers COKO's [[10x12 Board]]:
 +
[[FILE:CokoIII10x12Board.jpg|none|border|text-bottom|link=https://www.semanticscholar.org/paper/COKO-III%3A-The-Cooper-Koz-Chess-Program-Kozdrowicki-Cooper/8ca0c0f08ba564883b96f6126e2c0c3745fe31e7/figure/1]]
 +
Chess environment representation: minimal game board. (a) The [[Board Representation|chessboard represented]] by a [[Array|linear array]].<br/>
 +
(b) Representation of [[Pieces|pieces]], empty [[Squares|squares]] and border squares. (c) Move [[Direction|directions]] for [[King]] and [[Queen]].<br/>
 +
(d) The [[Knight]] dictates that two rows of border squares surround the [[8x8 Board|8 X 8 game board]].<br/>
 +
Columns 10 and 1 are considered adjacent.
 +
 
 +
==Search==
 
As described by Cooper in the 1971 Panel <ref>[[Ben Mittman]] ('''1971'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d1ee8 Computer Chess Programs (Panel)]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-3.computer_chess_panel.mittman/3-1%20and%203-3.computer_chess_panel.mittman_etc.1971.ACM.062303021.pdf pdf] from [[The Computer History Museum]]</ref>, Coko III does not use [[Alpha-Beta]]:  
 
As described by Cooper in the 1971 Panel <ref>[[Ben Mittman]] ('''1971'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d1ee8 Computer Chess Programs (Panel)]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-3.computer_chess_panel.mittman/3-1%20and%203-3.computer_chess_panel.mittman_etc.1971.ACM.062303021.pdf pdf] from [[The Computer History Museum]]</ref>, Coko III does not use [[Alpha-Beta]]:  
 
  Although the alpha-beta procedure is a great time saving method, it is unclear at this stage of program development what the full significance of applying such a method to a tactical-strategical game tree would be. Coko III does save the chess tree with periodic pruning to allow for the addition of more branches.  
 
  Although the alpha-beta procedure is a great time saving method, it is unclear at this stage of program development what the full significance of applying such a method to a tactical-strategical game tree would be. Coko III does save the chess tree with periodic pruning to allow for the addition of more branches.  
 
==ACM==
 
[[ACM#Communications|Communications of the ACM]], Vol. 16, 7 <ref>[[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[http://portal.acm.org/citation.cfm?id=362288 COKO III: the Cooper-Koz chess program]''. [[ACM#Communications|Communications of the ACM]], Vol. 16, 7</ref>
 
 
COKO III is a chess player written entirely in Fortran. On the [[IBM 360|IBM 360-65]], COKO III plays a minimal chess game at the rate of .2 sec cpu time per move, with a level close to lower chess club play. A selective tree searching procedure controlled by tactical chess logistics allows a deployment of multiple minimal game calculations to achieve some optimal move selection. The tree searching algorithms are the heart of COKO's effectiveness, yet they are conceptually simple. In addition, an interesting phenomenon called a tree searching catastrophe has plagued COKO's entire development just as it troubles a human player. Standard exponential growth is curbed to a large extent by the definition and trimming of the Fisher set. A clear distinction between tree pruning and selective tree searching is also made. Representation of the chess environment is described along with a strategical preanalysis procedure that maps the Lasker regions. Specific chess algorithms are described which could be used as a command structure by anyone desiring to do some chess program experimentation. A comparison is made of some mysterious actions of human players and COKO III. 
 
  
 
==Man-Machine Studies==
 
==Man-Machine Studies==
Line 42: Line 50:
 
=Publications=
 
=Publications=
 
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [http://www.linkedin.com/pub/john-licwinko/15/b07/962 John S. Licwinko], [[Dennis Cooper|Dennis W. Cooper]] ('''1971'''). ''[http://www.sciencedirect.com/science/article/pii/S0020737371800123 Algorithms for a minimal chess player: A blitz player]''. [http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%236830%231971%23999969997%23695565%23FLP%23&_cdi=6830&_pubType=J&view=c&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d904df3cf14dfeea642d77044a3a9d48 International Journal of Man-Machine Studies, Vol 3, 2]
 
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [http://www.linkedin.com/pub/john-licwinko/15/b07/962 John S. Licwinko], [[Dennis Cooper|Dennis W. Cooper]] ('''1971'''). ''[http://www.sciencedirect.com/science/article/pii/S0020737371800123 Algorithms for a minimal chess player: A blitz player]''. [http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%236830%231971%23999969997%23695565%23FLP%23&_cdi=6830&_pubType=J&view=c&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d904df3cf14dfeea642d77044a3a9d48 International Journal of Man-Machine Studies, Vol 3, 2]
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[http://portal.acm.org/citation.cfm?id=362288 COKO III: the Cooper-Koz chess program]'', [[ACM#Communications|Communications of the ACM]], Vol. 16, 7
+
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[https://www.semanticscholar.org/paper/COKO-III%3A-The-Cooper-Koz-Chess-Program-Kozdrowicki-Cooper/8ca0c0f08ba564883b96f6126e2c0c3745fe31e7 COKO III: The Cooper-Koz Chess Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 16, 7
 
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[http://portal.acm.org/citation.cfm?id=805706 COKO III and the future of inter-snap judgment communication]''. Proceedings of the ACM annual conference
 
* [[Ed Kozdrowicki|Edward W. Kozdrowicki]], [[Dennis Cooper|Dennis W. Cooper]] ('''1973'''). ''[http://portal.acm.org/citation.cfm?id=805706 COKO III and the future of inter-snap judgment communication]''. Proceedings of the ACM annual conference
 
* [[Paul Rushton]], [[Tony Marsland]] ('''1973'''). ''Current Chess Programs: A Summary of their Potential and Limitations''. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/Rushton-Marsland-Feb73.pdf pdf]
 
* [[Paul Rushton]], [[Tony Marsland]] ('''1973'''). ''Current Chess Programs: A Summary of their Potential and Limitations''. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/Rushton-Marsland-Feb73.pdf pdf]

Revision as of 15:18, 25 May 2018

Home * Engines * Coko

Coko, (COKO III) a chess program by Dennis Cooper and Ed Kozdrowicki which competed the first four ACM North American Computer Chess Championships, ACM 1970, ACM 1971, ACM 1972 (Coko III) and ACM 1972 (Coko IV). Coko, the Cooper-Kozdrowicki chess program was written in Fortran as a highly selective tree searcher in the spirit of a Shannon Type B program using a tree pruning system (TPS) consists of a set of commands designed for programming heuristic tree searches [1].

Descriptions

Abstract

COKO III: The Cooper-Koz Chess Program, Communications of the ACM, Vol. 16, 7 [2]

COKO III is a chess player written entirely in Fortran. On the IBM 360-65, COKO III plays a minimal chess game at the rate of .2 sec cpu time per move, with a level close to lower chess club play. A selective tree searching procedure controlled by tactical chess logistics allows a deployment of multiple minimal game calculations to achieve some optimal move selection. The tree searching algorithms are the heart of COKO's effectiveness, yet they are conceptually simple. In addition, an interesting phenomenon called a tree searching catastrophe has plagued COKO's entire development just as it troubles a human player. Standard exponential growth is curbed to a large extent by the definition and trimming of the Fisher set. A clear distinction between tree pruning and selective tree searching is also made. Representation of the chess environment is described along with a strategical preanalysis procedure that maps the Lasker regions. Specific chess algorithms are described which could be used as a command structure by anyone desiring to do some chess program experimentation. A comparison is made of some mysterious actions of human players and COKO III.  

Board Representation

Figure 2 from COKO III: The Cooper-Koz Chess Program covers COKO's 10x12 Board:

CokoIII10x12Board.jpg

Chess environment representation: minimal game board. (a) The chessboard represented by a linear array.
(b) Representation of pieces, empty squares and border squares. (c) Move directions for King and Queen.
(d) The Knight dictates that two rows of border squares surround the 8 X 8 game board.
Columns 10 and 1 are considered adjacent.

Search

As described by Cooper in the 1971 Panel [3], Coko III does not use Alpha-Beta:

Although the alpha-beta procedure is a great time saving method, it is unclear at this stage of program development what the full significance of applying such a method to a tactical-strategical game tree would be. Coko III does save the chess tree with periodic pruning to allow for the addition of more branches. 

Man-Machine Studies

International Journal of Man-Machine Studies [4]

The performance capabilities of the best computer chess programs are compared with their human counterparts with emphasis being placed on machine behavior limits. A grandmaster usually spends a lifetime collecting knowledge or information about the game. Some of this knowledge is given to COKO in the form of a 12 000-line FORTRAN program. Using this knowledge COKO plays very poorly but at the super rate of approximately one move/see. The use of a brute-force selective tree-searching procedure yields an order of magnitude improvement in performance at the standard rate of 3 min/move. Perhaps three orders of magnitude additional improvement is needed to defeat the world champion, a gap which must be bridged, if ever, by programming more chess knowledge into the machine. This paper discusses the “tree-searching catastrophe” as a natural phenomenon that plagues selective tree searching for both man and machine. In addition so-called “interminimal-game communication” is considered as a natural, powerful procedure frequently used by humans to guide their selective search and as a point of emphasis for future development. It is concluded that COKO's development is just beginning, with no immediate barriers to progress, and no lack of ideas for improvement. At present COKO combines brilliant solutions to individual board position puzzles with unimaginable blunders. 

Mate in one?

During the ACM 1971, Coko III offered a pawn versus Genie which, if accepted, would permit a mating sequence 17 plies deep. The pawn was taken, mate was announced, and the predicted line was followed, until ... [5]

    
    
    
    
    
    
    
    
        
      
      
       
       
      
   
      
        
♟♟      
  ♟  ♟  
      ♟ 
 ♙      
  ♕ ♙   
♚ ♔  ♙♙♙
     ♗ ♖
8/pp6/2p2p2/6p1/1P6/2Q1P3/k1K2PPP/5B1R w - - 0 38 

Apparently due to a bug, Coko III found other moves better than mate in one and threw the win ...

38. Kc1 f5 39. Kc2 f4 40. Kc1 g4 41. Kc2 f3 42. Kc1 fxg2 43. Kc2 gxh1=Q 44. Kc1 Qxf1+ 
and resigned later 0-1

Mater

According to Monroe Newborn in 1975, the chess mating combinations program Mater by George Baylor and Herbert Simon, initially written in IPL V, was ported to Fortran and incorporated into Coko [6] :

MATER is written by George Baylor and Simon in FORTRAN. It is able to search to great depths for checkmates. MATER is presently part of the Cooper-Kozdrowicki program. While MATER is an interesting program in its own right, the opportunity to checkmate one's opponent plays a relatively small computational part of the game of chess, and its inclusion in the Cooper-Kozdrowicki program does not seem to add measurably to the program's strength. 

See also

Publications

External Links

References

Up one level