4 ms·

TD-gammon is a well known version of this technique (with 2 ply lookahead, vs a 1600 deep mcts) https://en.m.wikipedia.org/wiki/TD-Gammon https://en.m.wikipedia

TD-gammon is a well known version of this technique (with 2 ply lookahead, vs a 1600 deep mcts) https://en.m.wikipedia.org/wiki/TD-Gammon https://en.m.wikipedia.org/wiki/TD-Gammon Temporal difference learning was previously consider weak at 'tactical' games, ie ones with gamestates that require long chains of precise moves to improve position (like many checkmate scenarios in chess) . For anyone more familiar with this technique, is it clear how the mcts/checkpoint system overcomes this? How sensative is the system to the tuning params for those parts of the alg. Like is Go a particularly good candidate because of the ~400 play positions resulting in a (relatively) small tree seach requirement? (I kinda cant believe im saying that go has 'a small search tree'!) We us td learning for the ai in our game Race for the Galaxy, so it's neat to hear about possible avenues for improvement!

shmageggy 9y ago
Yeah it's not clear to me why temporal difference learning all of a sudden works so well here? Is it the case that nobody had really tried it for learning a policy for Go with a strong NN architecture? In the Methods they mention TD learning for value functions but I don't see anything about policies. edit: OK, they're calling it policy iteration as opposed to TD learning. I guess I don't get the difference.
- psb217 9y ago
  TD learning is, in some sense, a component of policy iteration. TD learning is about learning the value function for a given policy. In policy iteration you use a value function to decide how to update the policy for which the value function was estimated, and you iterate between the "learn value" and "update policy" steps. https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/node20.html https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelb...
davidkuhta 9y ago
Wow, that was a really deep and enjoyable Wikipedia rabbit hole journey. I hadn't heard of Temporal Difference before (though I was familiar with Q-learning). It was interesting to note that TD-Gammon improved with expert designed features. I wonder if this was simply related to the technology of the field as it stood over 20 years ago or some underlying categorization or complexity associated with the games themselves (backgammon being more favorable to human comprehension than Go in this case). > Even though TD-Gammon discovered insightful features on its own, Tesauro wondered if its play could be improved by using hand-designed features like Neurogammon's. Indeed, the self-training TD-Gammon with expert-designed features soon surpassed all previous computer backgammon programs. It stopped improving after about 1,500,000 games (self-play) using 80 hidden units. For others: Richard Sutton, one of the pioneers of TD makes his Reinforcement Learning: An Introduction textbook available for free on his website: http://incompleteideas.net/sutton/ http://incompleteideas.net/sutton/ (MIT Press also links to it)
- shmageggy 9y ago
  PSA: The new edition of Sutton/Barto has a nice discussion of (the original) AlphaGo in the back. http://incompleteideas.net/sutton/book/the-book-2nd.html http://incompleteideas.net/sutton/book/the-book-2nd.html
narrator 9y ago
It's my opinion that TD Gammon was solved in the 1990s because backgammon is a 1 dimensional board. It didn't need the convolutional techniques of the Go neural nets to gain insight into the game and could thus be solved by a traditional neural net.
greysphere 9y ago
After digging a bit deeper into the paper, it seems a key part of the new scheme is the NN is trained to help guide a deep/sparse tree search (as opposed to TD-gammons fully exhaustive 2-ply search). It's somewhat surprising to me that the simple win/loss is a strong enough signal to train this very 'intermediate step' in the algorithm - a spectacular result! It begs the question what other heuristic based algorithms would be improved by replacing a hand rolled non-optimal heuristic function with a NN?
- sjg007 9y ago
  It's estimating the probability of winning from the position based on what it has already seen. So basically it's a giant conditional probability distribution. Is it mistaken to interpret this as a bayesian network?
deleted 9y ago
[deleted]

shmageggy 9y ago

Yeah it's not clear to me why temporal difference learning all of a sudden works so well here? Is it the case that nobody had really tried it for learning a policy for Go with a strong NN architecture? In the Methods they mention TD learning for value functions but I don't see anything about policies. edit: OK, they're calling it policy iteration as opposed to TD learning. I guess I don't get the difference.

psb217 9y ago
TD learning is, in some sense, a component of policy iteration. TD learning is about learning the value function for a given policy. In policy iteration you use a value function to decide how to update the policy for which the value function was estimated, and you iterate between the "learn value" and "update policy" steps. https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/node20.html https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelb...

davidkuhta 9y ago

Wow, that was a really deep and enjoyable Wikipedia rabbit hole journey. I hadn't heard of Temporal Difference before (though I was familiar with Q-learning). It was interesting to note that TD-Gammon improved with expert designed features. I wonder if this was simply related to the technology of the field as it stood over 20 years ago or some underlying categorization or complexity associated with the games themselves (backgammon being more favorable to human comprehension than Go in this case). > Even though TD-Gammon discovered insightful features on its own, Tesauro wondered if its play could be improved by using hand-designed features like Neurogammon's. Indeed, the self-training TD-Gammon with expert-designed features soon surpassed all previous computer backgammon programs. It stopped improving after about 1,500,000 games (self-play) using 80 hidden units. For others: Richard Sutton, one of the pioneers of TD makes his Reinforcement Learning: An Introduction textbook available for free on his website: http://incompleteideas.net/sutton/ http://incompleteideas.net/sutton/ (MIT Press also links to it)

shmageggy 9y ago
PSA: The new edition of Sutton/Barto has a nice discussion of (the original) AlphaGo in the back. http://incompleteideas.net/sutton/book/the-book-2nd.html http://incompleteideas.net/sutton/book/the-book-2nd.html

narrator 9y ago

It's my opinion that TD Gammon was solved in the 1990s because backgammon is a 1 dimensional board. It didn't need the convolutional techniques of the Go neural nets to gain insight into the game and could thus be solved by a traditional neural net.

greysphere 9y ago

After digging a bit deeper into the paper, it seems a key part of the new scheme is the NN is trained to help guide a deep/sparse tree search (as opposed to TD-gammons fully exhaustive 2-ply search). It's somewhat surprising to me that the simple win/loss is a strong enough signal to train this very 'intermediate step' in the algorithm - a spectacular result! It begs the question what other heuristic based algorithms would be improved by replacing a hand rolled non-optimal heuristic function with a NN?

sjg007 9y ago
It's estimating the probability of winning from the position based on what it has already seen. So basically it's a giant conditional probability distribution. Is it mistaken to interpret this as a bayesian network?

deleted 9y ago

[deleted]