Answers.Body: <p>If you can remember everything and there's no randomisation in your outcome like chess, there is absolutely <strong>no</strong> reason not to do that. Anybody who can remember all the possible board configurations in chess, by definition plays perfect chess. A perfect player would never lose.</p>
  
  <p>Unfortunately, most practical problems can't be solved by brute-force, and that includes chess. <strong>All</strong> chess players learn general chess principles. Nobody could memorize all possible opening variations.</p>
  
  <p>If you can somehow memorize every possibility, why not? But can you? </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-25T12:27:58.147Z
Answers.Text: Of course you can not do that. But you can, let's say, memorize 10 prototypic configurations. And then starting from them you can go on and optimize it. The question is now: how much should you memorize optimally. 
  
  I'm just looking for a field that's working on these kind of questions.
Answers.UserDisplayName: hh32
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-25T11:19:41.757Z
Answers.LastActivityDate: 2017-10-25T11:19:41.757Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>The The <a href="https://en.wikipedia.org/wiki/The_Oxford_Companion_to_Chess" rel="nofollow noreferrer">Oxford Companion to Chess</a> has entries on only 700 named openings, and lists another 1327 opening variations in the index, and I wouldn't be surprised if someone out there had them all memorized.  For an algorithm, however, storing that number of openings is trivial, and Chess algorithms traditionally made use of high-quality "game books" which are move-by-move records of chess games.</p>
  
  <p>The problem with <a href="https://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability" rel="nofollow noreferrer">intractable models</a>, like chess is that they are unsolvable, so brute-force is not an option, and any decision on a move, whether "memory" or "optimality" based, at least in the context of current advances, are probabilistic.  (<a href="https://en.wikipedia.org/wiki/Endgame_tablebase" rel="nofollow noreferrer">The exception is endgames</a> where the the problem becomes tractable, and <a href="https://en.wikipedia.org/wiki/Solved_game#Perfect_play" rel="nofollow noreferrer">perfect play</a> can be achieved.)  </p>
  
  <p>Essentially, the memory of a board state is only a small piece of the puzzle because the unsolvability of the game means that particular board state from a recorded game, where that state led to a successful outcome, will not guarantee a similar result in a new game, because new, more optimal strategies can always emerge.    </p>
  
  <p>Secondly, because of the extreme variation engendered by non-trivial games, it is extremely unlikely any current game would mirror the previous "memorized" game.  </p>
  
  <p>It is my understanding that "memory" as you define has been utilized in Chess engines, accessing a database of previous games to evaluate a position and derive a good move, but the intractability of Chess in general makes this method sub-optimal, and it has been definitively supplanted by newer methods (machine learning, neural networks).</p>
  
  <p>In the famous Giraffe Chess paper, Matthew Lai states:</p>
  
  <blockquote>
    <p>The job of the evaluation functions is to assign scores to positions statically (without looking ahead)</p>
  </blockquote>
  
  <p>But the method is highly nuanced and probabilistic.  Nevertheless, I think you'll be interested because the problem presented in the paper is rooted in the human vs. AI play method issue:</p>
  
  <blockquote>
    <p>...the way computers play chess is very different from how humans play. While both humans and computers search ahead to predict how the game will go on,
    humans are much more selective in which branches of the game tree to explore. Computers, on the other hand, rely on brute force to explore as many continuations as possible, even ones that will be
    immediately thrown out by any skilled human... How can a human searching 3-5 positions per second be as strong as a computer searching 200
    million positions per second? And is it possible to build even stronger chess computers than what
    we have today, by making them more computationally efficient? Those are the questions this
    project investigates.</p>
  </blockquote>
  
  <p>There is no simple answer to the trade-off question due to the complexity of the problem.  But this is an area where tremendous advances are being made.</p>
  
  <p>I'd strongly recommend reading <a href="https://arxiv.org/pdf/1509.01549.pdf" rel="nofollow noreferrer">Giraffe Chess (September, 2015)</a> as a primer. 
   It produced very exciting results, synopsized in the MIT Tech Review article "<a href="https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/" rel="nofollow noreferrer">Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at International Master Level</a>".  <em>(Giraffe's creator currently works as a <a href="https://matthewlai.ca/resume/" rel="nofollow noreferrer">Research Engineer in Machine Learning at DeepMind</a>.)</em> </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-26T21:43:26.573Z
Answers.LastActivityDate: 2017-10-27T21:15:08.040Z
Answers.LastEditDate: 2017-10-27T21:15:08.040Z
Answers.UserDisplayName: DukeZhou
Body: <p>I've been researching the following topic. Or rather, I would like to but I can't find anything because I'm not sure what to look for.</p>
  
  <p>I am interested weather there are some concepts or models that explain how humans (or cognitive systems in general) trade off <em>remembering</em> what to do in a particular situation versus <em>thinking</em> about the board state and devising a new solution. Consider the following example:</p>
  
  <p>A person plays chess. On their turn they must decide what to do. They could act according to one of the following extreme strategies:</p>
  
  <ol>
  <li>Remembering all possible board configurations and how the game ended (we'll call that <em>Memory</em>)</li>
  <li>Use the known set of rules to <em>simulate</em> the game in their mind and choose the optimal path (<em>Optimization</em>)</li>
  </ol>
  
  <p>I'd say the best choice is a trade off between these two. But how? When to choose one of the strategies?</p>
  
  <p>Is there a research field that is working on these kind of questions? What would I look for?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-27T05:42:15.803Z
Comments.Text: It is called [memoization](https://en.wikipedia.org/wiki/Memoization) and is not specific to AI
Comments.UserDisplayName: Basile Starynkevitch
Tags: <human-like><learning-algorithms><chess><combinatorial-games>
Title: Trading off "Memory" vs "Optimization"
UserDisplayName: hh32
ThreadText: # Trading off "Memory" vs "Optimization"
  
  (Asked by: username_0 on 2017-10-25)
  
  I've been researching the following topic. Or rather, I would like to but I can't find anything because I'm not sure what to look for.
  
  I am interested weather there are some concepts or models that explain how humans (or cognitive systems in general) trade off *remembering* what to do in a particular situation versus *thinking* about the board state and devising a new solution. Consider the following example:
  
  A person plays chess. On their turn they must decide what to do. They could act according to one of the following extreme strategies:
  
  1. Remembering all possible board configurations and how the game ended (we'll call that *Memory*)
  2. Use the known set of rules to *simulate* the game in their mind and choose the optimal path (*Optimization*)
  
  I'd say the best choice is a trade off between these two. But how? When to choose one of the strategies?
  
  Is there a research field that is working on these kind of questions? What would I look for?
  
  **Tags:** human-like, learning-algorithms, chess, combinatorial-games
  
  > **Comments:**
  > **username_1**: It is called [memoization](https://en.wikipedia.org/wiki/Memoization) and is not specific to AI  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2017-10-26. Score: 2 | Accepted answer
  
  The The [Oxford Companion to Chess](https://en.wikipedia.org/wiki/The_Oxford_Companion_to_Chess) has entries on only 700 named openings, and lists another 1327 opening variations in the index, and I wouldn't be surprised if someone out there had them all memorized. For an algorithm, however, storing that number of openings is trivial, and Chess algorithms traditionally made use of high-quality "game books" which are move-by-move records of chess games.
  
  The problem with [intractable models](https://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability), like chess is that they are unsolvable, so brute-force is not an option, and any decision on a move, whether "memory" or "optimality" based, at least in the context of current advances, are probabilistic. ([The exception is endgames](https://en.wikipedia.org/wiki/Endgame_tablebase) where the the problem becomes tractable, and [perfect play](https://en.wikipedia.org/wiki/Solved_game#Perfect_play) can be achieved.)
  
  Essentially, the memory of a board state is only a small piece of the puzzle because the unsolvability of the game means that particular board state from a recorded game, where that state led to a successful outcome, will not guarantee a similar result in a new game, because new, more optimal strategies can always emerge.
  
  Secondly, because of the extreme variation engendered by non-trivial games, it is extremely unlikely any current game would mirror the previous "memorized" game.
  
  It is my understanding that "memory" as you define has been utilized in Chess engines, accessing a database of previous games to evaluate a position and derive a good move, but the intractability of Chess in general makes this method sub-optimal, and it has been definitively supplanted by newer methods (machine learning, neural networks).
  
  In the famous Giraffe Chess paper, Matthew Lai states:
  
  > The job of the evaluation functions is to assign scores to positions statically (without looking ahead)
  
  But the method is highly nuanced and probabilistic. Nevertheless, I think you'll be interested because the problem presented in the paper is rooted in the human vs. AI play method issue:
  
  > ...the way computers play chess is very different from how humans play. While both humans and computers search ahead to predict how the game will go on,
  > humans are much more selective in which branches of the game tree to explore. Computers, on the other hand, rely on brute force to explore as many continuations as possible, even ones that will be
  > immediately thrown out by any skilled human... How can a human searching 3-5 positions per second be as strong as a computer searching 200
  > million positions per second? And is it possible to build even stronger chess computers than what
  > we have today, by making them more computationally efficient? Those are the questions this
  > project investigates.
  
  There is no simple answer to the trade-off question due to the complexity of the problem. But this is an area where tremendous advances are being made.
  
  I'd strongly recommend reading [Giraffe Chess (September, 2015)](https://arxiv.org/pdf/1509.01549.pdf) as a primer.
  It produced very exciting results, synopsized in the MIT Tech Review article "[Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at International Master Level](https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/)". *(Giraffe's creator currently works as a [Research Engineer in Machine Learning at DeepMind](https://matthewlai.ca/resume/).)*
  
  
  ---
  
  ### Answer by username_2 on 2017-10-25. Score: 2
  
  If you can remember everything and there's no randomisation in your outcome like chess, there is absolutely **no** reason not to do that. Anybody who can remember all the possible board configurations in chess, by definition plays perfect chess. A perfect player would never lose.
  
  Unfortunately, most practical problems can't be solved by brute-force, and that includes chess. **All** chess players learn general chess principles. Nobody could memorize all possible opening variations.
  
  If you can somehow memorize every possibility, why not? But can you?
  
  > **Comments:**
  > **username_0**: Of course you can not do that. But you can, let's say, memorize 10 prototypic configurations. And then starting from them you can go on and optimize it. The question is now: how much should you memorize optimally.   I'm just looking for a field that's working on these kind of questions.  
  
  ---
  
  