Planning

Home * Knowledge * Planning

Plan is law, fulfillment is duty, over-fulfillment is honor!

Planning,
the process of applying knowledge, thinking and prediction to create and maintain a plan, a temporal set of intended actions to achieve a certain goal, in chess, to finally win the game.

Terms of Planning

In 1997, Jan van Reek categorized planning in chess to three main characteristics, tactics, positional play, and strategy, where positional play serves as guideline for planning of a strategy :

	Terms of Planning	Aim	Dominating abstraction
Tactics	Short	To gain material or to mate	Matter
Positional play	Medium	To improve the position	Space
Strategy	Long	To swing the balance	Time

Long-range Planning

Long-range planning by human chess players is usually made on the basis of reasoning, experience, and intuition, as investigated by De Groot in 1946 .

Search and Evaluation

Conventional depth-first alpha-beta searchers have no real sense of planning other than minimaxing their score inside their search horizons. Inside chess programs, planning is often implicit due to look ahead and certain evaluation features and their associated weights. For instance, a bonus for a Rook on an open file, and another bonus to occupy the 7th rank is a typical example to mimic some kind of strategic planning. However, long-range planning and seeking for goals requires pattern recognition and associated advices if they match.

Oracle Approaches

Oracle approaches such as pre-processing and initializing piece-square tables based on features and pattern of the root may realize plans like minority attack and along with pawn structure and king placement, plans to attack the king. However, with todays typical search depths one has to consider path-dependencies, transposition table anomalies and resulting search instabilities. Instead, oracle approaches at or near the root, may be used to initialize dedicated piece-square tables for the sole purpose to control selectivity further down the tree, for instance to extend moves according to a certain plan.

Chess Quotes

• Frank Marshall: A bad plan is better than none at all.
• Emanuel Lasker: To find the right plan is just as hard as looking for its sound justification.
• Eugene Znosko-Borovsky: It is not a move, even the best move that you must seek, but a realizable plan.
• Alexander Kotov: It is better to follow out a plan consistently even if it isn't the best one than to play without a plan at all. The worst thing is to wander about aimlessly.

Chess Programs

• N.N.
• Paradise
• Planner
• Symbolic

See also

• CHE
• Chunking
• Cognition
• History Heuristic
• Learning
• Opponent Model Search
• Oracle
• Pawn Structure
• Pattern Recognition
• Pre-Processing
• Psychology
• Reinforcement Learning
• Strategy
• Tactics
• Time Management

Publications

1946 ...

• Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam, advisor Géza Révész; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6.

1950 ...

• Max Euwe (1953). Judgment and Planning in Chess. McKay Company, New York, N.Y.

1960 ...

• Adriaan de Groot (1965, 1978). Thought and Choice in Chess. Mouton & Co Publishers, The Hague, The Netherlands. ISBN 90-279-7914-6
• Jack Good (1968). A Five-Year Plan for Automatic Chess. Machine Intelligence Vol. 2 pp. 110-115, pdf from doczine

1970 ...

• Mikhail Botvinnik (1970). Computers, Chess and Long-Range Planning. Springer-Verlag, New York.
• Walter R. Reitman, James Kerwin, Robert Nado, Judith S. Reitman, Bruce Wilcox (1974). Goals and Plans in a Program for Playing Go. Proceedings of the 29th ACM Conference
• Larry R. Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. 4. IJCAI 1975, reprinted (1988) in Computer Chess Compendium
• Jacques Pitrat (1977). A Chess Combination Program Which Uses Plans. Artificial Intelligence, Vol 8, No. 3
• Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine
• David Wilkins (1979). Using Patterns and Plans to Solve Problems and Control Search. Ph.D. thesis, Computer Science Dept, Stanford University, Stanford, California, AI Lab Memo AIM-329
• David Wilkins (1979). Using plans in chess. In Proceedings of the 1979 International Joint Conference on Artificial Intelligence, (Tokyo, Japan), pp. 960-967.
• Jacques Pitrat (1979). A Program which Uses Plans for Finding Combinations in Chess. ICCA Newsletter, Vol. 2 No. 2

1980 ...

