I was recently introduced to Quarto, a game invented by Swiss mathematician Blaise Muller (which even has its own Wikipedia page). The conjecture of interest is that there are no draws possible in Quarto, that is, whether every possible game must produce a winning combination [particularly if true, this bears strongly on playing strategies]. On its face, there are 16! (slightly in excess of 20 trillion) different complete game positions possible, although, admittedly, there are many symmetries at play here.
In an attempt to prove/disprove the conjecture, I built a Quarto simulation in MATLAB that was somewhat smart (it pared many branches of the tree early). After about a week runtime, I called it quits; at that point it had looked at about 2.5 billion game combinations, and found no draws.
So I think I am looking for one of four things:
- A single counterexample of a complete Quarto board that is a draw.
- An analytic proof that no draws are possible.
- A pointer to someplace else where this question has been addressed previously.
- A strategy for parsing the required search space that is (at a minimum) about four orders of magnitude more efficient than brute force.
Any thoughts or insights?
Best Answer
If I understand correctly (you're not asking about perfect play),
seems to be a draw.
I got that from here.