Answers.Body: <p>Human chess and go experts clearly use evaluation functions. They do come up with moves that look sensible without evaluating the board position, but to validate these candidate moves they evaluate board positions that occur at the end of the variations they calculate. Pretty similar to AlphaGo. </p>
  
  <p>Inputting two board states and outputting a preference is a (much) more complex task than mapping one board state into the real numbers. And it gives you less information. So its a lose-lose choice. (I did try something very similar and it didn't work at all. The reason is that you didn't just double the input size, rather you made the input space quadratically bigger.)</p>
  
  <p>If you compare two board states that differ just by one move, then your input space doesn't quite explode as much, but you have to do a ton of comparisons to make a decision. The logical choice would be to output a preference distribution over all possible moves - but that's exactly what AlphaGo does in its policy network. There is also an <a href="https://arxiv.org/abs/1412.3409" rel="nofollow noreferrer">earlier paper</a> which trained a network to predict expert moves, which comes down to the same thing. And yes, both these networks play quite strongly without any search or board evaluation. But nowhere near AlphaGo-level.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T12:22:31.933Z
Answers.Text: Humans *sometimes* use evaluation functions. But not always. To use a trivial example in go, consider a suicide move of placing a stone directly in an opponent's single-space eye. This move is strictly dominated by the option of passing the turn. I can thus rule out the move even without looking at the rest of the board. In other words, if f() is an implicit evaluation function, I'm able to reason that f(A)>f(B), without actually calculating f(A) or f(B).
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T13:12:33.243Z
Answers.Text: To provide another illustration: imagine two board positions, A and B, where A is clearly-but-slightly superior to B. If I ask 100 experts which is superior, all 100 will say A. But if I ask half of them to estimate A's winning probability, and the other half to estimate B's winning probability, and they create their estimates independently, I am likely to get overlapping distributions. Forcing them to independently map board states to numbers effectively handicaps their ability to compare positions.
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T19:20:02.087Z
Answers.Text: As long as every expert maps A to a higher probability than B, there is no handicap at all. And of course the ability to consciously compare two positions might come from an unconscious independent mapping of both.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T19:29:52.070Z
Answers.Text: Of course if you ask one expert to compare A and B, he will rate A>B. But if you ask that expert to rate A, and tell him, "by the way, I have in this sealed envelope the true win probability of B, and after you rate A I'm going to open up the envelope and choose between A and B by comparing the numbers", you've made the expert's life considerably more difficult.
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T19:43:48.407Z
Answers.Text: Yes, because the expert isn't an expert in assigning accurate probabilities. He is an expert at making decisions. You ask him to do something he didn't train to do. Assigning accurate probabilities isn't relevant to playing well, assigning consistent probabilities is.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T19:50:15.703Z
Answers.Text: Yes, that's exactly my point. For humans, comparing options is an easier computational task than assigning accurate probabilities to the options. Accurate probability estimates are sufficient but not necessary for optimal decision making. Demanding that the expert perform his comparisons on the real number line handicaps him. So demanding the same of our AI systems might be a handicap as well.
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T20:04:45.757Z
Answers.Text: To be clear, it is a handicap when we force the mappings of A and B to the real number line to be made *independently*. That's why in my illustration I have half the experts estimate A and the other half estimate B without getting to talk to each other. Perhaps it might make sense to think of a "comparison" as a joint-estimate-vector with an uncertainty covariance matrix U; the handicap can be interpreted as restrictions on U.
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T21:12:19.417Z
Answers.Text: I don't yet see why comparing options would be an easier computational task than assigning accurate probabilities for humans. Humans are better at the former, because the train for it, not because it is easier. In fact I'm pretty sure that chess grandmasters are quite good at predicting engine scores, because they work with engines everyday. And that's pretty similar to probabilities.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T21:17:02.947Z
Answers.Text: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/50968/discussion-between-dshin-and-blindkungfumaster).
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-08T07:12:45.443Z
Answers.Text: @dshin Very interesting! Concerning "computational savings versus applying independent evaluations" from the discussion: There are heuristics in game engines giving preference to moves which were shown to be good in other parts of the search tree. This is like to "go through the kingside defensive lines again [... but ...] a lot faster" (again from the discussion). No idea if Alpha Go uses / could use such heuristics. I guess, my comment is only loosely related to your question, but aims at the same goal.
Answers.UserDisplayName: maaartinus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-30T07:30:54.553Z
Answers.LastActivityDate: 2016-12-30T07:30:54.553Z
Answers.UserDisplayName: BlindKungFuMaster
Body: <p>Fundamentally, a game-playing AI must solve the problem of choosing the best action from a set of possible actions.</p>
  <p>Most existing game AI's, such as AlphaGo, do this by using an <strong>evaluation function</strong>, which maps game states to real numbers. The real number typically can be interpreted as a monotonic function of a winning probability estimate. The best action is the one whose resultant state yields the highest evaluation.</p>
  <p>Clearly, this approach can work well. But it violates one of <a href="https://books.google.com/books?id=N_-5VRWai84C&amp;pg=PA477&amp;lpg=PA477&amp;dq=%22When%20solving%20a%20problem%20of%20interest,%20do%20not%20solve%20a%20more%20general%20problem%20as%20an%20intermediate%20step.%20Try%20to%20get%20the%20answer%20that%20you%20really%20need%20but%20not%20a%20more%20general%20one.%22&amp;source=bl&amp;ots=ReHvsikLSY&amp;sig=WkN0ETtVyEXlgkWWQoiY4b-qWxE&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwj6m6z-g5_OAhWGpB4KHf54DYcQ6AEIKTAC#v=onepage&amp;q=%22When%20solving%20a%20problem%20of%20interest%2C%20do%20not%20solve%20a%20more%20general%20problem%20as%20an%20intermediate%20step.%20Try%20to%20get%20the%20answer%20that%20you%20really%20need%20but%20not%20a%20more%20general%20one.%22&amp;f=false" rel="nofollow noreferrer">Vladimir Vapnik's imperatives</a> (in his book &quot;Estimation of Dependences Based on Empirical Data&quot;): &quot;<em>When solving a problem of interest, do not solve a more general problem as an intermediate step.</em>&quot; In fact, he specifically states as an illustration of this imperative,</p>
  <blockquote>
  <p>Do not estimate predictive values if your goal is to act well. (<em>A good strategy of action does not necessarily rely on good predictive ability.</em>)</p>
  </blockquote>
  <p>Indeed, human chess and go experts appear to heed his advice, as they are able to act well without using evaluation functions.</p>
  <p>My question is this: <strong>has there has been any recent research aiming to solve games by learning to compare decisions directly, without an intermediate evaluation function</strong>?</p>
  <p>To use AlphaGo as an example, this might mean training a neural network to take <strong>two</strong> (similar) board states as input and output a choice of which one is better (a classification problem), as opposed to a neural network that takes <strong>one</strong> board state as input and outputs a winning probability (a regression problem).</p>
  