• David Wilkins (1980). Using patterns and plans in chess. Artificial Intelligence, Vol. 14, pp. 165-203. Reprinted (1988) in Computer Chess Compendium
• Jacques Pitrat (1980). The Behaviour of a Chess Combination Program using Plans. Advances in Computer Chess 2
• Jonathan Schaeffer (1980). Long-Range Planning in Computer Chess. Master's thesis, Department of Computer Science, University of Waterloo
• Sarah E. Goldin, Barbara Hayes-Roth (1980). Individual Differences in Planning Processes. RAND note N-1488
• Jaime Carbonell (1981). Counterplanning: A Strategy-Based Model of Adversary Planning in Real-World Situations. Artificial Intelligence, Vol. 16
• Kai von Luck, Bernd Owsnicki (1982). N.N.: A View of Planning in Chess. in Wahlster, GWAI-82
• Helmut Horacek (1982). Construction of Planned Move Trees for Chess Pawn Endings. Sigart Newsletter 80, pp. 163-168.
• E. D. Cherevik, Y. M. Shvyrkov (1982). An ABC of Planning : Fundamentals of the Theory and Methodology of Economic Planning. Progress Moscow
• Hermann Kaindl (1982). Positional Long-Range Planning in Computer Chess. Advances in Computer Chess 3, also published as Hermann Kaindl (1983). Positional Long-Range Planning in Computer Chess. Vienna University of Technology, Austria.
• Ivan Bratko (1984). Advice and Planning in Chess Endgames. Artificial and Human Thinking (eds. S. Amarel, A. Elithorn and R. Banerji). North-Holland.

1985 ...

• Hans Berliner (1985). Goals, Plans, and Mechanisms: Non-symbolically in an Evaluation Surface. Presentation at Evolution, Games, and Learning, Center for Nonlinear Studies, Los Alamos National Laboratory, May 21.
• Richard Korf (1987). Planning as Search: A Quantitative Approach. Artificial Intelligence, Vol. 33, pp. 65-88.
• David Wilkins (1988). Practical Planning: Extending the Classical AI Planning Paradigm. (Morgan Kaufmann Series in Representation and Reasoning), amazon
• Bruce Abramson (1989). Control Strategies for Two-Player Games. ACM Computing Surveys, Vol. 21, No. 2
• Reiner Seidel (1989). A Model of Chess Knowledge - Planning Structures and Constituent Analysis. Advances in Computer Chess 5

1990 ...

• David Wilkins (1991). Working notes on paradise chess patterns. Technical Note 509, AI Center, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025
• Jens Christensen, Adam Grove (1991). A Formal Model Classical Planning. IJCAI-91, pdf
• Jens Christensen (1991). Automatic Abstraction in Planning. Ph.D. thesis, Stanford University
• Steven Walczak (1992). Pattern-Based Tactical Planning. IJPRAI, Vol. 6, No. 5
• Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1992). A hierarchical approach to strategic planning with non-cooperating agents under conditions of uncertainty. Proceedings of the First International Conference on AI Planning Systems
• Stephen J.J. Smith, Dana S. Nau (1993). Strategic planning for imperfect-information games. Technical Report, University of Maryland, College Park
• Mikhail Botvinnik, Evgeniĭ Dmitrievich Cherevik, Vasily Vladimirov, Vitaly Vygodsky (1994). Solving Shannon's Problem: Ways and Means. Advances in Computer Chess 7 » CC Sapiens
• Andreas L. Opdahl, Bjornar Tessem (1994). Long-Term Planning in Computer Chess. Advances in Computer Chess 7

1995 ...

• Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1996). Total-Order Multi-Agent Task-Network Planning for Contract Bridge. AAAI 1996
• Henry Kautz, Bart Selman (1996). Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. AAAI 1996, pdf
• Chrilly Donninger (1996). CHE: A Graphical Language for Expressing Chess Knowledge. ICCA Journal, Vol. 19, No. 4
• Jussi Tella (1997). Planning in Games. Seminar on Knowledge Engineering, Fall 1997, Helsinki University of Technology
• Jan van Reek (1997). Strategy in Chess. Schachfirma Fruth, Unterhaching, ISBN 3-9804896-9-8
• Jan van Reek, Jos Uiterwijk, Jaap van den Herik (1998). Planning a Strategy in Chess. ICCA Journal, Vol. 21, No. 3
• Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1998). Computer Bridge: A Big Win for AI Planning. AI Magazine, Vol. 19, No. 2
• Ian Frank (1998). Search and Planning Under Incomplete Information: A Study Using Bridge Card Play. Springer, Ph.D. thesis, University of Edinburgh

2000 ...

