UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The game of pentominoes Kuttner, Michael 1972

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1973_A6_7 K88.pdf [ 8.96MB ]
Metadata
JSON: 1.0302120.json
JSON-LD: 1.0302120+ld.json
RDF/XML (Pretty): 1.0302120.xml
RDF/JSON: 1.0302120+rdf.json
Turtle: 1.0302120+rdf-turtle.txt
N-Triples: 1.0302120+rdf-ntriples.txt
Original Record: 1.0302120 +original-record.json
Full Text
1.0302120.txt
Citation
1.0302120.ris

Full Text

THE GAME OF PENTOMINOES  by  MICHAEL KUTTNER  B.Sc,  University College London, 1966  A thesis submitted i n p a r t i a l f u l f i l m e n t the requirements f o r the degree of  MASTER OF SCIENCE  i n the Department of COMPUTER SCIENCE  We accept this thesis as conforming to the required standard.  THE UNIVERSITY OF BRITISH COLUMBIA December, 1972  In p r e s e n t i n g  this thesis  in p a r t i a l  f u l f i l m e n t o f the r e q u i r e m e n t s f o r  an advanced degree at the U n i v e r s i t y o f B r i t i s h Columbia, I agree  that  the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s .  I t i s understood that c o p y i n g o r p u b l i c a t i o n  of t h i s t h e s i s f o r f i n a n c i a l gain written  s h a l l not be a l l o w e d w i t h o u t my  permission.  Department o f  G(5Mfb M  The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada  SCf&\Gz  i  ABSTRACT  A study i n game-playing  programming i s made u s i n g the game o f  pentominoes which has a v e r y l a r g e b r a n c h i n g f a c t o r and where t h e r e e x i s t s almost no p r e c i s e , f a c t u a l i n f o r m a t i o n to guide the conduct  of  the p l a y . The  difficulties  encountered  imply t h a t some apparent  advantages  of h e u r i s t i c techniques a r e more h e a v i l y problem-dependent than i s usually  conceded.  A g u i d i n g d e v i c e capable o f l e a r n i n g i s i n c o r p o r a t e d which significantly  improves  the program's p l a y i n c o m p e t i t i o n w i t h v e r s i o n s  l a c k i n g i t and shows s u b j e c t i v e improvement w i t h human c o m p e t i t i o n .  ii  TABLE OF CONTENTS  contents  page  INTRODUCTION .  1  THE GAME PLAYING MILIEU  5  1.1  General Considerations  . . . . . . . . . . . . . . .  5  1.2  Polyominoes  7  1.3  The Game of Pentominoes  9  THE PENTOMINO PROGRAM  15  2.1  Basic Representations  15  2.2  Necessary  18  Improvements  THE 'INTELLIGENT' ADDITIONS AND  THEIR EFFECTS; . . . . . .  26  3.1  A i d s to Move S e l e c t i o n  26  3.2  Experimental Results  32  CONCLUSIONS  39  REFERENCES  43  APPENDICES  45  1  O p e r a t i o n o f the Programs  45  2  Listings  48  iii  ACKNOWLEDGMENT I w i s h : t o express my thanks t o Dr. R i c h a r d p a t i e n t supervision during  the p r e p a r a t i o n  Rosenberg f o r h i s  of t h i s t h e s i s , to the  N a t i o n a l Research C o u n c i l o f Canada p a r t o f t h i s work b e i n g c a r r i e d out under grant A-5552 and to S h e i l a T a y l o r f o r e n d u r i n g t y p i n g from my  handwriting.  1.  INTRODUCTION The  t r a d i t i o n a l reason,  problem s o l v i n g , f o r choosing experimental  research  employed by p e o p l e working i n h e u r i s t i c game p l a y i n g as a v e h i c l e f o r t h e i r  i s that s i t u a t i o n s o f great d i f f i c u l t y  t h e r e a r e v e r y few f o r m a l parameters i n v o l v e d .  a r i s e but  I t i s known t h a t  there  are no p s y c h o l o g i c a l o r s o c i a l f a c t o r s i n f l u e n c i n g t h e i r models, merely a few simply  defined  rules.  However, i t turns out w i t h most games much p l a y e d by humans t h a t t h e r e i s a body o f knowledge t h a t p r o v i d e s  guidance f o r p l a y e r s f a r  beyond t h e g i v e n r u l e s and the complete s e a r c h s p e c i f i c t o some games, t h a t guides may make g e n e r a l h e u r i s t i c  space.  p l a y e r s a l s o guides  techniques  less likely  The knowledge, programmers and  to evolve.  A game has been chosen - pentominoes - where v e r y l i t t l e indeed.  i s known,  Furthermore, s i n c e i t i n v o l v e s s p a t i a l judgment and c o m b i n a t o r i a l  c o n s i d e r a t i o n s , i t i s by no means completely  s t r a i g h t f o r w a r d to w r i t e a  program f o r i t . Initially,  thought c e n t r e d on f i n d i n g an i n t e r n a l  which might be u s e f u l f o r m a n i p u l a t i o n approach to t h i s game.  representation  i n a manner analogous to a human  As w i l l be seen t h e r e had been one program  d e s c r i b e d b e f o r e b u t the r e p r e s e n t a t i o n had to be much m o d i f i e d ;  like  most e a r l y polyomino programs i t was concerned only w i t h c o u n t i n g o r d i s s e c t i o n o f r e c t a n g l e s i n t o s e t s o f pentominoes. The  chosen r e p r e s e n t a t i o n had e f f e c t s on how the program would  " v i s u a l i s e " the s t a t e o f the board.  I t seemed p o i n t l e s s t o r e d i r e c t i t ,  p l a c e i t under the same c o n s t r a i n t s as a human, s i n c e i t s model o f board  2.  s t a t e produced i t s own advantages.  We might waste time d e a l i n g w i t h an  a r e a o f the board which seemed to be open and y e t accommodated no p i e c e s . The program however would d i s m i s s t h i s area immediately.  Fortunately  o r u n f o r t u n a t e l y , these d i f f e r e n c e s would l e a d the program development towards a s i t u a t i o n where d i f f e r e n t s t r a t e g i e s s h o u l d be deployed a human o r a machine opponent.  T h i s h i g h l i g h t s the c u r i o u s  against  situation  ( f o r e t o l d by Good [ 1 1 ] f o r a d i f f e r e n t reason) i n which machines p l a y chess  o n l y a g a i n s t o t h e r machines; v i z . the annual ACM tournament. The  f i r s t step i n b u i l d i n g and t e s t i n g t h i s game-playing program  was to develop to  the b a s i c code f o r m a n i p u l a t i n g  i n c l u d e a random move g e n e r a t o r  the board  and p i e c e s and  to enable moves t o be made, games to  be p l a y e d and s t a t i s t i c s and o t h e r i n f o r m a t i o n to be g a t h e r e d .  These  r o u t i n e s r e v e a l e d f o r the f i r s t time the t o t a l s i z e o f the move t r e e and the number o f c h o i c e s a t each p l y . S i n c e a p o s i t i o n w i t h 100 c h o i c e s f o r a move i s q u i t e c l o s e t o t h e end o f the game one s h o u l d hope t o determine the consequences o f a l l moves f a i r l y square  thoroughly, but having  t o c a l c u l a t e them anew f o r every  on t h e board made t h i s c o m p u t a t i o n a l l y  became apparent  t h a t some e x t r a b a s i c f a c i l i t i e s  d e s c r i b e d i n S e c t i o n 2.2. provide a l i s t  too time consuming. a r e needed.  So i t  These a r e  F i r s t l y , a l a r g e t a b l e was c o n s t r u c t e d to  o f p o s s i b l e moves f o r any g i v e n neighbourhood.  was w r i t t e n t o c o n s t r u c t l i s t s t o r e s t r i c t an i n t e r e s t i n g problem i n i t s e l f .  A program  them to manageable p r o p o r t i o n s ,  Then to s u s t a i n , m i n i m a l l y ,  the analogy  w i t h a human p l a y e r , an e x h a u s t i v e s e a r c h i s r e q u i r e d f o r the v e r y  late  stages o f the game when i t i s c l e a r t h a t a complete a n a l y s i s i s n e c e s s a r y .  3.  H e u r i s t i c s are f u t i l e w i t h o n l y two Because i t takes p l a c e at the end search  can be used.  c o n s t r a i n s the s e a r c h With these  p i e c e s remaining  to be  played.  of the game a s i m p l i f i e d  alpha-beta  I t w i l l be c l e a r t h a t even here the environment to be depth f i r s t and n o t h i n g e l s e .  routines present  the program can p l a y a t a  r a t e and becomes f o o l p r o o f near the end.  reasonable  There remains to c o n s i d e r  how  to make the program p l a y b e t t e r i n the e a r l y stages and more i m p o r t a n t l y i n the c r u c i a l p a r t o f the game b e f o r e an e x h a u s t i v e Chapter 3 d e s c r i b e s what has been done to c o n v e r t i n f o r m a t i o n gathered  by  the u p d a t i n g  program i n t o something l i k e the In one  view t h i s simply  s e t of n u m e r i c a l t h a t can be  search  the d e t a i l e d n u m e r i c a l  and move-making r o u t i n e s of  values  the  ' g e s t a l t ' concepts o f a human p l a y e r .  condenses to a mapping of p o s i t i o n i n t o a s m a l l i s h  values.  In another, i t r e p r e s e n t s  an e v a l u a t i o n f u n c t i o n  a p p l i e d to p o s i t i o n s i n the l a t t e r p a r t s o f a game, once  i d e a i s e s t a b l i s h e d of the importance of the moves p r e c e d i n g Supporting  is feasible.  r o u t i n e s were w r i t t e n t h a t c r e a t e and m a i n t a i n  the  search.  a t a b l e of  t h a t g i v e a judgment on whether p a r t i c u l a r k i n d s of p o s i t i o n s are  good or bad.  The  goodness i s measured by  the o n l y means that have  turned  up; p r a g m a t i c a l l y - d i d one win when t h a t k i n d o f p o s i t i o n o c c u r r e d previous  in  games?  Clearly so  the  t h e r e are too many p o s i t i o n s to g i v e each a d i s t i n c t  they are grouped by a n u m e r i c a l  d e s c r i b e d i n S e c t i o n 3.1.  computation, a form o f mapping t h a t i s  A l s o i t i s seen t h a t , s i n c e the e v a l u a t i o n i s  based on p a s t performance, t h e r e f o r e the a b i l i t y future r e s u l t s .  The  value  r e s u l t s i n t h i s chapter  i s inherent  show the  to improve  significant  4. improvement  i n playing strength  over the e a r l i e r  version.  R e s u l t s w i t h human opponents were more d i f f i c u l t  to e v a l u a t e  the machine t h a t moved randomly u n t i l near the end o b t a i n e d good r e c o r d , b e t t e r than 25%, we e s t i m a t e , from programmers i s an odd game.  a l l the way  against a l l kinds  up to b e g i n n e r s .  since  a remarkably o f opponents  I t i s c l e a r t h a t pentominoes  5. CHAPTER 1 1.1  THE  General  GAME-PLAYING MILIEU  Considerations  I n t e r e s t i n mechanisms b e h i n d almost as o l d as games themselves.  the p l a y i n g o f games i s p r o b a b l y Work on mathematical s o l u t i o n s to  puzzles of a l l kinds  i s always t a k i n g p l a c e .  chess automaton l a s t  century  f o r and  The  fraud of  Maelzl's  i l l u s t r a t e d , i f n o t h i n g e l s e , a demand  f a s c i n a t i o n w i t h machines o f t h a t k i n d .  In 1914  the  Spanish  i n v e n t o r L. T o r r e s y Quevedo produced a machine t h a t wins the endgame of k i n g and  rook a g a i n s t k i n g .  which thought i s r e a l l y n e c e s s a r y  He  commented, "the l i m i t s w i t h i n  need to be b e t t e r d e f i n e d . . . t h e  maton can do many t h i n g s t h a t are p o p u l a r l y c l a s s e d as The  chess  thought."  advent o f computers r e v o l u t i o n i s e d the p o s s i b i l i t i e s .  o r i g i n a l paper of Shannon [22] sparked  auto-  The  much work i n chess although  were a l r e a d y some h a n d - s i m u l a t i o n s  around at the time.  i n h i s general suggestions  need be  c o n f i n e d to chess;  applicability  t i c - t a c - t o e , the e i g h t - p u z z l e and many o t h e r  popular  to checkers,  In f a c t  there  nothing  there i s equal  pastimes.  However there have been many more reasons f o r computerised gamep l a y i n g than the e n t e r t a i n m e n t  o f games.  [20] and  o f the most s u c c e s s f u l e f f o r t s i n the  field.  [21] has  s t o o d as one  H i s i n t e n t i o n was  p o s s i b l e and  to t h i s end he i n c o r p o r a t e d as much i n f o r m a t i o n  expert p l a y e r s .  checkers  to have the program p l a y j u s t as w e l l as  v a l u a b l e checker b o a r d p o s i t i o n s as he  efficiently  Samuel's work w i t h  about  c o u l d p r o v i d e h i m s e l f and  Ih a d d i t i o n , he used p o l y n o m i a l  coded r e p r e s e n t a t i o n s and was  one  from  evaluation functions,  o f the f i r s t  to use  the  6.  alpha-beta  s e a r c h a l g o r i t h m , b e f o r e i t had even been c h r i s t e n e d .  Samuel's i n t e r e s t was n o t i n s i m u l a t i o n o f human thought but i n demonstrating to  d i g i t a l computing.  intelligent  processes  r e s u l t s u s i n g some techniques p e c u l i a r  On the o t h e r hand, many people have been employing  games f o r j u s t such s i m u l a t i o n s .  Newell,  [16] i s one o f the e a r l i e s t examples.  Shaw and Simon's chess p l a y e r  They were n o t so much concerned  w i t h r e s u l t s from the most e f f i c i e n t programming b u t w i t h problem s o l v i n g p r o c e s s e s .  the u n d e r l y i n g  Games have always been u s e f u l i n t h i s  because o f t h e i r f o r m a l s i m p l i c i t y  that y e t leads to very  area  complex  behaviour. - Chess has always had a s p e c i a l p l a c e i n the programming o f games and of  in artificial  i n t e l l i g e n c e because i t has been c o n s i d e r e d t h e game  thought, p a r e x c e l l e n c e , the mastery o f which would be c o n s i d e r e d to  r e q u i r e i n t e l l i g e n c e by a l l b u t the d e f i n i t i o n a l r e c i d i v i s t s who h o l d t h a t t h i n k i n g i s what machines don't do. Many groups o f people have b u i l t  chess p l a y i n g programs w i t h o u t any  s p e c i f i c r e s e a r c h g o a l b u t t o make a machine p l a y b e t t e r than machines o r o t h e r p e o p l e .  A landmark h e r e was G r e e n b l a t t ' s program [ 1 2 ]  which i n c l u d e d v e r y e f f i c i e n t of  other  code, e x t e n s i v e r o u t i n e s f o r the g e n e r a t i o n  p l a u s i b l e moves and time s a v i n g t r e e p r u n i n g methods.  T h i s program  beat Dreyfus who had w r i t t e n t h a t such t h i n g s were i m p o s s i b l e [ 5 ] ,  It  has been e n r o l l e d i n the U.S. Chess F e d e r a t i o n , has p l a y e d i n tournaments and  i t seems t h a t f u r t h e r e f f o r t s a l o n g the same l i n e s have l i t t l e to  c o n t r i b u t e to the s t a t e o f knowledge i n the f i e l d .  7.  H e u r i s t i c s e a r c h i n g i n problem environment  f o r experiments.  worked w i t h the e i g h t and  s o l v i n g has o f t e n used games as  the  The Graph T r a v e r s e r (Doran and M i c h i e [ 6 ] )  f i f t e e n - p u z z l e s , S l a g l e [23] developed  almost unbeatable program that p l a y s K a l a h w h i l e p r o d u c i n g  an  refinements  i n t r e e s e a r c h i n g and p r u n i n g t e c h n i q u e s . Most work i n computing w i t h games i s aimed a t u n c o v e r i n g some t h i n g s u n r e l a t e d to the games themselves  (with the e x c e p t i o n o f chess mentioned  above); e i t h e r methods of human thought h e u r i s t i c methods.  i n problem  solving or general  However i n almost a l l cases t h e r e i s a c o n s i d e r a b l e  body o f knowledge beyond the r u l e s t h a t r e l a t e s to the p l a y i n g o f the game.  Each game has i t s own  r e s u l t s h a r d e r to come by.  s p e c i a l approach There i s one  that may  f u r t h e r c l a s s o f games t h a t have  been used as r e s e a r c h t o o l s ; those where l i t t l e i s supposed to be i g n o r e d .  make g e n e r a l i s a b l e  i s known o r what i s known  Z o b r i s t ' s work w i t h Go,  [24], using numerical  v a l u e s to r e p r e s e n t v i s u a l o r g a n i s a t i o n o f the stones on a Go board, i s a good example and i t i s i n t o t h i s a r e a t h a t t h i s work  1.2  falls.  Polybmiribes Golomb [10] d e s c r i b e s the n-ominoes as g e n e r a l i s a t i o n s o f the  domino.  See,  f o r example, F i g u r e 1.  u n i t squares i n two  dimensions.  d u r i n g the course of t h i s study.  We  They a r e groups of s i m p l y  connected  s h a l l be c o n s i d e r i n g o n l y pentominoes  From F i g u r e 1, t h e r e a r e 12 b a s i c  5 - c e l l e d animals and they have been o r d e r e d and nicknamed F, I , L, N, T, U, V, W, their  X, Y,  shapes.  Z f o r convenience  and due  to the m i l d resemblance  in  P,  Monomino  •  Domino  Trominoes  Tetrominoes (a)  (b)  (c)  Pentominoes  U  w  X  I  Y  Figure 1 THE N-OMINOES FOR N < 5  9. When one a l l o w s  r o t a t i o n s and r e f l e c t i o n s there a r e then 63 d i f f e r e n t  o r i e n t a t i o n s t o be accommodated; c o n s i s t i n g o f one f o r the 'X' p i e c e t o as many as e i g h t f o r such as the 'F' p i e c e  (Figure 2 ) .  Pentominoes have been mentioned i n s e v e r a l p l a c e s  i n the p u z z l e  l i t e r a t u r e ; perhaps one o f the e a r l i e s t was i n the 7 4 ^ problem o f Dudeney [ 7 ] i n 1908 who d e s c r i b e d how a chess board was broken over the head o f the Dauphin by P r i n c e Henry. i t was d i s c o v e r e d  While the P r i n c e was busy  t h a t the board had been broken i n t o 13 p i e c e s  escaping - 12  pentominoes and the square t e t r o m i n o , the problem i n c i d e n t a l l y was merely to r e c o n s t r u c t  1.3  the b o a r d .  The Game o f Pentbmiribes Martin  Gardner has w r i t t e n s e v e r a l a r t i c l e s on pentominoes i n the  S c i e n t i f i c American [ 9 ] , based on communications w i t h Golomb and he has included The  d e s c r i p t i o n s o f p o s s i b l e games and some examples. r u l e s adhered to w h i l e programming a r e q u i t e a r b i t r a r y and  merely r e p r e s e n t  some c h o i c e s  among many v a r i a n t s .  A few t h i n g s have  been borne i n mind o f c o u r s e ; f o r example, i t must n o t be p o s s i b l e t o employ a simple a l g o r i t h m  i n order  to w i n and i t s h o u l d  p r e f e r a b l y be a  r e a s o n a b l e game to p l a y . The  r u l e s t h a t we s h a l l use throughout a r e the f o l l o w i n g : -  (i) A rectangular  checkerboard i s a v a i l a b l e f o r p l a y which need  not n e c e s s a r i l y have a l l i t s squares f r e e , ( i i ) A subset o f the 12 p i e c e s a l l o f them). and  are available ( i n practice usually  A move i s made by s e l e c t i n g one o f these  p l a c i n g i t uniformly  pieces  i n some v a c a n t space on the b o a r d .  16!  j  L_  9 I1 110 2 11 L 1 2 12 3 13 4 14 5 15 6 116 17 7 8 118 19 N 1 2 20 3 21 4 22 5 23 6 24 7 25 8 26 }27 P 1 J28 2 !29 3 30 5 31 6 32 7 33 8 34 35 T 1 2 36  2!  l  21-  a  17  n  18!  !3i 4!  ! L  •  7!  rs5i  I  4!  15!  n  D  n  21  4  T71  !  i  n  1 2 1  4  | I Figure 2 THE 63 PENTOMINO ORIENTATIONS  r  •  n 151 X  J52Y 53 54 55 56 57 58 59  160 !61 162 Ifi3  1 2 3 4 5 6 7 8 1 2  3 4  ri  il  n  74 13  J5_ 17  i2  3 4i  1  11. T h i s p i e c e i s then no l o n g e r a v a i l a b l e t o be chosen  again  and may n o t be moved, ( i i i ) A game i s between two p l a y e r s who must move a l t e r n a t e l y . The  p l a y e r who i s unable t o move l o s e s .  C e r t a i n r e c t a n g l e s recommend themselves f o r use. n a t u r a l , the 6 x 10 i s the 'squarest'  The 8 x 8 i s  r e c t a n g l e i n t o which the 12 p i e c e s  can be made t o f i t e x a c t l y , the 6 x 6 board f o r the s p e c i a l reason it  that  i s the s m a l l e s t r e c t a n g l e whose game outcome i s unknown. Most o f o u r work i s c o n f i n e d to the 6 x 10 b o a r d , c o n c e r n i n g  which  i t has been s a i d that there a r e , " a t l e a s t 5 moves, a t most 12, no draw, more openings than, chess." 2056 p o s s i b l e c h o i c e s  Indeed the program c a l c u l a t e d t h a t t h e r e a r e  f o r an opening move (not a l l o f them e s s e n t i a l l y  different). In Polyominoes [ 1 0 ] , Golomb w r i t e s c o n c e r n i n g "1.  strategy,  T r y to move i n such a way t h a t t h e r e w i l l be room f o r an even  number o f p i e c e s . 2.  I f a p l a y e r cannot analyse  t h i n g to complicate  the s i t u a t i o n , he s h o u l d  the placement so t h a t the next p l a y e r  have even more d i f f i c u l t y  do somewill  a n a l y s i n g i t than he d i d . "  A l s o i n the S c i e n t i f i c American [ 9 ] , October 1965, "The most u s e f u l s t r a t e g y i s t o t r y t o s p l i t the board i n t o s e p a r a t e  and e q u a l  areas.  Then there w i l l be an e x c e l l e n t chance t h a t the opponent's move can be matched by your n e x t move and so on." Thus, i t i s c l e a r how w e l l t h i s game f u l f i l s o u r requirement t h a t n o t h i n g be w e l l known i n advance.  12. SAMPLE GAME SHOWING SQUARE NUMBERING SCHEME  2 3 4 5 : 6 8 9 10 11 12 i  4.  13 14 15 16 17 18 NXV-  19 20 21 2 2 23. 24 25 26 27 28 29 30 36 42  m. (a)  48 / ///A  (b)  54 60  V \  1  xvx^ .(c)  iz21._.  13.  A sample game Is i l l u s t r a t e d  i n Figure  3.  The second  player's  moves i n (b) and (d) a r e attempts to m a i n t a i n symmetry, but one can see t h a t the concept l a c k s p r e c i s i o n s i n c e no two p i e c e s he  abandons t h i s p l a n and l o s e s .  I n t h i s case i t i s q u i t e l i k e l y  he would have l o s t a l s o by p l a y i n g player's  are a l i k e .  'symmetrically'.  In (f) that  I n (g) the f i r s t  f o u r t h move ensures a win by p l a c i n g the 'W' so as to d i v i d e  the r e m a i n i n g area n e a t l y enough i n t o two areas i n t o b o t h o f which one piece w i l l f i t . The that f i t s 'T'  second p l a y e r  cannot circumvent t h e l o s s by p l a y i n g the p i e c e  i n the second a r e a  f i t i n t o e i t h e r area.  i n t o the f i r s t  s i n c e b o t h the 'N' and the  Note a l s o t h a t t h e r e a r e t e n f r e e squares i n  the upper a r e a and one c o u l d f i t the !W' and 'Y' p i e c e s but n o t h e r e s i n c e both have a l r e a d y The is  fully  been  o f the program d i s c o v e r e d  together  played.  e i g h t h and n i n t h moves need n o t even be p l a y e d determined by now.  i n there  s i n c e the outcome  As an a s i d e , a n o t too s o p h i s t i c a t e d v e r s i o n  the w i n n i n g move when c o n f r o n t e d  w i t h the  p o s i t i o n a f t e r move 6, though i t was d i f f e r e n t from the move shown. Referring  to the 6 x 10 game, Golomb i s quoted i n [ 9 ] October 1965,  "...complete a n a l y s i s i s j u s t a t the l i m i t o f what might be performed by the b e s t h i g h  speed e l e c t r o n i c computer g i v e n a generous a l l o t m e n t o f  computer time and a p a i n s t a k i n g l y  s o p h i s t i c a t e d program."  We have noted t h a t t h e r e a r e 2056 opening moves, one q u a r t e r are e s s e n t i a l l y d i f f e r e n t . this instance  S e l e c t i n g a t y p i c a l 9 move game we f i n d i n  over 1100 c h o i c e s  move the average i s over 1400). a f t e r 6, 104; and so on.  o f which  a f t e r 2 moves have been made ( a f t e r one A f t e r 4 moves, 504 c h o i c e s  remained; and  A survey Firstly,  of many sample games r e v e a l s a t l e a s t two  things  clearly.  the t o t a l number of nodes i n the move t r e e seems to be of  the  21 o r d e r of 10  .  l e a v e ~3 x 10^^  A generous allowance f o r d u p l i c a t i o n of p o s i t i o n s would p o s i t i o n s to be  5 t h i s program of 10  examined.  An  increase i n e f f i c i e n c y  6 or 10  would reduce the time r e q u i r e d to s e a r c h  t r e e e x h a u s t i v e l y to 30 y e a r s .  I n o t h e r words, c o m b i n a t o r i a l  t i o n s e l i m i n a t e the above mentioned p o s s i b i l i t y o f a b r u t e  t r e e w i d t h from i t s overwhelmingly l a r g e s t a r t of the game at most 12 moves l a t e r  f o r c e approach.  p o s i t i o n may mined by  Considerable  seen l a t e r .  that  that the s i t u a t i o n i s  advantage must be  in fact). the deterprobably  taken o f t h i s s t r u c t u r e , as  I t i s p o s s i b l e to construe  our knowledge of the game.  j u s t before  (meaning h e r e t h a t the outcome w i l l be  i n s p e c t i o n at l e n g t h ) but b e f o r e  impossible. w i l l be  be a n a l y s e d ,  the  to the i n e v i t a b l e c o n c l u s i o n  (an average of j u s t under 9,  the c o n c l u s i o n the game i s t r i v i a l ,  the  considera-  Secondly, what must be n o t i c e d i s the i n e x o r a b l e narrowing of  Just before  of  t h i s as a major p a r t o f  15. CHAPTER 2 2.1  THE PENTOMINO PROGRAM  Basic Representations The f i r s t  attempts to m a n i p u l a t e polyominoes c o m p u t a t i o n a l l y  stemmed from attempts simply to count them, an open problem. was  one o f the e a r l i e s t and a t t h a t time i t was  many 10-ominoes t h e r e a r e .  Read [18]  not f u l l y agreed  how  T h i s l e d to programs d e s i g n e d to do the  same t h i n g , the g r e a t e s t attempt so f a r b e i n g by Lunnon [13] who enumerated  has  n-ominoes f o r n ^ 20 u s i n g about 150 hours o f background  computer time on an A t l a s . Counting l i k e  t h i s and d i s s e c t i o n of r e c t a n g l e s r e q u i r e s a machine  r e p r e s e n t a t i o n f o r the pentominoes.  In d e t e r m i n i n g t h a t t h e r e a r e 2339  ways o f f i l l i n g the 6 x 10 r e c t a n g l e w i t h a l l 12 p i e c e s , F l e t c h e r  [8]  used a r e p r e s e n t a t i o n based on the l e a d i n g square o f some pentomino  as  c e n t r e , the o r i e n t a t i o n b e i n g determined by the d i s p l a c e m e n t s o f the remaining c e l l s  from the f i r s t w i t h i n a 512  square g r i d which  also  c o n t a i n e d the b o a r d . U s i n g t h i s l e a d i n g square approach he was couple o f s p e c i a l t e s t s to r e j e c t  o b l i g e d to execute a  i m p o s s i b l e board s i t u a t i o n s .  Because  of  this,  the l a c k of symmetry p r o p e r t i e s , and the f a c t t h a t the i n f l u e n c e  of  a s i n g l e p i e c e from i t s l e a d i n g square c o u l d extend over most o f the  b o a r d , t h a t r e p r e s e n t a t i o n was The program cell; the  the one  rejected f o * this  employs the ' c e n t r e ' o f each pentomino,  t h a t minimises the sum  other c e l l s .  project. always a unique  o f the rook-wise d i s t a n c e s to a l l  I n F i g u r e 1 the c e n t r e i s the square t h a t c o n t a i n s the  l e t t e r of the a l p h a b e t .  C l e a r l y the ' d i s t a n c e ' to any o t h e r c e l l i s  16.  never more than 2 u n i t s .  The 12-neighbourhood shown i n F i g u r e 4, i s used  e x t e n s i v e l y , as w e l l as i t s a s s o c i a t e d c e l l - o r d e r i n g scheme. 63 o r i e n t a t i o n s w i l l  Any o f the  f i t i n the 12-neighbourhood when the c e n t r e s c o i n c i d e .  T h i s d e v i c e i s used t o r e p r e s e n t a p i e c e and a l s o p a r t s o f the b o a r d , i n t e r n a l l y , by t r a n s l a t i n g to s t r i n g s o f b i t s . F i r s t l y a piece. i n F i g u r e 5.  F o r example o r i e n t a t i o n 50, which i s W 4 i s shown  T h i s i s u n i q u e l y r e p r e s e n t e d by c e l l s 1, 2, 5 and 7 i n the  12-neighbourhood; a l t e r n a t i v e l y by the b i t - s t r i n g 1111  with  (from 1 t o 12) 0011 0101  zeros i n d i c a t i n g the c e l l s o f the p i e c e .  In complementary f a s h i o n the s t a t e o f the board w i t h r e s p e c t t o any p a r t i c u l a r square t h a t we choose can be r e p r e s e n t e d . the neighbourhood o f square 26 has c e l l s r e p r e s e n t i t as 0101 0101 0000 a t t h i s  I n F i g u r e s 6 and 7  2, 4, 6 and 8 f r e e so we can  time.  Now t h i s square 26 can be i s o l a t e d , and i n o r d e r to see which p i e c e s can be moved h e r e (a move meaning t h a t the c e n t r e o f the p i e c e w i l l be p l a c e d on t h i s square) one needs merely t o 'OR' i t s neighbourhood b i t s t r i n g w i t h the b i t s t r i n g s f o r the o r i e n t a t i o n s , and i f the r e s u l t i s a l l ones then t h e r e i s a ' h i t ' . 0101  F o r example, square 24 would have  0001 1010 and o r i e n t a t i o n 42 which i s U 4 has 1010 1100 1111. Now  (0101 0001 1010) 'OR'  (1010 1100 1111) i s (1111 1101 1111)  thus U 4 w i l l n o t f i t i n square 24.  However f o r square 26 and o r i e n t a -  t i o n 60 o r Z 1 (0101 and  0101 0000) 'OR'  i t clearly  (1010 1010 1111) = (1111 1111 1111)  fits.  In the program the board  i s kept  as a simple a r r a y , b u t each square  9 8  4  •tm  12 3  2  7 12!  6l Figure 4  ill!  THE 12-NEIGHBOURHOOD  i  !  :  I  pa i  1  ^**^  7  |5  5  Figure 5 SQUARES OCCUPIED BY ORIENTATION W 4  !  • .  •///  8  SI  4  -'  /  !  24  - /  26  i.  2  6  yj-'  •"/>  r  26 yy/s  life-  t  i  ;  V . ' /  VS" y .  1 •'>;.  :  1'  0101  0101 000  /  '/(/-\  Figure 6  Figure 7  APPLICATION OF 12-NEIGHBOURHOOD TO MOVE DETERMINATION  m y>%/^  mm  m 0101  0111 0000  0101  0111 1000  Figure 9 Figure 8 BIT STRINGS FOR CERTAIN NEIGHBOURHOODS  "777"  M  wA VV/t \s////  0101  0111 1100  F i g u r e 9a  1101  0111 1100  F i g u r e 10  18.  is bit  k e p t informed o f the s t a t u s o f i t s 12-neighbourhood by h a v i n g i t s s t r i n g updated when moves a r e made nearby. When e x e c u t i n g ,  the program i s informed o f t h e board dimension and  the p i e c e a v a i l a b i l i t y , and then c a l l s the r o u t i n e t h a t i n i t i a l i s e s the neighbourhoods c o r r e c t l y .  I f a move i s made another r o u t i n e i s c a l l e d  t h a t updates t h e s i t u a t i o n , e l i m i n a t e s  2.2  t h e p i e c e and so on.  Some Necessary Improvements The  bit-matching  tests j u s t described  are u s u a l l y 60 squares to c o n s i d e r  a r e q u i t e e f f i c i e n t but t h e r e  and 63 o r i e n t a t i o n s t o watch and to  do e v e r y t e s t every time would consume too much time even b e f o r e start  we  t h i n k i n g o f doing some a n a l y s i s o f p o s i t i o n s . 12 There a r e 2  o r 4096 d i f f e r e n t p o s s i b l e neighbourhoods.  I t would  be  u s e f u l i f we c o u l d d e c i d e which neighbourhood was a p p l i c a b l e ,  it  up somewhere and r e c e i v e a s h o r t l i s t  o f which a r e known to f i t .  dial  of candidate o r i e n t a t i o n s , a l l  However t h i s would e n t a i l , i n s t e a d o f c a l -  c u l a t i o n , maintenance o f 4096 t a b l e s each o f up to 63 i t e m s , an u n l i k e l y t r a d e - o f f u n l e s s we were d e s p e r a t e . Still, be  there  a r e some t h i n g s  to n o t i c e .  60 o n l y , and would be a subset o f the l i s t  The l i s t  f o r Figure  f o r Figure  7 would  8 which i s 42,  60; which i n t u r n i s a subset o f t h a t f o r F i g u r e 9; i . e . , 11, 18, 42, 60. Figure  9a and F i g u r e 9 a r e e q u i v a l e n t  f o r t h i s purpose.  We can a l s o see  from the b i t s t r i n g s i n v o l v e d t h a t 0000 0000 0000 r e q u i r e s a n u l l w h i l e 1111 1111 1111 r e t u r n s one  t o the o t h e r  on a 12-cube.  the f u l l  list,  63 o r i e n t a t i o n s , and to go from the  changing one b i t a t a time i s e q u i v a l e n t  t o f i n d i n g paths  19.  Perhaps one  c o u l d produce the s m a l l e s t p o s s i b l e l i s t  which would have the p r o p e r t y bourhood and shortest l i s t  that i t c o u l d be indexed  r e t u r n the c o r r e c t s u b s e t . c o u l d n o t be  of o r i e n t a t i o n s  f o r any  neigh-  A method o f c o n s t r u c t i n g t h i s  d i s c o v e r e d d u r i n g the course  of t h i s work.  So, what has been w r i t t e n i n s t e a d i s a program t h a t b u i l d s as lists  as p o s s i b l e to s a t i s f y  a super-list.  the requirement and  T h i s turned out  savings  over the t h r e a t e n e d  s u p e r - l i s t must be  concatenate them i n t o  to comprise 4974 items,  12 2  few  a  considerable  6 (2-1)  o r about 250,000.  a s s o c i a t e d merely the 4096 indexes and  With  this  lengths  of  sub-lists. Thus what i s done i s t h i s : indexed be  to r e t u r n the l i s t  checked f o r p i e c e Two  f o r any neighbourhood, the b i g l i s t  o f o r i e n t a t i o n s t h a t f i t and  examples w i l l i l l u s t r a t e  this.  Firstly,  sought which w i l l g i v e the l o c a t i o n and  t h i s end one  these need o n l y  availability.  the b i n a r y number 010101111100 i s converted is  is  l o o k s i n t o the b i g l i s t  r e f e r r i n g to F i g u r e  to decimal  1404.  A  couple  s i z e o f the move l i s t .  at l o c a t i o n (2 x 1404)  + a  9a,  To constant  o f f s e t o f 4975 = 7783. C o n s u l t i n g the c h a r t at t h i s l o c a t i o n , e x h i b i t e d i n Appendix 2B)  one  p o s s i b l e moves are a t 2185 t i o n 11,  18,  42  and  60.  (these p a r t s o f the l i s t s  f i n d s the couple  i n the b i g l i s t .  (2185  4).  So,  the  four  These are seen to be o r i e n t a -  The moves are L 1, L 8, U 4, and  Z 1 as  was  v e r i f i e d by i n s p e c t i o n . The decimal  second example, F i g u r e 10, p r o v i d e s b i n a r y 110101111100 o r 3452.  4975 + 3452 + 3452 = 11879.  are  At t h i s l o c a t i o n one  finds  20.  (3274 1 4 ) . The 14 o r i e n t a t i o n s a t 3274 a r e 3, 8, 11, 18, 21, 22, 25, 32,  38, 42, 43, 49, 54, and 60.  These moves a r e F 3, F 8, L 1, L 8,  N 3, N 4, N 7, P 6, T 4, V 1, W 3, Y 3, and Z 1. The  second problem to be f a c e d says t h a t even i f we had some  h e u r i s t i c s t o guide move s e l e c t i o n on some more o r l e s s r e l i a b l e b a s i s , when we a r e s u f f i c i e n t l y tree i s narrowing f a s t ,  c l o s e t o the end o f the game, and the s e a r c h then i t i s e s s e n t i a l t o stop and a n a l y s e t h e  p o s i t i o n thoroughly, o r r i s k overlooking any Of  p l a y e r o f t h i s game, b r u t e  the r i g h t move.  f o r c e a n a l y s i s takes over  c o u r s e , d e c i d i n g when t h i s i s p o s s i b l e d u r i n g  i s as c h a l l e n g i n g as the a n a l y s i s i t s e l f .  e a r l i e r on u n t i l  the time r e q u i r e d  eventually.  the c o u r s e o f a game  Because o f the sudden  n a t i o n f e a t u r e , t h e r e has to be a complete s e a r c h T h i s i s t r i v i a l t o do a t the v e r y  That i s , to  termi-  implemented somewhere.  end, and i n c r e a s i n g l y arduous  to do i t i s c l e a r l y n o t a v a i l a b l e .  Much judgment i n p l a y i n g the game i s concerned w i t h c h o o s i n g the p o i n t when one must be e x h a u s t i v e i n s t e a d o f making e s t i m a t i o n s .  It is  p o s s i b l e t h a t one p a r t o f a s u c c e s s f u l s t r a t e g y w i l l be to arrange t h a t it  i s you and n o t your opponent t h a t w i l l be l e f t w i t h a p o s i t i o n o f  that s o r t . Carrying  the analogy to the machine i t i s e q u a l l y c l e a r t h a t  l e s s o f what e l s e i t i s d o i n g , when the game i s d e t e c t a b l y to i t s f i n i s h , t h e program a l s o must make an e x h a u s t i v e A reasonable estimate of proximity  regard-  c l o s e enough  search.  t o the end i s a count o f the  number o f o r i e n t a t i o n s remaining f o r a p l a y e r t o choose from i n the c u r r e n t p o s i t i o n , perhaps m o d i f i e d  by the degree t o which they a r e con-  21.  c e n t r a t e d on a few  squares  on the b o a r d .  The more w i d e l y  s c a t t e r e d , the h a r d e r i t i s to d e c i d e the r e s u l t , as a T h e o r e t i c a l l y , the 6 x 10 pentomino board  and  they  rule.  i t s s t a t e can  r e p r e s e n t e d by a s t r i n g of 60 b i t s , on or o f f f o r occupancy. n a t e l y the game i s u n l i k e checkers than changing is difficult  a couple o f b i t s .  are  be  Unfortu-  i n t h a t t h e r e i s much more to a move  In f a c t , g i v e n o n l y t h i s b i t s t r i n g i t  to c a l c u l a t e what i s p o s s i b l e , l e t a l o n e do i t .  I f one  wants to c a r r y along 12-neighbourhoods and o t h e r u s e f u l i n f o r m a t i o n then the s t o r a g e requirements  i n core  (hundreds of b y t e s p e r p o s i t i o n )  mean t h a t o n l y v e r y few nodes c o u l d be expanded a t once i n c o r e ,  and  even then much time would be used m a i n t a i n i n g these neighbourhood statuses. The method was  s e l e c t e d whereby the board  i s not s t o r e d a t a l l a t  each node b u t o n l y the move made to r e a c h the node. board  (without d e t a i l s o f move counts  An  abbreviated  etc.) i s maintained  and movement  up and  down the game t r e e i s made by p l a y i n g and u n p l a y i n g moves on  'fast'  board.  By  this  t h i s means, l a r g e numbers o f v a r i a t i o n s can be saved and a l l of  the remaining moves i n the game can be p l a y e d merely by moving down the tree.  In f a c t , t h e r e i s l e s s v a l u e than might appear i n s a v i n g  tree.  The  the  s e a r c h can o n l y be made q u i t e c l o s e to the end of the game.  Two  moves l a t e r , when next  now  have become  the o p p o r t u n i t y a r i s e s ,  the s e a r c h w i l l  by  trivial.  S i n c e the p o s i t i o n s are not s t o r e d a t nodes, the s e a r c h i s depth f i r s t by n e c e s s i t y .  I f t h i s were not so the t r e e w i d t h ,  even a t  this  F i g u r e 11 FORMAT FOR THE TREE SEARCH  LEVEL 0  LEVEL 1  Unex- j paneled Node j  —  t=i. > o  LEVEL 2  22.  l a t e stage,  i s too wide f o r a b r e a d t h  reached i s a t e r m i n a l p o s i t i o n which which makes minimaxing and  first  search.  The  ' e v a l u a t e s ' simply  lowest to win  a p p l i c a t i o n of the a l p h a - b e t a  depth or l o s e ,  procedure v e r y  straightforward. There are two  k i n d s of nodes i n the t r e e , 'expanded' and  'unexpanded'  Nodes r e p r e s e n t i n g moves on the board are the expanded nodes. o f these  From  i s developed an unexpanded node, i n e f f e c t h a l f a l e v e l  one  lower  down, which i n d i c a t e s upon which square of the board a t t e n t i o n i s b e i n g focused.  In g e n e r a l s e v e r a l o r i e n t a t i o n s may  as c e n t r e , and  node, the f u l l  s e t o f unexpanded nodes are  f o r each square a v a i l a b l e as a move c e n t r e .  time the moves are p l a y e d by d e v e l o p i n g set  this  square  these become the expanded nodes.  From the i n i t i a l one  be p l a c e d w i t h  From one  developed  o f these a t a  the expanded nodes, then the  of unexpanded from the c u r r e n t expanded node, and  so on  (see  full  Figure  11). Most nodes c o n t a i n p o i n t e r s to f a t h e r , b r o t h e r s , son e t c . , l o c a t i o n s for  p l y l e v e l , whom to move, backed up v a l u e s , e t c .  r e c o r d the board square and  The  unexpanded nodes  the s t a t u s o f the 12-neighbourhood,  expanded nodes the p i e c e and The  The  the  i t s o r i e n t a t i o n as the move p l a y e d .  s e a r c h r o u t i n e i s w r i t t e n i n PL/I w i t h o u t  using pointer v a r i a b l e s  s e a r c h space i s an a r r a y of f i x e d s i z e whose garbage c o l l e c t i o n i s  simply  c o n t r o l l e d i n a manner j u s t as easy to implement i n F o r t r a n ,  say.  Each node p o i n t s t o the next a v a i l a b l e l o c a t i o n ; the f i n a l item p o i n t s 0  (see F i g u r e 12).  0 now  When a node i s f r e e d , the node t h a t was  p o i n t s to i t and  i t now  p o i n t s to 0.  On  the IBM  p o i n t i n g to  360/67, i f the  to  24.  Location of Next Item  No. o f Item-  Location o f Next Item  No. o f Item  1  1  2  1  2  3  2.  |  3  4  3  !  4  5  4  5  6  5  2 '  3 4  1  0 6  • • •  3000  0  3000  Initially  A f t e r Freeing  4 Item 4  F i g u r e 12 GARBAGE COLLECTION FOR THE TREE SEARCHING ARRAY  25.  c h a i n i n g s were r e s t r i c t e d to w i t h i n d i s c r e t e pages then t h e r e would be r e l a t i v e l y few o c c a s i o n s f o r p o i n t i n g a c r o s s page b o u n d a r i e s . i n PL/I one doesn't c o n t r o l page a l i g n m e n t s .  However  Consequently t h e r e i s some  d e t e r i o r a t i o n i f the s e a r c h c o n t i n u e s expanding nodes l o n g beyond the array s i z e  limit.  In p r a c t i c e , t h e s e a r c h develops i n excess o f 200 nodes p e r CPU second  (somewhat l e s s when t h e p a g i n g demands r i s e e x c e s s i v e l y ) .  dozen i n t e g e r s a r e needed f o r a node p l u s a few b i t s . 2 b y t e s a t l e a s t i n t h i s system.  A  Each i n t e g e r uses  Thus each node uses 26 b y t e s and t h e  a r r a y o f 3000 items o c c u p i e s 78,000 b y t e s , n o t too heavy a p r i c e .  Using  t h i s a r r a y the s e a r c h has been a b l e t o develop over 9000 nodes. A l i m i t o f 60 move c h o i c e s was s e t as the p o i n t when the program must make the f u l l s e a r c h ; and 100 when p l a y i n g human opponents. encountered no case where i t f a i l e d w i t h t h i s s e a r c h space. v e r y n o t i c e a b l e c o n t r a s t i n node development a w i n n i n g move i s found  I have  There i s a  between those cases where  ( i n v a r i a b l y j u s t a few CPU seconds a t most) and  those where a l o s s must be e s t a b l i s h e d  ( f r e q u e n t l y more than 4000 nodes  o r 20 seconds) i . e . i f a w i n w i l l be found, i t w i l l be found  quickly.  My t e s t s r e v e a l e d t h a t wins c o u l d be e s t a b l i s h e d i n p o s i t i o n s  offering  w e l l i n excess o f 100 c h o i c e s , b u t t h a t i f the w i n was absent, t h e s e a r c h would o v e r f l o w any r e a s o n a b l e s e a r c h space.  ( I n o t h e r words, i t i s v e r y  u s e f u l t o know whether one can win b e f o r e t r y i n g t o f i n d o u t ) . t h e r e i s e v i d e n c e f o r the u t i l i t y  As i t i s ,  o f c u t t i n g o f f the s e a r c h e a r l y , when  the p r o b a b i l i t y o f a s u c c e s s f u l outcome i s much reduced.  26.  CHAPTER 3 3.1  THE  "INTELLIGENT" ADDITIONS AND  THEIR EFFECTS  A i d s to Move S e l e c t i o n One  by a new  o f the f i n a l problems was  how  to r e p l a c e the random move g e n e r a t o r  one and be a b l e to n o t i c e the improvement.  The program c o l l e c t s numbers as i t s r o u t i n e goes around u p d a t i n g neighbourhoods of the  a f t e r a move has been made.  The r o u t i n e counts the number  squares where moves are p o s s i b l e , and f o r each one o f those i t counts number o f o r i e n t a t i o n s t h a t are a v a i l a b l e and do f i t i n t h a t  square.  An example from a sample game a f t e r 2 moves on a 6 x 6 b o a r d i s shown i n F i g u r e 13, a t o t a l o f 287  c h o i c e s f o r a p o s s i b l e move w i t h 19 p o s s i b l e  c h o i c e s f o r a square as c e n t r e f o r t h a t move. move t h e r e remain 137 moves and 13 These  In F i g u r e 14, a f t e r  another  centres.  two numbers and t h e i r r a t i o do o f f e r some i d e a o f space r e -  maining, r o u g h l y how  many moves and p r e v a l e n c e o f open areas i n the p o s i t i o n .  I t i s c e r t a i n l y n o t known, a p r i o r i , c o r r e c t n e x t move.  how  to c o n v e r t these concepts i n t o the  However, once s e v e r a l games have been p l a y e d , t h e r e may  e x i s t some reason to b e l i e v e t h a t 137:13 might i n d i c a t e a p o s i t i o n where one was was  more l i k e l y  to win than to l o s e .  I t might be found t h a t 200:13  u n f a v o u r a b l e , a l s o 137:18 and 137:8. The program t h a t uses such i n f o r m a t i o n to modify i t s b e h a v i o u r can a t  l e a s t be  'punished' f o r i t s mistakes and be hoped to l e a r n to improve i t s  play. The n u m e r i c a l measures are a form o f f e a t u r e e x t r a c t i o n . happened t h a t too many heterogeneous  I f i t had  c h a r a c t e r i s t i c s of the p o s i t i o n had  mapped i n t o the same s m a l l s e t o f numbers then some a l t e r n a t i v e mapping  0 ''/\ y'y'y'  12 F i g u r e 13  o  i  1 ! 2  0 0  6 -•/yy, 0 16 ! 8 o 1 0 !19 31 8 - i 3 19 21. 0 .-'  ,'  •/'  /  •  yyi<y] Figure  1 2 0 14  COUNTS OF POSSIBLE ORIENTATIONS IN THEIR CENTRE SQUARES  yi m  F i g u r e 15  m  m  F i g u r e 16  GAME POSITION TO ILLUSTRATE INFORMATION GATHERING PROCESS  28.  would have to be d i s c o v e r e d . represent  concentrations  What have been used a r e f i g u r e s t h a t  o f moves a l l over the board and from which the  i n f l u e n c e s o f t h e p i e c e s can be deduced.  T h i s approach i s somewhat a k i n  to t h a t o f Z o b r i s t i n GO [ 2 4 ] , s i n c e the i n f l u e n c e o f a b i s h o p is  i n chess  c l e a r l y enough d e f i n e d b u t t h a t o f an a n t i c i p a t e d move o f a GO  stone  i s n o t and o f a Pentomino p i e c e even l e s s s o . In chess,  and o t h e r games, one can have a c l e a r l y  'winning' p o s i t i o n  even though a f o r c e d c o n c l u s i o n cannot be demonstrated; f o r example, a queen ahead, o t h e r t h i n g s b e i n g  equal.  T h i s can be measured by a count  o f r e l a t i v e m a t e r i a l s t r e n g t h s , which w i l l be p a r t  (or a l l ) of a s t a t i c  e v a l u a t i o n o f a chess p o s i t i o n , and i s o n l y the f a c t t h a t these exist  being  features  t h a t makes such an e v a l u a t i o n p o s s i b l e . In Pentominoes, e i t h e r a win ( o r l o s s ) can be demonstrated (by  exhausting  c a s e s ) o r the p o s i t i o n i s not c l e a r .  Strategical  such as symmetry and the s i z e o f the d i s c r e t e , remaining  concepts,  areas  have been  mentioned, b u t t h e i r e f f e c t i s never such as to cause a p l a y e r to g i v e up as most would when a queen down i n chess. One knows by e x p e r i e n c e  that i t may be wise to a v o i d c e r t a i n k i n d s  of p o s i t i o n s , a r e a s , symmetries, e t c .  The i n t e n t i o n i s to have the  program develop s i m i l a r k i n d s o f i n f o r m a t i o n , p r a g m a t i c a l l y , b e t t e r i d e a s about good and bad p o s i t i o n s by t h e e x p e r i e n c e has  p l a y e d , u s i n g i n f o r m a t i o n t h a t i t has computed To  gaining o f games i t  itself.  t h i s end one hundred games o f random moves were generated w i t h i n  the program and t h e d e t a i l s o f move counts and c o n c e n t r a t i o n s each move.  A l l the games were a n a l y s e d  stored f o r  from t h e i r t e r m i n a t i n g move back-  29. wards u n t i l the p o s i t i o n s were beyond r e a s o n a b l e study. not  expect to spend more than 20 minutes on one  which had  some r o u t i n e s developed to do  too expensive to use  for this.  the game, where the outcome was and b u i l t A  into a f i l e  still  and  l e a s t one  other  This process  was  to choosing a  is distinct  used, o f t a k i n g a  example p o s i t i o n ( F i g u r e 15) w i l l h e l p  mation i s to be exhaustively  stored.  ( i t may  T p i e c e at square 49 Figure  from  piece  We  guess t h a t i t i s too d i f f i c u l t  not be)  w i l l win  infor-  to examine  more move i s generated, move 6,  i n i t s fourth o r i e n t a t i o n , abbreviated  a v a i l a b l e squares.  s i n c e e x a c t l y two  the  T 4 49,  see  The  There are 114  move suggested by  to t e l l  We  of  the program, V 2  assume t h a t the program i s t u r n i n g  I t computes t h a t i f i t p l a y s T 4 49, squares.  choices  21  moves remain.  R e t u r n i n g to F i g u r e 15,  15  so one  the r e s u l t i s easy to determine.  moves i n 15  moves.  r e v e a l what k i n d of  16.  Now  way  possible  f i n d i n g somewhere to put i t . An  in  there and  not  recorded  the program.  o f the  method i s e q u i v a l e n t  random scheme t h a t was  of  u s i n g an a v a i l a b l e random  played.  l o c a t i o n , then s e l e c t i n g something to p l a c e at  augmented by  s e l e c t e d , then one  chosen and The  computer,  to the s t a r t  c l e a r , the d e t a i l s were  accessed and  number g e n e r a t o r , a f r e e square was  the  the same t h i n g , r a p i d l y became  'random' game here means the f o l l o w i n g :  r e p e a t e d u n t i l the game ended.  p o s i t i o n and  At the p o s i t i o n n e a r e s t  l a t e r to be  o r i e n t a t i o n s f o r t h a t square was  A p e r s o n would  over  t h e r e w i l l remain 114  have seen t h a t i t would then l o s e , so we  moves  want some  i t t h a t t h i s i s a p o s i t i o n to be a v o i d e d so t h a t no  opponent  s h o u l d be l u c k y enough t o be l e f t w i t h i t . So we make an e n t r y o p p o s i t e 114 under number o f squares s u b t r a c t 8 from t h e s t o r e d v a l u e .  = 15.  We  T h i s v a l u e i s a r b i t r a r y but i s arranged  i n o r d e r to o b t a i n a r i p p l e e f f e c t .  I f 114:15 i s a poor p o s i t i o n t o  l e a v e , then so may w e l l be 113:15 o r 115:15, o n l y l e s s c o n c l u s i v e l y s o ; thus  the s u b t r a c t i o n s go as f o l l o w s :  The  p o s i t i o n before  111:15  -1  112:15  -2  113:15  -4  114:15  -8  115:15  -4  116:15  -2  117:15  -1  the T was p l a c e d had 161 c h o i c e s i n 27  Even though i t cannot be a n a l y s e d opposite f a v o u r a b i l i t y position  squares.  (supposedly) we guess t h a t i t may have  from i t s s u c c e s s o r  (perhaps we s h o u l d l e a v e  to the opponent so he can l e a v e us t h e good o n e ) .  away: 158:27  +1  159:27  +2  160:27  +3  161:27  +4  162:27  +3  163:27  +2  164:27  +1  So we  this file  31.  The  numbers are s m a l l e r s i n c e we  b e f o r e move 5 had  483  are l e s s convinced.  c h o i c e s i n 34 squares, 482:34  -1  483:34  -2  484:34  -1  The p o s i t i o n  as a l a s t g e s t u r e we  store:  A s e t o f r o u t i n e s have been w r i t t e n t h a t r e c e i v e a s e r i e s of move counts and  the amount to be added or s u b t r a c t e d and  r e b u i l d the  list  s t r u c t u r e t h a t w i l l r e f l e c t updated v a l u e s . C u r r e n t l y , a l l the p o i n t e r s and p o s i t i o n e v a l u a t i o n s are s t o r e d i n an a r r a y of j u s t over 3400 numbers. Appendix 2D. o f how  The  complete l i s t  I t s o p e r a t i o n can be made e x p l i c i t by  i s provided  g i v i n g an  in  example  the program uses i t to compare p o t e n t i a l moves.  Suppose t h a t the program i s t r y i n g to f i n d the most f a v o u r a b l e move in and  the p o s i t i o n drawn i n F i g u r e 15.  then examine the r e s u l t i n g p o s i t i o n s to count the number of moves  remaining  open and  l i e s between 49 and  their respective centres. 520,  t h e r e may  Imagine t h a t one move l e a v e s for  89 i s found i n the l i s t  Thus the v a l u e s  a r e to be  p a i r s of scores, a value The  I t w i l l p l a y the moves h y p o t h e t i c a l l y  v a l u e g i v e n f o r 89:15  be  I f t h i s number of moves  i n f o r m a t i o n to l o o k  89 c h o i c e s i n 15 squares.  o f f s e t by 47,  found b e g i n n i n g  a poor  The  pointer  i . e . , l o c a t i o n 42  (Appendix  at l o c a t i o n 946.  There a r e  f o r move c e n t r e counts 13, i s -10,  up.  15,  16,  23 and  25.  choice.  As a second case, suppose t h a t another move l e a v e s the p o s i t i o n 75:20.  Now  75 - 47 = 28.  p a i r s s t a r t i n g at 798,  P o i n t e r a t 28 = 798.  Scanning through  the v a l u e f o r c e n t r e count = 20 i s  +1.  the  2D).  32.  C l e a r l y the program w i l l p r e f e r the move t h a t l e a v e s In cases such as t h i s one, highest  3.2  s c o r e w i l l be  Experimental On  a l l moves w i l l be  t e s t e d and  were 60 o r fewer c h o i c e s  36  random games i n some d e t a i l and  d i d employ the s e a r c h  seconds CPU  perhaps more remarkable than was  t h i s game (such D u r i n g the  no  a c c e s s to the  guidance  An  average  computer  tests.  program moved f i r s t  i n a l l cases,  there  v e r s i o n of the program com-  l i m i t e d a c c e s s to the  When i t moved second, i t won.11 and  a plus score  took over when  e q u a l l y w e l l at the end.  time per game and  When the m o d i f i e d  incorporating  45.  a v e r s i o n of i t s e l f which had  prevented r e a l l y l a r g e s c a l e  3.  (15 cases) i t won  l o s t 10.  expected.  considering  The  12 and  newer v e r s i o n  obtaining  the unusual random e f f e c t s i n  as seeming to have a 'good p o s i t i o n ' but i n t e r n e c i n e phase o f one  l o s i n g anyway.)  program v e r s i o n p l a y i n g  against  i n i t i a t e d o n l y when 60 o r fewer move  choices  100  (the l i m i t was  lost  These r e s u l t s are  a n o t h e r , the minimax s e a r c h was remained  the  found t h a t the f i r s t p l a y e r wins  games were p l a y e d w i t h the m o d i f i e d  t a b l e s , but o f 60  f o r a move, we  the second p l a y e r wins  peting against  with  Results  examining the 100  games and  the one  chosen.  the assumption t h a t the f o o l p r o o f minimax s e a r c h  55  this position.  when p e o p l e p a r t i c i p a t e d ) .  As i t s  s o l e s t r a t e g y , some v e r s i o n c o u l d be programmed to make every attempt to a v o i d g i v i n g i t s opponent the chance to invoke the s e a r c h By b e i n g  the one  to s e a r c h  advantage would be  first  i t c o u l d be  gained s i n c e most o t h e r  routine.  suggested t h a t a  s t r a t e g i e s c o u l d be  crucial claimed  33. to be o n l y m a r g i n a l l y T h i s was was  effective.  not so i n p r a c t i c e .  f o r c e d to move w i t h o u t  f u t i l e gesture  S e v e r a l times d u r i n g games, a program  searching.  of e x h a u s t i v e l y s e a r c h i n g  about to l o s e .  then a l l o w e d  to d i s c o v e r t h a t i t was  the  just  In f a c t , no v e r s i o n used the s e a r c h c u t - o f f p o i n t i n  d e c i s i o n making; m o s t l y because i t had they  I t s opponent was  to p e r f o r m a g a i n s t p e o p l e ,  take no n o t i c e of such a r b i t r a r y , and  and  to them u n d e t e c t a b l e ,  What o f games between p e o p l e and v e r s i o n s of the program?  boundaries. I t would  have been v e r y expensive to undertake the s e r i e s of c o n t r o l l e d e x p e r i ments r e q u i r e d to be a b l e to d i s t i n g u i s h the random program w i t h  s e a r c h , because of the h i g h random success  the l a r g e amounts o f CPU How opponent?  s h o u l d one Not  by  'smart' v e r s i o n from  the  rate  and  time needed f o r each game.  measure the improvement i n an under or overmatched  counting v i c t o r i e s .  I t must be noted t h a t i n the  final  s e r i e s of 6 c o n t r o l l e d games w i t h human s u b j e c t s as opponents the machine l o s t but once. s i o n won  That l o s s was  with  the improved v e r s i o n , the random v e r -  a l l i t s 3 games.  What one  tries  to s e a r c h f o r i n s t e a d ( v i z . Samuel [20])  improvement i n the c l a s s of i n d i v i d u a l moves. compared w i t h those  i s an  These moves would  suggested by acknowledged good p l a y e r s  be  (sadly, hard  to come by i n Pentominoes). Here i s the most n o t i c e a b l e improvement, the newest v e r s i o n makes i n d i v i d u a l moves t h a t make sense i n t u i t i v e l y t h a t one  to i t s opponent; so much so  s u b j e c t a s c r i b e d to the r a t i o n a l i t y of i t s p l a y h i s a b i l i t y  b e a t i t when he  did.  The  random p l a y e r , on the o t h e r hand, was  to  confusing;  34. no one at  c o u l d t e l l what i t was  a l l until  the s e a r c h  up  t o , as, o f c o u r s e , i t was  up  to  nothing  phase.  There are f o u r sample games i n Appendix 2E f o r i l l u s t r a t i o n . one  shows the random machine moving second a g a i n s t i t s human opponent.  In F i g u r e 17a  the program has  generated moves 2, 4 and  being p a r t i c u l a r l y i n d i f f e r e n t . example of random versus The  o f the two  6,  pieces  t h a t f i t around squares 6 and  by p l a y i n g the N p i e c e as shown i n F i g u r e the s u b j e c t p l a y s f i r s t The  p l a y s i t s f i r s t move w i t h  d i f f i c u l t and its  The  line  took l e s s  than  The human c o u l d have  won  and p l a y s h i s f i r s t moves around has  access  the i n t e n t i o n of r e d u c i n g  to i t s t a b l e s  the open space  I t s p o s i t i o n i n F i g u r e 18a  the move i t chose seems to be a good t r y .  moves o f the N and Y p i e c e s i n the areas  shown.  and  i s very  Unfortunately,  opponent can f i n d the move of the T p i e c e , i n F i g u r e 18c,  t h i s i n a 24-node s e a r c h ; i t s p l a y now  The  17c.  program which now  p l a y s i n the middle o f the b o a r d .  12.  to f i n i s h the game.  second to expand only about 46 nodes.  the edge o f the board.  an  this.  o f f i g u r e s above the w i n n i n g move shows t h a t the s e a r c h  In game 2,  last  to l e a v e j u s t 2 moves but makes the mistake  program i n i t s s e a r c h uses the o t h e r one  CPU  the  T h i s game s e r v e s j u s t as w e l l as  random, they l o o k e d much l i k e  f i r s t p l a y e r plans  of u s i n g one  one  Game  leaving  The program v e r i f i e s  e x h i b i t s some purpose, whether  t h i s i s r e l e v a n t to w i n n i n g i s another m a t t e r . In game 3, the program moves f i r s t , it  c o n s i d e r s i s F i g u r e 19a.  ( F i g u r e 19b)  and  a f t e r 4 moves the  position  The move of the N p i e c e t h a t i t p l a y s  i s remarkably s t r o n g , q u i t e p o s s i b l y w i n n i n g a g a i n s t a l l  35  X'' / //  ///YY,  YY <YY  12  '/// X//i W V y  ^4X~  .\\\vv  \ • i. /////  '"////ft.  .• XX  Yy  Y YYs ////S/Y/Y  rx  YMSL .V-  i>XXv  't  KY-yy F7T ///  \y'// /Y////.'s  xxx Y  '  YYVy^-yy /,'>'•' Ys .-' ;  \ fi\  /' S Y y'  F i g u r e 17 POSITIONS FROM EXAMPLE GAME ONE  m  5 j-v/ ///•  YYYY/. Yy.  iXX If  Y•  X  7?///./A  /.///<•///  //A  i  '3 X. 1 WY//,  'YY\ •','\  '7  '/// ///  •A-  /Y?Y/A/ •/ //  7.  •v'X////, - / x/A/./.  . // /. 7//Y/ -V. ///////.  ////. YYYYJ  VYy-// \/YY  \YY • -VXXX! •••• /-X x/ /  'X-X; i  ! i  F i g u r e 18 POSITIONS FROM EXAMPLE GAME TOO  36.  replies. i n one  The  opponent's c h o i c e of the U p i e c e a l l o w s  move, a f t e r a 121 node s e a r c h .  Why  i t fails  19c  might e n t e r t a i n the  to d i s c o v e r .  I n game 4 the program moves f i r s t a g a i n , likely  finish  P l a c i n g the L p i e c e i n F i g u r e  l o o k s l i k e a b e t t e r attempt to p a r r y . reader  the game to  to be d i f f e r e n t from each o t h e r . )  Once a g a i n , a f t e r examining  the p o s i t i o n a f t e r 4 moves ( i n F i g u r e 20a) ( F i g u r e 20b).  F i n d i n g i t annoyingly  ( i t s f i r s t moves a r e v e r y  hard  the program p l a y s a f i n e move to a n a l y s e , i t s opponent p l a y e d  the Y p i e c e to c l o s e the area a t the top o f the board A f t e r 5 seconds CPU a f o r c e d win  time and  as shown.  took 42 seconds CPU  over 1000  ( F i g u r e 20c).  nodes the program's s e a r c h  yields  In a l l i t s games, the l o n g e s t s u c c e s s f u l s e a r c h  time expanding over  8200 nodes from a p o s i t i o n  with  100 move c h o i c e s . The  author  i s f o r c e d to say  t h a t t h i s program p l a y s a r e s p e c t a b l e  game of Pentominoes s i n c e i t once beat him when he was I t may  be p o i n t e d out t h a t t h e r e i s no  would enable  anyone to win  'algorithm'  a g a i n s t t h i s program.  t r y i n g to  win.  (or s e t of moves) which T h i s i s not  the  w i t h many game-playing programs t h a t use an e v a l u a t i o n f u n c t i o n . c a s e s , once a w i n n i n g l i n e has been found  i t can be r e p e a t e d  until  case In  their  the  programmer changes h i s program. For one  thing here,  the f i r s t move i s chosen randomly from 2056  (the random c h o i c e among equals f u n c t i o n achieves  i s u s u a l l y the most t h a t an e v a l u a t i o n  i n v a r y i n g from game to game).  More c r u c i a l l y ,  the  r e s u l t s o f a l l games are open to a n a l y s i s , the r e s u l t s o f which w i l l r e f l e c t e d i n a new  e d i t i o n of the move e v a l u a t i o n l i s t s .  be  P o s i t i o n s that  F i g u r e 19 POSITIONS FROM EXAMPLE GAME 3  a  b Figure  20  POSITIONS FROM EXAMPLE GAME 4  led to a loss w i l l be penalised heavily enough to dissuade the program from choosing moves that lead there. e d i t i o n of the l i s t s .  One  Appendix 2D contains the second  generally bad p o s i t i o n had had a few  favour-  able results during the random games, but not l a t e r against r e a l opposition.  These positions of l a t e r games were the information used  i n the update.  39. CHAPTER 4  CONCLUSIONS  The problems encountered I n t h i s r e s e a r c h g i v e r i s e t o c o n c l u s i o n s t h a t can be extended beyond pentominoes to embrace much o f the work i n game p l a y i n g and h e u r i s t i c  searching.  As Minsky [ 1 5 ] w r i t e s , p l a n n i n g i s now a more c r u c i a l a s p e c t before  (compared w i t h s e a r c h i n g )  artificial  intelligence.  He says  than  i n the human problem s o l v i n g areas o f t h i s i s because there i s reason t o  b e l i e v e t h a t human chess o r checker p l a y e r s c o n s i d e r o n l y dozens, o r a t most, a few hundred d i f f e r e n t p o s i t i o n s when d e c i d i n g on a move. programs have commonly e v a l u a t e d hundreds o f thousands.  He c l a i m s  these were e a r l y works and t h a t l a t e r on t h e r e were r e d u c t i o n s to  Some that  thanks  development o f some t h e o r y . T h i s t h e o r y , however, i s h e a v i l y dependent on s p e c i a l i s e d knowledge  of  a problem a r e a o f which the programmer i s aware - the a b i l i t y t o  ' e v a l u a t e ' a p o s i t i o n o r node i n a graph.  Without t h i s we suggest  that  the t h e o r y might as w e l l n o t e x i s t f o r a l l the h e l p i t can o f f e r . It  i s c l e a r from the c l o s i n g remarks i n the l a s t c h a p t e r  some sense, t h i s Pentomino p l a y i n g program can ' l e a r n ' . d e l i b e r a t e l y omitted  that, i n  However, we  the r o u t i n e s t h a t update the e v a l u a t i o n l i s t s  from  the main body o f the program i n o r d e r n o t to g i v e an exaggerated impression.  S i n c e t h e r e i s no a l t e r a t i o n t o the c o n c e p t u a l model i n t o which  the new i n f o r m a t i o n i s r e c e i v e d , t h i s called It to  ' l e a r n i n g ' had much b e t t e r be  adaptation. does have t h e advantage o f b e i n g s e l e c t i v e .  A f t e r the s t a r t  given  the program by the a n a l y s i s o f the 100 games, n o t each t r i a l has t o be  AO. recorded  i n these t a b l e s .  Thus the problem that was encountered i n  BOXES [1A] i s a v o i d e d , which was t h a t the e f f e c t o f an erroneous move given  e a r l y reinforcement  was s t i l l  apparent thousands o f t r i a l s  later.  I t i s suggested t h a t the ' e v a l u a t i o n ' o f p o s i t i o n s t h a t i s c a r r i e d out by the program i s analogous i n some ways t o t h a t o f human p l a y e r s of games who l e a r n to a b s t r a c t c e r t a i n f a v o u r a b l e positions.  In s p i t e of i t s very naive  straightforward ficial  features  representation  from  their  ( i n the form o f  l i s t s ) i n i t s own way i t i s more n a t u r a l than the a r t i -  c a l c u l a t i o n s employed by many game p l a y i n g programs, and perhaps  some o f i t s e f f e c t s c o u l d be i n c o r p o r a t e d 'Evaluation'  i s c r u c i a l not only  h e u r i s t i c s e a r c h methods i n g e n e r a l . made e x p l i c i t . game o r s e a r c h  i n t o more orthodox forms.  to game p l a y i n g b u t a l s o t o How c r u c i a l i t i s has n o t been  As we have seen, s t r a t e g i e s r e s u l t from knowledge o f t h e space t h a t i s a p a r t  from the formal  almost no such knowledge, nodes i n the s e a r c h uishable.  S l a g l e [23] f i n d s a very  rules.  When t h e r e i s  t r e e come to be i n d i s t i n g -  useful evaluation  function f o r  K a l a h , i f t h e r e had n o t been one the h e u r i s t i c s e a r c h would have stopped before  i t began.  N i l s s o n [17] i s t r y i n g to improve s e a r c h i n g  e s t i m a t i o n methods, the 'estimate'  which must be a v a i l a b l e a t any node  of the graph i s an e v a l u a t i o n o f c o u r s e . nothing  by c o s t  I n i t s absence, there i s  left.  In the GO-playing program o f Ryder [ 1 9 ] the i s s u e o f p o s i t i o n e v a l u a t i o n has been s h e l v e d  f o r the sake o f c a l c u l a t i n g numerous l o c a l e f f e c t s ,  which enable him a l s o t o d i s c o v e r p l a u s i b l e moves and t o a v o i d the s e a r c h i n a space t h a t explodes c o m b i n a t o r i a l l y  l i k e few o t h e r s  do; hence h i s  41. mere p a s s i n g r e f e r e n c e  to the work o f Z o b r i s t [ 2 4 ] .  Pentominoes has a p a u c i t y o f l o c a l c o n s i d e r a t i o n s i n d e e d , i s so l i t t l e  there  s t r a t e g i c a l i n f o r m a t i o n t h a t i t i s doubly remarkable t h a t  such an e f f e c t i v e p l a y i n g program has been produced. counter-example to the argument t h a t there w i l l  The Game i s a  always e x i s t  strategical  i n f o r m a t i o n t o use when one wants t o make an h e u r i s t i c - t y p e s e a r c h .  In  f a c t , , humans, make ' p l a u s i b l e moves' when they i n t e r a c t s o c i a l l y , n o t based on r u l e s o f s t r a t e g y o r an e v a l u a t i o n f u n c t i o n so much as u s i n g the v e r y l a r g e amount o f r e l e v a n t i n f o r m a t i o n t h a t they have access to internally.  The development, s t o r a g e  and use o f complex i n f o r m a t i o n  r e l e v a n t to p l a y i n g games seems t o be q u i t e an important computer game p l a y i n g r e s e a r c h i s n o t going j u s t to b e a t the l a t e s t d i g i t a l  to descend t o a  chess champion.  t h a t what i s needed f o r summarising s e a r c h  direction i f competition  Minsky [15] suggested  trees i s not a numerical  u t i l i t y - l i k e value but a d e s c r i p t i o n - l i k e expression  t h a t can be used  for analysis. In chess,  B o t v i n n i k [ 1 ] has produced a way o f m a t h e m a t i c a l l y  repre-  s e n t i n g the board, u s i n g h o r i z o n s , which w i l l make i t e a s i e r to c o n s i d e r plans  and a c t i o n s .  He p o i n t e d out that the chess p l a y i n g programs o f  the l a s t 20 y e a r s had got bogged down because they f o r a chess b o a r d and men f a i l i n g do.  first  coded a scheme  t o know f i r s t l y what they i n t e n d e d to  He expects to produce a v e r y good p l a y e r t h i s way b u t h i s view seems  inadequate. C l a r k e [ 2 ] goes so f a r as to propose a s p e c i a l language f o r d e a l i n g with  chess  ( A l g o l 64).  T h i s seems q u i t e i n t e r e s t i n g , b u t l i k e  Botvinnik  42.  must face the problem of the large body of information accumulated by experience. De Groot [3] took protocols from many levels of chess players with the i n t e n t i o n of distinguishing a Grandmaster from a Master and so on. This was a r e l a t i v e f a i l u r e .  There were c l e a r l y things happening below  the l e v e l of the most introspective protocol that the players were unaware of. revealing.  Another series of tests that he did ([3] and [4]) were more A p o s i t i o n was exposed to various players f o r just a few  seconds, and they were then asked to reconstruct the p o s i t i o n .  Only the  Grandmaster was able to produce the f u l l correct p o s i t i o n and also the winning move!  Lesser players, t y p i c a l l y , r e c a l l e d l e s s .  This only  applied to 'meaningful' chess positions. The problem, of course, i n computing, i s how to b u i l d up a 'vocabul a r y ' that increases comprehension of chess positions i n p a r a l l e l .  This  problem of large amounts of new knowledge w i l l not only occupy game playing research but also the computer l i n g u i s t s working with semantic models. The view, exemplified by Minsky [15], that 1,000,000 'facts' w i l l be enough f o r a great i n t e l l i g e n c e , i s c l e a r l y inadequate even i f someone knew what a 'fact' was.  I t i s shown to be so by the current work  of Papert et a l . on comprehending very young children's s t o r i e s .  The  problem i s one central to a l l of A r t i f i c i a l I n t e l l i g e n c e , not only to game playing.  43.  REFERENCES  [1]  B o t v i n n i k , M.M. (1970), Computers, Chess and Long Range P l a n n i n g , Sp r i n g e r-Ve r l ag.  [2]  C l a r k e , M.R.B. (1971), "Some Ideas f o r a Chess Compiler", NATO Symposium on Human T h i n k i n g - Computer Techniques f o r i t s E v a l u a t i o n , S t . Maximin, France.  [3]  De G r o o t , A.D. (1965), Thought and Choice i n Chess, G.W. The Hague and P a r i s : Mouton.  [4]  .  Baylor (ed.),  (1966), " P e r c e p t i o n and Memory Versus Thought: Some O l d Ideas and Recent F i n d i n g s , " i n B. Kleinmuntz ( e d . ) , Problem Solving: Research, Method, and Theory, New York, W i l e y , pp.19-50.  [5]  D r e y f u s , H.L. Monica,  (1965), Alchemy and A r t i f i c i a l I n t e l l i g e n c e , C a l i f o r n i a , Rand Corp.  [6]  Doran, J . and D. M i c h i e (1966), "Experiments w i t h the Graph T r a v e r s e r Program," P r o c . R. Soc. ( A ) , 294, pp.235-259.  [7]  Dudeney, H.E..  [8]  F l e t c h e r , J.G. (1965), "A Program to S o l v e the Pentominoes Problem by the R e c u r s i v e Use o f Macros," Comm. ACM 8 ( 1 0 ) , pp.621-623.  [9]  Gardner, M. "Mathematical Games Department" i n S c i e n t i f i c Magazine.  (1908), The Canterbury P u z z l e s , Dover  (1965), Polyominoes,  S c r i b n e r ' s , New  Santa  (1958).  American  [10]  Golomb, S.  York.  [11]  Good, I . J . (1968), "A F i v e - Y e a r P l a n f o r Automatic Chess," i n E. Dale and D. M i c h i e ( e d s . ) , Machine I n t e l l i g e n c e 2, American E l s e v i e r P u b l i s h i n g Company, Inc. pp.89-118.  [12]  G r e e n b l a t t , R., D. E a s t l a k e and S. C r o c k e r (1967) "The G r e e n b l a t t Chess Program," P r o c . FJCC, pp.801-810.  [13]  Lunnon, W.F. (1971), "Counting Polyominoes," i n Computers i n Number Theory, A t k i n and B i r c h ( e d s . ) , Academic P r e s s , New York, pp.347-372.  [14]  M i c h i e , D. and R.A. Chambers (1968), "Boxes: An Experiment i n A d a p t i v e C o n t r o l , " i n E. Dale and D. M i c h i e ( e d s . ) , Machine I n t e l l i g e n c e 2, American E l s e v i e r P u b l i s h i n g Company, I n c . pp.137-152.  44. [15]  Minsky, M. (1968), Semantic I n f o r m a t i o n P r o c e s s i n g , I n t r o d u c t i o n , . M.I.T. P r e s s , pp.1-31.  [16]  N e w e l l , A., J.C. Shaw and H.A. Simon (1963), "Chess P l a y i n g Programs and the Problems o f Complexity," IBM J . Res. Dev., 2, pp.39-70. R e p r i n t e d i n E. Feigenbaum and J . Feldman ( e d s . ) , Computers and Thought, McGraw-Hill Book Co., 1963.  [17]  N i l s s o n , N.J. (1969), " S e a r c h i n g Problem S o l v i n g and Game P l a y i n g Trees f o r Minimum L o s t S o l u t i o n s , " i n A.J.H. M o r r e l l ( e d . ) , I n f o r m a t i o n P r o c e s s i n g 68, V o l . 2 , pp.1556-1562, N o r t h - H o l l a n d , Amsterdam.  [18]  Read, R.C. (1962), " C o n t r i b u t i o n s t o the C e l l Growth Can. J . Math. XIV, pp.1-20.  [19]  Ryder, J.L. (1971), H e u r i s t i c A n a l y s i s o f Large Trees as Generated i n the Game o f GO, S t a n f o r d U n i v e r s i t y AIM-155.  [20]  Samuel, A.L. (1959), "Some S t u d i e s i n Machine L e a r n i n g U s i n g the Game o f Checkers," IBM J . Res. Dev.3(3), pp.210-229. R e p r i n t e d i n E. Feigenbaum and J . Feldman ( e d s . ) , Computers and Thought, McGraw-Hill Book Co., 1963.  [21]  Problem,"  (1967), "Some S t u d i e s i n Machine L e a r n i n g U s i n g t h e Game o f Checkers I I - Recent P r o g r e s s , " IBM J . Res. Dev. 1 1 ( 6 ) , pp.601-617.  [22]  Shannon, C.E. (1950), "Programming a Computer f o r P l a y i n g P h i l . Mag. 41, pp.256-275..  Chess,"  [23]  S l a g l e , J.R. and J.K. Dixon (1969), "Experiments w i t h Some. Programs t h a t Search Game T r e e s , " J ACM 1 6 ( 2 ) , pp.189-207.  [24]  Z o b r i s t , A.L. (1969), "A Model o f V i s u a l O r g a n i s a t i o n f o r t h e Game o f GO," P r o c . SJCC, V o l . 34, pp.103-112.  45. APPENDICES 1.  Operation  of the Programs  The main s e c t i o n s of t h i s program were w r i t t e n i n P L / I . the e x t e r n a l s u p p o r t i n g  r o u t i n e s were w r i t t e n i n F o r t r a n , due  exposed to some of the f i n e p o i n t s o f PL/I The i.e.,  game-player PENTO expects i t s i n p u t to be  items must be One  implementation and  f o l l o w e d by  can b e g i n by  $R  i n PL/I  Most o f to  being  support.  LIST format,  spaces.  t y p i n g something  RSR1:MHK0B + NEW:PL1LIB  like: PAR=FFF=RSR1:GGG  MHKPNF = RSR1:MHKPNF The  program spends a w h i l e  then types We  'INPUT NEW  reading  i n i t s r a t h e r cumbersome f i l e s  and  GAME SPECS'.  must then type i n some numbers:  A B C D E F G H A i s the a r e a of the board's r e c t a n g l e B i s the number of columns C i s the number of rows D represents  (eg.  60)  (6)  (10)  the number o f squares o f the r e c t a n g l e  that  are  unavailable E i s the number of p i e c e s  unavailable  F i s the debugging mode ( u s u a l l y  0)  G i s the minimaxing s e a r c h  ( d e f a u l t s to  limit  60)  H i s the mode of p l a y Note:  I f D > 0, we  must n e x t i n p u t the l i s t  concerned, s i m i l a r l y i f E > 0 the l i s t  o f the numbers of the  of pieces  squares  concerned must f o l l o w .  46. If  F i s not 0 then a p l e t h o r a of h e l p f u l  likely  to be p r i n t e d o u t .  follows  (some are now  (to the programmer) v a l u e s a r e  The v a l u e s t h a t can be taken by H are as  redundant):  1  You move f i r s t ,  2  Program moves f i r s t ,  3  You p l a y a l l the moves.  4  The program p l a y s a l l the moves.  5  T h i s was  6  A d e v i c e used  7  Used to generate  once used  c o n t r o l l e d by used  program p l a y s randomly w i t h s e a r c h . o t h e r w i s e as  1.  to gather s t a t i s t i c s about f i r s t  moves.  to a n a l y s e some games w h i l e p l a y i n g backwards. and  f i l e a s e r i e s of random games (an amount  G).  8-10  Not  now.  11  You move f i r s t ,  12  Program moves f i r s t ,  program has access to s e a r c h and a l l t a b l e s . as  11.  To p l a y a move one must type something o f t h i s  form:  ' T' 3 45 remembering the space a t the end o r 'N' To r e s t a r t a game, type 999  i n s t e a d of the 3.  One  7 34  can always t e r m i n -  a t e w i t h $END. One for  might a l s o wish  to update the f i l e o f move e v a l u a t i o n s .  example, the c h o i c e to c e n t r e r a t i o 87:21  e x t r a p o l a t i o n 196:28 a good one the move b e f o r e .  196  28 2  402  38 3  $END  i n the same game, and 402:38 was  Then one would i n p u t the f o l l o w i n g l i n e s :  $SOURCE MHKLD 87 21 1  gave a bad r e s u l t .  ( i n format  314)  Say, And  by  the s t a t e  The f o l l o w i n g i s the c o n t e n t o f MHKLD: $R MHKLOBJ 4=MHKPNF 5=*MS0URCE* 6=-WMK 7=*MSINK* $R *PERMIT PAR=MHKPNF NONE $E MHKPNF $C -WMK MHKPNF $R *PERMIT PAR=MHKPNF RO  48. 2.  L i s t i n g s of Routines,  T a b l e and Games  A.  The Pentomino P l a y i n g Program  B.  The Move L i s t s  C.  The E v a l u a t i o n L i s t Maintenance Program  D.  The Move E v a l u a t i o n T a b l e s  E.  Four Sample Games A g a i n s t Human Opponents  (Excerpts)  1  The Random V e r s i o n w i t h  2, 3 and 4  The Improved V e r s i o n  Search  49.  PENTO: PROC O P T I O N S ( M A I N ! ;  (A)  L I S T I N G OF  T H E M A I N PROGRAM  DCL  CPUTTME. ENTRY RETURNS ( FLOAT B I N ) , (WTIM,NTIM.) STATIC FLOAT B I N , MVW I N I T ( 5 0 ) , MVCNRW,MCNCRW MAVL(12) B I T ( 1 ) , •1 J I N , 2 JX B I T ( 4 ) I N I T ( ' O O O O ' B ) » 2 J L 1 1 2 ) B I T ( l ) , MJ DEFINED J IN, MFSTBD{256) INIT ( ( 2 5 6 ) 2 ) , MKA(4008) S T A T I C , MSLSTl13166) STATIC, MUD B I T 1 3 2 ) I N I T ( ( 3 2 ) * 0 * B ) , L I N E DEC F I X E D ( 9 , 3 ) , A S I Z E , MO BIN<15,4), MRCH(6), 1 S T A T S ( I O O ) , 2 MOVES, 2 G S I Z E , WESG C H A R ( 8 ) , TIME E N T R Y ( B I N ( 3 1 , 0 ) , B I N ( 3 1 , 0 ) , B I N ( 3 1 , 0 ) ) , (EMAT»EMUT»MITA,MIT8,MITC»?1ITD,MITE) BIN(31,0), MGCNT I N I T ( l ) , 1 KVAR{7), 2 KPNO, 2 KONO, 2 KOSQ, CARA C H A R ( l ) , MMM(12) I N I T ( ( 1 2 ) 0 ) S T A T I C , XXN FIXED B I N , PANTRY (12) B I T U 2 ) INIT (' 100000000000 ' B, ' 010000000000* B , '001000000000*8,*OOOIOOGOOOOO'8,* 000010000000*8,•000001000000*B, • 000000100000'B,'000000010000*B,'000000001000*8,* 0 0 0 0 0 0 0 0 0 1 0 0 » B , • 000000000010*B,'000000000001«B), XPANTRY(12) B I T ( 1 2 ) , T F 0 P S ( 1 2 ) STATIC FIXED BIN I N I T t l , 9 , 1 1 , 1 9 , 2 7 , 3 5 , 3 9 , 4 3 , 4 7 , 5 1 , 5 2 , 6 0 ) , SP0N0(64) STATIC FIXED B I N IN IT U 8 ) 1, 2, 2, ( 8 ) 3, ( 8) 4, ( 8 ) 5, { 4) 6 , ( 4 ) 7 (4)8,(4)9,10,(8)11,(4)12), S S T ( 6 4 ) STATIC BIT112) INIT('100001111111*8,•010010111111*3,•001011011111»Bt • 0 0 0 1 1 1 1 0 1 1 1 1 * 8 , » 0 0 0 1 0 1 111111*B,'100010111111*8, '010011011111«B,'001011101111*8, » I 0 1 0 1 1 1 1 0 1 0 1 * B , * 010111111010*3, • 101010110111*8,'010111011011'B,* 101011101101'B, »010101111110*8,»010111101011*8,*101001111101*B, '010110111110*B,* 1 0 1 0 1 1 0 1 0 1 1 1 » B » '100111101101*8,'110001111110*8,* 011010110111'B, » 0 0 1 1 1 1 0 1 1 0 1 1 » B , * 100110111110*8,*110011010111*8, '011011101011*B,'001101111101*8, • 001001111ill'B,'000110111111»B,*lOCOilOlll11*B, •010011101111*B,»010001111111*B,'001010111111*8, '000111011111*8,'100011101111*B, '000111111101«3, 100011111110*8,'010011110111*8,'001011111011'3 ' 0 1 0 1 0 1 1 O l l l l ' B , ' 1 0 1 0 0 0 1 1 1 l l l ' B , '01011001111 1*3, * 101011001111 ' 3 • 011011110011'B, 00111 1111001*8, '100111111100*8,*1100 11110110*8 '100110101111'B,'110001011111*3,'011010101111*8,'001101011111'B 'OOOOllllllll'B, 100011111101*8,'OlOOlllllllO'Bt'OOlOllllOlll'B^OOOllllllOll'B '000111111110'B,*1C0011110111*8,'010011111011 * 8,* 001011111101 *B '101010101111'B,'010101011111'B,* 101001011 111 * 8,'010110101111*B), 1 SF T(64) S T A T I C , 2 MSFF(4) I N I T ( - 1 6 , - 1 5 , - I , 1 6 , - 1 6 , - 1 , 1 , 1 7 , - 1 6 , 1 , 1 5 , 1 6 , - 1 7 , - 1 , 1 , 1 6 , - 1 5 , - 1 , 1 , 16,-16,-1,16, 17,-16,-1,1, 15,-17,-16, 1,16, -32,-16,16,32,-2,-1,1,2, -32,-16,16,17,-1,1,2,15,-17,-16,16,32,-15,-2,-1,1, -17,-1,1,2,-16,-15,16,32,-2,-I,1,17,-32,-16,15,16, -17,-1,16,32,-16,-15,-2,-1,-32,-16,1,17,1,2,15,16, f  8  8  9  50.  -2,-1»16,17,-32,-16,-1,15,-17,-16,1,2,-15,1,16,32, -16,-15,1,16,-1,1,16,17,-16,-1,15,16,-17,-16,-1,1, -16,-15,-1,1,-16,1,16,17,-1,I,15,16,-17,-16,-1,16, - 1 , 1 , 1.6, 32 7 - 1 6 , - 2 , - 1 , 16,-32, - 1 6 , - 1 ,,1,-16, 1,2,16, -17,-15,-1,1,-16,-15,16,17,-1,1,15,17,-17,-16,15,16, -32,-16,1,2,1,2,16,32,-2,-1,16,32,-32,-16,-2,-1, -17,-1,16,17,-16,-15,-1,15,-17,-16,1,17,-15,1,15,16, -16,-1,1,16, -16,-l,16,32,-16,-2,-l,l,-3 2,-16,l,16,-l,l,2,16, -2,-1,1,16,-32,-16,-1,16,-16,-1,1,2,-16,1,16,32, -17,-16,16,17,-15,-1,1,15,-16,-15,15,16,-17,-1,1,17), IX,KTEST,IY,IZ, IZA(5), MRAT 8 I N ( 1 5 , 5 ) , MESG CHAR(8), DY FIXED BIN, BTEST 8 I T ( 1 2 ) , BTSC12) B I T J l ) DEFINED BTEST, P A V H 12) FIXED BIN, P0N0(12) FIXED BIN INIT<8,2,8,8,8,4,4,4,4,1,8,4}, MDNA{12) I N I T ( 1 , 0 , - 1 , 0 , 1 , 1 , - 1 , - 1 , 0 , 2 , 0 , - 2 ) , MDN3U2) INIKO,1,0,-1,-1,1,1,-1,-2,0,2,0), U P D Q 2 ) B I T ( 1 2 ) I N I T I ' 0 1 1 1 1 1 1 1 1 0 1 1 * B , » 1 0 1 1 1 1 1 1 1 1 0 1 » B , » 110111 111 110* B '111011110U1«B,'111101111111*8,'lllllOilllll'B * 111111011111*8,* 111111101 1 1 1 * B , » 1 1 1 1 1 1 1 1 0 1 1 1 ' B ' 111111111011 'B,'111111111101* B » *11111111.1110*8) ALL SET B I T ( 1 2 ) I N I T { { 1 2 ) • 1 • B ) . ALLOFF B I T U 2 ) INI T ( ( 12 ) * 0' B ) , LNKA B I T ( 1 2 ) , L K ( 1 2 ) B I T ( l ) DEFINED LNKA, LNKB 3 I T ( 1 2 ) , L J U 2 ) B I T ( 1 ) DEFINED LNK8, 1 L N K E i - 2 LNKF 8 I T ( 4 ) INI T ( • 0000* B ) , 2 LNKD 8 I T U 2 ) , LNKG DEF LNKE, XCHKA(4) F I X E D ( l ) I N I T ( 2 , 1 , 2 , 1 ) , XCHKB(4) F I X E D ( l ) I N I T ( 4 , 3 , 4 , 3 ) , YCHKA(4) F I X E D ( l ) I N I T { 6 , 6 , 7 , 5 ) , YCHKB(4) F I X E D ( l ) I N I T ( 5 , 7 , 8 , 8 ) , INT1 B I T U 2 ) I N I T ( * 1 1 1 0 0 1 1 0 0 1 1 1 * 8 ) , INT2 B I T ( 1 2 ) I N I T ( * 1 0 1 1 1 0 0 1 1 1 0 1 * B ) , INT3 BIT112) I N I T ( ' 1 1 0 1 1 1 0 0 1 1 1 0 » B ) , INT4 B I T ( 1 2 ) I N I T ( » 0 1 1 I 0 0 1 1 1 0 1 1 ' B 3 , ALPH(12) CHAR(1 ) I NI T ( • F « , VI ' , ' L » , * N ' , » P ' , ' T • , * U* , * V ' , * w* , • X * , • Y  )t TMRLNK( 12 ) STATIC FIXED BIN I N I T ( 3 , 4 , 1 , 2 , 7,8,5,6, 11, 12,9,10) ; ON ENDFILE (SCARDS) GOTO REPENT; GOTO SEE; SAW: JONETM=0; IF MSLSTJ13166)-=63 THEN DO; PUT L I S T ( ( M S L S T ( I ) DO 1=13142 TO 1 3 1 6 6 ) ) ; STOP; END; GSTART: P U T L I S T ('INPUT NEW GAME S P E C S 5; PUT S K I P ( 2 ) ; G E T LIST (L,M,N,NA,NP,KTEST,MVW,MONDX); IF JONETM=0 THEN DO; J0NETM=1; IF MDNDX=6 THEN GOTO TOO; FRO: IF KTEST=-2 THEN PUT L I S T ( M K A ) ; END; JINITS,JINIT=0; IF MDNDX-.=7 THEN GOTO GSTARTA; HOVES(*)=0; G S I Z E ( * ) = l ; WESG=DATE; MITA=SUBSTR(WESG,7); MIT8 = SU8STR(WESG,4,2) ; MI TC= SUBSTR ( VJESG, 1, 2 ) ; MITE=MITA+100*MITB+10000*MITC; £ M A T = E M A T * M I T E / 1 0 0 0 0 ; PUT LI ST(DATE) ; PUT SKIP; PUT F I L E ( P S T A T ) L I S T ( D A T E ) ; GSTARTA: IF L -.= M*N THEN DO; MXXN = l ; GO TO XX; END; 1  IF NA >= L I NP >= 12 THEN 0 0 ; MXXN = 2 ; XX: PUT L I S T ( « N 0 GAME',MXXN); GOTO REPENT; END; IF MVW=0 THEN MVW=60; XPANTRY(1) = »011111111111*B; XPANTRY(2) = •lOllllllllll'B; XPANTRY{3) = '110111111111*8; XPANTRY(4) = • 1 1 1 0 1 1 1 1 1 l l l B ; DO K = 5 TO 1 2 ; X P A N T R Y ( K ) = U P D ( K ) ; END; I F M0NDX=8 THEN DO; KLOOQ: I F MGCNT>MVW THEN GOTO R E P E N T ; KH=0; KLOOP: KH=KH+l; GET S K I P F I L E ( P S T A T ) L I S T ( C A R A ) ; I F CARA='* * THEN DO; KH=KH-2; GOTO KLOOR; END; GET F I L E ( P S T A T ) L I S T < K O N O I K H ) , K O S Q ( K H ) ) ; KI = l ; K L O P : I F C A R A = A L P H ( K I ) THEN GOTO KLOQ; K I = K I + 1 ; GOTO K L O P ; KLOQ : KP-NO(KH)=KI; K O N O { K H ) = K O N G ( K H ) + T F O P S ( K I ) - l ; GOTO KLOOP; KLOOR: I F L 0 0 T T = 1 THEN DO; LOOTT=0; MGCNT=MGCNT+1; GOTO KLOOQ; END; KH=KH-1; I F KH<1 THEN GOTO KLOOQ; END; BOARD: B E G I N ; DCL ARCH(M) C H A R ( l ) , MVALLH,MCNCW,MVALLL,MCNH,MCNL,MVCNTA,MMAXFG I N I T I O ) , LNKC B I T U 2 ) . 1 M C S ( L ) , 2 MCNS, 2 MCNSQ, 2 M C N S D ( 8 ) B I T ( l ) , 1 LSQ, 2 NBOARO(L), 4 LNK 8 I T Q 2 ) , 4 MVCNT, 4 SWS, 6 CNTRE 8 I T ( 1 ) , 6 INFSW B I T ( l ) , 6 DEAD F I X E D B I N A R Y , 2 MVCNTALL I N I T I O ) , 2 MCNCN I N I T I O ) ; DEAD,MVCNT=0; PAVL=O; M A V L = ' I » B ; MCNSDT * » 1 ) = * 1'B » • IF MDNDX=8 THEN DO; N A , N P = l ; DO 1=1 TO KH; PAVL{KPNO(I))=1; BTEST=SST(KONO(I)); IZ8=K0SQU>; D E A D J I Z B ) = K P N O ( I ) ; J J = 2 ; KK=1; DO W H I L E « J J < 6 ) ; I F B T S ( K K ) = « 0 * B THEN DO; IZC=IZB+MDNA(KK)+M*MDNB{ KK) ; DEAD( I Z C ) = K P N O ( I ) ; J J = J J + 1 ; END; K K = K K + l ; END; END; GOTO I N T L ; END; I F NA 0 THEN BEGIN; DECLARE A(NA) F I X E D B I N ; GET L I S T U A I I I ) DO I I = 1 TO N A ) ) ; DO I I = 1 TO NA; D E A D ( A ( 1 1 ) ) = 1 3 ; END; END; I F NP -*= 0 THEN BEGIN; DECLARE B ( N P ) F I X E D B I N ; GET L I S T ( ( 8 ( 1 1 ) DO I I = 1 TO N P ) ) ; DO 11=1 TO NP; M A V L ( B ( I I )) = '0'B ; P A V L { B ( 1 1 ) ) = l ; END; END; INTL: BEGIN; DO I = 1 TO L ; •LNK(I) = A L L S E T ; IF I <= M THEN L N K ( I ) = LNK { I ) £ I M T 1 ; E L S E ,  I F K = M + M T H E N LNK ( I ) = LNK ( I ) £ UPD{9'); I F I > M * • ('N - 1 ) THEN LNK ( I ) = L N K { I ) £ I N T 2 ; E L S E I F I > M * ( N - 2 ) THEN L N K 1 I ) = L N K { I ) £ U P D U 1 ) ; I F MQ.D(I,,M) = 1 THEN. LNK.U ) • = LNK (I.) £ I N T 3 ; E L S E I F M O D ( I , M ) = 2 THEN L N K U ) = LNK ( I ) £UPD { 12 ) ; I F M O D ( I , M ) = 0 THEN L N K ( I ) = L N K ( I ) £ I N T 4 ; E L S E I F MOD( T , M } = M - 1 THEN L N K ( I ) = L N K ( I ) £ U P O i l Q ) ; END ; I F NA=0 THEN GOTO I N C ; INS: DO I =,1 TO L; I F DEAD ( I ) -.= 0 T H E N DO; LNKB = L N K ( I ) ; DO J = 1 TO 1 2 ; I F L J ( J ) -»= 'O'B THEN DO; K = I + M D N A ( J ) +M#MDN8 ( J ) ; I F D E A D ( K ) = 0 THEN DO; LNK(K) = LNK(K) £ UPD{TNRLNK(J)J; END I N B; I N C : DO I = 1 TO L ; I F D E A D ( I ) - = 0 T H E N GOTO N D I N C ; LNKD = L N K { I ) ; LNKH=4975+LNKG+LNKG; L N K I = M S L S T ( L N K H ) ; I F L N K I = 0 T H E N GOTO N D I N D ; L N K J = M S L S T ( L N K H + 1 ) ; I F NP=0 T H E N DO; M V C N T ( I ) = L N K J ; GOTO N D I N D ; END; DO 1 1 = 0 TO L N K J - l ; I F P A V L ( S P O N O ( M S L S T { L N K I + I I ) > ) =0 THEN M V C N T { I ) = M V C N T { I ) + 1 ; END; NDIND: I F M V C N T ( I ) > 0 T H E N DO C N T R E U ) = » 1 • B ; MCNCN = MCNCN + 1 ; M V C N T A L L = M V C N T A L L + M V C N T { I ) ; END; E L S E C N T R E ( I ) = 0 • B ; N D I N C : END I N C ; MCNCW=MCNCN; END I N T L ; CHIEF: BEGIN; VAGA: MXF=0; I F ( M D N D X = 1 ) | ( M D N D X = 3 ) | ( M D N D X = 1 1 ) THEN GOTO T H E F O E ; I F ( M D N D X = 6 ) | ( M D N D X = 1 2 ) THEN GOTO APMV; V AGB: I F M V C N T A L L -•= 0 THEN GOTO PMV; I WIN = 0; GEND: I F MDNDX>2 THEN DO; M I T A = l ; MIT3=0; CALL T I H E \ » I T A , M I T 3 , M I T C ) ; MITC=MITC-MITD; I F MDNDX=6 THEN I F J I N I T = 1 THEN MESG=' SMT WON'; E L S E MESG='SMT L O S T ' ; END; E L S E I F MDNDX=99 THEN MESG= * PART I A L «; E L S E MESG = « »; E L S E I F I W I N = 1 THEN MESG = ' I WIN*; E L S E MESG = ' YOU W I N ; PUT L I S T (MESG,MGCNT, U N I T S , M I T C ) ; I F MDNDX=7 THEN DO; PUT L I S T ! MOVES ( MGCNT ) G S I ZE •( MGCNT ) ) ; PUT S K I P F I L E ( P S T A T ) L I S T ( » * « , M O V E S ( M G C N T ) , G S I Z E i M G C N T } ) ; E N D ; PUT S K I P { 2 ) ; DO KK = 1 TO N i DO L L = 1 TO M; DY = D E A D ( M * ( K K - 1) + L L ) ; 8  1  f  I F DY = 0 THEN A R C H ( L L ) = ' 0 ' ; E L S E * I F DY < 1 3 T H E N A R C H I L L > = A L P H ( D Y ) ; E L S E A R C H I L L ) = •*•; END; PUT S K I P ( 2 ) E D I T ( A R C H ) (X(l)» A ( 1 ) U ; END; PUT S K I P 1 3 ) ; I F MGCNT=MVW THEN GOTO WINOUP; MGCNT=MGCNT+l; GOTO NDBD; WINDUP: PUT S K I P ( 2 ) L I S T ! ' N O - OF MOVES','NO. OF G A M E S ' ) ; ASIZE,MO=0; DO 11=1 TO MGCNT; ASIZE = ASIZE + G S I Z E ( I I ) ; M0=MQ+M0VES(II); M M M ( M O V E S ( I I ) ) = M M M ( M O V E S ( I I ) ) + 1 ; END; MO=MO/MGCNT; AS I Z E = A S I Z E / M G C N T ; DO 11=1 TO 1 2 ; PUT S K I P L I S T ( I I , M M M ( I I ) ) ; E N D ; PUT S K I P F I L E ( P S T A T ) E D I T I M M M ) ( 1 2 ( X ( 2 ) , F ( 2 ) ) ) ; PUT S K I P ( 2 ) L I S T ( ' T O T A L GAMES','AVGE MOVES','AV PROO OF C H O I C E S ' ) ; PUT S K I P L I S T ( M G C N T , M O , A S I Z E ) ; PUT S K I P F I L E J P S T A T ) L I S T ( M G C N T , M 0 , A S I Z E ) ; GOTO R E P E N T ; PMV: I F MDMDX<3 THEN I F MVCNTALL<=MVW THEN DO; C A L L MMAX; I F MXF=1 THEN GOTO EPMV; GOTO APMV; END; I F MDNDX=8 THEN DO; C A L L MMAX; GOTO KLOOR; END; APMV: MITA=MCNCN; M I T B = 7 ; C A L L K U T R A N D ( M I T B , M I T A , E M A T ) ; MQDX=EMAT; K L U = 0; K L U X = l ; K K K t I F D E A D ( K L U X ) = 0 THEN I F C N T R E ( K L U X ) = * 1 ' B THEN KLU = K L U + l ; I F MQDX <= K L U THEN GOTO K K K A ; K L U X = K L U X + l ; GOTO K K K ; K K K A : MITC=8; MITE=MVCNT(KLUX); C A L L K U T R A N D ( M I T C , M I T E , E M A T ) ; KLAN=EMAT; KWIZ = 0; J = 0 ; LNKD = L N K ( K L U X ) ; LNKI=MSLST(4975+LNKG+LNKG); 11=0; GEN: DO WHILE ( K L A N > K W I Z ) ; I F P A V L ( S P O N O ( M S L S T ( L N K I + I I ) ) ) = 0 THEN K W I Z = K W I Z + 1 ; 1 1 = 1 1 + 1 ; END; J=MSLST(LNKI+I1-1); IZ = KLUX; I X = S P O N O ( J ) ; I Y = J — T F O P S ( I X ) + 1 ; EPMV: MRAT=MVCNTALL/MCNCN; PUT S K I P E D I T ( A L P H ( I X ) , I Y , I Z , M V C N T A L L , M C N C N ) •(X(2),A(l),X(2),Fl2),X(2)fF(2),X(2),F(4),X(2),Fl2n: I F MDNDX = 7 THEN DO; PUT E D I T ( M R A T ) ( X 1 2 ) , F ( 5 , 2 ) ) ; PUT S K I P F I L E (PSTAT')' E D I T I A L P H ( I X ) , IY , I Z » MVCNTAL L, MCNCN, MR AT ) (X(2),A{1),X(2),F{2),X(2),F(2),X{2),F(4),X(2),F(2),X(2),F(5,2)); MOVES(MGCNT)=MOVES(MGCNT)+l; G S I Z E ( M G C N T ) = G S I Z E ( M G C N T ) * M V C M T A L L ; END; PUT S K I P 1 2 ) ; CALL UPDT; I F MVNDX = 0 THEN OUCH: DO; PUT L I S T ( I N V MV G E N ' ) ; S T O P ; E N D ; I F MDNDX=7 THEN I F MVCNTALL-^=0 THEN DO; L L , K K = 0 ; XYZ: L L = L L + 1 ; KK=KK+1; MRCH(LL)=0; IF D E A D ( K K ) = 0 THEN I F C N T R E ( K K ) = ' 1 • B THEN M R C H f L L ) = M V C M T ( K K ) ; I F LL~^ = M THEN GOTO X Y Z ; J J  8  PUT S K I P ( 2 ) E D I T t MRCH) ( 6 ( X < I ) , F < 2 > ) ) ; L L = 0; I F KK<L THEN GOTO X Y Z ; PUT S K I P { 3 ) ; END; I F M D N D X M O THEN GOTO T H E F O E ; I F MDNDX=6 THEN G E T 0 8S.MTR; I F MDNDX > 2 T H E N GOTO VAGA; THEFOE: I F MVCNTALL = 0 THEN DO; I WIN = 1; GOTO GEND; END; T H E F A : PUT L I S T ( * YOUR M O V E * ) ; PUT ' S K I P ( l ) ; GET L I S T ( C A R A , J , I n =l ; C L O P : I F I I > 1 2 T H E N DO; J - J + l O O ; GOTO CLOQ; END;... I F C A R A = A L P H ( I I ) THEN DO; J = J - 1 + T F O P S ( I I ) ; GOTO C L O Q ; END; I I = I I + l ; GOTO C L O P ; CLOQ: I F J > 9 9 9 8 THEN S T O P ; I F J > 9 9 8 THEN DO; M V C N T A L L t MCNCN = 0; MDNDX=99; GOTO GEND; END; CALL UPDT; I F MVNDX - 0 THEN DO; PUT L I S T {« I T I S S T I L L * ) ; GOTO T H E F A ; E N D ; I F MDNDX<3 THEN GOTO V A G B ; I F MDNDX<11 THEN GOTO T H E F O E ; JINIT=2; BSMTR: I F M V C N T A L L = 0 THEN GOTO GEND; I F J I N I T = 2 THEN J I N I T = l ; E L S E I F J I N I T = l THEN J I N I T = 2 ; E L S E DO; M I T A = 8 ; M I T B = 1 0 0 ; C A L L K U T R A N D ( M I T A M I T B , M I T C ) ; I F M I T O 5 0 THEN J I N I T = 2 ; E L S E DO; J ' I N I T , J I N I T S = 1 ; END; J IN I T S = J IN I TS + 1; M I T E = l ; M I T A = 0 ; C A L L T I M E ( M I T E , M I T A . M I T D ) ; END; I F MVCNTALL<=MVW THEN DO; I F MXF=1 THEN GOTO APMV; C A L L MMAX; I F MXF-.= 1 THEN GOTO APMV; GOTO EPMV; END; E L S E I F J I N I T = 2 T H E N GOTO APMV; ELSE MVSMPLR: B E G I N ; DCL 1•LOOKING*MCNCN)t 2 L K L O C , 2 L K O R N , 2 MVCNR* 2 MCNCR, 2 MSCOR, 2 M V L D X , 2 M V F L P , 2 M V L S D P ; MCNI=1; J I N D X = M + 1 9 ; DO 11=1 TO N; J I N D X = J I N D X + 1 6 - M ; DO J J = 1 TO M; K K = M * r i I - l ) + J J ; I F D E A D ( K K ) = 0 THEN DO; M F S T B D I J I N D X 5 = 0 ; I F C N T R E ( K K ) = ' 1 * B T H E N DO; M C N S ( M C N I ) = K K ; M C N S Q i M C N I ) = J I N D X ; M C N I = M C N I + l ; END; END; E L S E M F S T B D ( J I N D X ) = l ; J I N D X = J I N D X + 1 ; END; END; LKMCN=0; M V L D X = 0 ; MVMKR: DO 11 = 1 TO L ; I F D E A D ( I I ) = 0 THEN I F C N T R E ( I I 1 = '1'8 THEM DO; LKMCN=LKMCN+1; L N K D = L N K ( I I ) ; MLQOK=MSLST(4975+LNKG+LNKG); I F MLOOK =0 T H E N DO; PUT L I S T ! ' T R A P 1 0 * > ; GOTO NDMVMKR; END; MLKD=0; L K L O C ( L K M C N ) = I I ; M V F L P ( L K M C N ) = M L O O K ; MVLSDP(LKMCN)=MSLST(4976+LNKG+LNKG); LKLP: LKORNW=M SLST{MLOOK+MLKD); I F MAVL(SPONOT L K O R N W ) ) = * 1» B THEN DO; M V L D X ( L K M C N ) = M L K D ; L K O R N ( L K M C N ) = L K O R N W ; GOTO MVMKRS; END; MLKD=MLKD+l; MVLDX{LKMCN)=MVLDX(LKMCN)+1; I F M L K D < M V L S O P ( L K M C N ) THEN GOTO L K L P ; PUT L I S T C T R A P 1 1 » ) ; GOTO NDMVMKR; MVMKRS: C A L L F P L A Y { L K O R N W , M C N S Q I L K M C N ) , 1 ) ; C A L L KOUNT; t  MVCNR(LKMCN)=MVCNRW; MCNCR(LKMCN)=MCNCRW; CALL FUNPLAY(LKORNW,MCNSQ(LKMCN)); I F K T E S T = - 3 THEN PUT L I S T { L O O K I N G ( L K M C N ) ) ; NDMVMKR: END M V T S T R : DO 11 = 1 TO. MCNCN; C A L L S C O R E R { M V C N R ( I I ) , M C N C R ( I I ) , M S C Q R ( I I ) ) ; END; I F K T E S T = - 3 T H E N PUT L I S T ( M S C O R ) ; LKSCW=-2000; DO 11=1 TO MCNCN; I F M S C O R ( I I ) > L K S C W THEN DO; L K P T R = I I ; LKSCW = M S C O R ( 1 1 ) ; END; I F M S C O R ( I I ) = L K S C W THEN I F M V C N R ( I I ) < M V C N R ( L K P T R ) T H E N L K P T R = I I ; END; I F L K S C W - = - 9 0 0 T H E N GOTO C N T S C H ; FNDMV: IZ=LKLOC(LKPTR); J=LKORN(LKPTR); IX=SPONO(J); IY=LKORN(LKPTR)-TFOPS(IX)+l; GOTOEPMV; C N T S C H : I F M V C N T A L L > 7 0 0 THEN GOTO APMV; DO 11=1 TO MCNCN; MVLDX(II)=MVLDX(II)+l; DO W H I L E ( M V L D X ( I I X M V L S D P U I ) ) ; LKORNW=MSLST(MVFLP( 1 1 ) + M V L D X ( 1 1 ) ) ; I F M A V L ( S P O N O ( L K O R N W ) ) = «1*6 THEN DO; CALL F P L A Y ( L K O R N W , M C N S Q ( I I ) , l ) ; C A L L KOUNT; C A L L SCORER(MVCNRW,MCNCRW,LKSCOR); I F LKSCOR>LKSCW THEN DO; LKORN(II)=LKORNW; MVCNR(II)=MVCNRW; MCNCR(II)=MCNCRW; LKSCW,MSCOR(11) = LKSCOR; L K P T R = I I ; END; C A L L F U N P L A Y ( L K O R N W , M C N S Q f I I ) ) ; END; M V L D X ( I I ) = M V L D X ( 1 1 ) + l ; END; E N D ; GOTO FNDMV; END MVSMPLR; N C H I E F : END C H I E F ; GOTO G S T A R T ; UPDT: PROCEDURE; I F I Z > L I I Z < 1 THEN DO; PUT L I S T ('NO S Q U A R E ' ) ; GOTO MV; END; I F D E A D M Z ) > 0 THEN DO ; PUT L I S T ('DEAD S Q U A R E * ) » GO TO MV; END; IX = S P O N O ( J ) ; I F ( J < 1 1 J > 6 3 ) T H E N DO; PUT L I S T ('NO SUCH O R I E N T A T I O N ' ) ; GO TO MV; END; I F P A V L ( I X ) = 1 THEN DO; PUT L I S T ( ' P I E C E USED U P * ) ; GOTO MV; END; BTEST = S S T ( J ) ; I F A L L S E T -*= ( L N K ( I Z ) ! B T E S T ) THEN DO; PUT L I S T (*NO F I T * ) ; GO TO MV; END; P A V L ( I X ) = 1; MAVL ( I X ) = 0 B ; INFSW {*) = 'O'B; I Z A ( l ) = I Z ; D E A D { I Z ) = i x ; J J = 2; DO 1 = 1 TO 12 WHILE ( J J < 6 ) ; I F B T S ( I ) = 'O'B THEN DO; IZA(JJ)=IZ+MDNA(I)+M*MDNB(I); D E A D ( I Z A ( J J ) ) = IX ; J J = J J + l ; END; END; DOUP: DO L L = 1 TO 5; I F C N T R E ( I Z A ( L L ) ) = »1«B THEN DO; MCNCN = MCNCN - 1; MVCMTALL = M V C N T A L L - M V C N T ( I Z A ( L L ) ) ; END; LMKB = LNK ( I Z A ( L L ) ) DO MM = 1 TO 1 2 ; I F L J ( M M ) = ' l ' B THEN DO; K=IZA(LL)+MDNA(MM)+M*MDNBtMM); 1  MVMKR;  I F D E A D ( K ) = 0 THEN DO; INFSW(K) = H ' B ; LNK(K) = LNK(K) £ UPD{TMRLNK(MM)); END DOUP; CHK: DO NN = 1 TO L ; I F DEAD ( N N ) -.= 0 THEN GOTO NCHK; I F C N T R E ( N N ) = » O B THEN GOTO NCHK; LNKO = L N K ( N N ) ; LNKH=A975+LNKG+LNKG; L N K I = M S L S T ( L N K H ) ; I F L N K I = 0 THEN GOTO C H B ; MVCNTA=0; L N K J = M S L S T ( L N K H + 1 ) ; I F I N F S W ( N N ) = « 0 * B THEN DO; DO 11=0 TO L N K J - 1 ; I F S P O N O { M S L S T { L N K I + I I ) ) = I X THEN MVCNTA=MVCNTA+1; END; I F MVCNTA=MVCNT(NN) THEN GOTO C H 8 ; MVCNTALL=MVCNTALL-MVCNTA; MVCNT{NN)=MVCNT(NN)-MVCNTA; GOTO NCHK; END; E L S E DO; DO 11=0 TO L N K J - 1 ; I F P A V L ( S P O N O I M S L S T t L N K I + H ) ) ) = 0 THEN MVCNTA=MVCNTA+1; END I F MVCNTA=0 T H E N GOTO C H B ; MVCNT A L L = M V C N T A L L - M V C N T ( NN') +MVCNTA; MVCNT( NN )=MVCNTA; GOTO NCHK; END; CHB: MVCNTALL=MVCNTALL-MVCNT(NN); C N T R E ( N N ) = » 0 » B ; MCNCN = MCNCN - 1; NCHK: END CHK; MVNDX = 1 ; I F MMAXFG=0 T H E N MCNCW=MCNCN; RETURN; MV: PUT S K I P ( l ) ; MVNDX = 0; R E T U R N ; END U P D T ; KOUNT: P R O C ; MVCNRW,MCNCRW=0; J I N D X = M + 1 9 ; DO MM=1 TO N; J I N D X = J I N D X + 1 6 - M ; DO J J = 1 TO M; K K = M * ( M M - 1 ) + J J ; I F D E A D ( K K ) = 0 THEN I F C N T R E i K K ) = ' 1 » B THEN I F M F S T B D ( J I N D X ) = 0 THEN DO; CALL N E I G H t J I N D X ) ; MWIND=4975+MJ+MJ; I F M S L S T ( M W I N D ) > 0 THEN DO;; LKLN=MSLST(MWIND+1); LKLC=MSLST<MWIND); LKDP,LKCT=0; DO W H I L E ( L K O P < L K L N ) ; I F M A V L { S P O N O ( M S L S T ( L K L C + L K D P ) ) ) = « l B THEN DO; L K C T = L K C T + 1 ; MVCNRW=MVCNRW+1; END; L K D P = L K D P + l ; END; I F L K C T > 0 T H E N MCNCRW=MCNCRW+1; END; END; J I N D X = J I N D X + l ; NDKOUNT: END KOUNT; SCORER: PROC{MSCMV,MSCMC,MSCORW); M5CQRW-0; I F MSCHV>520 THEN DO; MSC0RW=-900; R E T U R N ; END; I F MSCMV<49 THEN DO; MSC0RW=-1000; R E T U R N ; END; I F M S C M 0 4 6 T H E N DO; MSC0RW=-950; R E T U R N ; END; I F MSCMC<10 THEN DO; MSCCRW=-980; R E T U R N ; END; MTSTNDX=MKA(MSCMV-47); I F MTSTNDX=0 THEN R E T U R N ; N R L P : MKAW=MKA(MTSTNDX) ; I F MKAW=0 THEN DO; MSCORW=MKA{MTSTNDX-1)*.5; R E T U R N ; END; I F MKAW>MSCMC THEN DO; M S C O R W = ( M K A ( M T S T N D X - 1 ) + M K A { M T S T N D X + 1 ) ) * . 5 ; RETURN ; END; I F MKAW<MSCMC THEN DO; MTSTNDX=MTSTNDX+2; GOTO N R L P ; END; MSCORW=MKA(MTSTNDX+1); t  s  END S C O R E R ; MMAX: P R O C E D U R E ; DCL WRES B I T ( 2 ) , 1 SPLIST(300Q), 2 MDEP» 2 M L E N , 2 NINE I» 2 MLBR, 2 MRBR, 2 MSON, 2 MORN» 2 MLOC, 2 M L E V , 2 MNEX, 2 MFAT, 2 M I N X , 2 MMOV 3 I T ( 2 ) , 2 MRES B I T ( 2 ) ; MWRK=0; K O D E C , N O D E C = l ; MCNSFZ,MCNI,MMAXFG,MTRAV,MARK=1; MNEXZ=2; DO 1 1 = 1 TO 1 2 ; I F P A V L ( I I ) = 0 THEN M A V L ( 1 1 ) = 1 » B ; E L S E M A V L ( 1 1 3 = • 0 » B ; END; DO 11=1 TO 2 9 9 9 ; M N E X { I I ) = 1 1 + 1 ; END; M N E X { 3 0 0 0 ) , M L B R ( 1 ) , M R B R ( 1 ) , M O R N ( 1 ) , M L O C ( 1 ) = 0 ; MMOV ( 1 ) = »01« B ; MNEI(13,NORN,NLOC=0; MRES(1)='10»B; MSON(1)=-999; MLBRI13,MRBR(1)=0; MWND=3000; M L E V ( l ) = l ; M C N S D ( * , 1 3 = 1 • B ; J I N D X = M + 1 9 ; DO 11=1 TO N ; J I N D X = J I N D X + 1 6 - M ; DO J J = 1 TO M; KK=M*<II-13+JJ; I F DEAD < KK 3 =0 THEN DO; M F S T B D ( J I N D X ) = 0; I F C N T R E ( K K 3 = '1•B THEN DO; M C N S ( M C N I 3=KK; MCNSQIMCNI3 = J I N D X ; M C N I = H C N I + l ; E N D ; END; ELSE MFSTBDJJINDX)=l; JINDX=JINDX+l; END; END; CONROT: I F K T E S T > 3 THEN PUT L I S T , ' C N R T • » S P L I S T ( M T R A V ) 3 ; I F MTRAV=MARK THEN I F M R E S t M T R A V ) < ' 1 0 » 8 THEN DO; N T I M = C P U T I M E ; MBTM=NTI M-WTIM;. GOTO MMA; E N D ; E L S E WTIM=CPUTIME; I F M R E S ( M T R A V 3 = *11 * B THEN GOTO A C R E N ; I F M R E S ( M T R A V 3 = * 10 * B THEN GOTO C R U N ; I F M S O N ( M T R A V ) = 0 THEN DO; I F MNE I ( MTRAV 3 -»=0 THEN DO; I F M R B R ( M T R A V ) = 0 T H E N DO; MRESIMFAT(MTRAV))=MRES(MTRAV); CALL DLT(MTRAV); I F M L B R ( M T R A V ) - = 0 THEN DO; MTRAV=MLBR(MTRAV3; MRBR(MTRAV3=0; MSON ( M F A T ( M T R A V ) ) = M T R A V ; E N D ; ELSE MSON(MFAT(MTRAV))=0; M T R A V = M F A T ( M T R A V ) ; GOTO CONROT; E N D ; I F MLBR { MTRAV ) -i = 0 THEN MRBR ( MLBR ( MTRAV 3 3 =MRBR (MTR AV ) ; CALL DLT(MTRAV); MTRAV=-MRBR(MTRAV3; MLBR(MTRAV)=MLBR(ML8R(MTRAV)); MSONIMFAT(MTRAV))=MTRAV; GOTO CONROT; END; MRES(MFAT(MTRAV 3 )=MRES(MTRAV); CALL FUNPLAY(MORN(MTRAV3,MCNSQ(MINX(MTRAV))3; M T R A V = M F A T ( M T R A V ) ; GOTO CONROT; E N D ; I F M N E I ( M T R A V ) = 0 THEN DO; I F M R E S ( M T R A V ) = » 0 0 * B THEN DO; C A L L F U N P L A Y ( M O R N ( M T R A V 3,MCNSQ(MI N X ( M T R A V ) ) 3 ; . M T R A V = M F A T ( M T R A V ) ; M R E S ( M T R A V ) = 0 0 • B ; GOTO CONROT; E N D ; I F M M O V ( M T R A V ) = ' 0 0 " 8 THEN I F MLBR ( MTRAV) -»=0 THEN DO; IE=MLBR(MTRAV); MLBR(MTRAV)=0; IEAD: CALL D L T ( I E ) ; I F M L B R ( I E ) - = 0 THEN DO; I E = M L B R ( I E ) ; GOTO I E A D ; E N D ; E N D ; CALL FUNPLAY(MORN(MTRAV),MCNSQ(MINX(MTRAV)33; M T R A V = M F A T ( M T R A V ) ; M R E S { M T R A V ) = » 0 1 » B ; GOTO CONROT; E N D ; I F M M O V ( M T R A V ) = » 0 1 ' B THEN I F M R E S ( M T R A V ) = » 0 0 ' B THEM 9  9  1  GOTO C O N E X P ; E L S E DO; I F M L B R { M T R A V ) = 0 THEN GOTO MI D E L ; IE=MLBR(MTRAV); MLBR(MTRAV)=0; IEBD: CALL D L T ( I E ) ; I F MLBR(.IE.)-»=0 THEN DO; I E = MLBR ( I E) ; GOTO I E B D ; END; MI D E L : I F M R 3 R ( M T R A V ) < = 0 THEN GOTO E N D E L ; I E = M R B R ( M T R A V ) ; MRBR ( M T R A V ) = 0 ; I E C D : C A L L D L T ( I E ) ; I F MRBR<IE)-»=0 THEN DO; I E=MRBR 11E) ; GOTO I E C D ; END; ENDEL: MTRAV=MFAT(MTRAV); M R E S ( M T R A V ) = ' 0 1 ' B ; GOTO CONROT; END; I F M R E S ( M T R A V } = » 0 0 « 8 THEN DO; M T R A V = M F A T ( M T R A V ) ; M R E S ( M T R A V ) = ' 0 0 • B ; GOTO CONROT; E N D ; C O N E X P : I F M D E P ( M T R A V ) > = M L E N I M T R A V ) THEN DO; I F M R B R ( M T R A V ) = 0 THEN DO; MRES(MFAT(MTRAV))=MRES(MTRAV); MTRAV=MFAT(MTRAV ) ; GOTO CONROT; END; E L S E DO; M T R A V = M R B R ( M T R A V ) ; M S O N ( M F A T ( M T R A V ) ) = M T R A V ; GOTO CONROT; END; END; MWOR=MSLST(MORN I M T R A V ) + M D E P ( M T R A V ) ) ; I F M A V L ( S P O N O ( M W O R ) ) = '08 8 THEN DO; M D E P ( M T R A V ) = M D E P ( M T R A V ) + 1 ; GOTO C O N E X P ; END; MWT=MTRAV; GOTO B C R E N ; CRUN: I F K T E S T > 4 THEN PUT L I S T ( ' C R U N ' ) ; IA=MCNCW; MWT=MTRAV; M W L = H L E V ( M T R A V ) ; L C R U N : I F I A = 0 THEN GOTO NDCRUN; I F MCNSD( IA,MWL)-.= '1 «B T H E N DO; I A = I A ~ l ; GOTO L C R U N ; END; C A L L N E I G H ( M C N S Q I I A ) ) *, MWIND=4975+MJ+MJ; I F M S L S T ( M W I N D ) = 0 THEN DO; M C N S D J I A , M W L ) = 0 * B ; I A = I A - 1 ; GOTO L C R U N ; END; I F MNEXZ=0 T H E N GOTO N D I S H T ; NODEC=NODEC+l; KODEC=KODEC+l; MF A T { M N E X Z ) = M T R A V ; MMOV(MNEXZ)=MMOV(MTRAV); MLEV(MNEXZ)=MLEV(MTRAV); MSON(MTRAV) MTRAV=MNEXZ; MNEI(MTRAV)=MJ; MORN(MTRAV)=MSLST(MWIND); MNEXZ=MNEX(MTRAV) ; MLEN(MTRAV)=MSLST(MWIND+1); MRBR(MTRAV),MOEP(MTRAV)=0; MINX(MTRAV)=IA; MLOC(MTRAV)=MCNS(IA); MRES(MTRAV)=»ll'B; ML3R(MTRAV) MSONIMTRAV)=-999; MCRUN: I A = I A - l ; I F I A = 0 THEN GOTO NDCRUN; I F MCNSD ( I A , MWL ) -»= 1 * B THEN GOTO MCRUN; CALL N E I G H ( M C N S Q ( I A ) ) ; MWIND=4975+MJ+MJ; I F M S L S T ( M W I N D ) = 0 THEN DO; , M C N S D ( I A , M W L ) = 0 B ; GOTO MCRUN; END; I F MNEXZ=0 THEN GOTD N D I S H T ; N0DEC=N0DEC+1; KODEC = KODEC-H ; MLBR(MTRAV)=MNEXZ; MFAT ( MNEXZ )=MFAT( MTRAV ) *, MSON(MFAT(MTRAV))=MNEXZ; MLEV(MNEXZ)=MLEV{MTRAV); 1  8  T  T  4  ,  ,  MMQV(MNEXZ)=MMQV(MTRAV);  I  Y  MR B R ( M N E X Z ) = M T R A V ; MTRAV=MNEXZ; M N E X Z - M . N E . X t M T R A.V.) ; MNEI  (MTRAV)=MJ;  MORN(MTRAV)=MSLST(MWIND); MINX(MTRAV)=IA; MLEN(MTRAV) = MSLST(MWIND+1); MOEPJMTRAV)=0; MLOC(MTRAV)=MCNS(IA); MRES(MTRAV)=MI«B; MLBRIMTRAV)» GOTO  MSON(MTRAV)=-999;  MCRUN;  NDCRUN:  IF  MWT=MTRAV  THEN  DO;  B THEN  *00* MRES(MTRAV)=»OO B; IF  MMOV(MTRAV) =  MSON(MTRAV)=0;  MRES(MTRAV)=•01'B;  ELSE  ,  END; ELSE  MLBR(MTRAV)=0;  GOTO  CONROT;  ACREN: IF  KTEST>4  PUT  THEN  L I S T ! « C R E N » ) ;  CREN: IF  IF  MDEP(MTRAV)>=MLEN(MTRAV)  MMOV(MTRAV)='00'B  ELSE  THEN  0 0 ;  MRES(MTRAV)=•01•B;  MRES(MTRAV)=»00»B;  MSON(MTRAV)=0; M W O R = MSL IF  THEN  GOTO  NDCREN;  END;  ST(MORN t MTRAV)+MDEP(MTRAV));  MAVL(SPONO(MWOR)) = ' 0 * B  THEN  MDEPlMTRAV)=MDEP(MTRAV)+1;  DO;  GOTO  CREN;  END;  BCREN: IF  MNEXZ=0  THEN  GOTO  NDISHT;  M0DEC=N0DEC+1; K0DEC=K0DEC+1; MDEP(MTRAV)=MDEP(MTRAV)+l; IF  MSONlMTRAV)=-999  ELSE  DO;  THEN  MLBR{MNEXZ)=0;  MLBR(MNEXZ)=MSON(MTRAV);  MRBR(MSON(MTRAV))=MNEXZ;  MSON{MTRAV)=MNEXZ; MRES(MNEXZ)='10»B; IF  THEN  MM0V(MTRAV)='01'B  ELSE  MMOVtMNEXZ)=•00•B;  MM0V(MNEXZ)= 01»B; ,  MNEI(MNEXZ)=0; MORN(MNEXZ)=MWOR; MLOC{MNEXZ)=MLOC(MTRAV); MINX(MNEXZ)=MINX(MTRAV); MFAT(MNEXZ)=MTRAV; M R B R (MNEXZ )  V  M S O N ( M N E X Z )=—"999 ;  MLEV(MNEXZ)=MLEV(MTRAV)+l; IF  MLEV(MNEXZ)>8  PUT  LIST{*DPTH  THEN  OOFL:  OFL * »NODEC);  DO; MXF=-1;  RETURN;  END;  MTRAV=MNEXZ; MNEXZ=MNEX(MTRAV); CALL  FPLAY(MWOR,MCNSQ(MINX(MTRAV))  ,MLEV(MTRAV));  NDCREN: GOTO  CONROT;  MMA: HRES =MRES(MTRAV) /*  IF  NORN-. =0  ;  THEN  NODO:  DO;  MTRAV=MSON(MTRAV); ABLQ:  IF  MRBR(MTRAV)<=0  MTRAV=MRBR(MTRAV);  GOTO  THEN ABLQ;  GOTO  A8GR;  END;  ABGR: I F MLOC't MTRAV) =NLQC T H E N GOTO A B F D ; C A L L D L T ( M T R A V ) ; M T R A V = M L B R ( M T R A V ) ; GOTO ABGR; A B F D : I F M L B R ( M T R A V ) = 0 THEN GOTO ABAD; I I = M T R A V ; ABrRD:. 11 = ML BR (11.) ; C A L L D L T U I ) ; I F M L B R ( I I ) - . = 0 THEN GOTO A 8 R D ; A B A D : I F W R E S = 0 1 » B THEN GOTO ABMW; I F M S O N ( M T R A V ) < 0 THEN GOTO ABCR; MTRAV=MSON(MTRAV) ; A 8 L R : I F M L B R ( M T R A V ) = 0 THEN GOTO A B L S ; M T R A V = M L B R ( M T R A V ) ; GOTO A B L R ; A B L S : I F MORN(MTRAV)=NORN THEN GOTO A B F N ; C A L L D L T ( M T R A V ) ; I F M R B R ( M T R A V ) < 0 THEN GOTO ABCR; M T R A V = M R B R ( M T R A V ) ; GOTO A B L S ; ABCR: CALL D L T ( M T R A V ) ; I F MNEXZ=0 THEN GOTO N D I S H T ; MNEI(MNEXZ),MLBR(MNEXZ),MRBR(MNEXZ)=0; MRES(MNEXZ)=*10*8; MMOV(MNEXZ)='01 8; I F M N E I ( M T R A V ) = 0 THEN M L E V ( M N E X Z ) = M L E V ( M T R A V ) ; E L S E MLEV(MNEXZ)=MLEV(MTRAV)+l; I F M L E V ( M N E X Z ) > 8 THEN GOTO D O F L ; M C N I = 1 ; A B L P : I F M C N S ( M C N I ) - = N L O C THEN DO; M C N I = M C N I + l ; GOTO A B L P ; END; MARK» MTRAV=MNEXZ; CALL FPLAY(NORN,MCNSQ(MCNl),MLEV(MTRAV)); NORN,NLOC=0; M N E X Z = M N E X ( M T R A V ) ; GOTO CONROT; ABMW: M T R A V = M S O N ( M T R A V ) ; ABMP: I F MORN ( MTRAV )-•= NORN THEN DO; M T R A V = M L B R ( M T R A V ) ; GOTO ABMP; END; A B F N : CALL F PLAY(NORN» MCNSQIMINX(MTRAV))»MLEV C M T R A V ) ) ; NORN,NLOC=0; END NODO; */ ABEX: MTRAV=MSON(MTRAV); I F MTRAV<=0 T H E N DO; PUT F I L E ( E E E ) L 1 S T ( S P L I S T ) ; M X F = - 1 ; GOTO NDMMAX; END; I F M R E S ( M T R A V ) = ' 0 0 8 THEN DO; M X F = 2 ; GOTO P U K E ; END; /* DO W H I L E { M R B R ( M T R A V ) - » = 0 ) ; PUT L I S T ( " T R A P 2* ) ; M T R A V = M R B R ( M T R A V ) ; END; N L E N = M L E N ( M T R A V ) ; NTRAV=MTRAV; DO W H I L E ( M L B R ( M T R A V ) - = 0 ) ; MTRAV=MLBR(MTRAV); I F M L E N ( M T R A V ) < N L E N THEN DO; N L E N = M L E N ( MTRAV) ; NTR.AV = MTR AV ; END; END; MTRAV=NTRAV; END; A8EY: I F MSON(MTRAV)<=0 THEN DO; C A L L D L T ( M T R A V ) ; M T R A V ^ M L B R ( M T R A V ) ; GOTO A B E Y ; END; I F M R E S ( M T R A V ) = ' 0 0 ' B THEN 0 0 ; I F M L B R ( M T R A V ) > 0 THEN DO; I K = M L B R ( M T R A V ) ; M R B R ( I K ) = 0 ; C A L L D L T { M F A T { I K ) ) ; END; END; */ MTRAV=MSON(MTRAV); J=MORN ( MTRAV ) ; I X = S P O N O U ) ; I Y = J - T F O P S ( I X ) + l ; IZ=MLOC(MTRAV); CALL F P L A Y ( J , M C M S Q ( M I NX(MTRAV))» MLEV(MTRAV) ) ; MXF=l; PUKE: PUT L I S T ( K O D E C , M B T M , M T R A V , N O D E C , M X F ) ; RETURN; /* PUT S K I P ( 2 ) ; C A L L UPDT; I F MVNDX=0 THEN DO; PUT L I S T f ' I N V MACH M O V E ) ; GOTO N D I S H T ; END; ,  1  ,  1  61.  ENEMA: I F M V C N T A L L = 0 THEN DO ; I W I N = 1 ; GOTO NDMMAX; END; ENEMO: PUT L I S T { ' YOU TO M O V E ' ) ; PUT S K I P ( 2 ) ; GET L I S T ( C A R A , N O R N , N L O C ) ; 11 = I.V F L O P : I F 1 1 > 1 2 THEN DO; NORN=NORN+100; GOTO FLQQ; END; I F C A R A = A L P H ( I I ) THEM DO; NQRN=NORN-l + T F Q P S t I I ) ; GOTO F L O Q ; E N D ; 1 1 = 1 1 + 1 ; GOTO F L O P ; FLOQ: I F N 0 R N > 9 9 9 8 THEN S T O P ; I F N 0 R N > 9 9 8 THEN DO; M V C N T A L L , M C N C N = 0 ; MDNDX=6; GOTO NDMMAX; END; J=NORN; I Z = N L O C ; C A L L U P D T ; I F MVNDX=0 T H E N DO; PUT L I S T C I T I S S T I L L ' ) ; GOTO ENEMO; END; I F MVCNTALL-i=0 THEN GOTO MMA; I W I N = 0 ; * / GOTO NDMMAX; DLT: PROC(ID); I F KTEST>1 THEN PUT L I S T ( ' D L T ' , I D ) ; IDW=ID; MNEX(ID)=0; MNEX(MWND),MWND=ID; KODEC=KODEC-l; I F M S O N ( I D ) < = 0 THEN GOTO N D O L T ; INLP: ID=MSON(ID); L P : I F M L B R U D ) - * = 0 T H E N DO; ID = M L B R ( I D ) ; GOTO L P ; END; ILLP: I F M S O N ( I D ) < = 0 T H E N GOTO I M L P ; GOTO I N L P ; I M L P : I F I D = IDW T H E N GOTO N D D L T ; MNEX(ID)=0; MNEX(MWND),MWND=ID; KODEC=KODEC-l; I F M R B R ( I D ) < = 0 THEN GOTO I O L P ; I D = M R B R ( I D ) ; GOTO I L L P ; I O L P : I F ( M F A T ( I'D )<=0 ) ] ( M F A T ( I D ) > 3 0 0 0 ) THEN DO; I F K T E S T > 1 THEN DO; PUT L I ST ( ( S P L I S T ( 11 ) DO I I = M A X ( 1 , I D - l O O ) TO MINI 3 0 0 0 , I D + 1 0 0 ) ) ) ; E N D ; GOTO N D D L T ; END; ID=MFAT(ID); M S O N ( I D ) = 0 ; GOTO I M L P ; N D D L T : ID=IDW; END D L T ; N D I S H T : M8TM=CPUTIME-WTIM; L 0 0 T T = 1 ; PUT L I S T ( O V E R F L O W * , M 8 T M , N Q D E C ) ; MXF=-1; I F MDNDX=8 THEN DO; PUT S K I P I 3 ) ; GOTO NDMMAX; E N D ; /£ MTRAV-MARK; GOTO MMA; * / .MDMMAX5' END MMAX; NEIGH: PROCEDURE(JJ); MJ = 0; I F M F S T B D t J J + 1 ) = 0 T H E N DO; J L ( 1 ) = ' 1 ' B ; I F M F S T B D t J J + 2 ) = 0 THEN J L ( 1 0 ) = » 1 * 3 ; I F M F S T B D t J J - 1 5 ) = 0 THEM J L ( 5 ) = * I » B ; I F M F S T B D t J J + 1 7 ) = 0 THEN J L { 6 ) = * 1 * B ; END; I F M F S T B D t J J - 1 ) = 0 THEN DO; J L ( 3 ) = * 1 ' B ; I F M F S T B D ( J J - 2 ) = 0 THEN J L ( 1 2 ) = ' 1 ' B ; I F M F S T B D ( J J - 1 7 ) = 0 THEN J L < 3 ) = ' 1 ' 9 ; I F M F S T B D t J J + 1 5 ) = 0 THEN J L ( 7 ) = * L ' B ; END; I F M F S T B D t J J - 1 6 ) = 0 THEN DO; J L ( 4 ) = ' 1 ' B ; I F M F S T B D t J J - 3 2 ) = 0 THEN J L { 9 ) = * 1 » 8 ; I F M F S T B D ( J J - 1 5 ) = 0 THEN J L ( 5 ) = « 1 ' B ; 1  I F M F S T B D ( J J - 1 7 ) = 0 THEN J L ( 8 ) = » 1 ' B ; END; M F S T B D U J + 1 6 ) = 0 THEN 0 0 ; J L I 2 ) = ' I • 3 ; I F M F S T B D { J J + 3 2 ) = 0 THEN J L { 1 1 ) = « 1 ' 3 ; I F MFST3D{ J J + 15 ). = 0 THEN J U 7 ) > = * 1 ' B ; I F M F S T B D ( J J + 1 7 ) = 0 THEN J L ( 6 ) = « 1 ' B ; END; END N E I G H ; KUTRAND: P R O C ( E M Y T , K R N G , K R E S ) ; DCL (EMYT,KRNG,KRES) FIXED B I N ( 3 1 ) , TRUNC F I X E D D E C ( 2 , 0 ) ; I F EMYT>7 THEN EMYT=8; E L S E EMYT=7; CALL TIME(EMYT,0,EMAT); TRUNC=EMAT; KRES=((TRUNC+1)*KRNG)/1CG0; I F K R E S < K R N G THEN K R £ S = K R £ S + 1 ; END KUTRAND; FPLAY: PROCEDURE!IWO,IWL,MWLV); I F K T E S T > 4 THEN PUT L I S T l ' F P L Y * ) ; MAVL(SPONO(IWO))='0'B; MFSTBD(IWL)=1; DO I H = 1 TO 4; MFSTBD < I W L + M S F F ( I WO »IH)) = 1; END; I F MMAXFG=1 THEN DO; DO I H = 1 TO MCNCW; M C N S D I I H , M W L V ) = ' 0 • B ; I F M C N S D ( I H t M W L V — 1 ) = ' 1 ' 8 THEN I F M F S T B D t M C N S Q ( I H ) ) = 0 THEN MCNSD(IH,MWLV)=«1*3; END; END F P L A Y ; FUNPLAY: PROCEDURE(IWO,IWL>; I F K T E S T > 4 THEN PUT L I S T { ' F U N P * ) ; M A V L I S P O N O ( I W O ) ) = * 1'B ; MFSTBD(IWL)=0; DO I H = 1 TO 4; M F S T 8 D ( I W L + M S F F I I W O , I H } ) = 0 ; E N D ; END F U N P L A Y ; NDBD: END BOARD; I F MDNDX-.=7 THEN GOTO G S T A R T ; E L S E GOTO G S T A R T A ; TOO: GET F I L E { M H K P N F ) L I S T ( ( M K A ( I I ) DO 11=1 TO 4 0 0 8 ) ) ; GOTO F R O ; S E E : GET F I L E ( F F F ) L 1 S T I < M S L S T < I I ) DO 11 = 1 TO 1 3 1 6 6 ) ) ; GOTO SAW; R E P E N T : PUT S K I P L I S T ( ' T H A N K YOU AND B Y E - B Y E ) ; END P E N T O ; IF  1  (B)  0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 4 30 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580  : : : : : : :• : : : : : ':  i  1 45 23 14 35 59 44 14 63 5 32 54 38 25 1 28 47 56 55 39 16 38 60 17 1 31 58 57 24 3 35 10 7 43 6 34 60 26 4 33 58 9 6 3 31 54 14 49 23 42 18  : : : : : : : :  41 21 18 40 26 40 20  t  : : : : ': : : : ": : • : : .: ': : ': :: ': : :: ': :: "i .: :: :: ': ": : :: : :: : •' :  1  63.  EXCERPTS FROM THE COMPLETE MOVE LISTS  57 52 40 17 37 61 55 17 7 6 33 55 44 42 2 29 48 33 17 50 20 40 62 23 2 32 59 6 46 4 37 12 53 58 8 36 8 44 5 34 61 13 19 4 32 59 39 53 27 47 13 16 14 24 22 50 35 62 23  34 18 47 21 39 63 58 20 12 8 34 56 9 49 4 30 51 19 23 61 25 42 5 45 6 34 60 52 57 7 41 15 30 2 11 38 54 59 7 35 10 16 24 5 33 61 61 58 23 50 42 26 61 37 23 51 44 1 36  20 24 60 26 41 10 2 46 24 11 36 57 11 60 5 31 52 35 28 1 27 48 55 56 8 36 9 29 13 8 49 22 24 17 18 42 27 3 12 37 14 18 29 7 35 63 2 I 29 51 60 27 2 43 27 54 45 6 45  36 29 2 27 49 12 58 53 41 18 38 60 18 16 6 33 55 45 41 2 29 49 28 4 13 38 11 23 19 17 51 25 37 21 22 47 25 18 15 39 20 42 34 8 37 10 7 3 32 55 3 40 7 46 28 55 52 19 2  46 42 328 50 15 31 15 48 22 40 62 21 26 7 34 57 10 47 3 30 51 26 15 16 40 21 36 34 21 53 38 46 41 23 51 38 22 19 48 36 62 47 21 39 15 20 4 33 56 8 50 20 1 29 56 59 29 3  9 48 4 30 51 22 21 25 61 23 42 3 43 27 12 35 58 12 63 6 31 52 35 19 20 49 37 45 42 28 54 43 10 49 28 54 43 42 24 51 45 11 48 26 41 12 25 5 34 - 60 21 62 31 3 32 57 13 34 4  13 62 5 31 53 25 37 30 1 27 47 59 54 40 15 37 61 15 5 7 32 53 44 39 25 51 43 9 47 30 56 44 12 63 29 55 9 50 29 52 46 40 52 27 49 17 30 6 36 62 32 12 48 5 33 62 42 47 5  16 6 7 32 54 38 43 39 3 28 50 32 8 50 19 39 63 22 14 8 34 58 10 47 27 52 46 11 60 32 59 55 15 3 32 56 13 62 30 55 53 60 57 28 50 41 31 8 38 11 49 10 53 6 36 9 60 48 7  19 11 8 33 56 43 10 49 4 29 51 22 13 62 24 41 4 44 26 13 36 59 14 63 30 53 54 18 2 33 63 58 25 4 33 57 16 1 31 57 56 I 2 30 51 63 43 22 40 9 54 17 58 11 38 16 16 52 8  590 600 610 620 630 640 650 660 670 680 690 700 710 720 730 740 750 760 770 780 790 800 810 820 830 840 850 860 870 880 890 900 910 920 930 940 950 960 970 980 990 1000 1010 1020 1030 1040 1050 1060 1070 1080 1090 1100 1110 1120 1130 1140 1150 1160 1170 1180  : : : ' : : ' : • : " : ' 3: .: : " -: : ' : : <: ': : :: : ": .: : •: ': : : : : : : : : : .: : : : :  14 39 14 47 12 48 5 33 57 6 46 28 54 30 8 42 45 59 19 55 45 42 33 46 42 5 32 56 37 11 55 53 59 1 33 61 1 4 31 59 58 23 56 8 49 6  :  4 7  : : : : : : : : : : : •: :  35 12 16 42 43 3 12 17 20 52 19 7 59  17 41 10 55 41 49 O  34 60 24 2  31 56 49 22 47 52 22 24 57 23 2 35 24 6 7 33 61 58 27 .5 7 56 62 2 35 23 16 5  32 63 2  28 57 38 60 15 5 1 55 22 20 48 54 18 22 2 3 27 53 34 8 1  26 49 17 56 63 58 8 38 62 29 3 32 59 53 23 51 59 25 29 58 47 3 41 48 11 8 37 63 63 23 60 22 32 5 37 45 20 8 35 24 17 29 9 54 16 19 52 10 33 25 51 11 22 33 45 29 58 42 30 5  27 50 15 12 39 21 11 40 16 48 5 33 61 58 23 55 18 38 30 10 6 4 49 1 23 14 39 21 31 32 10 44 40 6 41 6 40 14 37 46 21 32 35 9 26 28 5 5  14 50 27 52 21 42 41 56 31 59 9 33 14  28 51 39 22 61 24 18 42 9 52 7 35 17 7 29 56 9 43 33 36 13 7 51 18 40 17 41 43 39 34 14 26 9 7 48 36 13 17 39 7 41 33 44 13 27 30 57 45 61 29 53 32 50 5  1 32 62 18 35 16  30 53 63 33 2  37 2 2  47 18 57 14 37 10 12 32 60 13 44 34 45 34 8 53 29 47 21 49 25 1 38 17 50 11 12 51 52 19 21 49 37 3 36 45 44 40 31 5 3 56 1 30 58 40 62 26 2 36 29 24 37 20  31 56 4 41 7  43 27 50 62 20 17 41 15 41 33 13 42 4 35 46 36 17 56 36 60 27 50 49 4 40 20 3 18 24 52 9 34 26 51 53 6 38 52 59 1 34 63 4 3 31 59 8 28 50 3 38 36 46 51 26  32 59 5 50 25 1 28 51 11 23 21 50 63 3 34 19 3 7  37 53 52 28 59 57 2 28 51 2 5 47 23 16 21 28 55 11 47 27 53 10 11 51 59 11 2 35 26 15 7 34 62 25 35 61 6 40 45 57 53 27  33 61 23 61 30 3 29 54 40 36 26 51 2 4 36 35 8 12 51 56 60 30 63 62 3 30 53 15 6 51 36 27 43 29 57 46 60 28 54 12 18 54 25 21 4 37 44 19 6 36 27 49 44 10 7 48 52 3 54 31  35 63 23 15 31 4 32 55 1 45 27 53 25 6 38 44 54 15 52 19 29 32 20 34 4 31 54 30 8 54 46 38 54 31 58 57 2 30 56 43 22 55 43 32 5 39 5 39 13 38 38 60 55 14 16 51 13 4 56 39  65.  1190 1200 1210 1220 1230 1240 1250 1260 1270 1280 1290 1300 1310 1320 1330 1340 1350 1360 1370 1380 1390 1400 1410 1420 1430 1440 1450 1460 1470 1480 1490 1500 1510 1520 1530 1540 1550 1560 1570 1580 1590 1600 1610 1620 1630  : : : : ,: : : : : ": : «: ': : ,: : ": :: : :: : :: •: :: -: : : i: :: : : •: •: : •: : : ': .: *: : .: ': : ': 16 40 .: 165 0 : 1660 •: 1670 : 1680 'i 1690 : 1700 i: 1710 : 1720 : 1730 : 1740 : 1750 : 1760 : 1770 : 17 80 : 1  48 31 43 29 56 39 27 13 59 43 51 36 23 ... 39 42 8 51 41 39 16 42 45 23 32 10 7 58 33 38 21 28 58 22 25 51 48 14 50 39 21 1 4 33 43 25 32 60 16 29 58 45 23 32 60 18 27 59 1 8 41  50 39 58 33 57 10 34 16 38 54 52 45 28 50 6 17 53 47 50 25 48 52 47 35 15 24 1 34 32 43 29 61 33 27 53 52 17 51 61 24 6 5  37 37 30 34  44 26  31 61 35 28 34 46 24 31 61 20 14 49  61 7 1 34 62 14 36 19 44 1 55 46 41 61 11 21 54 63 61 27 49 9 60 37 25 31 3 38 3 54 31 39 50 29 58 20 26 53 2 37 24 7 39 58 49 36 33  27 33 10 56 47 36 36 29 33 47 40 17 50  62 24 3 36. 31 20 38 26 16 2 57 53 4 34 23 28 56 12 1 29 51 46 2 49 38 39 4 42 22 1 33 14 55 30 62 23 27 56 7 46 29 8 41 2 63 38  59 50 35 14 4 63 38 . 57 48 35 23 48 27 51  30 48 4 .3 8 58 46 51 35 26 5  58 56 19 36 47 30 63 15 2 30 52 57 4 51 43 48 5 50 27 2 37 61 56 31 40 36 28 59 20 42 34 21 49 21 4 47 3 62 37 20 19 2 49 1 62 37 6 62 28 53  53 61 5 42 37 53 54 44 27 6 10 33 47 46 60 32 35 22 3 31 58 13 8 53 44 61 8 51 40 5 41 10 1 34 16 45 31 61 30 18 47 27 50 10 6 51  22 1 48 36 10 6 51 20 3 50 34 2 30 56  37 10 8 50 43 1 55 45 40 28 14 56 63 57 2 33 33 44 6 32 59 19 17 54 55 12 18 54 50 6 48 12 3 36 62 2 32 4L 31 62 48 28 51 17 8 54 9 5 51 45 15 3 52 9 5 51 36 3 31 61  46 12 18 51 15 4  56 52 9 31 17 35 5 18 3 37 4 55  7 34 60 34 21 56 58 15 22 55 62 7 51 15 7 38 1 3 33 17 48 11 57 30 54 46 11 55  18 7 52 46 44 13 53 16 7 53 60 4 32 63  14 15 22 54 25 5 57 59 11 35 20 45 14 24 4 41 19 5 8 38 62 6 28 59 37 25 27 57 11 12 55 4 8 42 6 5 35 63 49 40 2 31 61 53 23 56 43 12 55 53 55 25 58 45 14 54 29 5 33 48  20 25 27 55 30 8 9 32 21 37 23 17 26 29 7 49 28 26 13 40 36 11 30 63 30 43 29 62 18 24 57 5 20 48 29 7 41 14 53 60 3 32 63 15 23 57 54 24 57 56 17 30 59 52 26 56 42 7 39 20  66.  1790 : 1300 : 1810 : 1820, : 1830 : 1840 : 1850 : 1860 : 1870 : 1880 : 1890 : 1900 : 1910 ; 1920 3 1930 : 1940 : 1950 : 1960 : 1970 : 1980 J 1990 : 2000 ' 2010 : 2020 ': 2030 : 2040 : 2050 : 2060 :: 2070 :3 2080 :: 2090 :• 2100 ::• 2110 :: 2120 : 2130 ': 2140 ': 2150 ': 2160 :• 2170 .: 2180 :" 2190 : 2200 :• 2210 : 2220 : 2230 : 2240 : 2250 : 2260 : 2270 r, 2280 : 2290 : 2300 : 2310 :< 2320 : 2330 : 2340 : 2350 : 2360 : 2 370 : 2380 : 1  1 52 31 49 26 5 56 7 2 18 60 33 15 58 48 3 24 51 5 3 40 15 57 40 28 59 3 51 32 11 48 18 55 29 14 46 32 24 21 20 29 28 12 40 4 39 26 19 5 35 11 36 28 56 57 37 53 2 51 53  29 3 33 25 44 33  51 29 6 24 2 35 22 7 61 18 29 52 14 6 48 12 34 47 30 63 6 55 49 16 53 22 56 34 39 1 34 48 41 23 34 30 15 62 5 41 35 34 8 39 40 46 31 61 3 39 56 5 54 56  36 4 35 8 59 35 36 33 17 57 3 37 25 12 54 42 30 57 12 7 51 22 9 60 31 58 22 56 60 40 58 27 57 48 2 4 36 7 11 36 47 32 22 1 7 49 52 47 14 49 1 2 32 42 4 50 11 21 59 40  62 5 39 32 3 61 53 10 23 6 4 41 38 15 27 50 31 61 22 20 53 33 13 2 32 7 23 59 16 61 24 29 62 52 20 5 40 31 60 46 57 33 25 6 8 50 59 52 17 51 6 3 33 62 5 51 40 26 14 60  34 7 50 38 22 28 56 12 28 11 7 49 43 25 9 62 33 55 33 27 58 17 19 4 35 12 28 9 26 14 37 33 62 9 30 6 47 37 40 11 2 37 38 29 27 51 13 20 26 53 24 5 37 1 7 54 9 27 17 1  42 8 51 60 42 41 35 22 32 13 8 51 44 30 16 1 34 28 41 29 62 23 52 5 37 2 29 54 27 10 43 36 16 18 31 8 51 61 1 18 3 41 43 34 28 61 16 23 27 56 29 7 41 29 8 61 16 28 20 6  13 14 53 27 50 14 45 38 41 19 21 54 55 14 26 4 35 10 50 31 56 28 I  8 39 41 32 8 40 12 46 38 13 24 49 11  54 12 6 42 4 49 55 47 30 63 40 36 28 59 48 14 50 34 27 14 1 31 23 34  16 26 56 40 62 17 52 44 52 34 28 59 58 20 59 5 37 17 61 32 10 41 16 21 49 10 33 13 60 7 1  50 42 57 53 23 56 43 34 60 7 51 58 48 31 13 60  45 30 63 57 17 51 48 30 20 6 32 36 47  19 27 59 13 50 23 59 55 29 42 30 63 53 31 8 7 39 23 1 36 55 47 6 26 51 17 36 11 13 20 3 51 I  63 21 27 57 58 47 6 8 54 42 2 32 16 1 2 31 18 20 21 53 18 31 36 52 35 45 20  45 30 61 16 26 45 3 58 9 47 32 12 10 39 13 19 48 56 2 38 4 63 11 27 54 53 38 21 9 31 5 54 19 17 37 28 60 2 57 24 21 63 60 3 33 19 6 4 32 62 23 27 54 24 33 46 57 37 46 23  2390 2400 2410 2420 2430 2440 2450 2460 2470 2480 2490 2500 2510 2520 2530 2540 2550 2560 2570 2580 2590 2600 2610 2620 2630 2640 2650 2660 2670 2680 2690 2700 2710 2720 2730 2740 2750 2760 2770 2780 2790 2800 2810 2820 2830 2340 2850 2860 2870 2880 2890 2900 2910 2920 2930 2940 2950 2 960 2970 2980  : : : : : : : : : : : : : : : : : .: :: : : : :: '• : •: : : ': : : :: .: ': ': •: :: : : .: ': : : :: :  36 31 25 20 28 19 26 30 59 57 41 1 5 53 2 61 22 8 42 2 27 62 61 14 30 19 39 5 51 59 1 42 7 63 17 24 29 16 58 37 54 21 11 57 38  :  11  : •: *: : .: ": :: •i ': ': *i :  50 59 22 5 19 19 32 33 4 35 44 47 37 1  :  2 32 38 23 31 47 39 31 60 2 5I 34 8 56 30 15 33 25 48 7 28 16 2 4 31 26 7 8 55 39 3 50 20 2 20 37 32 26 24 30 57 37 23 10 62 18 62 3 55 28 39 34 35 43 7 45 55 60 49 40  4 39 55 36 32 4 1 32 6 3 53 20 14 59 37 63 41 27 49 31 29 26 7 5 34 35 25 22 62 61 4 51 31 30 53 1 33 35 37 39 14 14 27 33 18 21 8 22 19 26 47 47 37 44 8 52 58 2 51 20  5 49 58 2 33 28 2 34 29 7 54 36 26 9 63 39 50 29 51 48 32 35 30 55 36 44 30 27 13 7 5 56 48 31 41 3 40 52 43 1 20 17 28 43 43 54 27 42 35 35 63 60 49 55 30 59 6 4 53 23  8 51 40 3 41 35 6 38 23 17 56 13 27 37 31 4 61 30 58 58 33 44 31 56 38 45 31 29 16 30 8 62 53 49 61 5 50 59 2 4 36 20 32 55 54 9 25 50 44 14 9 2 51 58 33 10 23 8 54 36  14 53 62 5 50 63 8 40 36 21 9 16 30 46 39 5 1 31 60 1 38 52 48  I 51 52 48 33 19 31 27 14 21 15 2 6 51 7 21 5 46 46 36 58 8 59 38 62 5 17 52 4 54 29 51 12 36 17 56 - 46  17 56 1 7 51 15 13 49 11 23 35 19 31 54 7 28 2 32 62 3 40 59 49 3 53 59 53 34 26 48 29 17 24 25 7 11 54 30 41 8 53 53 40 22 25 16 13 4 26 23 57 3 59 34 53 15 11 21 63 .1  27 63 6 14 53 44 16 51 18 32 45 45 35 57 24 47 3 34 12 5 50 41 15 20 58 12 1 38 35 14 33 41 37 58 31 18 57 12 49 27 56 1 51 50 42 26 16 33 39 45 6 21 63 42 56 22 46 28 6 20  28 10 29 17 56 55 25 52 24 33 52 52 39 21 41 55 6 38 41 6 51 63 39 25 13 61 3 42 44 20 34 61 46 10 48 27 62 15 63 34 2 5 54 3 3 27 26 12 50 56 11 28 15 36 13 25 57 30 11 36  30 15 48 27 61 5 27 58 46 37 59 4 51 49 48 12 7 40 61 22 55 39 10 27 16 15 4 50 52 53 36 2 39 14 21 28 9 25 31 51 31 6 56 27 32 40 44 15 61 4 13 30 25 3 19 33 34 32 57 16  68. 2990 3000 3010 3020 3030 3040 3050 3060 3070 3080 3090 3100 3110 3120 3130 3140 3150 3160 3170 3180 3190 3200 3210 3220 3230 3240 3250 3260 3270 3280 3290 3300 3310 3320 3330 3340 3350 3360 3370 3380 3390 3400 3410 3420 3430 3440 3450 3460 3470 3480 3490 3500 3510 3520 3530 3540 3550 3560 3570 3580  : : : : : : : : : : : J : : . : : : ; : : J : ': :: 5 : : :: :: • :: :: : :: • : *: -: : ': : <: : : : : : : : ': : *: : : : : : :  45 27 10 9 26 61 2 51 46 34 19 43 28 35 20 38 53 17 28 60 58 2 10 59 2 33 8 7 52 25 9 18 60 49 12 15 25 9 12 5 56 44 39 50 34 56 57 37 43 2 54 48 33 55 34 45 6 60 53 38  52 31 12 57 27 1 5 53 53 36 35 58 29 44 31 40 30 53 29 30 38 6 17 3 4 34 25 12 55 42 59 54 27 50 22 44 27 37 22 19 10 45 33 61 52 59 36 51 44 4 63 62 35 58 36 52 8 13 10 51  29 33 22 18 31 6 14 56 10 38 44 2 32 52 1 51 49 30 32 31 43 28 23 42 6 35 38 15 58 11 16 27 32 60 33 55 30 43 33 26 55 5 50 17 36 9 46 53 55 8 15 16 50 15 38 59 23 19 58 54  48 35 38 24 33 40 17 59 43 51 45 21 33 59 5 55 63 49 33 39 54 35 36 32 7 41 13 19  I  3 21 26 50 40 62 17 5 31 54 50 39 12 26 61 23 45 37 9 54 58 21 25 52 51 25 51 2 28 35 37 55  62 50 44 29 35 16 26 10 53 54 52 41 38 2 6 56 7 63 34 14 9 37 45 49 12 47 44 29 22 32 27 62 38 35 23 26 34 57 61 47 22 35 4 28 4 46 45 56 6 28 38 3 59 30 55 30 32 45 43 56  3 51 55 48. 37 52 27 38 15 55 59 3 51 17 23 2 24 3 36 20 44 51 46 60 15 51 59 30 38 49 50 11 3 44 28 39 38 4 28 50 33 14 5 41 8 54 52 59 34 30 43 5 61 58 56 49 34 52 46 57  5 53 58 62 50 20 28 44 25 56 7 6 54 53 27 21 41 4 42 53 59 52 53 22 19 52 3 33 18 60 62 21 3 55 41 1 51 15 33 61 50 45 39 47 30 57 3 10 47 32 55 7 12 10 13 63 36 59 1 9  7 56 1 3 51 23 31 55 30 57 24 11 55 10 28 37 2 6 47 10 11 55 56 25 28 55 22 34 43 3 3 32 22 10 4 8 52 55 41 63 61 56 14 63 35 18 7 12 60 37 58 26 22 53 19 17 47 14 5 16  14 59 16 5 54 36 32 58 4 9 37 18 57 58 32 17 7 8 51 15 21 57 8 38 29 58 42 35 54 18 8 40 25 45 19 13 58 5 35 5 26 4 56 13 51 24 33 22 11 49 I  27 38 4 35 53 51 20 27 26  26 61 52 7 59 45 35 37 8 13 12 22 9 14 36 46 41 23 56 25 32 58 13 44 30 63 4 51 8 54 42 49 42 56 35 16 59 39 4 14 35 19 33 19 53 29 35 38 57 51 29 31 44 8 44 4 56 31 36 35  4790 4800 4810 4820 4830 4840 4850 4860 4870 4880 4890 4900 4910 4920 4930 4940 4950 4960 4970 4980 4990 5000 5010 5020 5030 5040 5050 5060 5070 5080 5090 5100 5110 5120 5130 5140 5150 5160 5170 5180 5190 5200 5210 5220 52.30 5 240 5250 5260 5270 5280 5290 5300 5310 5320 5330 5340 5350 5360 5370 5380  : : : -: : : ': ': ': ': ,: : : :: : •: :: ': ': : :: : :: :: :: •: : :: «: :: :: •: : •: .: : •: : : : : •: .: :: : .: ': ': : : : : •: : : : : : :  58 50 3 52 32 11 57 16 59 32 22 57 36 14 52 22 58 8 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  1 51 7 54 36 21 58 26 1 37 24 58 37 16 53 25 10 27 51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 o 0 0 0 0 0 0 0 0 0 0 0 0 0 0  3 61 9 57 33 28 1 27 2 40 29 2 46 20 56 29 36 28 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  5 62 18 59 51 32 5 31 5 51 33 6 51 26 59 30 53 30 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  7 2 24 2 53 37 27 35 6 54 37 11 53 27 3 33 56 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.  27 6 29 6 55 38 31 37 11 57 38 17 54 31 4 34 1 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  29 28 33 10 56 43 40 51 21 3 43 21 56 35 7 33 2 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  31 32 35 17 53 51 1 52 27 7 51 23 57 36 3 42 4 39 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0  33 40 37 • 23 2 54 5 54 28 12 54 28 1 45 12 51 5 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  48 41 51 28 6 55 9 57 31 18 55 32 5 51 15 55 6 47 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  •o  . 0  6590 6600 6610 6620 6630 6640 6650 6660 6670 6680 6690 6700 6710 6720 6730 6740 6750 6760 6770 6780 6790 6800 6810 6820 6830 6840 6850 6860 6870 6880 6890 6900 6910 6920 6930 6940 6950 6960 6970 6980 6990 7000 7010 7020 7030  : : • i ': ': '' : •: : : ': •: :: : :: :: : : :: :: :: :: :: ': :i :: : ": :: : :i .: : : : <: : :: •: : : : :  7040. : 7050 :  7060 7070 7080 7090 7100 7110 7120 7130 7140 7150 7160 7170 7180  983 983 0  1 2  0  1  983 983 0 983 983  0  0 1722 0 0 0 1722 0 983 ' 983 0 983 983 0 820 0 820 0 820 1789 1789 2161 820 1789 820 2161 820 0 820 0 820 0. 1789 1789 820 1789 1789 2161 820 0  0 1  0 0 0  0 983  0 0  : : : : : : : :  0 0 0 0 0 0 0 0  :  0  : :  0 0  :  0  :  0  0 0  0 0  0  I  0 2 1 0 1 2  0  I  0 1 0 2  I  2 2 4 1 4 2 1 0 2  0 1 0 2 1 4 1 2 2 4 0 0  0 0 1722 0 0 983 983 0 983 983 820 0 820 0 820 0 1789 1789 820 1789 1789 2161 820 0 820 0 820 0 820 1789 1789 2161 1789 1789 820 0  0 0 0  0 0 0  0 0  0  0  0 0 0  0 0 0 0 0 0 0  0 0 0 0  0 0 0 0 0 0  2 1 0 1 2 0 0 0 0 0 1 0 0 1 2 0 2 1 1 0 2 0 1 0 2  I  4  1 2 2 4 0 2 0 1 0 2 1 2 2 2 1 4 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0  983 983 0 983 983 0 0 1722  1 2 0 2 1 0 0 1  0  0  0 0 0 0 983 0 0 983 983 0 820 0 820 0 820 1789 1789 2161 1789 1789 820 0 820 0 820 0 820 0 1789 2161 820 1789 1789 2161 0 0  0 0 0 0 2 0 0 1 2 0 2 .0 1 0 2 1 2 2 2 1 4 0  0 0 0 0 0 0 0 0 0 0 0  0 0  0 0  1 0 2 0 2 0 2 2 4 1 2 2 0 0 0  0 0 0  0 0 0 0  0 0 0 0  0 0  0  983 0 0 983 983 0 1722 0 0 0 1722 0 0 983 0 0 983 0 820 0 820 0 820 0 1789 2161 820 1789 1789 2161 820 0 820 0 820 0 820 1 789 820 2161 1789 2161 820 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  2 0 0 1 2 0  1 0 0 0 1 0 0 1 0 0 2 0  1 0 2 0 2 0 2 2 4  1 2 2 1 0 2 0 1 0 2 1 4 2 2 2 4 0 0 0  0 0 0 0 0 . 0 0 0 0 0 0 0 0 0  983 0 0 983 0 0 0 1722 0 1722 0 0 983 983 0 0 983 820 0 820 0 820 0 820 1789 820 2161 1789 2161 820 0 820 0 820 0 820 1789 1789 2161 820 1789 820 2161 0 0  0'  C 0 C 0 0 0 0 0 0 0 0 0 .0 0  1 0 0 2 0 0 0 1 0 1 0 0 1 2 0 0 1 1 0 2 0 1 0 2 1 4 2 2 2 4 0 1 0 1 0 2 1 2 2 4 1 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  7L90 : 7200 : 7210 : 7220 : 7230 : 7240 : 7250 : 7260 : 7270 : 7280 : 7290 : 7300 : 7310 : 7320 : 7330 : 7340 : 7350 : 7360 .: 7370 : 7380 : 7390 -: 7400 ': 7410 :: 7420 .: 7430 :: 7440 . 7450 ': 7460 : 7470 :: 7480 : 7490 :: 7500 :: 7510 ': 7520 :: 7530 :: 7540 :: 7550 .: 7560 i: 7570 :: 7580 : 7590 : 7600 : 7610 : 7620 : 7630 : 7640' ' 7650 : 7660 : 7670 : 7680 : 7690 3 7700 : 7710 : 7720 : 7730 : 7740 : 7750 : 7760 : 7770 : 7780 :  0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 o  0 0 0 0 0 0 0 0 0 0 0 0 567 567 0 0 0 754 1585 1585 754 754 0 499 499 2078 2173 2173 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0  0 0 0 0 0 0  0 0 0 0 0 0 0 0 0  0 1 1 0 0 0  2 1 1 4 4 0 1 2 2 2 2  0  0 0  2185 2219 567 499  2 2 3 6  0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0  0 0 0 0 0 0 0 411 567 0 0 0 0 754 1585 567 754 0 0 499 499 2078 2173 2078 0 2185 2185 567 567 2185  0  0 0 0  0  0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0  0 0 0 0 0  0 0  0 0  0 0 1 1  0 0 0 0 I  1 2 4 0 0 2 2 1 2 4 0 2 2 3 3 4  0 0 0  0 0 0  0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 411 411 0 0 411 0 754 754 567 567 1585 0 0 499 2078 2078 2078 2078 0 2185 499 567 2185 2185  0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0  0 0 0 0 0 0 •0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0  0  0 0 0  0 0 0  0  0 0 0 0 0  0  0  0  0 0 0  0 1  1 0 0 2 0 I  1 2 2 2 0 0 2 1  1 4 4 0 2 3 3 4 4  0 0 0  71. 0 0 0  0  0  0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0.  0 411 411  0 0 0 1 0 0 2 2  0  0  0 411 0  754 754 567 1585 1585 0  0 499 2 078 2078 2078 0  0 499 499 2219 2185 499  1  2 2 2 2 0 0 1 1  2 4 0 0 3 3 2 4 6  0 0  0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0  0 0  0  0 0  0 0 0 0 0 0 0 0 0 0  0 0 0 567 411 0 0  754 754 1585 1585 754 0 499 499 2078 2078 2173 0 0 499 2219 2219 499 499  0 0  0 0 0 0 0 0 0 0  0 0 1  2 0 0 2 2 1  2 4 0 1 1 2 2 2 0 0 3 2 2 6 6  72. 11390 11400 11410 11420 11430 11440 11450 11460 11470 11480 11490 11500 11510 11520 11530 11540 11550 11560 11570 11580 11590 11600 11610 11620 11630 11640 11650 11660 11670 11680 11690 11700 11710 11720 11730 11740 11750 11760 11770 11780 11790 11800 11810 11820 11830 11840 11850 11860 11870 11880 11890 11900 11910 11920 11930 11940 11950 11960 11970 11980  : : •: : •: .: : : : : : ': : •: : .: ": ': .: :: : : ': ': -: .: •: •: : :: : :. :: «: : :: : *' :. •: : : : *: : . : .: ': .: ' : : ' '. • '' ' :  0 0 1058 1058 0 1839 903 1839 1839 2827 1839 903 0 0 1058 1058 0 0 1839 903 2827 1839 903 1839 0 1471 2064 3192 3251 362 1019 117 3288 3274 3219 3251 3274 1270 1270 3619 3629 1821 2064 1019 1471 2839 117 3219 4125 3274 3653 3653 1099 2353 2853 1933 3672 2827 3288 1652  0  0 1 2 0  1 4 2  1 2 2  4 0  0 2  1 0  0 2 4 2  1 4 2  0 1 3 6 3 2  9 2  3 6  5  9 9 1 4 6  4 6  10 14 4 6 12 3  10 14 4 6  4 2  9 8  4 6  10 14  0 105 8 1058 0 0 1839 903 2827 1839 90 3 1839 0 0 1058 1058 0 0 1058 1839 1839 2827 1839 903 2827 0 1652 2064 362 3251 2064 1019 3274 3288 1652 3219 3298 3274 1270 1270 4116 3629 3629 2064 2339 1471  0 2 1 0 0 2 4 2 1 4 2 0 0 1 2 0 0 2 2 1 2 2 4 2 0 3 3 1 3 5 9 3 3 9 5 5 9 2 4 6 4 9 10 2 4  2339  3  117 4107 4125 117 3653 1933 1099 4135 2853 362 3672 903 3288 4149  12 9 10 18 4 2 4 6 9 6 4 10 10 6  1058 1058 0 0 1058 1839 1839 2827 1839 903 2827 0 1058 1058 0 0 1058 1058 2827 1839 903 1839 1839 2827 2064 1652 3192 362 3251 2064 117 3274 3288 1652 4107 3298 754 1270 3619 4116 3629 3629 4415 2839 117 2839 4125 4107 499 117 1099 1933 3653 4135 362 362 4425 903 2827 4149  1 2 0 0 2 2 I 2 2 4 2 0 2 1 0 0 1 2 2 1 4 2 1 2 1 3 3 1 6 5 1 3 5 9 6 5 13 2 4 6 6 9 10 2 6 8  6 9 13 13 2 2 9 6 3 6 7 10 9 6  1058 0 0 1053 1058 2827 1839 903 1839 1839 2827 1058 1058 0 0 1058 1058 1839 2827 1839 903 2827 1839 903 2064 1933 3192 3219 3251 1019 117 165 2 3288 3 298 4107 754 754 1471 3619 3 192 3629 4415 4415 117 117 4116 4125 3219 499 1099 1099 1933 3653 2853 362 362 4425 3672 2827 4135  1 0 0 0 0 1058 1058 I 2 1839 2 2827 1839 1 4 903 2827 2 1839 L 903 2 1053 1 0 2 0 0 0 1058 2 1058 0 1 1839 1 2 903 1839 2 1839 4 2827 2 1839 1 4 903 1471 1 1 1933 3 3192 3219 3 6 362 1019 5 117 I 5 1652 5 3274 3 3298 6 3251 8 754 1270 13 1471 2 4 3619 9 3192 6 1821 7 4415 1019 10 117 3 6 2839 9 4116 3219 6 3219 12 13 | 3 2 7 4 1099 I 3653 2 6 1933 9 2853 4 2853 1933 3 12 362 7 2827 6 3672 9 1652 10 4135  0 0 2 1 1 2 2 4 2 1 4 1 0 0 1 2 0 1 4 2 1 2 2 4 1 1 6 3 2 5 2 5 6 3 9 8 1 2 6 9 6 7 14 3 6 9 8 12 14 1 6 6 2 4 8 12 6 6 14 10  11990 12000 12010 12020 12030 12040 12050 12060 12070 12080 12090 12100 12110 12120 12130 12140 12150 12160 12170 12180 12190 12200 12210 12220 12230 12240 12250 12260 12270 12280 12290 12300 12310 12320 12330 12340 12350 12360 12370 12380 12390 12400 12410 12420 12430 12440 12450 12460 12470 12480 12490 12500 12510 12520 12530 12540 12550 12560 12570 12580  4149 3298 362 4158 4182 1099 4205 1821 1099 4232 903 2839 423 2 3312 499 117 1965 1997 3325 1691 170 1997 1356 3325 3682 170 2867 170 1117 1965 1117 3692 3711 4432 2441 1306 3376 3682 1356 170 4270 3389 1058 3403 3415 2613 4280 1058 4442 3735 4242 3403 4306 1503 2881 223 223 4316 2441 2831  9 8 18 6  6 S  10 13 12 o  12 14 10 13 19 24 1 1 3 5 1 5 2 9 4 3 9 6 1 6 2 9 6 7 9 8 3 10 8 18 10 3 5 6 3 8 6  13 7 6 10 12 6  13 4 12 3 10 12 14  4149 193 3 362 3312 4182 1270 4206 4182 1099 4153 903 1471 4232 1821 499 0 1997 1356 3325 3366 170 3338 1306 1306 3682 1356 170 2867 3692 1117 3692 3711 3711 2441 1691 4261 4252 1117 1306 4270 1997 3403 1058 223 3415 3338 3403 3735 3389 1839 3389 3366 3415 2867 2881 2881 1965 4326 223 2542  9 13 18 6 13 10 9 12 9 12 13 10 18 19 0 3 1 6 3 2 6 4 1 6 4 12 6 4 4 6 4 10 6 14 6 6 8 12 6 14 3 9 2 5 9 9 4 10 6 14 10 8 14 9 2 8 9 18 8  2853 1933 3312 331.2 3619 1270 1821 4182 1019 4158 3672 1471 4135 1821 1099 . 1997 3325 1691 170 1997 3338 1691 3682 1306 4242 170 2867 1997 1117 3692 1965 4432 2441 4432 3376 3682 3376 3325 4270 4252 1356 3403 223 . 3389 4280 1058 3366 3735 4242 3735 4306 1503 4280 1053 223 4316 223 2881 4326 611  14 13 3 4 10 13 8 9 18 9 10 13 14 18 18 1 3 3 1  5 3 9 4 2 6 6 2 8 2 9 2 7 9 10  3 10 4 13 10 9 13 6 1 5 6 13 5 6 10 9 6 13 9 18 3 6 6 14 6 13  2853 2827 3312 1270 3619 4206 1821 2064 1019 1471 3672 90 3 4135 3298 1099 1356 3325 1965 170 3338 1691 1306 3682 1356 3325 2867 170 2867 3692 1117 1965 2441 1691 3711 4252 1117 1306 4270 1997 1356 170 223 3 389 1053 3403 3415 2618 1839 3389 4442 3415 2867 3403 2881 1965 2081 22 3 2542 4316 2441  14 12 3 8 10 6 8 14 18 3 10 18 14 14 18 1 6 1 2 6 5 1 6 2 9 6 3 9 6 1 6 6 14 6 6 8 8 6 14 8 18 2 3 5 9 3 8 • 6 14 7 8 14 12 2 8 4 12 8 10 12  3298 2827 4153 1270 1099 4206 1821 2064 4232 1471 2839 903 3312 3298 117 1691 0 1997 3338 1691 3366 1306 4242 1306 2867 1997 1356 170 1965 3692 1117 4432 3711 3711 3376 3325 4261 4252 1356 1306 223 3389 3403 1058 3366 3415 3333 3735 3735 3389 4280 1058 3366 4316 223 2881 4326 611 4326 223  8 12 6 8 8 6 13 14 6 8 14 18 13 14 24 3 0 3 3 9 3 2 6 4 2 8 4 12 2 4 4 10 4 10 4 13 6 9 13 12 1 5 3 9 5 5 9 9 4 10 9 18 10 6 6 9 6 13 9 18  12590 12600 12610 12620 12630 12640 12650 12660 12670 12680 12690 12700 12710 12720 12730 12740 12750 12760 12770 12780 12790 12800 12810 12820 12830 12840 12850 12860 12870 12880 12890 12900 12910 12920 12930 12940 12950 12960 12970 12980 12990 13000 13010 13020 13030 13040 13050 13060 13070 13080 13090 13100 13110 13120 13130 13140 13150 13160  4335 1965 1839 1117 2542 3415 1356 1852 3782 4470 4566 3523 4014 3825 4505 3448 4626 4935 3908 754 4526 4903 3192 3544 3475 1621 3846 1852 3097 3158 3219 272 3865 4692 4858 3568 4077 2780 33 3 8 2987 4363 2084 4280 1058 1439 3997 4526 235 3 4956 2383 2011 223 2578 2289 903 567 1535 6 4  6 14 8 18 14 14 18 8 4 13 10 21 14 8 14 19 10 21 21 36 8 16 19 24 18 31 13 26 23 24 32 39 5 14' 14 27 15 19 28 24 18 31 26 41 32 17 19 30 19 32 32 49 24 34 39 44 36 53  4335 1117 1839 4306 611 3376 170 3763 3782 4761 3429 4491 3070 4505 1852 4387 2926 3251 1156 3846 4825 466 3 3192 4774 2954 2895 3846 3929 983 3884 715 2185 4692 4713 4545 4727 2618 3976 1234 3595 4053 1652 1789 2323 1195 4746 3042 4839 2 383 2441 942 4792 1965 2734 518 2542 820 117  10 12 13 10 19 13 24 4 8 13 14 8 19 8 19 16 13 23 26 5 14 14 27 18 24 31 19 17 30 24 39 34 10 14 21 10 21 21 36 18 24 31 32 24 39 15 28 19 26 32 41 19 32 32 49 36 44 53  1839 1117 4261 3415 1356 1306 1852 3763 4449 3763 4581 3782 4014 1852 4612 3825 4566 2926 4626 4649 3744 4449 4774 3711 2895 1400 4597 2473 3097 790 2185 321 4713 4692 3865 3810 3338 2501 4792 3595 3018 1652 2648 2323 362 3042 4872 2799 4206 223 864 2415 2578 674 2219 455 411 1  8 18 9 14 18 18 1 8 8 19 10 12 21 12 10 21 15 23 23 10 12 21 13 24 24 39 15 23 28 30 26 41 10 21 12 15 23 28 13 24 24 39 26 30 41 23 15 28 26 41 30 26 30 41 29 44 44 63  1839 4335 1965 3376 170 2542 1352 3744 4449 3810 3 523 4491 3070 4597 4612 4505 2926 4626 3782 3 846 3692 4839 3544 3629 1400 4677 2043 3 929 983 3950 1324 1878 4919 4545 3568 3976 2618 3865 4397 3499 1722 4727 1503 1933 362 4526 2799 1270 2 255 4182 864 4158 1117 1471 1753 1356 i '0  13 6 14 13 24 14 4 8 13 5 14 14 27 10 14 21 19 15 28 8 19 14 18 24 31 10 21 21 36 26 32 41 16 8 19 17 30 19 18 24 31 19 32 32 49 13 23 26 34 24 39 24 39 32 36 44 53 0  4261 4335 1117 1306 4306 611 3744 3763 4470 3810 4581 3429 3825 3825 4811 3448 4935 3782 754 4649 4663 4470 4345 1691 3475 4677 3744 2473 3950 715 1878 272 3865 4545 3653 2501 2780 1234 3499 2987 4363 2682 2648 1156 4746 3125 2353 1270 4077 2129 1019 1535 2734 518 2219 170 630 0  9 10 12 13 10 19 4 13 8 8 16 19 5 14 14 27 17 19 30 14 10 21 18 31 24 15 19 28 19 32 32 49 8 14 19 23 13 26 18 31 24 24 34 39 10 21 21 36 24 32 39 32 26 41 36 53 44 0  75.  20  21 90 50 70 80  10 14  300  200  100  IMPLICIT I N T E G E R S (A-Z) DIMENSION A ( 4 0 2 0 ) , E ( 3 6 , 4 7 8 ) DO 2 0 1=1,36 DO 20 J = l , 4 7 8 EI I , J ) = 0 DO 21 1 = 1 , 4 0 0 8 , 1 2 K=I+ll READ ( 4 , 1 2 1 2 , E N D = 9 0 ) I A U ) , J = I , K ) 1=1 1=1+1 IF (1-473) 70,70,10 J=A(I> I F ( J . L E . O ) GO TO 50 Q=A(J)-9 R=I+2 E(Q,R)=A(J+1) J=J+2 IF ( A ( J ) ) 50,50,80 READ < 5 , 1 4 , E N D = 1 0 0 0 ) 8,C,D FORMAT ( 3 1 4 ) I F ( B . L T . 4 9 ) GO TO 1 C 0 0 I F ( 8 . G T . 5 2 0 ) GO TO 1000 I F ( C . L T . 1 0 ) GO TO 1 0 0 0 I F ( C . G T . 4 6 ) GO TO 1 0 0 0 G=C-9 B=B-45 IF (D-2) 100,200,300 E(G,8)=E(G,8)-2 E(G,B-1)=E(G,B-1)-1 E(G,B+1)=E(G,B+1)-1 GO TO 10 E(G,B-3)=E(G,B-3)+l E(G,B-2)=E(G,B-2)+2 E(G,B-l)=E(G,B-l)+3 E(G,B+l)=E(G,B+l)+3 E(G,B+2)=E(G,B+2)+2 E(G,B+3)=E{G,8+3)+l E(G,B)=E(G,B)+4 GO TO 10 E(G,B-3)=E(G,B-3)-l E(G,B-2)=E(G,B-2)-2 E{G,B-l)=E(G,B-l>-4 E(G,B+l)=E(G,B+l)-4 ElG,B+2)=E(G,B+2)-2  E(G,B+3)=E(G,B+3)-l E(G,B)=£{G,B)-3 1000  1010  1015 1020 1030  GO TO 10 1=4 J=2 K = 474 A{2)=0 L=0 L=L+1 IF ( L . G T . 3 6 ) GO TO 1 1 0 0 IF ( E ( L , I ) ) 1015,1010,1015 IF ( A ( J ) ) 1030,1020,1030 AU) =K A(K)=L+9 A(K+1)=E(L,I)  (C)  ROUTINE THAT BUILDS AND UPDATES THE MOVE EVALUATION TABLES  1100 1110 1120  1200 1210 1212 1215  K=K+2 GO TO 1 0 1 0 IF ( A ( K - l ) ) 1110,1120,1110 A(K)=0 K = K+1 I F ( J . G T . 4 - 7 2 ) GO TO 1200 1=1+1 J=J +1 L=0 A { J) = 0 GO TO 1 0 1 0 A(1)=K WRITE ( 6 , 1 2 1 2 ) A FORMAT (1216) WRITE ( 7 , 1 2 1 5 ) A ( l ) FORMAT ( 1 6 H ARRAY S I Z E NOW STOP END  (D)  1 2 3 4 5  6 7 3 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59  3436 603 735 839 937 1065 1201 1303 1385 1461 1537 1637 1727 1835 1931 2053 2093 2165 2216 2302 2368 2414 0 2538 2630 2677 2753 0 2822 2886 2936 0 3008 3029 3053 3083 0 0 3148 0 3182 3214 3268 0 3300 3336 3390 3419 -4 16 -6 10 17 -3 12 0 -3 12 17  474 616 744 852 946 1084 1212 1312 1394 1470 1548 1644 1736 1842 1942 2060 2100 2174 2223 2311 2375 2419 2500 2545 2639 2632 2762 2795 2825 2893 2943 2961 0 3032 3056 3086 3114 0 3151 0 3135 3219 0 0 3303 3 3 43 3395 3424 18 -8 15 -2 -4 15 -10 10 16 -2 -4  THE MOVE EVALUATION LISTS  485 627 753 865 957 1105 1225 1321 1405 1479 1561 1649 1747 1849 1957 2065 2107 2183 2230 2320 2380 2428 2505 2552 2644 2687 2771 2798 2828 2896 2950 2964 0 0 3059 3089 3117 0 3156 0 3190 3226 0 0 3306 3352 0 3431 -8 18 -3 12 18 -11 14 -5 -4 13 19  496 638 764 880 968 1124 1236 1330 1416 1484 1572 1654 1760 1860 1974 2068 2114 2192 2239 2327 2383 2437 2510 2559 2649 2692 2776 2801 2833 2901 2955 2969 0 0 3062 0 3122 0 3161 0 3197 3229 3273 0 0 3355 0 12 0 -4 16 -10 -1 16 -4 12 17 -2 -2  511 649 773 891 981 1141 12 47 1337 1423 1487 1585 1663 1773 1871 1989 2073 2119 2197 2248 2334 2386 2448 2515 2566 2654 2699 2781 2806 2838 2908 2958 2974 0 0 3065 0 3127 0 3166 "0 3204 3232 3276 3291 0 3353 0 -1 12 0 -5 14 0 -5 15 -5 -8 14 0  526 664 780 902 994 1154 1258 1344 1428 1490 1594 1672 1786 1882 2004 2076 ' 2124 2200 2259 2341 2391 2461 2520 2577 2659 2706 0 2311 2845 2915 0 2983 0 0 3068 0 0 0 3171 0 0 32 3 7 3279 3294 33 0 9 3361 3400 14 -2 10 17 -4 10 17  -6 13 19 -4 10  539 683 787 909 1007 1167 12 6 9 1353 14 3 7 1495 1505 1681 1797 1893 2015 2079 2129 2203 2270 2348 2396 2472 2525 2590 2664 2715 0 2816 2854 2918 0 2990 3011 3035 3071 3092 0 3139 0 0 0 3242 3282 3297 3314 3366 3403 -12 14 _  i -A.  -2 15 -4 -8 16 -1 -1 15 -5  552 700 798 . 916 1020 1176 1280 1362 1444 1504 1616 1694 1808 1904 2026 2082 2138 0 2279 2353 2401 2433 2530 2601 0 2726 2786 2319 2863 2921 0 29 9 7 3014 3038 3074 3095 3130 3142 0 0 0 3249 3285 0 3319 3373 3406 15 -12 12 18 -10 12 0 -8 14 0 -1 12  569 713 811 923 1035 1185 1289 1371 1451 1515 1625 1707 1819 1913 2037 2085 2147 2206 2286 2358 2404 2492 0 2610 2667 2735 2789 0 2870 2924 0 3002 3019 3043 3077 3102 3133 3145 0 3176 0 3256 3288 0 33 24 3380 3409 2 15 -5 -2 16 -8 10 17 -8 10 16 -1  586 724 826 930 1050 1192 1296 1378 1456 1526 1630 1718 1328 1922 2046 2088 2156 2209 2293 2363 2409 2497 2535 2619 2672 2746 2792 0 2879 2929 0 3005 3024 3048 3080 3109 3136 0 0 3179 3209 3263 0 0 3329 3385 3414 16 1 14 0 -4 14 -8 -16 15 -4 -2 13  60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119  -4 -1 19 -2 18 -2 1.3 20 4 1 17 -2 4 22 -5 22 4 22 1 -8 16 -2 10 17 -8 14 0 -4 15 -2 10 0 15 -4 -6 16 -3 16 -8 12 25 -2 15 -1 1 22 -4 4 20 31 -2 6 20 31 -6 13 24 -2 21 1  14 0 -9 19 -4 18 -2 -2 17 0 1 13 0 6 22 6 0 2 0 16 -10 16 -1 -2 16 -4 13 21 -1 13 -4 10 -8 0 16 -3 23 -4 15 -2 4 23 -3 12 31 1 12 31 -1 -4 20 31 -3 -1 21 -8 2 22 -1 22  -2 10 20 -6. 19 -8 14 0 1 10 18 -4 10 0 6 0 10 0 10 -8 20 -5 13 21 -1 15 -8 2 16 -2 13 -8 16 10 -4  23 -8 23 -10 13 0 -2 16 -4 -2 23 -1 -8 21 0 -2 -2 21 0 -8 18 0 6 22 2  16 -8 -2 20 -6 19 1 10 18 . -4  -1 14 -1 13 0 16 -1 10 -4 20 2 17 -1 3 17 -4 14 0 -4 14 -1 15 -3 -1 23 -4 25 -16 16 -4 12 25 -1 15 0 2 15 0 -I  10 21 0 -4 10 22 -4 13 24 4 0  -1 13 0 -4  20 -9 16 -8 -2 13 19 4 13 -1 14 -1 16 -2 16 3 21 -1 14 0 -4 16 -8 10 17 -2 14 -4 0 15 -2 0 1 25 -8 15 -4 3 25 -4 10 24 -4 10 22 -4 -2 10 22 -1 7 20 -4 1 0 20  17 -8 10 0 -8 20 2 13 19 -8 -1 16 -2 14 I  17 -2 16 -10 0 1 20 -1 13 21 -1 15 -1 -2 16 -1 16 10 -9 0 13 0 2 23 -5 13 0 2 23 -2 2 22 -8 -1 13 22 -2 5 13 23 -1 18 0 13 -7  -2 14 -4 10. 0 -4 18 -4 -2 14 22 8 14 2 16 -1 17 -5 20 10 0 1 ! 15 -2 4 17 -2 13 21 -8 15 -3 -2 16 13 -2 13 0  -3 16 -2 12 31 1 12 31 1 15 23 -1 4 13 23 -4 1 21 -2 13 -1 21  19 -1 13 -3 10 0 -4 14 20 3 2 17 3 16 2 20 -1 20 4 -4 10 21 -4 14 0 -8 16 -4 1 17 -2 0 15 -8 -1 15 -4 12 25 -4 15 -8 -1 24 -2 -4  23 -2 4 15 23 -2 2 18 24 -4 20 -2 20 2  78. -4 18 -4 13 -3 10 19 2 -I  16 0 1 16 4 17 1 20 3 0 15 -2 2 16 -2 13 21 -2 14 0 -1 16 10 -16 0 15 -10 15 -1 3 23 -3 13 0 1 15 0 3 18 24 - i  3 18 24 -8 4 22 I  18 -2 22  20 -1 18 -2 13 -4 -4 1622 6 10 22 6 17 -2 22 2 22 10 -I  15 0  -2 15 -4 3 17 -4 10 0  -4 -4 16 15 -7 16 -8 13 0  -4 16 -1 10 25 -8 10 24 -1 6 18 24 -4 6 20 0  9 21 -1 21 1  .12 0 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179  0 20 0 -4 23 -1 20 -4 15 1 21 1 0 14 -16 17 -1 0 15 -1 32 2 23 -4 -1 27 20 18 -2 28 -1 26 -2 26 4 21 -4 19 0 3 28 -2 24 -1 1 27 30 4 0 19 30 -5 23 -8 23 -12 23 -3 3 29  20 -2 12 26 -8 22 -1 20 -8 15 -1 0 14 -8 15 -2 0 15 -1 23 -1 32 1 0 20 2 4 -1 20 -1 18 -1 32 -1 24 3 21 -8 19 32 4 28 -1 28 20 1 JL  2 0 20 -1 6 30 -5 23 -12 29 -6 24 0 4  -4 21 1 -2 26 2 21 -4 20 -5 23 14 -4 15 -3 0 14 -2 16 4 0 -2 32 17 1 0 27 20 1 0 -2 0  I  32 3 24 1 21 -3  I  0 3 28  I  -3 0 0 20 3 20 0 4 30 -7 31 1 25 1 23 31  21 4 20 0 -1 23 -4 21 -1 21 2 -2 15 -3 17 14 -2 16 -2 0 16 0 -1 -8 27 17 4 2 27 18 0 13 0 2 32 3 24 -1 20 0 19 0 2 0 25 20 20 4 23 2 19 31 2 31 4 31 1 25 -1 3  3 22 -1 12 0 -3 22 -8 21 -2 0 . 15 -4 17 -4 -4 15 -1 23 16 -4 16 0 19 1 -1 0 27 1 -8 13 -4 13 0 3 32  I  24 1 20 2 19 0 19 -2 -3 2 23 -4 22 -2 1 31 3 0 3 29 2 24 0  22 3 21 2 12 0 I 23 -4 23 15 -8 17 -8 0 15-... -4 "°21 3 -8 17 -2 16 -2 0 20 20 2 28 0 -2 21 -8 13 0 4 28 -2 21 2 20 4 19 2 0 27 23 -2 27 -1 20 0 2 0 19 0 2 27 , 2 24  2 23 3 21 3 12 0 2 23 3 -5 17 -4 22 14 -8 21 -1 0 19 -1 17 -1 0 17 3 3 28 -2 18 18 2 21 -4 13 0 1 28 -4 21 3 20 3 25 20 2 -1 27 2 23 1 19 0 19 -2 19 31 1 25 3  23 -2 22 1 15 4 12 0 4 0 17 -2 22 -1 -8 17 -2 23 16 -2 19 -2 17 17 -2 27 27 -1 0 -4 -1 24 3 19 -2 13 32 2 24 -8 21 4 20 -1 -8 0 27 3 30 -8 22 -4 19 -4 22 -1 3 29 4 25  -1 26 4 22 -1 15 3 12 0 15 -1 22 -4 0 15 -1 23 2 -4 23 -4 19 -4 -4 20 3 3 0 18 0 21 1 24 -1 19 -1 3 32 -7 24 -4 21 2 0 25 27 4 30 8 27 -2 22 -8 22 -2 22 0 3 27 6  0 -1 23 3 21 -2 15 2 12 -4 23 -1 0 14 -4 21 1 0 19 3 23 -8 19 19 2 0 0 18 -4 13 1 26 2 21 -2 19 0 2 28 -4 24 -2 21 19 -I 3 30 6 0 1 23 -4 22 -4 23 -1 23 31 2 27  180 131 182 183 184 185 185 187 183 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 223 229 230 231 232 233 234 235 2 36 237 238 239  3 27 6 25 2 0 18 -8 15 0 4 27 3 0 16 0 -1 22 31 -4 22 31 5 26 -1 30 -2 -4 -1 0 -1 3 28 25 25 -1 26 -8 30 2 0 1 27 2 4  27  2 27 -1 28 4 0 22 4 28 22 3 3 -2 3  29 4 27 4 27 15 -4 18 -4 15 0 3 0 16 -4 16 27 -2 2 26 -8 -1 31 5 26 -1 0 26 0 31 0 25 -1 3 1 26 -4 30 3 0 23 0 1  0 27 3 28 1 28 -5 0 22 *3 23 -1 1  0 0 30 0  3 29 3 27 1 -2 19 -8 18 -2 15 0 16 -2 21 -8 3 23 0 2 23 0 -6 31 5 31 17 1 31 -4 21 2 0 0 26 -2 30 4 0 23 3 22 28 20 4 28 -1 . 28 -9 40 22 2 23 -7 0 23 23 25 1 21  31 2 29 2 0 18 2 19 -4 18 -1 19 -1 20 3 21 31 3 16 27 3 22 0 -3 31 -1 -8 0 -2 0 2 28 21 21 -1 30 3 0 23 4 24  1 1 3 28  2 31 -5 32 3 1 23 -4 28 22 3 -1 0 4  4 31 1 31 15 -2 20 3 19 -2 18 1 20 1 23 2 2 24 -2 -1 24 -4 22 0 -2 0 26 17 0 31 25 -2 1 -7 30 2 0 23 3 24 -1 0 0 27 4 31 -1 32 -1 0 23 -2 28 -2 2 30 30 30 21 0  0 3 31 i -1 19 -1 20 4 19 -1 20 1 21 1 22 0 -2 22 31 -8 23 -2 17 0 17 2 -2 31 -2 1 0 25 25 1 0 23 2 24 -2 0 22 20 3 31  -2  32 -2 40 25 -1 28 -4 0 23  2 4 2 2 21  24 0 2 0 18 1 27 -1 20 3 19 1 21 4 27 -1 16 26 -4 2 26 2 23 -1 17 -4 30 0 -4 0 28 21 4 2 0 21  1  24 -4 26 23 1 2 28 -I 0 -1 40 2 -1 28 -8 40 22 1 0 0 0 25 3  4 24 0 24 -1 0 1 27 -2 20 2 21 3 27 4 23 -4 1 23 0 3 24 1 22 -2 26  -1 17 0 21 -I 3 0 0 21 -1 24 -8 26 -1 2 0 27 3 0 20  0 1 0 28 -5 40 I 3 30 23 23 21 -1 29  25 3 24 1 25 15 0 2 27 -5 21 2 27 3 31 2 21 27 4 16 27 -4 24 -1 26 3 0 -1 31 1 0 25 21 21 -2 24 -4 26 -2 30 0 20 2 0 20 2 20 0 25 -4 40 2 0 23 I 3 1 1 0 -1  6 25 2 25 1 -4 15 0 3 27 1 27 3 0 I 24 1 1 24 -1 -1 26 -2 24 5 30 17 31 -8 31 21 3 -2 -4 24 -2 26 -4 30 1 23 1 28 20 3 27 1 25 -2 40 3 0 22 -2 0 30 30 25 21 0  240 241 242 243 244 245 246 247 248 2 49 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 236 287 288 2 89 290 291 292 293 294 295 2 96 297 298 299  21 31 31 27 2 27 -1 22 0 -1 0 -1 -4 -4 -1 2 0 25 2 25 3 22 3 24 1 43 43 31 0 0 0 27 -1 29 -4 30 3 0 28 28 0 21 21 0 1 3 32 -2 -1 26 -1 25 -1 26 31 -2 1 39 39 -1  2 -1 -1  L 30 3 27 3 22 0 22 27 27 27 27 27 24 3 27 1 24 4 27 -1 24 -1 -1 -2 27 27 27 1 31 -2 31 1 0 23 -2 -1 32 -1 -1 29 0 30 -1 0 26 2 0 -2 35 2 2 0 31 1 3 0  29 0 0 30 2 30 4 27 4 22 2 -1 -4 -4 -1 1 3 27 3 27 1 28 -1 27 -3 0 0 0 2 4 2 23 1 31 3 31 23 1 30 30 -1 31 31 .1 29 3 0 26 3 28 25 30 -2 0 39 26 3 0 0 25  -2 26 26 1 32 3 30 3 27 3 32 0 0 0 0 0 25 4 30 2 27 -1 28 -2 27 24 24 31 28 29 28 -2 0 2 0 4 2 28 3 1 0 3 3 0 4 0 26 4 28 -2 -8 -2 0 26 -1 2 0 26 25 2  0 -1 -4 32 -3 32 4 30 2 27 1 24 24 24 25 24 4 0 1 29 1 29 -2 28 -1 -9 -2 -1 -2 -1 -1 0 23 0 23 0 28 -2 0 0 31 0 0 29 30 26 3 30 -1 0 0 35 35 3 0 31 31 -1 1 39  21 31 32  -2. 0  —Q 32 3 30 1 0  -2 -8 -2 1 2 27 22 0 -1 29 -1 30 -1 30 43 31 0 0 0 29 23 2 23 4 23 -1 30 28 32 1 21 31 2 2  2  29 2 30 25 25 -1 -1 31 26 4  2 39 26 3  1 -2 -1 0 22 0 -1 32 2 30 22 27 27 27 0 25 3 1 22 30 -2 30 3 30 1 -2 -1 27 27 27 -1 1 26 3 27 3 30 4 -2 -1 0 -2 2 0 0 29 i 32  I  -4 -4 0 0  I  3 39 0 2 -1 41  29 0 0 26 1 22 40 2 32 I 1 -2 -8 -2 24 3 0 24 2 2 30 4 0 2 0 0 0 1 3 3 0 26 -1 27 -1 30 3 31 30 0 31 31 0 29 26  2  30 -1 0 26 30 25 26 0 31 -1 31 0 39 -2  ox. -1 26 26 -4 26 2 -1 40 2 32 0 0 0 0 1 27 24 3 24 0 3 0 22 0 24 24 24 28 28 29 26 -2 27 -2 29 2 31 1 2 32 2 4 31 3 1 30 3 0 25 1  -I  -1 1 26 3 0 1 26 4 0  0 -2 -8 27 -2 26 0 -2 40 2 24 24 24 24 25 2 4 25 2 22 0 22 2 22 -8 -4 -1 -1 -1 -2 -1 28 -1 29 -2 31 2 0 0 -2 0 0 1 30 29 4 32 25 -2 28 0 30 0 4 39 26 0 -2 41 25  300 30L 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359  3 0 39 39 0 2 4 0 29 5 0 0 38 0 -1 0 29 32 32 0 3 41 37 33 0 0 30 3 1 0 34 -1 41 41 34 2 0 31 -1 4 2 1 37 37 30 -1 0 2 4 0 0 0 0 0 0 0 0 0 0 0  39 25 -1 -1 36 0 0 29 5 0 34 30 -1 34 0 41 -2 -4 -1 33 37 -2 -1 -1 30 26 4 0 0 36 -1 0 1 3 3 0 32 1 0 36 36 0 4 2 3 0 37 37 37 0 0 0 0 0 0 0 0 0 • 0 0  2 3 0 0 -1 29 36 1 0 29 -1 -2 0 -1 38 -2 32 41 41 3 -2 0 0 37 1 -1 33 30 38 -I 0 29 0 0  41 30 2 32 31 -1 -2 37 0 0 38 0 3 3 1 0 0 0 0 0 0 0 0 0 0 0  41 0 31 31 0 -2 3 0 29 3 0 34 34 42 -2 0 -1 -1 -1 0 41 33 33 -1 33 30 4 2 -1 0 34 -2 34 34 3 -1 0 3 3 0 0 2 30 30 -2 0 0 0 38 0 0 0 0 0 0 0 0 0 0 0  -1 25 -1 -1 36 36 0 29 5 0 30 -1 -1 -2 0 41 0 0 0 33 -1 1 -2 0 1 3 0 33 0 36 -2 0 2 4 0 32 32 0 32 31 31 0 2 4 0 0 30 30 -1 0 0 0 0 0 0 0 0 0 0 0  0 2 39 36 1 3 36 2 0 29 -1 38 0 0 38 -1 29 32 33 4 0 41 37 31 0 33 26 2 38 -2 0 29 41 41 30 I  3 31 1 3 1 37 37 37 -2 37 1 3 0 0 0 0 0 0 0 0 0 0 0 0  25 0 -2 -1 0 0 2 0 29 2 34 -2 34 42 -1 0 -1 -3 1 37 33 -I  4 25 0 0 29 29 0 29 5 0 -2 0  -2 -1 0 29 32 41 0 -1 2 0  -2 -2 30 3  0 0  -I 0  30 30 0 36 -1 0 0 0 34 1 32 32 -2 -1  -2 0 34 -1 2 4 -2 34 0 2 36 36 36 3 3 1 0 1 37 37 30 0 0 0 0 0 0 0 0 0 o . 0  2 0  -I  0 0 38 31 0 4 2 3 0 0 0 0 0 0 0 0 0 0 0  39 L 31 36 -1 -1 36 3 0 29 38 30 42 0 41 -1 -3 -2 33 0 37 33 31 31 33 26 3 1 38 -1 0 34 34 30 2 41 4 2 0  0 0 30 30 -I  1 37 0 0 33 0 0 0 0 0 0 0 0 0 0 0  1 0 -2 -2 36 36 1 0 29 I  -1 -1 -1 38 -1 0  0 0  2 33 -1 -1 -1 -1 2 -2 33 33 - i 0  29 1 3 -1 41 1 0  36 31 31 37 1 3 0 36 2 30 30 -2 0  0 0 0 0 0 0 0 0 0 0  (E>  SAMPLE GAMES  606  10 0 0 0 1 0 0 1  YOUR MOVE 'w» 1 8 Y  2  29  1507 53  YOUR MOVE * J1 2 21 NO F I T IT IS S T I L L  1  i « 1 25  F  h  10  668  h5  59  283  26  k9  13  YOUR MOVE •u' 2 k9 P  k  YOUR MOVE ' 1 * 6 25 8 V  2  31*  1 WIN  1 f  0 0 0 0 0 0  V> 1  3  -M  v v :v0 0 :  U.:-/.U' 0V 0 0 y;jo o P/P- 0  \///77A  P R.P.  YOUR MOVE  INPUT NEW GAME SPECS GO 6 1.0 0 0 0 100 11 YOUR MOVE 'v' 3 6 F  1 3 3  1698  51  YOUR MOVE ' 1 * 8 35 P  k  21  518 hO  51  173 2k  YOUR MOVE 'u' 3 2 I  2  YOUR MOVE * t * 3 46 23 Y 8 25 YOUR MOVE ' n 1 1 17 YOU WIN  O O O O O O INPUT NEW GAME SPECS  INPUT NEW GAME SPECS 60 6 10 0 0 0 100 12 T  12  2056  44  1070 48  60  YOUR MOVE ' p 4 23 1  YOUR MOVE •vv* 2 9 40  370  32  25  42  10  YOUR MOVE •u'. 4 53 30  V  1  WIN  o ojSllofi O ;^vW-.kT\\T-i  OVi 0 0 \W/f0, •8 O OfN/VW'IO O 0 •F ' 0 N: ;.N ' N 0  F F i.u;y:-o 0 0! U ; 0  o o oru^ttio INPUT NEW GAME SPECS  INPUT NEW GAME SPECS 5 0 5 10 0 0.0 1 0 0 12 1  31  2 056  ou  YOUR MOVE. t* 5 2 2 1  8  716 kS  2k  YOUR MOVE »x' 1 8 k50 2  1' ko YOUR MOVE 'y' 5 5 9k N 7 3k  k5  22  YOUR MOVE •v' 1 55  U  k 5k  I.WIN"  '/• •///////,<-  o  m o P§ o 1>; ;  OO t-;P/P ; M>-N L L :  i  t  :.;pi o o  .F  :  o '  Cy |o,h-'F;u  LV'l o  :  O :F-  o  :  'IK!  ;.y>y vy- o:;u ;u. i IMPUT MEW GAME SPECS $.end  ;  THANK YOU AMD BYE-BYE EXE CUT iON TERM I NATED  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 2 0
United States 2 1
Russia 1 0
City Views Downloads
Shenzhen 2 0
Mikhnevo 1 0
Mountain View 1 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0302120/manifest

Comment

Related Items