a futarchy experiment

Previous topic - Next topic

gwern

Quote from: koeppelmann on September 11, 2014, 07:30:28 PM
Of course, but not with Monte Carlo tree search. https://en.wikipedia.org/wiki/Monte_Carlo_tree_search It is a heuristic that does not converge to the perfect game.

Yes, it does, if you think about how it works, it converges on perfect play, and your link says so: "it has been proven that the evaluation of moves in MCTS converges to the minimax evaluation" ("with "average" back-up and UCT move selection, the root evaluation converges to the "min-max" evaluation when the number of simulations goes to infinity").

koeppelmann

Quote from: gwern on September 12, 2014, 03:38:02 PM
Quote from: koeppelmann on September 11, 2014, 07:30:28 PM
Of course, but not with Monte Carlo tree search. https://en.wikipedia.org/wiki/Monte_Carlo_tree_search It is a heuristic that does not converge to the perfect game.

Yes, it does, if you think about how it works, it converges on perfect play, and your link says so: "it has been proven that the evaluation of moves in MCTS converges to the minimax evaluation" ("with "average" back-up and UCT move selection, the root evaluation converges to the "min-max" evaluation when the number of simulations goes to infinity").

Well - a Monte Carlo tree search consist of two parts. The tree search and a Monte Carlo simulation. A tree is build up until a certain point. Now this nodes are evaluated by a monte carlo simulation where stones are placed randomly until the board could be evaluated. Now we have two options to spend additional computer power. Expanding the tree search and/or expanding the monte carlo simulation. If we expand the tree search to all the leaves of the game tree we basically end up with a min/max approach since the monte Carlo simulation part is not necessary. However, if you use the additional computing power on more monte carlo simulations it does not converge always.
The part your cited is only true for games with random turn order - that is obv. not the case for Go.

"It converges to perfect play (as k tends to infinity) in board filling games with random turn order, for instance in Hex with random turn order"

koeppelmann

I am curious what subsidy Robin Hanson thinks it necessary to get such a market working:

https://twitter.com/robinhanson/status/510561329195667456

zack

There are a little over 1000 professional go players: http://www.lifein19x19.com/forum/viewtopic.php?f=13&t=580

over 90% seem to need money in a bad way: http://www.lifein19x19.com/forum/viewtopic.php?f=13&t=8396

The cost to learn to use prediction markets is pretty high. They are complex tools.
The cost to learn cryptocurrency is also very high.
The cost to convert Yuan/Won/Yen -> bitcoin -> truthcoin is very high. Especially before we build the truthcoin exchange.

If we were to give free truthcoins to every single professional go player, it would lower the cost a TON.
These people are very comfortable competing for prize money in high-pressure environments.

gwern

Quote from: koeppelmann on September 12, 2014, 07:55:03 PM
Now we have two options to spend additional computer power. Expanding the tree search and/or expanding the monte carlo simulation. If we expand the tree search to all the leaves of the game tree we basically end up with a min/max approach since the monte Carlo simulation part is not necessary. However, if you use the additional computing power on more monte carlo simulations it does not converge always.

Well, yeah, that's the whole point of MCTS: it provides an approximation of value at the leaves when you can no longer explore the game tree more deeply and outperforms min/max that way. But why would you spend indefinitely more computing power on just the simulation part...? Pointing that out is about as insightful as saying 'imagine a MCTS which only explored one ply deep, clearly it would not do well'; well sure if we assume the most idiotic possible interpretation...