How can one create visualisations like Figure 3 (assuming it's latex)[0]? I have to write my Bachelor thesis soon and need to improve my latex-skills. I only know to to use the math-mode and write text.
Hi - I'm one of the authors on this paper. We had professional designers do the figures for this paper; Fig3 in particular was far better than what we could do ourselves.
Probably TikZ. There are several frontend UIs available for accelerating the process of creating diagrams. One is ktikz, which I initiated a while ago.
You can create images using your favorite image creation software (e.g. Adobe Illustrator, Inkscape, MS Paint, D3, anything) and embed them in a LaTeX document.
With regards to Texas Hold'em, Conterfactual Regret Optimisation [1][2] was already able to beat humans in limit games, while it seems that this new approach is able to do the same in no-limit games. My naive understanding is that no-limit games are harder to crack because there are more possible outcomes, thus the available information (poker is an "imperfect information" game) becomes "even more imperfect".
[1] https://arxiv.org/abs/1407.5042 (yes, the author is the same Oskari Tammelin who created Jeskola Buzz, a popular piece of music software).
One thing I haven't seem come up in discussions or media coverage about this is that the heads up game is entirely a different thing than playing with 5 other players.
For what is worth, heads-up is a very popular game, and from reading the paper, the approach should more or less be applicable to 6max or full ring, except it will be way more computationally expensive (but not unfeasibly so like before).
In my understanding the approach is based on game theoretic principles that do not extend naturally to more than two players. If that's correct then it's not only a computational issue.
See
http://www.nature.com/news/how-rival-bots-battled-their-way-...
Yip, exactly this. The CFR algorithm they speak of is based on finding a nash equilibrium for each strategy-pair in the game tree. Something that I think can only be computed for 2 players, and no more.
There has been quite a bit of work (and several papers) on using CFR for games with >2 players. It is not theoretically guaranteed to converge to a Nash, and usually doesn't in practice either (there's one case in a toy game, in 3p Kuhn poker, where it does converge). However, even though it doesn't converge to Nash, the algorithm is still well defined, and the resulting strategies appear strong in competitions against other computer adversaries, as demonstrated in the Annual Computer Poker Competition.
Surely you can adapt it to compute an approximation of a mixed Nash equilibria. My game theory isnt at a high level, but there are similar computations you can perform, and when I used to play poker, you'd have common calculations based on it for more than 2 players when you are playing with a limited stack. I dont see how that wouldnt be adaptable (abeit more computationally expensive) for more players, but I might be missing something.
Nash equilibria are still guaranteed to exist. But it's only the 2p zero-sum perfect recall case where an equilibrium has useful properties, like being robust against any opponent strategy, including a worst-case opponent who knows your strategy. In a multiplayer (> 2 players) game, opponents can collude against you and playing your part of a Nash gives no useful guarantees on performance. Even if they aren't colluding, in poker games, the presence of a bad player just before you in turn order can hurt your EV worse than their own. And even if all players independently compute their own Nash equilibria (there can be many) and use the piece for their position, then that combination of strategies may not itself be a Nash equilibria.
According to Wikipedia, and my memory from school, Nash equilibrium doesn't exist unless all players are aware of the optimal strategy and are seeking it.
I don't know of a survey paper on CFR for multiplayer, but it's been showing up in conference papers and theses.
Here's a link to a shorter conference paper where CFR does converge to a Nash, in 3p Kuhn poker. It describes a family of equilibria, where one player (the second to act, IIRC) has a parameter that can't affect their own EV (...or else it wouldn't be a Nash), but does determine how much the other two players win/lose from each other. This illustrates the problem in equilibria for multiplayer games: if you're players 1 or 3, then even if you are playing a Nash, and everyone else does too (albeit different equilibria), then you can still lose.
https://webdocs.cs.ualberta.ca/~games/poker/publications/AAM...
For a longer read, the best I know of is probably Rich Gibson's PhD thesis. He focussed on CFR for multiplayer games.
Game theory is domain specific. Generic methods in AI tend to dominate domain knowledge over time. Although I agree that other game-theoretic techniques might help here.
Game theory is specific to the domain of agents optimizing outcome in adversarial, cooperative, or (rarely) solitary systems. That's a pretty big domain.
This seems to be a major threat to online casinos.
Is there any study on how they plan on fighting the AI's that will likely be flooding the market soon ?
The market has been flooded with them for years. They have various mechanisms for fighting them like mouse detection and scanning your computer for various programs and confiscating your funds if caught. In the end, people will always find a way around the detection methods though.
Like using a chess computer, it seems that there would be no way to protect against someone who relays the cards to a separate machine, and then enters the bids by hand on their own computer.
There are ways to detect cheating on chess websites, though these methods are not perfect. The two main signatures are:
1) Playing moves that the engine recommends consistently. This looks for people who are inhumanly good, even the top chess players in the world regularly deviate from engine suggestions.
2) Time between moves always takes a minimum threshold, the time needed to relay the position to the engine. Humans vary wildly in the time thought based on the position, in a way that cheaters do not.
Neither of these detection methods are perfect, especially for small numbers of games. I don't think we will see large prizes for on-line chess tournaments because of possible cheating.
Somewhat easy to detect a human using a computer, by comparing to what the computer would do, the rating of the player and the usual play of the player.
However, a chess professional would be able to use a chess computer almost undetected, as they know what would look like "computer moves", but could use it to just choose the best of their own suggested moves.
Heads-up is a contrivedly simple scenario compared to solving poker in general. There have been bots for a long time that have co-existed with real players, and we're likely not close to a scenario where bots can reliably beat real players in general for real world scenarios.
However, in theory even a break-even bot could be a gold mine because it can earn loyalty points. That's how it was the last time I was playing online, I don't know if loyalty programs still work the way they used to. Of those programs would just go away if abused enough.
Online poker has the concept of "bonus whoring" where one takes advantage of various loss-leader promotions offered by different sites.
A typical promotion would be offering a 20% bonus on a $1000 deposit, with the caveat that you must play in, say, 1000 raked games before cashing out. It's possible to play in games where the total expected rake if the user breaks even is, say, $100, leaving $100 profit.
Why do you say we're not close to solving Poker in real-world scenarios? The multiplayer version is likely to be harder, but is it so hard, that it'll take decades more?
Depends what you're trying to achieve. If it's a bot that beats most humans, that probably already can be done. If it's a bot that earns more from a cash ring game than the world's best would against all levels of players...
It took many years for a computer to bridge the gap between better at chess than almost all humans and better than the best human.
When they released the initial paper a few months ago I looked into it and it sounds like this wont be profitable anywhere except the highest levels (although obviously the highest costs are in the training phase).
This in combination with casinos already doing a lot for bot-detection makes me think that we are at least a few years away until this is an issue.
[0] the paper: https://arxiv.org/pdf/1701.01724.pdf