|
Post by steadyeddie on Dec 18, 2016 6:13:58 GMT -8
At the most basic level my Nodes just form a tree which is the T in MCTS.
It escaped my notice for some time that in some games (but by no means all) a position can be reached from more than other node. I've got no idea how important it is, but I figured what I needed to do was cache Node from a hash of the position, and save memory. What you end up with after you do this, is not a Tree, but a Directed Acyclic Graph. So the T is, in fact, bogus.
I don't have edges, but i know people do. Instead I'm just storing references to the children, alongside the list of moves.
It took me a while to realise I needed to store the score for both sides, as opposed to just my score, so I could simulate the other player playing the move that is best for them. That's needed for multi-player games, and for non zero-sum games.
|
|
|
Post by Andrew Rose on Jan 27, 2017 13:32:10 GMT -8
Sometimes, the nature of the graph depends on whether you choose to ignore "environment" propositions - especially step counters, which can make otherwise identical states appear different. Removing these can further cut down on the number of states, but at the cost of perhaps not knowing whether the game is about to end. In puzzles, that's a simplification that Sancho definitely makes. I can't remember what we do for 2+ player games.
|
|