Pioneer

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Pioneer

Frederick McCubbin - The pioneer, 1904 [1]

Pioneer, (Russian: Пионер)
was a Soviet Artificial Intelligence project headed by Mikhail Botvinnik with the aim to develop a chess program to model a Chess Master's Mind, also used as general purpose planning tool to solve economical problems in the Soviet Union. Based on a hierarchical mathematical model consisting of square control, trajectories, sheaves of trajectories, and counter trajectories of attacking and defending pieces, piece chains, and zones, and the intermediate goal to win material within a given horizon, its purpose was a minimax best-first search of extremely narrow but deep game trees. The name Pioneer was chosen in 1977, when the program was invited to play the WCCC 1977 in Toronto. However, Pioneer was never completed in a way that it could play a game of chess in public under tournament conditions [2].

Early Ideas

Botvinnik's early ideas on attack maps were already formulated and published the late 50s and 60s. At Moscow Central Chess Club [3] in 1966, with the skeptical Georgy Adelson-Velsky and others attending, he introduced the concept of trajectories and found Vladimir Butenko as supporter and collaborator. Butenko first implemented the 15x15 vector attacks board representation on a M-20 computer, determining trajectories. The table below demonstrates the distance from a square (here c2) on a 8x8 board, superimposed on the 15x15 array in such a way that the from square (c2) coincides with the central square of the 15x15 array, which is the origin, tail, or base of all displacement vectors [4] .

     ╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
 210 ║  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 ║
     ╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
 195 ║  7 |  6 |  6 |  6 |  6 ║  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 180 ║  7 |  6 |  5 |  5 |  5 ║  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 165 ║  7 |  6 |  5 |  4 |  4 ║  4 |  4 |  4 |  4 |  4 |  4 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 150 ║  7 |  6 |  5 |  4 |  3 ║  3 |  3 |  3 |  3 |  3 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 135 ║  7 |  6 |  5 |  4 |  3 ║  2 |  2 |  2 |  2 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 120 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 |  1 |  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
 105 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 ║  0 ║  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
  90 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 |  1 |  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
  75 ║  7 |  6 |  5 |  4 |  3 |  2 |  2 |  2 |  2 |  2 |  3 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  60 ║  7 |  6 |  5 |  4 |  3 |  3 |  3 |  3 |  3 |  3 |  3 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  45 ║  7 |  6 |  5 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  30 ║  7 |  6 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  15 ║  7 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
   0 ║  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 ║
     ╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
        0    1    2    3    4    5    6    7    8    9    10   11   12   13   14

Boris Stilman gave following example to generate a set or sheave of trajectories for a king moving from f6 to h1 [5] :

D(f6,K)          +  D(h1,K)          =  SUM                 SUM == D(f6,h1)
5 4 3 2 2 2 2 2     7 7 7 7 7 7 7 7     c b a 9 9 9 9 9     . . . . . . . .
5 4 3 2 1 1 1 2     7 6 6 6 6 6 6 6     c a 9 8 7 7 7 8     . . . . . . . .
5 4 3 2 1 0 1 2     7 6 5 5 5 5 5 5     c a 8 7 6|5|6 7     . . . . . 1 . .
5 4 3 2 1 1 1 2     7 6 5 4 4 4 4 4     c a 8 6|5 5 5|6     . . . . 1 1 1 .
5 4 3 2 2 2 2 2  +  7 6 5 4 3 3 3 3  =  c a 8 6|5 5 5 5|    . . . . 1 1 1 1
5 4 3 3 3 3 3 3     7 6 5 4 3 2 2 2     c a 8 7 6|5 5 5|    . . . . . 1 1 1
5 4 4 4 4 4 4 4     7 6 5 4 3 2 1 1     c a 9 8 7 6|5 5|    . . . . . . 1 1
5 5 5 5 5 5 5 5     7 6 5 4 3 2 1 0     c b a 9 8 7 6|5|    . . . . . . . 1

Mathematical Projection

In Botvinnik's hierarchical Mathematical Projection (MP) of chess as a complex system, trajectories build the lowest level of the hierarchy. The concepts of zones as intermediate level of the MP consists of a network of main trajectories conform to attacking or defending plans determined elsewhere, negation trajectories, that is opponent's counter trajectories which may block or combat the primary trajectory in time, and own supporting counter-counter trajectories. The MP controls the growth of a search tree inside a best-first search, and prunes all branches forward which could not reach a goal in time. After Botvinnik introduced the concept of Zones in 1970, Butenko refused further cooperation and began to write his own program [6] .

Further Research

