Difference between revisions of "Planning"

From Chessprogramming wiki
Jump to: navigation, search
 
(12 intermediate revisions by the same user not shown)
Line 11: Line 11:
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
!      
+
!  
 
! Terms of Planning  
 
! Terms of Planning  
 
! Aim  
 
! Aim  
 
! Dominating abstraction  
 
! Dominating abstraction  
 
|-
 
|-
−
| Tactics  
+
! style="text-align:left;" | Tactics  
−
| Short            
+
| style="text-align:center;" | Short  
−
| To gain material or to mate  
+
| style="text-align:center;" | To gain material or to mate  
−
| Matter  
+
| style="text-align:center;" | Matter  
 
|-
 
|-
−
|  Positional play  
+
! style="text-align:left;" |  Positional play  
−
| Medium    
+
| style="text-align:center;" | Medium  
−
| To improve the position  
+
| style="text-align:center;" | To improve the position  
−
| Space  
+
| style="text-align:center;" | Space  
 
|-
 
|-
−
| Strategy  
+
! style="text-align:left;" | Strategy  
−
|   Long  
+
| style="text-align:center;" | Long  
−
|   To swing the balance  
+
| style="text-align:center;" | To swing the balance  
−
| Time  
+
| style="text-align:center;" | Time  
 
|}
 
|}
  
Line 118: Line 118:
 
