6
$\begingroup$

This question has come from my experiment of building a cnn based tic-tac-toe game that I'm using as a beginner machine learning project. The game works purely on policy networks, more specifically -

  1. During training, at the end of each game, it trains itself on the moves the winner/drawer made for each board position. That is, its training data consists of board positions and the moves made by the winning player on each position.
  2. While playing, it predicts its own moves solely based on that training (that is, it predicts what move would a winning player make with the current board). It doesn't use any type of search or value networks.

I'm seeing that if I train it against a player that predicts the perfect move (using a recursive search) every time, the AI gets good at drawing about 50% games. But if I train it against a player that makes random moves, it doesn't get better at all.

Wouldn't one expect it to learn well (even if slower) regardless of the level of its opponent? Since each game ends in a draw or win for one player, shouldn't it be able to extract features for the winning/drawing strategies even when learning from random players? Or does this behavior mean that the model is not optimal?

Improve this question
$\endgroup$
5
  • $\begingroup$ Does your current CNN utilize "monte carlo"? $\endgroup$
    – DukeZhou
    Feb 26, 2017 at 1:56
  • 1
    $\begingroup$ No, no search at all. It's purely policy based - deciding its next based on what winners of its training games have made in similar situations. $\endgroup$
    – Achilles
    Feb 26, 2017 at 4:10
  • $\begingroup$ I think a problem you may be facing with a random player is that a your game consists of many moves, and a winning player does not make only winning moves. In your example, your moves are random, and the fact that your random player wins against another (random, initially) CNN player is, well, random, too. So I find it intuitive to say that there is not information to gain from observing a random player, and no way to get "better" than it. This would be different in a game with fewer moves, where a good move is more closely related with winning, such as in tic-tac (2x2 tic-tac-toe). $\endgroup$
    – bers
    Sep 26, 2018 at 8:40
  • $\begingroup$ (I am aware that you cannot lose a tic-tac if you make the first move, but you can draw - so by observing a random player, your policy-based CNN should at least be able to learn how to not draw when making the first move.) $\endgroup$
    – bers
    Sep 26, 2018 at 8:43
  • $\begingroup$ Ultimately, in tic-tac-toe and more complex games, I would expect that you would need some way to measure the goodness of an individual position, and by extension, measure the goodness of a move to learn only from good moves. $\endgroup$
    – bers
    Sep 26, 2018 at 8:44

1 Answer 1

Reset to default
1
$\begingroup$

(I'd leave this in the comments but sadly I can't.)

Here's a great paper (leveraging formal game theory) in which "players" make strategic choices based on each event ("move") and an algorithm calculates the best strategy for all players based on each player's abilities throughout the multi-stage "game". So instead of learning from winning and predicting what the next perfect move the player thinks (based off of learning) will lead to a "win", the player calculates an optimal strategy and moves to win the game itself over multiple moves.

https://users.ece.cmu.edu/~youzhib/paper/bao2017csf.pdf

Note: This paper deals with cyber war games so is heavily tilted towards that domain, but if you take away the game theoretics and concept of strategy over a multi-stage game like ti-tac-toe, you should be able to improve your overall outcomes. That being said, how the model would accommodate a random "player" with random moves would be interesting to see.

Improve this answer
$\endgroup$

You must log in to answer this question.

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