In the 70s and 80s, a team around Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman, Vadim Mirniy and Mikhail Chudakov worked on Pioneer at the State Committee for Science and Technology, Moscow, USSR, the National Research Institute for Electrical Engineering, Moscow, USSR and the USSR Academy of Sciences, Moscow, USSR. Botvinnik and his team proposed a attack map and offset map move generating strategy [7] based on Vector Attacks [8] , and a hierarchical geometrical model based on trajectories, sheaves of trajectories and chains - a set of pieces, each with their trajectories, enjoying the property of aiding or hindering the attack of a piece against a target. Based on this research, Boris Stilman later coined the term Linguistic Geometry [9] , a new type of game theory [10]. Alexander Reznitskiy and Mikhail Chudakov presented the current state of a long development originated by Botvinnik in an 1990 ICCA Journal article [11].

Controversy

Botvinnik published abilities of Pioneer and its successor CC Sapiens on selected positions, but they never played a complete game of chess in public. For his publication Three Positions [12] , Botvinnik was heavily criticized by Hans Berliner [13] [14] [15] [16] , and his old chess rival David Bronstein [17] .

Photos

McGill University 1977

3-3.Botvinnik.McGill University Lecture.Montreal.1977.102645344.NEWBORN.lg.jpg

Botvinnik's Lecture on Pioneer at McGill University 1977 - any questions? Monty Newborn left [18]

Moscow 1980

ReznitkiyStilmanDonskoyBotvinnikNewborn.jpg

A. Reznitskiy, B. Stilman, M. Donskoy (Kaissa), M. Botvinnik, Monty & Amy Newborn [19] [20] [21] [22]

Timeline

[23]

1958 Botvinnik's idea to make computer grandmaster.
1960 Botvinnik's Lecture Humboldt University Berlin: "Men and machines at the chessboard."
1961 Article: MM Botvinnik, Men and machines at the chess board. Chess in the USSR, 1961, № 3, Moscow
1964 Goal game of chess (Botvinnik, PIONEER , Mansurov, 2004).
1966 Dispute in Central Chess Club. Trajectory shapes. 15x15 table. Vladimir Butenko programs the trajectory of chess pieces
1968 Book: MM Botvinnik, chess algorithm , Nauka, Moscow, 1968 tactical cost of pieces
1969 Concept of Zones
1970 Book: MM Botvinnik Computers, Chess and Long-Range Planning. Springer
Butenko's refusal to fruther cooperate with Botvinnik
1972 New Programmers: Boris Stillman and Alexander Yudin
Computer time on an English computer ICL 4/70 (clone of IBM/360)
1976 Stillman BM, About the formation of the playing area. Dep. VINITI 3947-76, (also in Stillman BM, 1979 ). Stillman BM The tree in the zone busting game. Dep. VINITI 3947a-76 (also in Stillman BM, 1979 ).
1976 Invitation to a second world championship of chess programs in Toronto, Canada.
1977 Chess program dubbed Pioneer
1978 MM Botvinnik, BM Stillman, AD Yudin Artificial chess master. Bulletin of the Academy of Sciences of the USSSR, Moscow, 1978, № 4, p.82-91.
1978 BM Stillman Research-based management model of a chess game. Technical report, VNIIE, Moscow, 1978
1978 Grants for computer time:
At University of Mannheim (Hans Meuer) for the improvement and completion of the PIONEER project (For 0.5 year), Germany [24].
At University of Dortmund (Hans-Jürgen Appelrath) for the development of AI theory of complex systems and its application to the PIONEER project (for 0.5 year), Germany.
From Control Data Corp. (CDC, David Cahlander) for the improvement of the PIONEER program and development of efficient methods for solving practical search problems (for 0.5 year), USA.
1980 MM Botvinnik, BM Stillman, AD Yudin, AI Reznitskii, MA Tsfasman The chess players and computers. Preprint for the 2nd International Symposium on Artificial Intelligence, 9 pages, Repino, Leningrad, Russia, in October 1980.
Retired programmer: Alexander Yudin
1980 New developer: Mikhail Chudakov, Vadim Mirniy
1981 Retired programmer: Michael Tsfasman
1981 The grant for computer time (600 rubles)
From the USSR National Committee for Science and Technology for the design of new methods and software for solving complex search problems, (For 3 years, MM Botvinnik, BM Stilman, V Mirniy, AI Reznitskiy), USSR.
1988 Retired programmers: Vadim Mirniy and Boris Stillman
1990 Dismissed programmers: Alexander Reznitskiy and Mikhail Chudakov
1990 End of project Pioneer
1994 CC Sapiens

Quotes

Rushton and Marsland

Paul Rushton and Tony Marsland, 1973, in Current Chess Programs [25] :

