Imperfect-Information Games on Quantum Computers: A Case Study in Skat
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.
Kai: I'm Kai.
Mira: And I'm Mira, here with Lev.
Kai: We're looking at the paper: "Imperfect-Information Games on Quantum Computers".
Mira: Here's the gist of the paper. Imperfect-Information Games on Quantum Computers: A Case Study in Skat illustrates how quantum computers can play a significant role in solving games with imperfect information by using quantum registers to encode game information and quantum gates to model game progress, potentially yielding a computational speedup over classical approaches Problem Context Game theory has had a major impact on many sectors beyond games Some of the predicted economic variables are only partially known through probability distributions It has been shown that n-player imperfect-information games may be NP-hard
1: , making them difficult to compute classically To solve them formally, or at least approximate the game-theoretic solution, significant advantages may be obtained from the computational power of entangled quantum systems Quantum Game Theory Concepts Around 25 years ago, quantum game theory began to attract attention
11, 12: The idea was to use entangled initial states and quantum correlations to establish cooperation that is not possible classically The concept of a classical player, corresponding to a simple random variable on a finite-cardinality probability space, has been shown to extend to that of a quantum player, corresponding to a self-adjoint operator on a quantum-probability Hilbert space Quantum versions of von Neumann’s minimax theorem for zero-sum games—often considered the starting point of game theory—were proven in
13: Encoding and Game Evolution The paper details a quantum encoding of Skat, where the initial state is represented as a superposition of all possible card distributions Φini⟩ = 1/√N · (Φ1⟩ + Φ2⟩ + · · · + ΦN ⟩ This involves constructing kets as ψi⟩ = ψ(1)i⟩ ψ(2)i⟩...
Kai: ψ(ni)i>, where each card state can be represented as an nc-digit binary number Game progress is modeled by unitary operators U, which are decomposed into parts that act only on one card, such as U = O 32 i=1 Ui Playing a card involves applying a single Pauli-X gate, conditioned on the table qubit being in state 0⟩ Quantum Counting and Payoff The evaluation of the winning probability is achieved through quantum counting, which is a combination of Grover’s algorithm and quantum phase estimation (QPE) The number of paths N in the subset of winning paths can then be counted via N = N tot · sin2 ϕ / 2 A suitable payoff function Pn(x) is introduced to define the game-theoretic solution, maximizing the expectation value Pn(x) = Xn i=1 (pwin(x, i) · Val(x, i) won − 2 ·
1 − pwin(x, i): · Val(x, i) lost Quantum Feasibility and Complexity The complexity of the quantum algorithm is estimated by counting the CX gates necessary for execution For N = 10, card playing and trick taking lead to a CX count approximately of order 107 The whole circuit has to be executed with 1,000 shots, or even more, to obtain a good approximation This gives around 1016 CX gates It has been shown that the game information of an imperfect-information game such as Skat can be encoded into quantum states, and that the game’s initial state can be prepared as a superposition using unitary gates A quantum advantage may arise in the tree search as the game size increases Future work should investigate a suitable payoff function for player A and how to put the Skat The paper is best interpreted as a theoretical and pedagogically accessible study of quantum feasibility for solving partially observable problems References
1: Jean R.
Mira: S.
Kai: Blair, David Mutchler, and Cheng Liu.
Title and authors: Kai: So we're looking at this paper now called "Imperfect-Information Games on Quantum Computers: A Case Study in Skat". It looks like they’re using Skat as a specific example to see how quantum computers can handle games where you don't know everything at the start.
Mira: Right, it’s about taking something that's hard for classical computers because of that incomplete information—like knowing what cards are hidden—and seeing if quantum registers and gates can give us an edge. It frames this as a problem that gets really big in terms of state space size when you add uncertainty to the game.
Lev: From my side, I'm thinking about the hardware aspect. They mention needing roughly four hundred logical, error-corrected qubits just to handle the state space for Skat using a quantum computer <ref:2411.15294#pg2>. That puts a real strain on what we can actually build right now with current superconducting systems and what fidelity we can expect.
Kai: Exactly. So the paper is saying that in terms of state-space size alone, a machine with about four hundred logical qubits could manage it <ref:2411.15294#pg2>. It’s setting a benchmark for how big the quantum advantage could theoretically be for these kinds of games compared to traditional hardware.
Mira: What's interesting is how they map the game itself onto quantum concepts. They start by saying that around twenty-five years ago, people started looking at quantum game theory <ref:2411.15294#pg3>. The core idea there was using entangled initial states to create cooperation that classical players just can't achieve <ref:2411.15294#pg3>.
Lev: So it’s connecting the abstract math of quantum game theory, like von Neumann’s minimax theorem for zero-sum games which they mention in thirteen, to a practical card game like Skat <ref:2411.15294#pg2>. That's a big leap from pure theory to something concrete.
Kai: And they explain how they do that by encoding the initial state as a superposition of every possible card distribution, which they write as Phiini⟩ equals one over N times the sum of all individual distributions <ref:2411.15294#pg2>. It’s a lot of bookkeeping just to set up the starting point.
Mira: And then for game progress, they model it with unitary operators, like U which they decompose into parts that only act on one card at a time <ref:2411.15294#pg2>. This is the mechanism for how the game evolves as players play their cards.
Lev: When you look at the execution cost, they estimate that playing a card and taking a trick leads to about ten to seven thousand C-X gates <ref:2411.15294#pg3>. And when you run that whole circuit with one thousand shots or more, you're talking about around ten to the power of sixteen C-X gates <ref:2411.15294#pg3>. That’s a lot of gate operations for what they’re trying to solve.
Title and authors: Kai: Ten to the power of sixteen C-X gates is a massive number, so that speaks directly to the complexity and feasibility on physical hardware today, doesn't it? It shows that even with quantum speedup, the actual circuit depth is still quite high for a practical run <ref:2411.15294#pg3>.
Mira: The paper then talks about how they evaluate winning probability using something called quantum counting, which mixes Grover’s algorithm and quantum phase estimation <ref:2411.15294#pg3>. They use that to count the number of paths in the set of winning paths, which they call N equals N tot times sin squared phi over two <ref:2411.15294#pg3>.
Lev: That counting process is where you need precision, and it links back to the payoff function they introduce, Pn(x), which maximizes the expectation value Pn(x) equal to X i equals one pwin of x i times Val of x i won minus two times one minus pwin of x i times Val of x i lost <ref:2411.15294#pg3>. It’s trying to define the game-theoretic solution through this expectation value.
Kai: So, to summarize what we have covered so far, the paper is showing that Skat can be encoded into quantum states, and that by using those unitary gates for progress and quantum counting for payoff, you can potentially find a better way to play than classical methods <ref:2411.15294#pg2>. It’s a theoretical study of how to approach partially observable problems with this tool.
Mira: And they suggest some improvements in the approach themselves <ref:2411.15294#pg3>. They point out that they extended a double-dummy Skat solver, which was fast for open-card play, to handle partially observable gameplay using Monte Carlo sampling <ref:2411.15294#pg3>.
Lev: That's interesting because moving from just open cards to partial observability introduces machine learning methods, like those used in research on bridge and Skat that involve Monte Carlo sampling <ref:2411.15294#pg3>. But they also mention the use of knowledge-based paranoia search and weighted sampling of belief space <ref:2411.15294#pg3>.
Kai: So the improvement mentioned is basically moving beyond just solving the perfect information version to dealing with hidden cards by using those advanced search techniques <ref:2411.15294#pg3>. It shows that they can beat a top player once in an unofficial match by including hope cards twenty-seven <ref:2411.15294#pg1>.
Mira: That’s a nice application of incorporating uncertainty into the quantum framework, which is crucial since Skat has that inherent randomness in the deal <ref:2411.15294#pg2>. They also classify Skat based on its combinatorial, strategic, and fortune aspects in Fig. two <ref:2411.15294#pg3>.
Lev: When you look at what this means for real hardware, the complexity estimate is a bit scary; they need around ten to the power of sixteen C-X gates just to get a good approximation when running one thousand shots <ref:2411.15294#pg3>. That suggests that while the concept is sound, translating this into something you can run reliably on today's noisy hardware is a huge hurdle for practical implementation <ref:2411.15294#pg3>.
Title and authors: Kai: So what does this actually change for us who are looking at quantum computing right now? It shows that the problem isn't just about solving hard optimization problems; it’s about how we can structure the game information itself onto these quantum registers <ref:2411.15294#pg1>.
Mira: I think the real implication is in formalizing strategies for complex, incomplete-information games that are too large for classical search methods <ref:2411.15294#pg3>. It gives a language to discuss how quantum correlations could establish cooperation even where classical players can't <ref:2411.15294#pg3>.
Lev: For me, the limitation they state is that it’s still a theoretical study of quantum feasibility for solving partially observable problems <ref:2411.15294#pg3>. They are not showing a fully optimized, practical solver yet; they’re showing the path to one.
Kai: Exactly. The future work they suggest is investigating a suitable payoff function for player A and how to put the Skat game into this framework more robustly <ref:2411.15294#pg3>. It points toward where the next generation of quantum algorithms needs to focus in terms of strategy design <ref:2411.15294#pg3>.
Mira: So, to wrap up on this paper, it’s a theoretical and pedagogically accessible study focused on showing that game information can be encoded into quantum states, and the initial state can be prepared as a superposition using unitary gates <ref:2411.15294#pg3>. It’s about proving the feasibility of using quantum counting to find winning paths in these types of games <ref:2411.15294#pg3>.
Lev: From an engineering standpoint, it’s a good exercise in defining the necessary complexity before you try to build a scalable system for something like Skat <ref:2411.15294#pg3>.
Kai: Yeah, and that complexity estimate gives us a very concrete number to work against when we think about scaling up these quantum systems for more complex scenarios <ref:2411.15294#pg3>.
Mira: So the paper suggests that quantum advantage might arise specifically in the tree search as the game size increases beyond what classical methods can manage efficiently <ref:2411.15294#pg3>. That’s where we’d really want to see those speedups materialize, if we can build it <ref:2411.15294#pg2>.
Lev: It’s interesting that they compare the state-space size alone to what a quantum computer with roughly four hundred logical, error-corrected qubits might handle <ref:2411.15294#pg2>. That number really grounds the discussion in current hardware capabilities, not some distant future machine.
Kai: So we’ve seen how they encode the game and what the complexity looks like on paper <ref:2411.15294#pg3>. We need to keep an eye on how those state-space size estimations evolve as we build more qubits with better error correction <ref:2411.15294#pg2>.
Mira: And we need to figure out that payoff function they mentioned, because that's what really defines the game-theoretic solution for player A in this context <ref:2411.15294#pg3>.
Lev: I just think it’s a solid foundation for understanding how quantum computation can tackle these kinds of search problems, even if the gate count is high right now <ref:2411.15294#pg3>.
Kai: It definitely gives us something tangible to discuss in the lab about what kind of quantum advantage we are actually aiming for in practical applications <ref:2411.15294#pg3>.
The paper's summary: Kai: So, to wrap up on that Skat paper we just looked at, they basically show you how you can take a game where you don't know everything—like Skat—and encode all that uncertainty into quantum states using those quantum registers we talked about.
Mira: Right. It’s like they built a map of every single possible way the cards could have been dealt at the start, and they put that whole map into a quantum superposition.
Lev: And then to play the game, you use these unitary operators to model what happens when you play one card or take a trick, which keeps evolving that superposition.
Kai: The big payoff here is using quantum counting—which mixes Grover’s algorithm with phase estimation—to actually figure out the winning probability by counting all those possible paths in the game tree.
Mira: That lets you calculate an expectation value, which is basically a score that tells you how much better Player A is expected to do than Player B, based on those quantum states.
Lev: But let's be real about the numbers they gave us. They estimated needing about ten to the power of sixteen C-X gates just for one thousand shots to get a decent approximation.
Kai: That number is massive, so it’s a huge hurdle for what we can build right now with current hardware. It shows the theoretical path is there, but the physical implementation has a lot of work to do on the gate count and fidelity.
Mira: What this changes for us as theorists is that it gives us a way to formalize strategies for these complex games where classical search methods just choke because they can't handle all those possibilities.
Lev: It suggests that if we can scale up the qubits with better error correction, maybe this approach could actually start giving some meaningful advantage in the tree search part of the game.
Kai: That’s the main takeaway—it proves that you can encode imperfect information into quantum systems and use quantum counting to search for optimal play in those games.
Mira: And they suggest future work should focus on defining a better payoff function for Player A, because right now, that’s what needs further refinement to really make it a practical solver.
The paper's improvements: Tom: So, we're talking about what the authors think they should do next with this Skat quantum game study, right? They aren't just stopping at showing a proof of concept for encoding Skat information into those quantum states we discussed earlier.
Kai: They suggest focusing on making the payoff function for Player A really robust, because right now it’s a bit vague, and that needs to be defined better to get a real game-theoretic solution.
Mira: Yeah, they point out that they need to figure out exactly how Player A is supposed to maximize their score in this complex setting—that specific definition of the payoff function is the next big assumption underneath all this quantum math.
Lev: From my side, I think that defining a proper payoff function is crucial because it dictates what kind of search algorithm you even need to design for the game.
Kai: And they also mention extending their double-dummy Skat solver, which was good for simpler games, to handle the partial observability we're talking about here using Monte Carlo sampling techniques.
Mira: That’s a move toward handling more realistic scenarios, because in actual play, you don't always know every single card right from the start.
Lev: So it means they’re moving away from just a perfect information setup to something that accounts for the messy reality of trick-taking games where information is hidden.
Kai: It shows they’re trying to bridge the gap between pure quantum theory and solving these kinds of practical, partially observable problems in card games.
Mira: The implication there is that this approach could be useful for any game, not just Skat, if you can figure out a way to map the specific rules onto these quantum registers effectively.
Lev: But they are also clear about what they aren't doing yet, which is that this paper itself is still mostly a theoretical study of quantum feasibility for these problems.
Kai: So the limitation is that it’s not a fully optimized, ready-to-deploy solver yet; it’s a blueprint showing the path forward.
Mira: They suggest looking at how to put the Skat game into this framework more robustly, which means they need to refine those search and strategy components we talked about.
Conclusion: Kai: So we’ve been looking at the "Imperfect-Information Games on Quantum Computers: A Case Study in Skat" paper, which showed how you can encode a game like Skat into quantum states to try and beat classical approaches.
Mira: It really boils down to encoding the game's starting state as a superposition of all possible card distributions, which is the core idea they need for this work to make sense.
Lev: And even though they mapped it out, remember that ten to the power of sixteen C-X gates is what you’d be dealing with on real hardware right now, so scaling up is definitely a big challenge.
Kai: That's the caveat—the theoretical path looks good, but the engineering for running it reliably at that gate count is still a long way off.
Mira: They are still pointing toward refining that payoff function for Player A because without a solid definition of what winning means in this quantum context, you can't truly solve the game.
Lev: I agree with Mira on the payoff function; it’s the missing piece that connects the quantum mechanics to an actual strategy for playing Skat.
Kai: And they are trying to move toward a better version of their solver by including techniques like Monte Carlo sampling when dealing with partial information.
Mira: It’s interesting how they’re combining those different methods, like quantum counting and Monte Carlo sampling, to try and solve this kind of complex problem.
Lev: For me, the main point is that this gives us a solid benchmark for the complexity we need to overcome if we want to build something that can actually run on real quantum processors.
Kai: It’s definitely an interesting study showing how game information itself can be structured onto quantum registers in a way that classical computers just don't handle well.
Mira: So, while it’s still mostly theoretical feasibility right now, the idea of using entanglement to establish cooperation where classical players can't is what makes this whole area so compelling.
Lev: And honestly, looking at the complexity estimate for ten to the power of sixteen gates on real hardware just confirms that we need serious progress in qubit count and error correction before we see this kind of advantage in practice.
U. Armbräuster, S. Edelkamp, G. Maresch, E. Schulze
Atos Future Makers Research Community · Computer Science Department, Faculty of Electrical Engineering, Czech Technical University of Prague · Department of Theoretical Computer Science and Mathematical Logic, Charles University in Prague · Institute for Discrete Mathematics and Geometry, Technical University of Vienna · Bull GmbH
quant-ph, cs.ET, cs.GT
Submitted: 2024-11-22
Updated: 2026-05-17
Journal ref: Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems 2026 (pp. 2509-2517))
DOI: 0.65109/PYJU2489
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 69/100
The gist: Imperfect-Information Games on Quantum Computers: A Case Study in Skat illustrates how quantum computers can play a significant role in solving games with imperfect information by using quantum…
Key concepts
- Quantum Encoding
- The game's initial state is represented as a superposition of all possible card distributions. This involves creating quantum states where every possible starting scenario exists simultaneously. This allows the quantum computer to consider all possibilities at once, which is key to handling imperfect information.
- Unitary Operators (Game Progress)
- Unitary operators model how the game progresses, such as playing a card. These operators are decomposed into smaller parts that act on individual cards. Playing a card is specifically modeled by applying a Pauli-X gate, conditioned on the table qubit being in state |0>, simulating the action of playing a specific card.
- Quantum Counting
- Winning probabilities are calculated using quantum counting, which combines Grover's algorithm and quantum phase estimation. This technique efficiently counts the number of winning paths within the game's state space, providing a way to determine the likelihood of Player A winning.
- Payoff Function Pn(x)
- A payoff function is introduced to define the game-theoretic solution. This function calculates an expected value based on whether a specific move leads to a win or loss, weighted by the value of that outcome. The goal is to maximize this expectation value, representing the best strategic choice for a player.
Terminology
Summary
Imperfect-Information Games on Quantum Computers: A Case Study in Skat illustrates how quantum computers can play a significant role in solving games with imperfect information by using quantum registers to encode game information and quantum gates to model game progress, potentially yielding a computational speedup over classical approaches
Problem Context
Game theory has had a major impact on many sectors beyond games Some of the predicted economic variables are only partially known through probability distributions It has been shown that n-player imperfect-information games may be NP-hard [1], making them difficult to compute classically To solve them formally, or at least approximate the game-theoretic solution, significant advantages may be obtained from the computational power of entangled quantum systems
Quantum Game Theory Concepts
Around 25 years ago, quantum game theory began to attract attention [11, 12] The idea was to use entangled initial states and quantum correlations to establish cooperation that is not possible classically The concept of a classical player, corresponding to a simple random variable on a finite-cardinality probability space, has been shown to extend to that of a quantum player, corresponding to a self-adjoint operator on a quantum-probability Hilbert space Quantum versions of von Neumann’s minimax theorem for zero-sum games—often considered the starting point of game theory—were proven in [13]
Encoding and Game Evolution
The paper details a quantum encoding of Skat, where the initial state is represented as a superposition of all possible card distributions Φini⟩ = 1/√N · (Φ1⟩ + Φ2⟩ + · · · + ΦN ⟩ This involves constructing kets as ψi⟩ = ψ(1)i⟩ ψ(2)i⟩... ψ(ni)i>, where each card state can be represented as an nc-digit binary number Game progress is modeled by unitary operators U, which are decomposed into parts that act only on one card, such as U = O 32 i=1 Ui Playing a card involves applying a single Pauli-X gate, conditioned on the table qubit being in state 0⟩
Quantum Counting and Payoff
The evaluation of the winning probability is achieved through quantum counting, which is a combination of Grover’s algorithm and quantum phase estimation (QPE) The number of paths N in the subset of winning paths can then be counted via N = N tot · sin2 ϕ / 2 A suitable payoff function Pn(x) is introduced to define the game-theoretic solution, maximizing the expectation value Pn(x) = Xn i=1 (pwin(x, i) · Val(x, i) won − 2 · [1 − pwin(x, i)] · Val(x, i) lost
Quantum Feasibility and Complexity
The complexity of the quantum algorithm is estimated by counting the CX gates necessary for execution For N = 10, card playing and trick taking lead to a CX count approximately of order 107 The whole circuit has to be executed with 1,000 shots, or even more, to obtain a good approximation This gives around 1016 CX gates
Conclusion and Outlook
It has been shown that the game information of an imperfect-information game such as Skat can be encoded into quantum states, and that the game’s initial state can be prepared as a superposition using unitary gates A quantum advantage may arise in the tree search as the game size increases Future work should investigate a suitable payoff function for player A and how to put the Skat The paper is best interpreted as a theoretical and pedagogically accessible study of quantum feasibility for solving partially observable problems
References
[1] Jean R. S. Blair, David Mutchler, and Cheng Liu. Games with imperfect information
[2] H. J. Bremermann. p. 0 To solve them
formally, or at least approximate the game-theoretic solution, significant advantages may be obtained from the
computational power of entangled quantum systems. A well-known statement by the mathematician and
computer scientist Hans-Joachim Bremermann from the
1960s reads [2].Where the paper says it
[3] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
[4] Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa. How many qubits are needed for quantum computational supremacy? p. 3 Therefore, a quantum-mechanical description
and encoding of the problem in terms of quantum states
is needed first, so that a gate set can be defined that
properly represents the progress of the game. ENCODING
In principle, there are many different ways to map a
given card distribution to a state vector.Where the paper says it
[5] Jonathan Schaeffer, Yngvi Bj¨ornsson, N. Burch, Akihiro Kishimoto, Martin M¨uller, Robert Lake, Paul Lu, and Steve Sutphen. Solving checkers
[6] R. Gasser. Harnessing Computational Resources for Efficient Exhaustive Search
[7] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan and Demis Hassabis. Mastering Chess and Shogi by self-play with a general reinforcement learning algorithm. p. 1 In others, such as
chess, Shogi, and Go, computers clearly outperform humans [7]. Card-game play has recently become a research objective for decision making under imperfect information,
and current card-game solvers are beginning to challenge human pre-eminence. Maresch,4 and E. Schulze5
1Atos Future Makers Research Community, Wagramer Straße 19, 1220 Vienna
2Computer Science Department, Faculty of Electrical Engineering, Czech Technical University, Prague
3Department of Theoretical Computer Science and Mathematical Logic
Faculty of Mathematics and Physics, Charles University in Prague
4
Institute for Discrete Mathematics and Geometry,
Technical University of Vienna, Wiedner Hauptstraße 8-10, Vienna
5Bull GmbH, Von-Der-Wettern-Straße 27, 51149 Cologne
For decades, it has been known that quantum computers might serve as tools for solving specific classes of problems that have long been considered computationally infeasible.Where the paper says it
Where the paper says it
[8] Tristan Cazenave and V´eronique Ventos. The αµ search algorithm for the game of bridge
[9] Stefan Edelkamp. Challenging human supremacy in Skat
[10] F. Schettler and G. Kirschbach. Das große Skatvergnügen
[11] David A. Meyer. Quantum strategies
[12] Jens Eisert, Martin Wilkens, and Maciej Lewenstein. Quantum games and quantum strategies
[13] Andreas Boukas. Quantum formulation of classical two person zero-sum games
[14] C. E. Lemke and J. p. 1 Today, imperfect-information games are solved using different methods. Finding Nash equilibria via the
Lemke–Howson algorithm [14], modeling the problem as
a Bayesian game in which uncertainty is represented by a
probability distribution [15], and applying so-called counterfactual regret minimization [16], in which the regret
function of alternative strategies is minimized, are among
the most established methods for finding the best strategies for games of this category. Today, imperfect-information games are solved using different methods. Finding Nash equilibria via the
Lemke–Howson algorithm [14], modeling the problem as
a Bayesian game in which uncertainty is represented by a
probability distribution [15], and applying so-called counterfactual regret minimization [16], in which the regret
function of alternative strategies is minimized, are among
the most established methods for finding the best strategies for games of this category.Where the paper says it
Where the paper says it
[15] John C. Harsanyi. Games with incomplete information played by bayesian players, i-iii
[16] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information
[17] Emanuel Lasker. Das verst¨andige Kartenspiel
[18] Emanuel Lasker. Strategie der Spiele – Skat
[19] Joseph Petrus Wergin. Wergin on Skat and Sheepshead
[20] S. Grandmontagne. Meisterhaft Skat spielen
[21] Thomas Kinback. Skat-Rätsel – 50 lehrreiche Skataufgaben mit L¨osungen und Analysen
[22] Manfred Quambusch. Gläserne Karten – Gewinnen beim Skat
[23] Siegfried Harmel. Skat–Zahlen
[24] Rainer G¨oßl. Der Skatfuchs – Gewinnen im Skatspiel mit Mathematische Methoden
[25] Jeffrey Richard Long. Search, Inference and Opponent Modelling in an Expert-Caliber Skat Player
[26] Douglas Rebstock, Christopher Solinas, Michael Buro, and Nathan R. Sturtevant. Policy based inference in trick-taking card games
[27] Stefan Edelkamp. Improving computer play in skat with hope cards
[28] Douglas Rebstock, Christopher Solinas, and Michael Buro. Learning policies from human data for Skat
[29] Stefan Edelkamp. On the power of refined skat selection
[30] Stefan Edelkamp. ELO system for skat and other games of chance
[31] Sebastian Kupferschmid. Entwicklung eines DoubleDummy Skat Solvers mit einer Anwendung f¨ur verdeckte Skatspiele
[32] Thomas Keller and Sebastian Kupferschmid. Automatic bidding for the game of Skat
[33] Michael Buro, Jeffrey Richard Long, Timothy Furtak, and Nathan R. Sturtevant. Improving state evaluation, inference, and search in trick-based card games
[34] Christopher Solinas, Douglas Rebstock, and Michael Buro. Improving search with supervised learning in trick-based card games
[35] Timothy Michael Furtak. Symmetries and Search in Trick-Taking Card Games
[36] Stefan Edelkamp. Knowledge-based paranoia search
[37] Gal Cohensius, Reshef Meir, Nadav Oved, and Roni Stern. Bidding in spades
[38] Junkang Li, Bruno Zanuttini, Tristan Cazenave, and V´eronique Ventos. Generalisation of alpha-beta search for AND-OR graphs with partially ordered values
[39] Samuel Bounan and Stefan Edelkamp. Trick costs for αµ and new relatives
[40] Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen., Zhe Wang., Audrunas Gruslys., Aleksandra Malysheva., Mina Khan., Sherjil Ozair., Finbarr Timbers., Toby Pohlen, Tom Eccles, Mark Rowland, Marc Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos. Mastering the game of stratego with model-free multiagent reinforcement learning. p. 2 Although
Skat is studied here, the results should be transferable
to other card games and games with incomplete information. For example, Stratego is a classical two-player
zero-sum game with partial observability.Where the paper says it
[41] Fereshte Mozafari, Heinz Riener, Mathias Soeken, and Giovanni De Micheli. Efficient boolean methods for preparing uniform quantum states
[42] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition
[43] Stefan Edelkamp. Could the declarer have discarded it? p. 2 Skat deal with the Diamond 8 and Ace taken, and
the Heart and Club 8 discarded by the declarer in the middle. trick-taking: in clockwise order, each player places a
card on the table, and the winner of the trick leads
the next trick.Where the paper says it
[44] Stefan Edelkamp. Dynamic play via suit factorization search in skat
[45] Leonid Abdurakhimov, Janos Adam, Hasnain Ahmad, Olli Ahonen, Manuel Algaba, Guillermo Alonso, Ville Bergholm, Rohit Beriwal, Matthias Beuerle, Clinton Bockstiegel, Alessio Calzona, Chun Fai Chan. Generalisation of alpha-beta search for AND-OR graphs with partially ordered values
[46] Alok Shukla and Prakash Vedula.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Quantum computers can play a significant role in solving games using quantum registers to encode game information, allowing for
a potential computational speedup over classical approaches
by usingquantum counting of winning paths.
-
AI systems can be adapted to solve imperfect-information games by mapping them onto quantum circuits where the initial state is prepared as a superposition of all possible distributions, effectively representing the
superposition of all possible distributions at the beginning.
-
The improved system can evaluate game outcomes by measuring a score operator SA and calculating the overlap with a favorable subspace, which yields
the probability that player A wins the game,
allowing for recommendations based on maximizing an expectation value payoff function.
Abstract
For decades it is known that Quantum Computers might serve as a tool to solve a very specific kind of problems that have long thought to be incalculable. Some of those problems are of a combinatorial nature, with the quantum advantage arising from the exploding size of a huge decision tree. Although this is of high interest as well, there are more opportunities to make use of the quantum advantage among non-perfect information games with a limited amount of steps within the game. Even though it is not possible to answer the question for the winning move in a specific situation, people are rather interested in what choice gives the best outcome in the long run. This leads us to the search for the highest number of paths within the game's decision tree despite the lack of information and, thus, to a maximum of the payoff-function. We want to illustrate on how Quantum Computers can play a significant role in solving these kind of games, using an example of the most popular German card game Skat. Therefore we use quantum registers to encode the game's information properly and construct the corresponding quantum gates in order to model the game progress and obey the rules. Finally, we use a score operator to project the quantum state onto the winning subspace and therefore evaluate the winning probability for each alternative decision by the player to be made by using quantum algorithms, such as quantum counting of the winning paths to gain a possible advantage in computation speed over classical approaches. Thus, we get a reasonable recommendation of how to act at the table due to the payoff-function maximization. This approach is clearly not doable on a classical computer due to the huge tree-search problem and we discuss peculiarities of the problem that may lead to a quantum advantage when exceeding a certain problem size.
Sources
- The {\alpha}{\mu} Search Algorithm for the Game of Bridge
- Policy Based Inference in Trick-Taking Card Games
- Learning Policies from Human Data for Skat
- On the Power of Refined Skat Selection
- ELO System for Skat and Other Games of Chance
- Improving Search with Supervised Learning in Trick-Based Card Games
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements