Outwitters AI?

[awpertunity]

How would a minimax search even work? Before that you would somehow need a solid metric for giving a score to every possible state of the game, no? That's the main challenge, then searching for a certain window of turns is easy enough.

I think even the fog of war wouldn't be as big of an issue using some sort of hidden markov model.

[Ganwell]

well, thats the beauty of mcts, fog of war is no problem. its a statistical method, it will simulate both players and during expansion it will have a lot of possible states for the opponent (because of fow). but the same UCT policy (reversed) is applied to these unknown states. it not actual minmax its uct/reverse-uct or how ever you'd like to call it. mcts doesn't need metric just policy to bias random selection.

[awpertunity]

(07-19-2014 12:03 AM)Ganwell Wrote:  well, thats the beauty of mcts, fog of war is no problem. its a statistical method, it will simulate both players and during expansion it will have a lot of possible states for the opponent (because of fow). but the same UCT policy (reversed) is applied to these unknown states. it not actual minmax its uct/reverse-uct or how ever you'd like to call it. mcts doesn't need metric just policy to bias random selection.

I don't know what mcts is, but if I'm understanding that correctly it sounds like 2 bots might be able to play each other properly. But if a bot is using its statistical model to model how a human plays its perception will probably be way off.

[Ganwell]

(07-19-2014 02:47 AM)awpertunity Wrote:  I don't know what mcts is, but if I'm understanding that correctly it sounds like 2 bots might be able to play each other properly. But if a bot is using its statistical model to model how a human plays its perception will probably be way off.

That might be a problem. The prototype will hopefully show such problems. Since it will consider good moves the as well as bad ones because it balances exploration and exploitation (good moves), I don't fear that problem too much. My biggest concern: not finding terminal states at all because if you don't systematically attack you can play ow for ever. By default mcts is heuristic free, if I don't find terminal states I have to add heuristic to bias the search... a lot more work.

http://en.wikipedia.org/wiki/Monte-Carlo_tree_search

[awpertunity]

How can there be no heuristic anyway? Monte Carlo is just a method of choosing which states to search but the algorithm still needs a way to compare the searched states against each other..

[Ganwell]

Well you simulate random moves till you reach terminal states then you select the node that leads to the most wins (very simplified), it is great since you can always stop when time is up and you can add heuristics if needed. Mcts is the algorithm that lead to a breakthrough in computer Go. The wiki link gives a great overview.

[awpertunity]

Oh wow. Yeah I think that would take way too long to find any terminal state at all with no heuristics. And the modeling of the opponent becomes really important too for it to be any good.