A novel idea has been proposed by Botvinnik. He believes it is important to know which pieces are able to reach a certain square or sector of the board in a set number of half-moves. In this manner it is possible to determine the pieces that one should be concerned with when planning a move and it establishes what Botvinnik calls an "horizon." Thus one could vary the horizon by changing the amount of time pieces are allowed to take in arriving at a given area. At the present time some of his ideas have been programmed, but the successful completion of a program based on Botvinnik's ideas has not yet been announced. 

David Kittinger

David Kittinger and Scott McDonald in Computer Chess Digest Annual 1984 on Novag Constellation [26] :

The Novag Constellation programs represent a significant evolutionary step in the development of microcomputer chess programs. The program represents the first commercial implementation of the attack map / offset map move generating strategy proposed by former World Chess Champion Mikhail Botvinnik and subsequently refined by myself for faster move generation as pieces come off the board. 

Reznitskiy and Chudakov

Alexander Reznitskiy and Mikhail Chudakov in ICCA Journal, Vol. 13, No. 4 [27]:

PIONEER has been tested on various positions. For experiments we used an 80386 based computer running at 20 MHz. The outcome shows the approach described in its advantage as well in its disadvantage.
So far PIONEER cannot regarded as a competetive player. The program is not fast enough to play under tournament conditions. It takes up to several hours to complete a search. Moreover, we found out, PIONEER  fails to find a solution in some positions (especially in endgames).
Nevertheless, fortunately in mosts cases PIONEER manages to find the strongest move. If so, the program has found this move in a human fashion. It discovers the position's essence, correctly specifies subgoals and directs its search towards these subgoals. In accordance with this, all the trees are small, narrow and deep, and contain only reasonable variations of variable depth, truncated by logical considerations. 

Boris Stilman

Boris Stilman in Linguistic Geometry. Acknowledgments [28] :

This book was inspired by the results of long and fruitful collaboration in the 70s and 80s with Professor Mikhail Botvinnik, my research adviser and project director. At the very beginning he shaped my thinking about complex search problems. One scientist said that this unimaginably difficult work could have started because Botvinnik, a chess player, did not anticipate the difficulties of programming, while Stilman, a computer scientist, did not anticipate difficulties of playing chess. Every time when the team of researchers experienced serious problems in the development of the project PIONEER, Dr. Botvinnik used to say: “If a human chess master can make it, a computer will make it as well.” He believed in the existence of a general algorithm, or a small collection of general algorithms, used intuitively by all the chess masters and grandmasters in playing chess. Essentially, discovery, simulation and generalization of these algorithms were the goals of the project PIONEER. An attempt to construct and investigate a mathematical model based on those algorithms is the goal of this book. Alexander Yudin, Alexander Reznitskiy, Mikhail Tsfasman, Mikhail Chudakov have worked with me in the 70s and 80s to develop project PIONEER. My friend and colleague, Vadim Mirniy, with whom we worked in the 80s provided major insights and pushed our research and software implementations to much higher level. Also, in the 70s an invaluable technical assistance in software development was provided by Dmitry Lozinskiy, Lidia Poltavets, and Anatoliy Kostrukov. Four major scientists, the founders of computer science and engineering in the former Soviet Union, Academician Viktor Glushkov, Professors Bashir Rameev, Viacheslav Myasnikov and Nikolay Krinitskiy contributed to the establishment of the organizational framework, provided major funding and access to the state-of-the-art computers for project PIONEER.
Project PIONEER and the first theoretical generalizations related to the origin of LG would have never succeeded without constant support of numerous Soviet scientists. I am grateful to all of them. Here, I would like to acknowledge those whose decisive support came at the most difficult times. They are Academician Nikolay Krasovsky, Academician-correspondent, Lenin Prize Winner Yakov Tsipkin, Academician-correspondents Yury Rudenko and Hermogen Pospelov, Professors Dmitry Pospelov, David Yudin, Vladimir Yakubovich, Georgy Adelson-Velsky, Yuriy Shakarian, Gavriil Shalit, Lev Mamikoniants and Dr. Mikhail Donskoy.
Scientific exchange with researchers from around the world allowed our team to overcome isolation of the former Soviet Union. A list of major participants of this exchange includes Professor Monty Newborn from McGill University, Canada, Professors Tony Marsland and Randy Goebel from the University of Alberta, Canada, Professor Jaap van den Herik from the University of Limburg, The Netherlands, Professor Ben Mittman from Northwestern University, USA, Dr. David Cahlander from CDC Corp., USA, Ken Thompson from Bell Labs, USA, Dr. Hans Meuer from the University of Mannheim, Germany, Dr. H.-J.Appelrath from the University of Dortmund, Germany, David Levy from London, UK. 

See also

Selected Publications

[29]

1968 ...

1970 ...

