There are very few missing pieces for a game like MTG. The main reasons we don't have a Stockfish for MTG is that it's a PITA to implement the rules and that nobody cares (or at least not enough to make it happen.)
There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
>There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
We don't have superhuman play for bridge.
Poker and bridge are quite different from each other in terms of solving them. Among other things, the hidden information space in poker (at least, in hold'em) is far smaller than in bridge (or Stratego, for that matter, as discussed in the linked paper). This makes hold'em solvable using CFR, an algorithm which essentially optimizes play by considering all the possible holdings than the opponent might have and their best strategy with each one. Even going from two to four hidden cards per player (Omaha) requires a slightly different approach although you can still use CFR as the basis for the search algorithm.
Bridge has 13 hidden cards per player which makes CFR basically impossible to apply, at least in any obvious way--just way too many states. Similarly you see it's not used at all in this Stratego paper.
Sure, but you can do Monte Carlo with a double-dummy solver.
The point is that, especially for games perceived as being lower-status like MTG and other board games, I'm more inclined to believe the answer is closer to "nobody is willing to pour in the resources to seriously try" as opposed to "we definitively cannot with current science and technology."
Monte Carlo with a double-dummy solver is fundamentally insufficient for good single-dummy play because it is incapable of understanding information. It won't take discovery plays (lines aimed at discovering more information about the opponents' hands before choosing a line of play) and will systemically overvalue positions which are good double dummy but require a guess. It doesn't understand falsecarding (because double dummy, it doesn't matter).
I agree that many games could make progress if people were actually inclined to try.
I think it will get a bit better in the coming decade thanks to continued hardware improvements & powerful LLM coding agents making it more feasible for amateurs to tackle these things at home. Personally I've been working on a game AI project for the last month at home based around published techniques for a similar game, using my 5090 for training and Opus for implementation and orchestrating tasks and so on. It's going quite well and it looks like I'm on track for a SOTA, superhuman AI at the end. Doing this ten years ago would have been incomparably harder.
I think computer bridge will take off soon. LLMs have allowed double-dummy solvers to move from ~0.1sec to microseconds (if you allow 99.9% accuracy) and parsing human bidding system descriptions must either be possible or v close.
>LLMs have allowed double-dummy solvers to move from ~0.1sec to microseconds (if you allow 99.9% accuracy)
I don't know what this is referring to. The ubiquitous dds library, which is AFAIK basically the only double dummy solver, has not seen any real improvements. Neither of those numbers look right to me, I think it's more in the range of ~10ms.
There's a crank who was claiming some magical improvements a little while ago that really just boiled down to AI psychosis (and having absolutely no understanding of what he was claiming). I hope that's not what you're referring to.
I'll concede an order of magnitude for dds, I may not have been using it optimally. The claims made by Lorand Dali for his neural net solver were a thousand times faster with a slight drop in accuracy (99.9%+ I think)
I believe this was used in his 'ben' bridge engine, https://github.com/lorserker/ben/ now maintained by ThorvaldAagaard, though I have to admit it now seems to be heavily dds focussed, so there may have been a rollback along the lines you outlined.
I'm attempting to recreate the concept myself, so should soon have an idea whether its moonshine or not,
I wasn't aware of this although this project had a substantial error rate. Flipping through the YouTube video it only predicted the correct number of tricks 70% of the time--so I'm not sure if your 99.9% is referring to a different project that I'm unable to find, or if you misremembered. I don't think anything like this was ever used in Ben; looking at the commit history, I think Ben has always used the standard dds library.
FWIW I'm pretty confident that you could beat the performance of the project I linked with a fairly straightforward transformer architecture.
Yes - you are right, 70% for a correct answer is what the talk says. Id misremembered the higher (~99%) numbers because for my purpose (simulating many random deals compatible with known cards to get probability distributions on hidden card positions and trick taking possibilities in each suit/notrumps ) a one trick error is quite acceptable. I agree a more straightforward architecture is a promising approach. Once I have generated weights in a form usable in C, I am also curious as to whether they can direct DDS's tree search as a kind of probabilistic oracle.
(There was some Ben code to use a neural net double dummy evaluator, because Ive used it, but it was removed. Ill try and find the git point it was removed.)
also the keras model ben/models/TF2models/RPDD_2024-07-08-E02.keras is still present in the current repo but not apparently used. It was trained on ten million deals where all double dummy info is known.
> There is nothing that, in principle, makes MTG different from poker or bridge
There is - metagame. There is no universal optimal strategy in a trading card game, because what is optimal depends on what decks and strategies other people are playing.
I'm sure you could train a neural network to play a specific deck within a specific metagame of a specific card game, but you would probably have to keep re-training it when there are new decks/combos/releases/rotations/banlists/metagame shifts.
> There is nothing that, in principle, makes MTG different from poker or bridge
Only in the most general form they are games with cards and hidden information with a state space that some form of tree search can theoretically play out.
The difference is the size of the search space. In MTG the search space is unimaginably huge. It would make Go's search space look like a spec of hydrogen in the middle of the universe.
It would require completely different techniques to produce a computer good at MtG than one that is good at bridge.
MTG is also severely constrained (small hand, mana -> possible moves) although I don't think it's anywhere near the same. In my opinion the rules are effectively what change the whole dynamics. You can't plan as efficiently without knowing what your opponent holds and having to take into account all possibilities (with infinite energy/compute time perhaps)... I don't doubt you can train a model to play well, I just think it should be much more level to the human player. In MtG you also have the randomness which is not easy to model nor account for - the perfect play by an LLM can be the worse once the opponet draws next.
In my own game you don't have shuffle/draw randomness but the pool of options is statistically tending to infinite (if I would have 500 or 1000 scrolls designed and MtG depending on the format has that depth) when compared to something like chess, or this game. On the other hand in my own game you have to account for much more depth on the possible options your opponent has.
There's only so many card interactions that strong players actually think about.
Ex: you don't really care if the opponent plays Giant Growth or Chastise. The effect is that the opponent is playing a combat trick, and combat has moved from attackers favor into defenders favor.
To defeat an instant speed combat trick requires a combat trick of your own, or a generic counter spell of some kind. Some have interactions (ex: Doom Blade beats Giant Growth but not Chastise), but the overall gist is that opponents can do things after combat is declared. You only need to keep track of how many combat tricks you think the opponent has.
---------
Other situations are card advantage (ex: 2 for 1. If the opponent spends 1 cards to defeat only 2 cards of yours). The traditional card for this is Mindrot, but well placed counterspell can turn a combat trick into. 2-for-1 reversal.
You don't necessarily keep track of how your opponent makes 2-for-1 opportunities. You just have vague gists of them.
---------
Good spells have huge applicability. Doom blade or Murder is high because killing opponent creatures at instant speed handles the vast majority of creature buffed combat tricks, and also serves as a way to stop enemy combos and other such tricks.
In contrast, chastise is very niche. If the opponent were playing like Swords to Plowshares (powerful white instant speed removal), it's pretty much always better than chastise.
If the opponent plays chastise instead, you take that as a win because you know they could have had a deck of better cards. But for whatever reason decided to play with weaker cards...
I agree in a way, but at the same time, and I think it's a bit more applicable to MtG due to the limit of cards you can have as possible plays at any given time (outside of combos), and I believe too that you can train a bot to be good, better than average - I doubt arena doesn't have bots - but I still think that without unbound compute/time it's a game where human players have much better odds to outsmart an AI if they're good players. MtG has for the past 10 or more years been re-hashing the same play patterns, while introducing some new mechanics on most cycles, but pretty much you have staples throughout most editions that are just variations on that - card advantage, denial, combat tricks, removal, curve and then the rarity enabled bombs/combos
But even then (not saying I'm right) I think the depth of choices, effects and so on, on a format like modern, or legacy, would be very difficult for an AI to top against pros. If you add draft into the mix it gets worse for the AI in my view too.
Because a good play in most situations can easily be a bad play under others. That doesn't happen in chess for instance, given enough decision depth to the algos to see the future game. In my own game I think those situations can occur much easier due to you always having your full deck available. Also, in MtG it's easy to get into table states that are either ahead/behind and then you kinda just have to protect your position (like with denial decks). Then you have the effects that you might remove a creature threat (graveyard) but then that enabling a combo you weren't expecting that needs a creature on the grave, or enabling delve cards or whatever have you. It's much less clear cut for a probabilistic model to make the optimal play at every single interaction. So the more you train the model on all the variations and possible follow ups, the more you dilute its certainty isn't it? In chess, or this game, or RTS such as starcraft, that doesn't really happen in my view.
I'm also a Poker player and the way Poker AIs solved this problem was by making the best estimate of the Nash Equalibrium and playing around it.
No human can possibly keep up with all the possibilities or combinations that are accounted for.
Games of incomplete information have been IMO soft-solved as of.... Maybe 5 years ago? As in, stronger than any human can possibly reach (ie: massive GB-sized matricies accounting for all information iterated over millions of iterations of "he thinks that I think that he thinks that I think that....")
It's not a true Nash Equalibrium, which remains outside of the realm of even computers to compute. But a computer can always reach a closer / better estimate of any Nash Equalibrium, which covers all games of incomplete information.
--------
For Poker, it turns out that a few types of bet sizes (3x pot, 1.5x pot, pot, half pot, quarter pot) covered enough betting patterns to reach superhuman.
And frankly, MtG is simpler than the bluffing game in Poker. Like MtG has bluffs but it's no where close to Pokers level.
There's no crazy deep game for Red Deck Wins vs Control. The game basically plays itself out (Red tries to win before Control comes online. Control tries to stall before Red Deck Wins). There are some games with complex board states but they're largely a game of bluffing + card counting (opponent holds 4 cards, two of which were since the start of game and 2 were top decked in the last two turns. He at best has only planned for 2 responses or got lucky with the other two newest cards. Do I have a play that beats two cards yet?)
The card counting is harder since we can hide which cards were top decked or held since the start by just rearranging/shuffling our hand. We could have 0-4 counters or setups waiting for the gating decision.
The possible game state is also much larger than poker. Deck construction alone is 60 cards out of about 30,000 unique cards. Sure, not all cards are viable in all decks, but we can have 1-4 copies of a card in our deck.
So we might not even know if we’re playing against mono-red or multicolored since the decklist is unknown. You can think you’re playing mono-red and then they suddenly play a Plains. Poker at least always has the same 52 cards to reason about.
I do think AI could be great at coming up with decklists though.
Yeah I am of the same opinion. And of those unique cards (although formats will limit the total number) they all can play differently in different contexts/states of the game - even a "bear" (2/2 vanilla), can be just a bear, or part of a strategy (if other cards pump those specific cards being played, or enhance them), while poker they're always evaluated in aggregate from 52 cards that are split between players, so you can always remove the ones you're holding, the ones on the table. So 48 cards to calculate possibilities after initial deal + whatever is on the table. The fact that they're shared also means you can exclude immediately what is revealed and what you hold on your hand from those calculations.
Hm, I don't really agree. I think that bluffing feels more important in poker because of the usual monetary value attached, and is more of a strategic hindrance when playing against bots, while it's very important between humans because (usually) of the money involved - even in this article there's a mentioning that the bots don't care about bluffing and that for humans that is part of the normal gameplay and mastery.
There's also the decision points, in poker it's way less. You're dealt cards, the table reveals cards, you bet/ante, move to the next, bet/ante. It's a very finite sequence of moves until disclosure. Plus it's 52 cards divided by the table players while on MtG it's 60 per players that you can't know (even lands can interact beyond being a resource and in competitive lists usually they do, specially in older formats) - although with enough/infinite time/memory you can probably generate a table for all possibilities, you still have to contend with the interactions other than the card types. A 9 Diamond is a 9 diamond. A Skull Clamp is a Skull Clamp but the way it interacts, its value/threat is highly dependent on context that can/might be hidden.
While I think that MtG is indeed "poker" like underneath the keywords, it's many more levels and I think bluffing can be way more "complex" but simply isn't because even at the pro-tour level prize pools are insignificant when compared to serious poker tables.
Some MtG players are known to also dabble/play poker regularly.
I also think that the structure of poker game-play is more prone to be exploited by a competent bot - if you have a "budget" and you assign a bot to a table where the antes are "in-line" with the "budget" it has, it can mathematically (within a very high degree of probability) always turn a profit - ultimately humans fail in part because they enter "bluff" kingdom against a bot as the bots can just rely on mathematical probabilities. Made up numbers but the idea being, you have $200 to play. Choose a table where this allows you to play X games at least, say antes of cents, it should be able to make money most of the time at some point.
Yes, but as the other reply mentioned, the thing is you don't know if it's red deck wins, or a RDW with a tweak for the metagame and building the "he thinks that I think that he thinks" tables would probably require for practical terms what could amount to infinite storage and any of these chains, if followed through, can land the bot in a losing position hard to come back from. Now, to be honest, most MtG players aren't that good either, they play it more like a hobby/fun game, rather than approach it as poker/probabilities.
[...]The protests were successful, and the Ampelmännchen returned to pedestrian crossings. They can now also be seen in some western districts of Berlin.[4] Some western German cities such as Saarbrücken[14] and Heidelberg[15] have since adopted the design for some intersections.
I am begging you on my knees to please stop posting this cringe.
The model is just out. It could be good, great even, I don't know. But I do know that this index has Opus 5, one of the worst releases of 26, ahead of Astra. What information are we supposed to deduce from number having gone up?
What's more valuable than a good benchmark? IMO a benchmark that has been run against very many competitors and versions. Collecting data has something going for it, and it's up to the readers to interpret and make the best use out of it.
This index doesn't have "Astra" and "Opus 5". Every entry with corresponding data is a `(model, reasoning)` tuple.
So I'm unclear what you're actually saying and wondering if you've missed that. Are you saying that at every reasoning level it says Opus 5 beats Astra? I just compared Opus 5 high to Astra high and it has Astra as generally better than Opus.
I don't try to say that the parent commenter is right in any way, but the two models' "high" settings probably doesn't mean the same thing. So probably comparing only them is not useful.
You forgot to include whatever you're proposing instead.
"Trust me bro, Astra is better" isn't perhaps as useful as you seem to believe. I'm not even saying it is right or wrong, just that my opinion on this topic is still just one additional subjective data-point.
Only thing I wish with these benchmarks is that they would run repeat tests every couple of months. Then re-rank based on that too. We've seen a lot of performance fall-off after a couple of weeks with new releases.
Yeah unfortunately the benchmarks are usually provided by the company themselves, unquantized, thinking set to extra-extra-ultra-high, best of 10 runs, etc etc. It's hard to know how that's going to map to real world users.
That it's better in specific ways? What difference does it make when it came out? The benchmark results are not going to change unless they're messing with the model.
Yes, but crucially, in ways that are increasingly decoupled from any practical pattern of usage, considering that I wouldn't see how you can argue that Astra is worse than Opus 5.
One man's modus ponens is another's modus tollens I guess.
It's endlessly fascinating how culture, religion and even language influence stylistic choices, even though Chess is a purely abstract game.
The obvious ones: in Western sets the king has a cross on top, and Islamic traditions only use abstract shapes. But I wonder if the "usual" designs aren't at least somewhat influenced by the English language specifically. Bishops have a stylized miter and Rooks are a tower with crenellations, but e.g. in Russian Bishop is "elephant" and Rook is "boat". Even in many other Western European languages "Bishop" as in the piece is not the same as bishop as in the religious office, e.g. "fou" in French, "alfil" in Spanish, "Laufer" in German.
The reason I hate chess is exactly the bishop symbol. I cannot explain it but I just can stand it. The idea on my mind of a bishop in war. I wish future generations will go back to the elephant as symbol internationally.
What feels more off to me is why does the king have a cross? And why does a religion use the murder weapon of its messiah as its main logo? What if He was killed by a rock or a rifle or a guillotine? What would the king be carrying on his head?
1. Because many ancient monarchs claimed they had divine backing as the basis of their right to rule. A ruler wearing religious symbols strengthens that association. Chess kings from non-christian countries don't have crosses but go with other symbolism.
2. Because the most famous miracle performed by Jesus is that the crucification didn't stick: he rose from the dead after a few days and ascended to heaven not much later. So the cross is not so much a murder weapon as a callback to the central promise of christianity: that believing will grant you eternal life in Heaven after you die. It should be noted that early christians didn't really use the cross as a symbol btw, that came much later.
> (This approximation should be familiar to many from an algorithmics class.)
You need both sides though :)
What makes it interesting for estimating algorithmic complexity is that \log{n!} \in \Theta(n \log n). One side is obvious as you note, the other less so, but there's a famous trick to do both at once:
The new procedure targets inappropriate behavior by parents and spectators directed at children, coaching staff members, referees, match officials, or other parents and spectators. This includes, but is not limited to:
Verbal abuse (insults or profanity), as well as physical assault or shoving of one’s own children;
Verbal abuse, physical assault, or shoving of staff members of one’s own team;
Verbal abuse, physical assault, or shoving of players or staff members of the opposing team;
Continuous challenging, verbal abuse, physical assault, or shoving of referees and match officials;
Verbal or physical altercations with other parents or spectators.
<<<<<<
If that's the situation in, and it can't be stressed enough, a children soccer game, then yes, abandoning the match is probably the right choice. I assume they are only defining a formal procedure for practices that already exist.
>If that's the situation in, and it can't be stressed enough, a children soccer game
It's not extremely common in my area, but it is more common than you would think. Parents treat their children like lottery tickets when it comes to athletics. And God help you if you're the unfortunate umpire at a travel league game that makes a questionable call.
The youth sports industry is fucking gross and nobody seems to notice.
Source: we will not let our children participate in travel leagues and they do not want to participate in them either, for this specific reason.
I umpired baseball in my early teens and even 30 years ago it was bad.
Grown men getting into the face of 14 years old umpires over calls, at games for kids barely out of tee-ball. It just doesn’t matter that much.
I remember a coach who would flip over 20 gallon coolers and send ice and drinks flying in the dugout.. in front of his team of 10 years old umpires olds.
In Texas, there's an association, TASO, that is in charge of referees for all sports. There is no requirement about having experience in officiating at all. You attend a few meetings, pay the fees, and start officiating. The crazy thing is that once a TASO member, you can move from sport to sport. It's easy to see officials that are definitely out of their depth. As a player, it is insulting that they can't play their sport because the one in charge of the match is not very good. As parent, it's aggravating because their kid and teammates are getting boned. After personally experiencing the literal "inside baseball" of Texas high school officiating, they bring some of the flak on their officials in their attitude on who can be an official. I knew people that just slid from one sport to the next based on season as a source of a fairly decent income. Volleyball refs just sit in a chair, so physical fitness doesn't really limit how good of an official they can be. Soccer refs on the other hand...
That's the association's problem, not the referees. When I refereed basketball in Australia, referee grading was done according to FIBA standards and you had to be evaluated before any promotion in your referee grade and that could be (at the lowest levels) 3 games on 3 occasions through to 10 games or more. And when we got to a certain (albeit relatively high) level, we'd have every game recorded and reviewed.
No disagreement, which is why I said that the association is to blame. If a ref isn't good enough yet they still continue to be assigned games, then the org allowing that to happen is at fault. The immediate response is that they don't have enough officials to to start sitting officials based on performance/ability. That's just further indictment to me, but "it's just a kid's game" blah blah.
Baseball in particular has a problem with anger is the arguments. Like there is no argument without a hostile tone. Players/managers never seem to merely appeal a call -- they jump straight to harsh yelling.
Compare it to soccer where there is also a lot of whininess in the complaining about calls.
It's become accepted that vulgar, angry, disagreement is acceptable until it goes "too far".
Tantrums are just socially accepted in baseball, and some other sports.
Probably being born from public schools, and teachers being the referees, they don't have to take any nonsense from players and can take the ball away from you, lose you ground you have gained, or card you if are abusive to the referee.
Abusive parents on the sidelines can result in sanctions on clubs.
Even if you think the referee made a bad call, it is never acceptable to be abusive to match officials.
It blows my mind the things I see in football they allow people to get away with.
I love how in rugby if two guys are going a little two hard at each other the referee will call them over along with their captains, and address the captains while these gigantic players stand there like children.
One other offshoot of rugby officiating is they will admit wrongs and they'll say things like "I didn't see that." Compare that to the NFL where the refs make a bad call and the league will back them up to the point of being ridiculous by reinterpreting the rules to make the officials right (see "not a catch").
Absolutely - I used to referee basketball in Australia, including at a high level.
Extremely high level junior, was generally not an issue. As was true local league.
It was the intermediates, the travel leagues. Where "your kid is good but is still not going to be a pro" (the NBA sends a letter to all new D1 college players congratulating them on the effort they've put in to get this far - and to focus on their education, as the NBA drafts <1% of D1 college players, let alone anybody else). Those were the ones where the parents were convinced that their kid was going to be a pro and the only thing holding him back was "that fucking referee".
We had the power to eject those parents from the venue. Which was usually a conversation that went something like this:
Ref: You need to leave the venue until the end of the game.
Parent: It's my fucking kid's game and I'm not leaving and you can't fucking make me.
Ref: You're right, I can't remove you from the venue. I can however forfeit the game on your child's behalf.
Kid: Daaaad. [usually weary as this tends not to happen just the once]. Go and wait in the car. Pleaseeeee.
Parent: I will go and wait in the car, and we're going to wait and when you come out, you and I are going to fucking get into it, ref.
Cue security, if not police, walking refs to their cars.
I spent several years as a soccer ref including high school matches. It never failed that every time I hit my whistle, the side of the stadium opposite of the direction of me signaling the foul would always erupt in jeers. You could always tell the helicopter parents complaining about non-calls not appreciating that soccer is a contact sport. There was only one game where the officiating crew was escorted by police, but I really felt that was over blowing the situation. There was the one game were we had to temporarily suspend the match because of gunfire in the area not aimed at the pitch, but uncomfortably close.
The funny thing is, I became a ref because I was giving the ref of one of the games I was on the touchline coaching wasn't abusive, but definitely a constant barrage of second guessing. At the end of the match, one of the association members suggest that if I didn't like the level of refereeing that I should become a ref myself. I accepted the Pepsi challenge that rest of history. My favorite experience was a coach that was getting a bit grating. I remembered a line an old timer mentioned that I decided to give a try, "hey coach! you got an assistant? you better get 'em warmed up!"
As a coach, the absolute worst part of the 10 year experience absolutely was the parents. Luckily, I never had abusive parts. It was always over excited cheering for the dumbest things from people that had no clue about tactics and thinking that blindly booting the ball up the pitch was awesome. We had no player with the speed or skill of going over the top route one, so it was just a dumb play. Usually, by the end of the season some of the other parents could usually get them calmed down. It also helped to remind some of the over the top parents that this was recreational play, and everyone got the same t-shirt at the end of the season. Nobody was getting scholarships. It was basically bragging rights for the kids back at school.
As teens my brother and I both refed youth soccer. The parents were the absolute worst part of the experience. One of them actually followed my brother back to his car after a game to yell at him more. It was so bad that the ref association took the guy to what I've always called "soccer court" (not sure what it actually was) to have him banned from coming back for the rest of the season. That was a U-12 girls rec game by the way.
That's the perfect age for shitty parents as that's the age where the "good" players have left rec and moved to club teams so that the ones that are left are the ones with bent out of shape parents for their kid not making a club team.
Not all parents are assholes, and as a solo coach, there's no way I could have survived without some of the parent's support with various aspects of managing a team. By the third or fourth season, the parents that had started with me would help wrangle some of the other parents.
> By the third or fourth season, the parents that had started with me would help wrangle some of the other parents
This is where we were with one of my kids' teams. Once they got older and split into the elite-national/regional club level (about U12), the parents were not healthy. Over time, the parents started to realize that their kid wasn't likely to play D1 college soccer, so there wasn't a point in being "those parents".
It also helped that a few of us that either coached, played, or ref'd would "help guide" the other parents. It is now to the point where I wouldn't want my kid to change teams because our parents are so awesome.
There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
reply