Feature Request: Randomized results.

[Meerkov]

This is probably out of scope, but I would like to see the following game formulation supported:

"Crazy Connect Four" is a variant of connect four.

• After each move, the current player rolls a six sided die.
• If the die comes up "6", then the player immediately takes another full turn, including die roll.

This MCTS implementation doesn't support randomized results of a move, as each move must map to exactly 1 outcome. Since the player doesn't control the outcome of the die, there is no way to model this without modifying the tree structure, because each choice of the player can lead to two possible child states.

Perhaps: Each node of the tree is instead a map<NodeHash, Node>. After calling do_move, take a hash of the state. If it doesn't exist, add it to the tree. Then navigate to the appropriate node.

[PetterS]

Can it be done without any performance hit or significantly increased complexity?

I will most likely not implement this, as I am (whenever I work on MCTS at all) is more focused on the even more general case of games with imperfect information (information sets etc.).

Feel free to send a PR if you come up with something good!

[Meerkov]

I felt a FR for imperfect information would require this refactoring first.

You would need to do at least a few extra operations, because you would need to do minimum of 1 hashing operation and 1 comparison whenever performing a move that is within the tree. For games of perfect information it's possible the overhead is insignificant.

[theKGS]

PetterS: It will require adding a check to detect if a node is a random node or not. This could be a boolean stored in the node. When the algorithm detects a random node, instead of doing traversal with UCT you simply pick a child at random (regardless of if it has been visited before or not), probably using a weight vector created in the State.

You must also change the do_random_move function IF you want your randomness support to make use of weight vectors.

The only notable performance hit occurs when traversing over random nodes. Traversing normal nodes cost only a simple if statement. (you need to see if the node is random or not)

I'd tell you to look at my own code, but alas it is terrible and outdated.

[PetterS]

Perhaps a randomness can be a player on its own? Then the code needs to support several players but that should not be too hard….

[theKGS]

PetterS: Yes that's how I did it. Internally my MCTS implementation deals with player IDs indexed from 0 to n-1 where n is the number of players. I also had a special rule that a negative player ID in a node meant that the choice at that point was entirely random, then I wrote specific rules to manage the that within the tree policy function.

On monday I'll probably have added back support for stochastic games in my own implementation if you want an example of how it can be implemented.

[PetterS]

That’s cool. I won’t be working on this, but if you or someone produces a
nice pull request I will likely merge it.

On Sat, Jul 16, 2016 at 12:04 AM theKGS notifications@github.com wrote:

PetterS: Yes that's how I did it. Internally my MCTS implementation deals
with player IDs indexed from 0 to n-1 where n is the number of players. I
also had a special rule that a negative player ID in a node meant that the
choice at that point was entirely random, then I wrote specific rules to
manage the that withing the tree policy function.

On monday I'll probably have added back support for stochastic games in my
own implementation if you want an example of how it can be implemented.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#6 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAvI0QBC4xtVft5HWn00NrJ7bh3eCxU8ks5qWAP0gaJpZM4HbbnC
.