5
$\begingroup$

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 (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).

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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 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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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). $\endgroup$
    – dshin
    Commented Dec 30, 2016 at 12:22
  • $\begingroup$ 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. $\endgroup$
    – dshin
    Commented Dec 30, 2016 at 13:12
  • $\begingroup$ 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. $\endgroup$
    – BlindKungFuMaster
    Commented Dec 30, 2016 at 19:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – dshin
    Commented Dec 30, 2016 at 19:29
  • $\begingroup$ 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. $\endgroup$
    – BlindKungFuMaster
    Commented Dec 30, 2016 at 19:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .