??????
You are not logged in.
There may be some live Cordial Minuet events in NYC next weekend. Still ironing out the details.
Update:
Yes, this is happening tonight at 8pm:
https://www.facebook.com/events/747999818630147/?ref=22
They've got Cordial Minuet kiosks set up and working on their own local server.
Babycastles
137 West 14th St, New York, New York
Anyone have any feedback about the changes to the water color strokes in v10? Does it give you the extra info at the end that you might want? Is it confusing at all?
Well, I've been inviting more people from my release mailing list. Doing batches of 100 invites per day. 100 more will be invited later today.
Do you use Bitcoin for anything, Preece?
I kinda feel like the Bitcoin supporters are like the Ron Paul supporters---very vocal, but pretty much a non-factor when the rubber hits the road. One guy chimes in on every comment roll saying, "You're a fool not to use Bitcoin." Probably that's a guy who has some money invested in Bitcoin.
I'm not saying that Bitcoin isn't a good idea, but from where I sit, it basically doesn't exist in the real world.
The other problem is that Bitcoin, being anonymous and all that, further complicates all of my tax obligations and such. I think it would turn me into at least 2x the government target that I already am.
Big change to the way that rows and columns are blacked out throughout the game, leaving the board more visible for study by the end of a round.
SourceForge is down right now, so the final source and change log haven't been pushed to the public repository yet.
From the change log:
--Fixed stale list of other games when returning to waiting for opponent.
--Changed row coloring of our row to make our possible squares from their
perspective more visible. Changed reveal black-stroking to ensure that
all squares in row that they gave to themselves are visible at the end
of the game.
--Changed FOLD key command to f instead of x (thanks Zed).
--Added left/right arrow keys for picking reveal column (thanks Zed).I changed it (for v10, not out yet) to NOT paint black masks over your rows when you win them. It still paints them over your column though (to show which square you won, even after other rows come in later and intersect with your first column).
This leaves "my possible squares from my opponent's perspective" still visible.
During reveal, only a row black mask is added for your square now. Thus, it doesn't further darken squares in your opponent's rows.
During your opponent's reveal, their column is black-masked, but their row is only faintly black-masked, leaving the row that they picked for themselves totally readable.
During final reveal, only their columns are black-masked.
Furthermore, the black mask brush strokes have been lighted overall.
The board at the end certainly doesn't look as striking, but it contains a lot more useful information, and it provides more information along the way (you can learn to read the board to see what your opponent is seeing about your numbers along the way).
Well, until someone finds a hole, yes.
Yeah, this concerns me too.
The squares that get darker and darker (the green squares that you don't score yourself) are actually the wrong ones in the current implementation. It should be showing you something about your opponent's perspective (with possible won squares for you being more visible), but with the way that the darkening works, the ones that are possible for you from your opponent's perspective get the darkest, while ones that are clearly not possible for you (intersected by red) are still visible by the end of the round, before the reveal.
There will always be a pacing element to this game that prevents very close study post-round, except at very high levels of play.
But, the information should at least be visible on the board!
To rephrase it, in the turn-based, full-information version (where p2 sees p1's picks before picking), do any boards exist that are not an automatic win for player 2 using a per-pick greedy strategy? Is the turn-based, full information version trivial to solve for every board as a win for p2? Or can you force p2 to explore the game tree? Is p2 guaranteed to win if p2 explores the game tree, or can P1 force a win on certain boards?
Okay, I wrote some code to answer this question.
First, if your opponent is playing a known minmax gametree search strategy, then a simple greedy, per-move choice beats them on 100/100 test boards.
However, there exists a strategy that beats a per-move omniscient greedy strategy for certain boards. In my tests, it's about 3% of boards where we can force a win against a per-turn greedy opponent even if the opponent knows what we are picking (even if they are running our algorithm and picking the per-turn greedy choice against our picks).
Here is a sample board where this is true:
0 1 2 3 4 5
------------------------------
0 | 14 22 12 24 30 9
------------------------------
1 | 5 32 15 36 6 17
------------------------------
2 | 3 27 33 29 18 1
------------------------------
3 | 26 4 23 2 25 31
------------------------------
4 | 35 16 8 7 11 34
------------------------------
5 | 28 10 20 13 21 19
------------------------------Here are the player moves:
Player moves: R C
------
0 5
4 0
2 4
5 2
1 1
3 3Read that move table as the first line picking a square for the R player, and the second line picking a square for the C player. Assume the C player is knows what R is going to pick (can simulate R's strategy). Note that the C player makes a greedy choice each turn.
On turn 1, C gives the R player a 9 and takes 35 for itself.
On turn 2, C gives the R player 18 and takes 20 for itself.
BUT, on turn 3, C is stuck taking a way-lower score (32 vs 2 or 36 vs 4).
Essentially, it is possible to paint the greedy player into a corner on certain boards. Note that, on boards where such a move sequence exists, there is exactly one move sequence (out of 720) that does it.
However, the R player still loses here if the omniscient C player simply runs minmax against it. Minmax vs. Minmax, where C can simulate R's choice before picking, makes R lose by at least 25 points on this board.
To summarize:
A) If your opponent is playing any deterministic (pure) strategy that you can simulate on your end, a simple greedy choice per-turn will win on 97% of boards.
B) If your opponent is playing any deterministic (pure) strategy that you can simulate on your end, a pure strategy exists that will beat that strategy on 100% of boards.
I've measured (B) empirically but not proven it. If is true, then there is no pure Nash equilibrium for this game.
Thank you, Jere!
Yeah, I mean, would I trust my credit card number with Target?
Yeah, when I designed this game, I wasn't so concerned with whether it was solvable or not in terms of the picking game. I wanted to ensure that there was no pure Nash equilibrium (which would make it broken), and the "complexity" of the game, in terms of multiple rounds on the same grid (as compared to RPS) is just there to build an interesting betting structure around a progressive narrowing of hidden information.
Mixed strategies, even if known to all, are fine in terms of my design goals, because mixed strategies leave room for donkeyspace. Even RPS has this (playing rock 4x in a row to bait your opponent into playing paper). But RPS has no obvious spot on which to hook an interesting betting structure. Also, one of my other design goals was that it be a truly novel game.
I now believe that I was wrong about the 50% upper/lower bound when playing the Nash eq even if you're opponent is not, but I stand by my claim that the Nash eq is not optimal if you're opponent is not playing Nash eq. Yes, a rational opponent would move toward Nash eq to raise their win percentage against your Nash eq strategy---but I'm talking about an irrational opponent. Nash eq. is unexploitable. But your irrational opponent's strategy IS exploitable, and there is nothing about the Nash eq. strategy that causes it to take full advantage of an exploitable opponent.
Thus, the Nash eq. and the optimal strategy against a given opponent are two different things (unless the given opponent is playing the Nash eq. strategy, in which case they are the same thing).
Thus, even iterated RPS or iterated prisoner's dilemma is not simply "solved" through the Nash equilibrium. That's why there are bot competitions for these games and active research into more complex strategies.
As for simultaneous decision games that are intractable to solve, I think space of possible strategies is exponential in the number of rows/columns. So... wouldn't 8x8 or 10x10 do the trick there? 10x10 gives us 10^13 leaves. Not that I want to make that game, because that kind of intractability is not what I'm shooting for anyway (and I believe a bigger grid would make a less interesting betting game).
Thanks for that PDF link, Zed!
And yeah, that must have been you that emailed me.
I feel sure that it's true that there is no PURE Nash eq here, which essentially means that if your opponent is playing a deterministic strategy, you can always beat them, every round (even if they're searching the game tree in a deterministic way), and I think a greedy per-turn strategy would win here.
But I have no proof of this truth. It's clear that on turn 1, if you know what they will pick, you can always give yourself a higher number than they give you, but this also affects future possible picks in complicated ways.
Perhaps the proof can happen by working backward.
Assuming that you're opponent is using a known, deterministic strategy (you can run the same algorithm as them and know what they will pick in any situation), in the last pick, there are 4 squares left on the board, and you know which ones are left. Say they are in A, B, C, D order, with A the highest and D the lowest.
Worst case possible pattern:
A B
C D
They will pick the top row for themselves, and no matter what, you will get a lower turn score that final turn.
Is there a way to play, on some board layouts, that allows them to force this situation if you are making greedy choices (given that you know what they will pick) on turn 1 and 2? Yes, I've found this to be true on an example board. By controlling what you pick on turn 1 and 2, against a per-turn greedy omniscient player, you can force a higher score for yourself than them on turn 3.
What about turn 2, where there are 16 squares left... (A, B, C, D, ... O, P) Could there be one row where all 4 numbers left in that row are higher than the remaining 12 numbers? That could be a row that looks like this:
1 A B C D 2
Where they forced you to pick the first and last columns on turn 1 as your greedy choices. This row could work:
1 25 26 28 29 2
And I've seen rows like this on an example board. In this case, it is possible to force the per-turn greedy, omniscient player to take a lower score than you on turn 2.
But can you do it on both turn 2 and 3, in series? Certainly you cannot do it on turn 1---the greedy omniscient player can always give themselves a higher score than you on turn 1. But, in so doing, can you set them up to take a lower score in both turn 2 and 3 that lets you win?
On turn 1, the average score of a number is 18.5. Thus, the best case highest number you can let them take (if you give them a column with the lowest high number) is 21 (the worst-for-them possible column is 16 17 18 19 20 21), and the best-case lowest number you can let them give you (if you give yourself a column with the highest low number) is 13 (suppose you also, in this hypothetical best-for-you board, had a column like 13 14 15 22 23 24). So, best case, you might be able to only allow them a score gap of 8 on turn 1. That's the lower bound---the score gap the greedy omniscient player can force on turn 1 will never be lower than 8.
So, given that you're always at least 8 behind after turn 1 against greedy omniscient, can you recover 8 points by forcing certain columns in turns 2 and 3?
Seems like I need to code up some AIs to search this space. If your opponent is peeking and given themselves the highest score-gap per turn, is there a leaf in the game tree where you have a higher total score?
To rephrase it, in the turn-based, full-information version (where p2 sees p1's picks before picking), do any boards exist that are not an automatic win for player 2 using a per-pick greedy strategy? Is the turn-based, full information version trivial to solve for every board as a win for p2? Or can you force p2 to explore the game tree? Is p2 guaranteed to win if p2 explores the game tree, or can P1 force a win on certain boards?
Finally, I will note that I feel like I'm falling down a Turing/Godel rabbit hole here. We're talking about reacting to deterministic strategies in a deterministic way by taking the strategy into account. Asking whether any deterministic strategy A has a deterministic strategy B that always beats it, and whether a function F(A) = B exists. But what if the A[] strategy takes a strategy S as as an input and soundly beats the input strategy? What is B = F( A[ B ] )?
Like a Turing Machine that runs the halting-detection algorithm on itself and does the opposite.
Good stuff, as usual, Zed.
I was, admittedly, working off of my understanding of Nash eq as applied to much simpler games than CM. Like, in RPS, where the Nash eq is to pick randomly with 1/3 weights, and all that does is guarantee that you win 50/50, regardless of whether your opponent plays rock every time or not.
Still, I think the reasoning is sound that even in CM, you wouldn't want to stick with the Nash eq "no matter what," because it offers no guarantee of winning a given round. If your opponent is playing a known deterministic strategy, for example, there is clear strategy that will always beat that strategy (every round).
I've heard from someone else who came the the same conclusion as you regarding the infeasibility of applying minimax to the betless game as a single move. There was some reference to a linear programming algorithm for computing such things that had a specific running time given the number of possible strategies, but I can't find it now.
Can you post a link that explains "recursively dominated?" My searches aren't turning up much on that topic.
The following post ignores betting at first:
The Nash equilibrium is only "optimal" in a particular, narrowly-defined way, essentially guaranteeing that you lose the least no matter what strategy your opponent is using and that you stand to gain nothing by switching away from the Nash eq yourself if your opponent is also playing the Nash eq. It's an attractor in the strategy space, a gravity well.
But it is NOT optimal in terms of how much you could win against various different strategies. If your opponent is not playing the Nash eq, you'd better switch strategies, because by playing the Nash eq, you've stuck yourself with no net winnings and rewarded your opponent with more winnings than they deserve. Let's say their strategy is as simple as "always pick column 1 for me and 2 for you." If you're sticking with your Nash eq strategy, you will win 50% of the rounds. Your opponent's strategy is just as good as your Nash eq strategy in terms of the outcome.
The only way you can punish your opponent for their bad strategy, and thereby take more than 50% of the money, is to deviate from your Nash eq strategy. In fact, you could jump up to winning 100% of the rounds.
But at that point, your strategy has become exploitable too. Back when you were playing Nash eq, your opponent had no motivation to switch from "c1 c2," because doing so would net them no more wins against Nash eq. But now that you've deviated, they are motivated to deviate. Note that they won't be motivated to switch to Nash eq themselves at this point, because that would only get them back to 50% wins. They could climb above that by exploiting the weakness in your new, non-eq strategy.
Here is the interesting, counter-intuitive crux: the only way to make money at the game is to play a non-optimal strategy.
Taking the rake into account, if you are playing the Nash eq strategy, you've guaranteed that you will lose money over time, no matter what your opponent is doing. There's a guarantee that you won't lose more than a certain amount, but a guarantee that you will win nothing. If your opponent is playing the Nash eq strategy, all your strategies become equal, all losing the same limited amount of money over time, and tying the so-called optimal strategy.
The only way that you can possibly win money is to play a non-optimal strategy. If your opponent sticks with Nash eq, you will do no worse. However, if your opponent ever deviates, you will be able to exploit their deviation.
Baiting them into deviating is donkeyspace.
Who would spend time writing a bot that plays the Nash eq strategy? A bot that is guaranteed to lose money, no matter what? No, in the real world, the Nash eq is not actually the best bot. Step one is an evolutionary bot that adapts to the opponent's behavior. Step ten is far beyond that:
http://edge.org/conversation/on-iterate … er-dilemma
Yes, the Nash eq is a kind of strategic gravity well, but a well that has many holes when you're down in it in the real world. Especially when the Nash eq itself is complex, the smallest crack in one opponent's strategy will quickly cause both players to slip out of that well, chasing each other's exploitabilities in a rising cyclone that is unlikely to return.
I get your point that I could profit by building such a Nash eq bot and running it. Then I'd have a game where everyone, the bot included, would lose a fixed amount of money over time, no matter what people were trying to do against the bot. I'd think I'd be shooting myself in the foot by doing that, because people would stop playing.
In conclusion, the only player that would be willing to play the Nash eq for long would be a bot that was funded by the house, at which point I'd be making $0 (me running a stable full of bots that were all losing money to me).
Now add betting strategies.
Yes, a mixed strategy Nash Equilibrium exists in this game.
Finding that strategy is a different matter, however. The Nash Equilibrium is different for each board and it would need to be computed in realtime for each new game by exploring the full, 500,000-leaf game tree. This may or may not be feasible in terms of computational complexity. If it is claimed to be feasible, we need to start talking about what algorithm would be used and what it's complexity characteristics are.
Optimal play of Holdem with no rake is 0 EV if your opponent is playing optimally. With the rake, it's negative EV.
But the point of Holdem, and why it's interesting, is donkeyspace, and even more important, higher-order donkeyspace. Here's how I explained it in an email:
Simplify it to heads-up, no-limit holdem with a rake. If both players play optimally, computing pot odds and all that, then the expected value for both players is negative. First order donkeyspace is making moves that might convince your opponent that you aren't actually CAPABLE playing optimally, to get them to try to raise their EV by taking advantage of your sub-optimal play, which effectively pushes them into sub-optimal play that you can take advantage of in turn. But of course, your opponent knows that you're probably doing this on purpose, that you're pretending to be a donkey and not actually a donkey. So then you push into second-order donkeyspace, where the players are trying to figure out just exactly how far their opponent's pretending is going to go, while modulating their own level of pretending in turn. It's no longer, "Hmm... how bad is my opponent at this game?" but instead, "Hmm... how far out into sub-optimal play is my opponent actually going at this moment in the game, and are they out far enough on their limb so that with a little extra downward pressure, by standing a bit further out on my own limb, I can snap theirs."
It seems quite similar to a martial arts contest, like fencing (or JSB Joust!), where risk is a resource that players are trading in (and obviously fighting video games).
I haven't played complete information, turn-based games (like Chess or Go) extensively enough to know whether this kind of dance is totally eliminated by the practically-infinite layers of "even more optimal play" that never hit bottom. I imagine scenarios in Chess, like traps, where your opponent does something that looks stupid, but you know your opponent is not stupid, so there must be something more going on here several moves in the future. But you CAN figure it out, if you think hard enough. There is a right answer (or set of equivalent answers) to any trap or puzzle that arises. Or did your opponent actually just have a small stroke, or crack under the pressure? Strangely, there is an answer to even that question lurking deep in the game's current state.
In Poker, that answer is unknowable before the showdown.
And donkeyspace is this game's bread-and-butter.
So, even if computing the Nash equilibrium were trivial, there'd still be a non-trivial game in donkeyspace. But unlike RPS or "odd or even," computing the Nash equilibrium is not trivial, and is at least out of reach for humans without computer assistance (and perhaps out of reach for computers too), so this game has an extra layer that RPS doesn't have.
(Building an interesting betting structure around RPS is an open problem.)
As a starting point toward seeking the Nash equilibrium, my empirical tests match your observation that picking your first column randomly with 1/6 weight is not optimal (AI bots that I've written can beat a random opponent by looking at the game tree and picking the column that has a slight advantage game-tree wise).
Arrow keys for picking the reveal column are on the to-do list. I probably won't use them when there are two sliders to pick because the modality will be confusing.
And...
Already found a bug.
The list of other games on the waiting screen is stale if you come back to that screen later. Wait 12 seconds for it to fetch the latest list of other games. This will be fixed in v10.
The reason this game is no-limit is pretty simple:
I play no-limit Holdem exclusively, and have no experience (not a single game's worth) with limit Holdem. There's a lot of smoke blown about "no-limit being an art" when compared to limit. See the film Rounders---I think there's a quote in there about that.
I'm not sure I've seen the other one you're referencing. Link?
I don't know if the GDC version is online for free anywhere, but he re-gave the talk at NYU later:
Fixed all known bugs, improved a bunch of little things.
Change Log is here:
Fixed in v9