• Mark Brockington (2000). Computer Chess Meets Planning. ICGA Journal, Vol. 23, No. 2
• Alex B. Meijer, Henk Koppelaar (2001). Pursuing abstract goals in the game of Go. BNAIC 2001
• Adi Botea (2002). Using Abstraction for Heuristic Search and Planning. Research Summary. In Proceedings of the 5th International Symposium on Abstraction, Reformulation, and Approximation SARA-02, volume 2371 of Lecture Notes in Artificial Intelligence, 326-327, Kananaskis, AB, Canada.
• Ari Shapiro, Gil Fuchs, Robert Levinson (2002). Learning a Game Strategy Using Pattern-Weights and Self-play. CG 2002
• Adi Botea, Martin Müller, Jonathan Schaeffer (2002). Using Abstraction for Planning in Sokoban. CG 2002
• Joelle Pineau (2004). Tractable Planning Under Uncertainty: Exploiting Structure. Ph.D. thesis, Carnegie Mellon University, pdf
• Malik Ghallab, Dana Nau, Paolo Traverso (2004). Automated Planning: Theory and Practice. Morgan Kaufmann Publishers
• Yan Radovilsky, Solomon Eyal Shimony (2004). Generalized Model for Rational Game Tree Search. SMC 2004, pdf

2005 ...

• Adi Botea, Markus Enzenberger, Martin Müller, Jonathan Schaeffer (2005). Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators. Journal of Artificial Intelligence Research 24 (2005) 581-621, pdf
• René Alquézar, A. Gonzalez Camargo, Alejandro González Romero (2006). Evolving Plans for the KRKa2 Chess Ending. Artificial Intelligence and Applications 2006
• Adi Botea (2006). Improving AI Planning and Search with Automatic Abstraction. PhD Thesis, University of Alberta, pdf
• Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning ECML-06, LNCS/LNAI 4212, pp. 282-293. introducing UCT, pdf
• Frantisek Sailer, Michael Buro, Marc Lanctot (2007). Adversarial planning through strategy simulation. Computational Intelligence and Games, pdf
• Zvi Retchkiman Königsberg (2007). A Combinatorial Game Mathematical Strategy Planning Procedure for a Class of Chess Endgames. International Mathematical Forum, Vol. 2, No. 68
• Sylvain Gelly, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Yann Kalemkarian (2008). The Parallelization of Monte-Carlo Planning - Parallelization of MC-Planning. ICINCO-ICSO 2008: 244-249, pdf, slides as pdf
• Akihiro Kishimoto, Alex Fukunaga, Adi Botea (2009). Scalable, Parallel Best-First Search for Optimal Sequential Planning. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS-2009) (Best Paper Award), pages 201-208, pdf
• Gerhard Trippen (2009). Plans, Patterns and Move Categories Guiding a Highly Selective Search. Advances in Computer Games 12, pdf

2010 ...

• Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010
• Raghuram Ramanujan, Bart Selman (2011). Trade-Offs in Sampling-Based Adversarial Planning. ICAPS 2011, best paper, VideoLecture » UCT
• Ari Weinstein, Michael L. Littman (2013). Open-Loop Planning in Large-Scale Stochastic Domains. AAAI-2013
• Ari Weinstein (2013). Local Planning For Continuous Markov Decision Processes. Ph.D. thesis, Rutgers University, advisor Michael L. Littman, pdf
• Arthur Guez, David Silver, Peter Dayan (2014). Better Optimism By Bayes: Adaptive Planning with Rich Models. arXiv:1402.1958v1
• Arthur Guez, Nicolas Heess, David Silver, Peter Dayan (2014). Bayes-Adaptive Simulation-based Search with Value Function Approximation. NIPS 2014, pdf

2015 ...

• Arthur Guez (2015). Sample-based Search Methods for Bayes-Adaptive Planning. Ph.D. Thesis, Gatsby Computational Neuroscience Unit, University College London, pdf
• Malik Ghallab, Dana Nau, Paolo Traverso (2016). Automated Planning and Acting. Cambridge University Press
• Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, David Silver (2019). Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model. arXiv:1911.08265

2020 ...

• Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, David Silver (2020). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, Vol. 588

Forum Posts

• Plans in chess programs? by Rodney Topor, CCC, June 16, 1999
• Implementing Planning in an Engine by Tom Likens, CCC, February 04, 2004
• Possible definition of planning by Charles Roberson, CCC, February 12, 2004
• When will the chess programmers write an engine that plans ? by Thorsten Czub, CCC, March 20, 2020

External Links

• Planning from Wikipedia
• Plan (disambiguation) from Wikipedia
• State space planning from Wikipedia
• Strategic planning from Wikipedia
• Plan from Wikipedia
• Automated planning and scheduling from Wikipedia
• Hierarchical task network (HTN) from Wikipedia
• Planning fallacy from Wikipedia
• Forecasting from Wikipedia
• Prediction from Wikipedia
• Planning in Chess by Natalia Pogonina, Chess.com, June 21, 2010
• Bigbonobo Combo - Whitecube plan, YouTube Video

References

Up one Level