Tags: <reference-request><game-ai><chess><go><evaluation-functions>
Title: Can games be solved without an evaluation function?
UserDisplayName: dshin
ThreadText: # Can games be solved without an evaluation function?
  
  (Asked by: username_0 on 2016-12-30)
  
  Fundamentally, a game-playing AI must solve the problem of choosing the best action from a set of possible actions.
  
  Most existing game AI's, such as AlphaGo, do this by using an **evaluation function**, which maps game states to real numbers. The real number typically can be interpreted as a monotonic function of a winning probability estimate. The best action is the one whose resultant state yields the highest evaluation.
  
  Clearly, this approach can work well. But it violates one of [Vladimir Vapnik's imperatives](https://books.google.com/books?id=N_-5VRWai84C&pg=PA477&lpg=PA477&dq=%22When%20solving%20a%20problem%20of%20interest,%20do%20not%20solve%20a%20more%20general%20problem%20as%20an%20intermediate%20step.%20Try%20to%20get%20the%20answer%20that%20you%20really%20need%20but%20not%20a%20more%20general%20one.%22&source=bl&ots=ReHvsikLSY&sig=WkN0ETtVyEXlgkWWQoiY4b-qWxE&hl=en&sa=X&ved=0ahUKEwj6m6z-g5_OAhWGpB4KHf54DYcQ6AEIKTAC#v=onepage&q=%22When%20solving%20a%20problem%20of%20interest%2C%20do%20not%20solve%20a%20more%20general%20problem%20as%20an%20intermediate%20step.%20Try%20to%20get%20the%20answer%20that%20you%20really%20need%20but%20not%20a%20more%20general%20one.%22&f=false) (in his book "Estimation of Dependences Based on Empirical Data"): "*When solving a problem of interest, do not solve a more general problem as an intermediate step.*" In fact, he specifically states as an illustration of this imperative,
  
  > Do not estimate predictive values if your goal is to act well. (*A good strategy of action does not necessarily rely on good predictive ability.*)
  
  Indeed, human chess and go experts appear to heed his advice, as they are able to act well without using evaluation functions.
  
  My question is this: **has there has been any recent research aiming to solve games by learning to compare decisions directly, without an intermediate evaluation function**?
  
  To use AlphaGo as an example, this might mean training a neural network to take **two** (similar) board states as input and output a choice of which one is better (a classification problem), as opposed to a neural network that takes **one** board state as input and outputs a winning probability (a regression problem).
  
  **Tags:** reference-request, game-ai, chess, go, evaluation-functions
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2016-12-30. Score: 3
  
  Human chess and go experts clearly use evaluation functions. They do come up with moves that look sensible without evaluating the board position, but to validate these candidate moves they evaluate board positions that occur at the end of the variations they calculate. Pretty similar to AlphaGo.
  
  Inputting two board states and outputting a preference is a (much) more complex task than mapping one board state into the real numbers. And it gives you less information. So its a lose-lose choice. (I did try something very similar and it didn't work at all. The reason is that you didn't just double the input size, rather you made the input space quadratically bigger.)
  
  If you compare two board states that differ just by one move, then your input space doesn't quite explode as much, but you have to do a ton of comparisons to make a decision. The logical choice would be to output a preference distribution over all possible moves - but that's exactly what AlphaGo does in its policy network. There is also an [earlier paper](https://arxiv.org/abs/1412.3409) which trained a network to predict expert moves, which comes down to the same thing. And yes, both these networks play quite strongly without any search or board evaluation. But nowhere near AlphaGo-level.
  
  > **Comments:**
  > **username_0**: Humans *sometimes* use evaluation functions. But not always. To use a trivial example in go, consider a suicide move of placing a stone directly in an opponent's single-space eye. This move is strictly dominated by the option of passing the turn. I can thus rule out the move even without looking at the rest of the board. In other words, if f() is an implicit evaluation function, I'm able to reason that f(A)>f(B), without actually calculating f(A) or f(B).  
  > **username_0**: To provide another illustration: imagine two board positions, A and B, where A is clearly-but-slightly superior to B. If I ask 100 experts which is superior, all 100 will say A. But if I ask half of them to estimate A's winning probability, and the other half to estimate B's winning probability, and they create their estimates independently, I am likely to get overlapping distributions. Forcing them to independently map board states to numbers effectively handicaps their ability to compare positions.  
  > **username_1**: As long as every expert maps A to a higher probability than B, there is no handicap at all. And of course the ability to consciously compare two positions might come from an unconscious independent mapping of both.  
  > **username_0**: Of course if you ask one expert to compare A and B, he will rate A>B. But if you ask that expert to rate A, and tell him, "by the way, I have in this sealed envelope the true win probability of B, and after you rate A I'm going to open up the envelope and choose between A and B by comparing the numbers", you've made the expert's life considerably more difficult.  
  > **username_1**: Yes, because the expert isn't an expert in assigning accurate probabilities. He is an expert at making decisions. You ask him to do something he didn't train to do. Assigning accurate probabilities isn't relevant to playing well, assigning consistent probabilities is.  
  > **username_0**: Yes, that's exactly my point. For humans, comparing options is an easier computational task than assigning accurate probabilities to the options. Accurate probability estimates are sufficient but not necessary for optimal decision making. Demanding that the expert perform his comparisons on the real number line handicaps him. So demanding the same of our AI systems might be a handicap as well.  
  > **username_0**: To be clear, it is a handicap when we force the mappings of A and B to the real number line to be made *independently*. That's why in my illustration I have half the experts estimate A and the other half estimate B without getting to talk to each other. Perhaps it might make sense to think of a "comparison" as a joint-estimate-vector with an uncertainty covariance matrix U; the handicap can be interpreted as restrictions on U.  
  > **username_1**: I don't yet see why comparing options would be an easier computational task than assigning accurate probabilities for humans. Humans are better at the former, because the train for it, not because it is easier. In fact I'm pretty sure that chess grandmasters are quite good at predicting engine scores, because they work with engines everyday. And that's pretty similar to probabilities.  
  > **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/50968/discussion-between-username_0-and-username_1).  
  > **username_2**: @username_0 Very interesting! Concerning "computational savings versus applying independent evaluations" from the discussion: There are heuristics in game engines giving preference to moves which were shown to be good in other parts of the search tree. This is like to "go through the kingside defensive lines again [... but ...] a lot faster" (again from the discussion). No idea if Alpha Go uses / could use such heuristics. I guess, my comment is only loosely related to your question, but aims at the same goal.  
  
  ---
  
  