* [https://en.wikipedia.org/wiki/Henry_Kautz Henry Kautz], [[Bart Selman]] ('''1996'''). ''Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search''. [[AAAI|AAAI 1996]], [http://www.cs.cornell.edu/selman/papers/pdf/plan.pdf pdf]
 
* [https://en.wikipedia.org/wiki/Henry_Kautz Henry Kautz], [[Bart Selman]] ('''1996'''). ''Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search''. [[AAAI|AAAI 1996]], [http://www.cs.cornell.edu/selman/papers/pdf/plan.pdf pdf]
 
* [[Chrilly Donninger]] ('''1996'''). ''CHE: A Graphical Language for Expressing Chess Knowledge''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
 
* [[Chrilly Donninger]] ('''1996'''). ''CHE: A Graphical Language for Expressing Chess Knowledge''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
 +
* [http://fi.wikipedia.org/wiki/Jussi_Tella Jussi Tella] ('''1997'''). ''[http://www.cs.hut.fi/~sto/planning-seminaari/tella/planning-in-games.htm Planning in Games]''. Seminar on Knowledge Engineering, Fall 1997, [https://en.wikipedia.org/wiki/Helsinki_University_of_Technology Helsinki University of Technology]
 
* [[Jan van Reek]] ('''1997'''). ''Strategy in Chess''. Schachfirma Fruth, Unterhaching, ISBN 3-9804896-9-8
 
* [[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''. [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
 
* [[Jan van Reek]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1998'''). ''Planning a Strategy in Chess''. [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
Line 130: Line 131:
 
* [[Joelle Pineau]] ('''2004'''). ''Tractable Planning Under Uncertainty: Exploiting Structure''. Ph.D. thesis, [[Carnegie Mellon University]],  [http://www.cs.mcgill.ca/~jpineau/files/jpineau-thesis.pdf pdf]
 
* [[Joelle Pineau]] ('''2004'''). ''Tractable Planning Under Uncertainty: Exploiting Structure''. Ph.D. thesis, [[Carnegie Mellon University]],  [http://www.cs.mcgill.ca/~jpineau/files/jpineau-thesis.pdf pdf]
 
* [https://scholar.google.com/citations?user=A4v885AAAAAJ&hl=en Malik Ghallab], [[Dana S. Nau|Dana Nau]], [https://scholar.google.it/citations?user=ho38I-wAAAAJ&hl=en Paolo Traverso] ('''2004'''). ''[http://projects.laas.fr/planning/aptp/index.html Automated Planning: Theory and Practice]''. [https://en.wikipedia.org/wiki/Morgan_Kaufmann_Publishers Morgan Kaufmann Publishers]
 
* [https://scholar.google.com/citations?user=A4v885AAAAAJ&hl=en Malik Ghallab], [[Dana S. Nau|Dana Nau]], [https://scholar.google.it/citations?user=ho38I-wAAAAJ&hl=en Paolo Traverso] ('''2004'''). ''[http://projects.laas.fr/planning/aptp/index.html Automated Planning: Theory and Practice]''. [https://en.wikipedia.org/wiki/Morgan_Kaufmann_Publishers Morgan Kaufmann Publishers]
 +
* [[Yan Radovilsky]], [[Solomon Eyal Shimony]] ('''2004'''). ''Generalized Model for Rational Game Tree Search''. [https://dblp.uni-trier.de/db/conf/smc/smc2004-2.html  SMC 2004], [https://www.cs.bgu.ac.il/~yanr/Publications/smc04.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57560&start=14 Re: Interesting ideas] by [[Karlo Balla|Karlo Bala Jr.]], [[CCC]], September 09, 2015</ref>
 
==2005 ...==
 
==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, [http://www.jair.org/media/1696/live-1696-2537-jair.pdf pdf]
 
* [[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, [http://www.jair.org/media/1696/live-1696-2537-jair.pdf pdf]
Line 143: Line 145:
 
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]
 
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]
 
* [[Raghuram Ramanujan]], [[Bart Selman]] ('''2011'''). ''[http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2708 Trade-Offs in Sampling-Based Adversarial Planning]''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011], [http://videolectures.net/raghuram_ramanujan/ best paper], [http://videolectures.net/icaps2011_ramanujan_sampling/ VideoLecture] » [[UCT]]
 
* [[Raghuram Ramanujan]], [[Bart Selman]] ('''2011'''). ''[http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2708 Trade-Offs in Sampling-Based Adversarial Planning]''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011], [http://videolectures.net/raghuram_ramanujan/ best paper], [http://videolectures.net/icaps2011_ramanujan_sampling/ VideoLecture] » [[UCT]]
−
* [[Stefano Cianciulli]], [[Stavros Vassos]] ('''2013'''). ''Planning for Interactive Storytelling Processes''. [http://icaps13.icaps-conference.org/technical-program/workshop-program/planning-in-games/ ICAPS-2013], [http://stavros.lostre.org/files/CianciulliVassos2013Jaco.pdf pdf]
 
 
* [[Ari Weinstein]], [[Michael L. Littman]] ('''2013'''). ''Open-Loop Planning in Large-Scale Stochastic Domains''. [[Conferences#AAAI-2013|AAAI-2013]]
 
* [[Ari Weinstein]], [[Michael L. Littman]] ('''2013'''). ''Open-Loop Planning in Large-Scale Stochastic Domains''. [[Conferences#AAAI-2013|AAAI-2013]]
 
* [[Ari Weinstein]] ('''2013'''). ''Local Planning For Continuous Markov Decision Processes''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Rutgers_University Rutgers University], advisor [[Michael L. Littman]], [http://cs.brown.edu/~mlittman/theses/weinstein.pdf pdf]
 
* [[Ari Weinstein]] ('''2013'''). ''Local Planning For Continuous Markov Decision Processes''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Rutgers_University Rutgers University], advisor [[Michael L. Littman]], [http://cs.brown.edu/~mlittman/theses/weinstein.pdf pdf]
Line 151: Line 152:
 
* [[Arthur Guez]]  ('''2015'''). ''Sample-based Search Methods for Bayes-Adaptive Planning''. Ph.D. Thesis, Gatsby Computational Neuroscience Unit, [https://en.wikipedia.org/wiki/University_College_London University College London], [http://www.gatsby.ucl.ac.uk/~aguez/files/guez_phdthesis2015.pdf pdf]
 
* [[Arthur Guez]]  ('''2015'''). ''Sample-based Search Methods for Bayes-Adaptive Planning''. Ph.D. Thesis, Gatsby Computational Neuroscience Unit, [https://en.wikipedia.org/wiki/University_College_London University College London], [http://www.gatsby.ucl.ac.uk/~aguez/files/guez_phdthesis2015.pdf pdf]
 
* [https://scholar.google.com/citations?user=A4v885AAAAAJ&hl=en Malik Ghallab], [[Dana S. Nau|Dana Nau]], [https://scholar.google.it/citations?user=ho38I-wAAAAJ&hl=en Paolo Traverso] ('''2016'''). ''[https://www.cambridge.org/core/books/automated-planning-and-acting/E6DE5715A2190651352DFB0869916BC3# Automated Planning and Acting]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press]
 
* [https://scholar.google.com/citations?user=A4v885AAAAAJ&hl=en Malik Ghallab], [[Dana S. Nau|Dana Nau]], [https://scholar.google.it/citations?user=ho38I-wAAAAJ&hl=en Paolo Traverso] ('''2016'''). ''[https://www.cambridge.org/core/books/automated-planning-and-acting/E6DE5715A2190651352DFB0869916BC3# Automated Planning and Acting]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press 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''. [https://arxiv.org/abs/1911.08265 arXiv:1911.08265] <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=2&t=72381 New DeepMind paper] by GregNeto, [[CCC]], November 21, 2019</ref>
 +
==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'''). ''[https://www.nature.com/articles/s41586-020-03051-4 Mastering Atari, Go, chess and shogi by planning with a learned model]''. [https://en.wikipedia.org/wiki/Nature_%28journal%29 Nature], Vol. 588 <ref>[https://deepmind.com/blog/article/muzero-mastering-go-chess-shogi-and-atari-without-rules?fbclid=IwAR3mSwrn1YXDKr9uuGm2GlFKh76wBilex7f8QvBiQecwiVmAvD6Bkyjx-rE MuZero: Mastering Go, chess, shogi and Atari without rules]</ref>
  
 
=Forum Posts=
 
=Forum Posts=
 +
* [https://www.stmintz.com/ccc/index.php?id=56104 Plans in chess programs?] by Rodney Topor, [[CCC]], June 16, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=347144 Implementing Planning in an Engine] by [[Tom Likens]], [[CCC]], February 04, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=347144 Implementing Planning in an Engine] by [[Tom Likens]], [[CCC]], February 04, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=348682 Possible definition of planning] by [[Charles Roberson]], [[CCC]], February 12, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=348682 Possible definition of planning] by [[Charles Roberson]], [[CCC]], February 12, 2004
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=73418 When will the chess programmers write an engine that plans ?] by [[Thorsten Czub]], [[CCC]], March 20, 2020
  
 
=External Links=
 
=External Links=
Line 167: Line 173:
 
* [https://en.wikipedia.org/wiki/Forecasting Forecasting from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Forecasting Forecasting from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Prediction Prediction from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Prediction Prediction from Wikipedia]
−
* [https://www.chess.com/article/view/planning-in-chess Planning in Chess] by [https://en.wikipedia.org/wiki/Natalia_Pogonina Natalia Pogonina], [http://www.chess.com/ Chess.com], June 21, 2010
+
* [https://www.chess.com/article/view/planning-in-chess Planning in Chess] by [https://en.wikipedia.org/wiki/Natalia_Pogonina Natalia Pogonina], [[Chess.com]], June 21, 2010
 
* [http://opsound.org/artist/bigbonobotheinternationalbigbono/ Bigbonobo Combo] - Whitecube plan, [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
 
* [http://opsound.org/artist/bigbonobotheinternationalbigbono/ Bigbonobo Combo] - Whitecube plan, [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
 
: {{#evu:https://www.youtube.com/watch?v=ttOGPYZWtuQ|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=ttOGPYZWtuQ|alignment=left|valignment=top}}
Line 173: Line 179:
 
=References=  
 
=References=  
 
<references />
 
<references />
−
 
 
'''[[Knowledge|Up one Level]]'''
 
'''[[Knowledge|Up one Level]]'''
 +
[[Category:Quotes]]
 +
[[Category:Music]]

Latest revision as of 11:19, 6 August 2021

Home * Knowledge * Planning

Plan is law, fulfillment is duty, over-fulfillment is honor! [1]

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 [2] categorized planning in chess to three main characteristics, tactics, positional play, and strategy, where positional play serves as guideline for planning of a strategy [3]:

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 [4].

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

[5]

  • 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

See also

Publications

1946 ...

1950 ...

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

1960 ...

1970 ...

1980 ...

1985 ...

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

Forum Posts

External Links

References

  1. ↑ Лозунг «План — закон, выполнение — долг, перевыполнение — честь!» в здании Ольховско-Батьковского торфяного предприятия в Кубринске, Переславский район - «Plan is law, fulfillment is duty, over-fulfillment is honor!» Building Olkhovskaya Batkovsky - peat enterprise Kubrinsk, Pereslavskiy district, Photo by Н. Частов (N. Part), November 1997, Five-Year Plans for the National Economy of the Soviet Union - Wikipedia
  2. ↑ Jan van Reek (1997). Strategy in Chess. Schachfirma Fruth, Unterhaching, ISBN 3-9804896-9-8
  3. ↑ Jan van Reek, Jos Uiterwijk, Jaap van den Herik (1998). Planning a Strategy in Chess. ICCA Journal, Vol. 21, No. 3
  4. ↑ Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam; 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
  5. ↑ Chess Quotes - Strategy
  6. ↑ Judgment and Planning in Chess, games from Dr. Max Euwe's book Judgment and Planning in Chess. chessgames.com
  7. ↑ Re: Interesting ideas by Karlo Bala Jr., CCC, September 09, 2015
  8. ↑ New DeepMind paper by GregNeto, CCC, November 21, 2019
  9. ↑ MuZero: Mastering Go, chess, shogi and Atari without rules

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Planning&oldid=25721"