Humans are better at playing the board game go than the best computers in the world by 3 stones.
A go game generally has less than 200 moves, each move has about 300 choices to choose between.
If we asked the prediction market which move is best, and each move was well funded, we could play the best game of go that has ever been played in history. We could be multiple stones better than the best player in the world.
This would require about 200 separate prediction markets, each with about 300 states.
This experiment would solve 2 problems at once. 1) distributing some initial coins. 2) bringing publicity to our project.
We would give free coins to all the best go players in the world before the game, that way the best go players in the world will be the ones making bets on the game.
If a prediction market can be better at playing go than any individual human, maybe it can be better for government too.
Good idea!
But I think the question is wrong. The question could not be - which move is best, because this can not be answered. The question can only be: will this move lead to victory, right? But if this is the case - all predictions on the other moves will be refunded? (Or will they loose the money?) Anyways, in both scenarios every player tries to pick the move of the majority - and than the incentive structure is broken, isn't it?
(But maybe I just need to read the futarchy proposal)
Quote from: zack on September 09, 2014, 02:30:11 AM
If we asked the prediction market which move is best, and each move was well funded, we could play the best game of go that has ever been played in history.
Existing Go AIs are embarassingly-parallel Monte Carlo trees with anytime properties where the more computing power you invest the better each move is, and the ratings are based on relatively quick matches (maybe an hour per move at most?); so if anyone cared about creating the best game ever, all you have to do is is buy something like a 64-core machine and run two copies against each other for a year or three. That no one has done this, or has repeated 'Kasparov vs the Internet', suggests there's not a whole lot of interest in such games. As Hanson might 'gameplaying isn't about winning'.
Quote from: gwern on September 09, 2014, 03:41:54 PM
or has repeated 'Kasparov vs the Internet', suggests there's not a whole lot of interest in such games
That chess game was played by plurality vote (which works kinda like democracy or majority rule). It is a FAR less effective means of aggregating information from a crowd.
LMSR Prediction markets (like truthcoin), as far as I am aware, are the most effective way of aggregating information from a crowd.
Quote from: gwern on September 09, 2014, 03:41:54 PM
Existing Go AIs are
Teams of one person with an AI are much better at go than either humans or AI alone. I suspect that such teams will be the biggest winners in this experiment.
Quote from: gwern on September 09, 2014, 03:41:54 PM
Existing Go AIs are embarassingly-parallel Monte Carlo trees
I don't think games played with monte carlo trees are very interesting. I don't get any better by watching computers do this, because I am incapable of such complex calculation.
Watching people bet would be incredibly interesting to me because on every turn you get a weighted graph of the entire board. You can numerically compare how good every move on the board is based on the price of the shares.
Quote from: koeppelmann on September 09, 2014, 03:18:56 PM
all predictions on the other moves will be refunded?
Paul probably explains it best: https://github.com/psztorc/Truthcoin/blob/master/docs/2_PM_Types.pdf
Here is my attempt at explaining:
The board is 19x19, so there are 361 spots to play on.
In the end, you will either win, or lose.
So there exist 361*2=722 states. You can by shares in any of these states.
If the state you buy shares in never happens, then those shares are worthless. no refund.
If you think the best move is move A, you should probably buy shares in the state where he plays A, and then wins the game.
If the player doesn't play A, then your money would disappear.
So usually people hedge their bets. You would bet that A wins the game, and you would purchase 360 more states. You would bet that every other move leads to losing the game.
Usually there are multiple good moves on the board, maybe up to 10. So for each good move, you bet that it leads to a win, and for each bad move, you bet that it leads to a lose.
It is important to consider price too. If a good move already has a really high price, then maybe it is not worth purchasing. Your expected winnings are very small, and your money would end up getting locked till the end of the game. There is a incentive to save your money for the bets that will make the most money. Being able to see which moves are under-valued or over-valued is profitable.
Quote from: koeppelmann on September 09, 2014, 03:18:56 PM
Anyways, in both scenarios every player tries to pick the move of the majority - and than the incentive structure is broken, isn't it?
A debate on this topic https://www.youtube.com/watch?v=Tb-6ikXdOzE
I agree with Hanson's and Friedman's perspectives.
If the majority was doing something stupid, it is a massive opportunity to make money.
If the majority buys the winning state of a bad move, then it is in everyone's monetary interest to buy losing states of that move until the price gets fixed.
We need the shares to have a price close to 50/50 for the most important moves on the board.
If we are winning the game by a lot, the price will become 100/0 on every move.
If we are losing the game by a lot, the price will become 0/100 on every move.
So we may need to switch from this question: "Will we win?" to this question: "Will we win by 2 or more stones?" or this one: "Will we lose by 1 or more stones?"
Quote from: gwern on September 09, 2014, 03:41:54 PM
Quote from: zack on September 09, 2014, 02:30:11 AM
If we asked the prediction market which move is best, and each move was well funded, we could play the best game of go that has ever been played in history.
Existing Go AIs are embarassingly-parallel Monte Carlo trees with anytime properties where the more computing power you invest the better each move is, and the ratings are based on relatively quick matches (maybe an hour per move at most?); so if anyone cared about creating the best game ever, all you have to do is is buy something like a 64-core machine and run two copies against each other for a year or three. That no one has done this, or has repeated 'Kasparov vs the Internet', suggests there's not a whole lot of interest in such games. As Hanson might 'gameplaying isn't about winning'.
Actually the capability of Monte Carlo tree search are provable limited. Infinite computing power would not lead in all cases to the perfect game.
Quote from: zack on September 09, 2014, 04:37:26 PM
If the state you buy shares in never happens, then those shares are worthless. no refund.
Thanks for the links, Zack. But from what I have read a two dimensional would be used. For each move a binary decision is sold (could be even better a scaled claim with the number of stones won or lost as "n") Now all this market are traded and the move where the winning shares have the highest price will be chosen. All other trades on the moves that did not where chosen would get reverted (refunded).
Quote from: zack on September 09, 2014, 04:09:09 PM
That chess game was played by plurality vote (which works kinda like democracy or majority rule). It is a FAR less effective means of aggregating information from a crowd.
LMSR Prediction markets (like truthcoin), as far as I am aware, are the most effective way of aggregating information from a crowd.
The efficiency of aggregation is irrelevant. People don't care enough about such matches to make them good PR.
Quote
Teams of one person with an AI are much better at go than either humans or AI alone. I suspect that such teams will be the biggest winners in this experiment.
Advanced chess is already on the outs: the chess AIs have gotten so good that you need to be pretty much a grandmaster to add much of anything. In another decade I suspect it'll be toast.
Quote
I don't think games played with monte carlo trees are very interesting. I don't get any better by watching computers do this, because I am incapable of such complex calculation.
Watching people bet would be incredibly interesting to me because on every turn you get a weighted graph of the entire board. You can numerically compare how good every move on the board is based on the price of the shares.
You aren't capable of the complex calculation of grandmaster play either, so I'm not sure why that would matter. And you can numerically compare the value even more precisely by looking at an AI's estimate for each move.
Quote from: koeppelmann on September 09, 2014, 09:46:44 PM
Actually the capability of Monte Carlo tree search are provable limited. Infinite computing power would not lead in all cases to the perfect game.
Cite? My understanding was that in the limit it searched the full game tree and so played optimally.
When I play a game, I'm usually trying to think several moves ahead. So if I had 300 choices to make on one turn, and so did my opponent, I would almost need to bet on Move_6 conditional on opponent's_Move_5 conditional on Move_5 conditional on opponent's_Move_4 conditional on Move_4 conditional on opponent's_Move_3...which would be [300^6 = 7.29e+14] * 2 (win-lose) = 1.458e+15 states.
Which would just be silly.
However, you could have an expert Go player "phone a market" when they are lost on a move. That might at least be entertaining.
For 'easy' PR, we might just steal the popular new items of the day: Where is that Malaysian plane? What will happen with Ukraine? Politics/Sports. etc.
Quote from: psztorc on September 10, 2014, 02:20:13 PM
For 'easy' PR, we might just steal the popular new items of the day: Where is that Malaysian plane? What will happen with Ukraine? Politics/Sports. etc.
Yes, particularly sports. I have zero interest in professional sports, but I can't deny: there are a *lot* of people who are *very* interested in Bitcoin betting on sports and have been burned by past centralized bookies.
Quote from: gwern on September 09, 2014, 10:32:58 PM
Quote from: koeppelmann on September 09, 2014, 09:46:44 PM
Actually the capability of Monte Carlo tree search are provable limited. Infinite computing power would not lead in all cases to the perfect game.
Cite? My understanding was that in the limit it searched the full game tree and so played optimally.
The search tree for a go game is about 300^300 in size. is such a gigantic number, even google wont calculate it.
I think it is about 10^690, compare to the number of atoms in the universe: 10^80
Quote from: psztorc on September 10, 2014, 02:20:13 PM
When I play a game, I'm usually trying to think several moves ahead. So if I had 300 choices to make on one turn, and so did my opponent, I would almost need to bet on Move_6 conditional on opponent's_Move_5 conditional on Move_5 conditional on opponent's_Move_4 conditional on Move_4 conditional on opponent's_Move_3...which would be [300^6 = 7.29e+14] * 2 (win-lose) = 1.458e+15 states.
I agree that strategy involves thinking ahead.
I disagree with everything else you said.
Can you provide some sort of reasoning as to why we would have conditional bets that way?
If you don't think prediction markets can be used to perform good go strategy, do you agree with Robin Hanson's idea that they could perform good governance strategy? http://hanson.gmu.edu/futarchy.html
Quote from: gwern on September 09, 2014, 10:32:58 PM
People don't care enough about such matches to make them good PR.
That is why each question will need to be well-funded. So there is a monetary prize for the whistle-blower who reveals most secrets.
Quote from: gwern on September 09, 2014, 10:32:58 PM
Advanced chess is already on the outs: the chess AIs have gotten so good that you need to be pretty much a grandmaster to add much of anything. In another decade I suspect it'll be toast.
That is why I suggested the game go rather than the game chess.
Quote from: gwern on September 09, 2014, 10:32:58 PM
You aren't capable of the complex calculation of grandmaster play either, so I'm not sure why that would matter. And you can numerically compare the value even more precisely by looking at an AI's estimate for each move.
The estimates the AI give are information we already know. AI is written off of the same strategies I could read in a go book.
There exist a lot of secret strategies in go. People have no incentive to share secrets. These secrets strategies have not been introduced into the AIs yet.
Many such secrets are controlled by fraternities of go players, who pass down the secret for generations.
When a strategy is secret, it is not put through the same scrutiny. So a lot of bad-secrets exist.
Truthcoin would incentivize whistle-blowers to reveal good-secrets, and it would punish people who reveal bad-secrets.
Truthcoin would dramatically increase the amount of accurate open-source knowledge about go strategy.
Did you by any chance get to watch TwitchPlaysPokemon?
Exhaustively selecting every move on a Go board is different from yes/no on a few policy choices. In Futarchy, we are voting yes/no on a few governance proposals, and they probably don't interfere with each other. If they do, the government can go back and eliminate the contradictions, or remove a previously instated policy.
Go-moves are non-reversible and perfectly-dependent on each other.
Quote from: zack on September 10, 2014, 03:14:14 PM
The search tree for a go game is about 300^300 in size. is such a gigantic number, even google wont calculate it.
I think it is about 10^690, compare to the number of atoms in the universe: 10^80
'infinite computing power'; 'in the limit'.
Quote from: zack on September 10, 2014, 03:14:14 PM
Quote from: gwern on September 09, 2014, 10:32:58 PM
People don't care enough about such matches to make them good PR.
That is why each question will need to be well-funded. So there is a monetary prize for the whistle-blower who reveals most secrets.
Or... you could take that huge heap of money and do things more likely to work, such as feeding it into the market-makers for sports problems and past prediction market standbys like presidential elections (instead of beating an idiosyncratic dead horse).
Quote from: zack on September 10, 2014, 03:14:14 PM
Quote from: gwern on September 09, 2014, 10:32:58 PM
You aren't capable of the complex calculation of grandmaster play either, so I'm not sure why that would matter. And you can numerically compare the value even more precisely by looking at an AI's estimate for each move.
The estimates the AI give are information we already know. AI is written off of the same strategies I could read in a go book.
There exist a lot of secret strategies in go. People have no incentive to share secrets. These secrets strategies have not been introduced into the AIs yet.
Many such secrets are controlled by fraternities of go players, who pass down the secret for generations.
When a strategy is secret, it is not put through the same scrutiny. So a lot of bad-secrets exist.
Truthcoin would incentivize whistle-blowers to reveal good-secrets, and it would punish people who reveal bad-secrets.
Truthcoin would dramatically increase the amount of accurate open-source knowledge about go strategy.
Huh? It's pretty hard to understand how a Monte Carlo tree 'thinks' since it's taking weighted averages over thousands of leaves of game-trees and seeing their random playouts. You want opacity, you got it. And prediction markets don't incentivize people to 'reveal good-secrets' in your setup - it incentivizes them to reveal good moves. I don't think you've thought this through at all.
Lots of branches open:
1. go solvable with infinite computing power?
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.
But with https://en.wikipedia.org/wiki/Minimax it clearly is but Zack is right: the numbers are gigantic. (That is why the heuristic is used.
2. Could the futarchy concept be used for games (with moves ahead)
Very clearly: If it is not usable than futarchy simply does not work! Every political decision highly interferes with parallel/future decisions. It is way more complex then the closed world of a game.
3. What brings good PR.
a) Sport does not. There is already betfair.com (of course, it is not crypto and it is not decentralized - but this is not enough for PR)
b) recent news: we try to do it all the time:
https://www.fairlay.com/predict/registered/new/message-from-satoshi-nakamoto-1/
https://www.fairlay.com/predict/registered/new/mh370-plane-found-in-april/
https://www.fairlay.com/predict/registered/new/mtgox-will-find-50-000-more-btc
sure, we are not decentralized yet - the design of our site is obv. not prefect - but: you should not expect people getting very curious just because you offer such events. (However, they always bring a few 1000 clicks)
So - that is why I really like zacks idea of such a "show game" for futarchy.
As a "proof of concept" I could start a simpler version and start a game of: https://en.wikipedia.org/wiki/Connect_Four
In theory it is known that the first mover can always win the game. To get the game started we would predict against it and then let the crowd play against the strongest bot we can find.
Should be fun.
Afterwards it could be extended to Go on a 9*9 (that is still far away from being solved completely)
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").
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"
I am curious what subsidy Robin Hanson thinks it necessary to get such a market working:
https://twitter.com/robinhanson/status/510561329195667456
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.
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...