Boris Stilman (1975). Formirovanie Mnozestva Puchkov Traektorii. (Formation of the Set of Trajectory Bundles) , pp. 70-78
Boris Stilman (1979). Zoni Igri. (Fields of Play). pp.70-104.
Boris Stilman, Michael Tsfasman (1979). Pozicionnaja Ocenka i Prioriteti. (Positional Value and Assignment of Priorities). pp. 104

1980 ...

Michael Tsfasman, Boris Stilman (1984). The Positional Estimate and Assignment of Priorities.

1990 ...

2000 ...

Forum Posts

1993 ...

Re: Botvinnik article by Peter Gillgasch, rgcc, October 23, 1996
Re: Botvinnik article by Marc-François Baudot, rgcc, November 07, 1996 » Advances in Computer Chess 7

2000 ...

2010 ...

External Links

Chess Program

Энциклопедия шахмат - Ботвинник В.Линдер, И.Линдер, (The Encyclopedia of Chess - Botvinnik) B. Linder, J. Linder
По стопам ПИОНЕРа (In the footsteps of Pioneer)

Misc

Young Pioneer Organization of the Soviet Union - Wikipedia
Young Pioneer camp from Wikipedia
Category:Pioneer movement - Wikimedia Commons

References

  1. Frederick McCubbin, The pioneer, 1904, oil on canvas, National Gallery of Victoria, Melbourne, The Pioneer (painting) from Wikipedia
  2. Re: KAISSA for PC, I'm the proud owner by Eugene Nalimov, CCC, February 01, 2002
  3. The last day of the “Botvinnik Memorial” by Anna Burtasova, ChessBase News, September 07, 2011
  4. Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  5. Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  6. Лингвистическая Геометрия Бориса Штильмана (Linguistic Geometry Boris Stilman) by Alexander Timofeev, По стопам ПИОНЕРа
  7. David Kittinger, Scott McDonald (1984). Report from the U.S. Open. Computer Chess Digest Annual 1984 pp. 15-33
  8. Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  9. The Home Page of Linguistic Geometry
  10. José Roberto Mercado Vega, Zvi Retchkiman Königsberg (2009). Modeling the Game of Arimaa with Linguistic Geometry. CIG'09 » Arimaa
  11. Alexander Reznitskiy, Mikhail Chudakov (1990). Pioneer: a Chess Program Modelling a Chess Master's Mind. ICCA Journal, Vol. 13, No. 4
  12. Mikhail Botvinnik (1993). Three Positions. ICCA Journal, Vol. 16, No. 2
  13. Hans Berliner (1993). Playing Computer Chess in the Human Style. ICCA Journal, Vol. 16, No. 3
  14. Kasparov missed Beautiful win; Botvinnik's Program muffs analysis by Hans Berliner, rec.games.chess, July 9, 1993
  15. Botvinnik article by Jonathan Schaeffer, rgcc, October 23, 1996
  16. Hans Berliner against Mikhail Botvinnik by Alexander Timofeev
  17. David Bronstein (1993). Mimicking Human Oversight. ICCA Journal, Vol. 16, No. 3
  18. Photo Courtesy Monroe Newborn from The Computer History Museum, archive.computerhistory.org - /resources/still-image/Chess_temporary/still-image/
  19. Tony Marsland, Monty Newborn (1981). A brighter future for Soviet computer chess? ICCA Newsletter, Vol. 4, No. 1, pdf
  20. Monroe Newborn and Soviet computer chess developers in Moscow, Gift of Monroe Newborn, 1980
  21. Computer chess pioneer Mikhail Donskoy passes on from ChessBase News, January 16, 2009
  22. Kaissa & Botvinik by Shay Bushinsky, rgcc, October 16, 1997
  23. based on По стопам ПИОНЕРа, Chronology
  24. Martin Meuer: "I Wanted to Do Something Different in Conjunction with Computers" | chess-news.ru, June 28, 2012
  25. Paul Rushton, Tony Marsland (1973). Current Chess Programs: A Summary of their Potential and Limitations. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, pdf
  26. David Kittinger, Scott McDonald (1984). Report from the U.S. Open. Computer Chess Digest Annual 1984 pp. 15-33
  27. Alexander Reznitskiy, Mikhail Chudakov (1990). Pioneer: a Chess Program Modelling a Chess Master's Mind. ICCA Journal, Vol. 13, No. 4
  28. Boris Stilman (2000). Linguistic Geometry - From Search to Construction. Operations Research/Computer Science Interfaces Series. Springer US, ISBN: 978-0-7923-7738-2, Acknowledgments
  29. ICGA Reference Database (pdf)
  30. Paul Rushton, Tony Marsland (1973). Current Chess Programs: A Summary of their Potential and Limitations. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, pdf
  31. Computers, Chess and Long-range Planning by Botvinnik by John L. Jerz
  32. Martin Meuer, son of Hans Meuer who worked with Botvinnik

Up one Level