https://wiki.lesswrong.com/index.php?title=Search_space&feed=atom&action=historySearch space - Revision history2022-08-19T14:59:24ZRevision history for this page on the wikiMediaWiki 1.31.12https://wiki.lesswrong.com/index.php?title=Search_space&diff=9480&oldid=prevAlex Altair: Created page with "A decision tree. Each layer shows the search space for that iteration. A '''search space''' is the set or domain through which an algor..."2012-06-28T08:42:25Z<p>Created page with "<a href="/wiki/File:SearchTree.png" title="File:SearchTree.png">360px|thumb|right|A decision tree. Each layer shows the search space for that iteration.</a> A '''search space''' is the set or domain through which an algor..."</p>
<p><b>New page</b></p><div>[[File:SearchTree.png|360px|thumb|right|A decision tree. Each layer shows the search space for that iteration.]]<br />
<br />
A '''search space''' is the set or domain through which an algorithm searches. In computer science, the space may be a well-defined and finite data structure. Or, as in decision theory, it may be a vast and possibly infinite set whose elements need to be individually generated during the search.<br />
<br />
For example, in the game Guess Who, the players each begin with a set of character cards from which to choose. They then take turns asking yes-or-no questions about the other player's choice. The set of cards is the search space for this game. This set is finite and known ahead of time.<br />
<br />
In chess, the search space is much more complicated. The search space is the set of all possible valid moves. For a given turn the space is finite, but the set of all possible games is infinite. Since the player is trying to maximize the probability of winning, they must search through many turns. These possibilities must be generated during the search.<br />
<br />
In the context of AI, the search space is used to define the [[optimization power]] of the AI. [[Eliezer Yudkowsky]] defines optimization power as follows. If <math>S</math> is the search space and <math>S_+</math> is the set of options better or equal to the chosen one, the the optimization power is<br />
<br />
<math>-log\frac{S_+}{S}</math>.<br />
<br />
==Blog posts==<br />
*[http://lesswrong.com/lw/va/measuring_optimization_power/ Measuring Optimization Power]<br />
*[http://lesswrong.com/lw/aq9/decision_theories_a_less_wrong_primer/ Decision Theories: A Less Wrong Primer]<br />
*[http://lesswrong.com/lw/dbj/backward_reasoning_over_decision_trees/ Backward Reasoning Over Decision Trees]<br />
<br />
==See also==<br />
*[[Decision theory]]<br />
*[[Optimization process]]</div>Alex Altair