Added another game to my playable list of games. (I implemented this year ago, then somehow lost it.) You can now play #Slimetrail: https://kyleburke.info/DB/combGames/slimetrail.html
#combinatorialgames
Hi folks -- I am pleased to announce the public release of Tetro Domain, a small #pico8 strategy game playable on desktop web and mobile: https://puleo.itch.io/tetrodomain
As I mentioned in a previous post, this game is built around the concept of the strategy-stealing argument: its rules have been designed so that there is a nonconstructive proof that the first player always has a winning strategy on any board the game can generate. As the proof is nonconstructive, it does not actually provide any indication of what the winning strategy *is* -- but I believe it ends up being an interesting little strategic challenge to work out the winning strategy that is guaranteed to exist.
The computer opponent you play against is not *especially* strong, but I've found it to be strong enough to sneak out the occasional win against me if I let my guard down. I'm biased, of course, but I've found playing it on mobile especially to be an entertaining way to get a quick strategy fix within a couple of minutes.
I think that *probably* the strategy-stealing argument could be pushed much further to a game with more complexity than this game has -- this design is fairly simple but I'm quite pleased with how it came together.
🎉🥳 I won today's Hackenbush game playing as 🔴 Red!
#combinatorics #gametheory #combinatorialgames
Play Hackenbush at: https://hackenbush.vercel.app/
We got our first talk scheduled for #Sprouts2026! https://kyleburke.info/sprouts/sprouts2026/ I'm looking forward to receiving more proposals.
I've also been getting questions about writing #AIPlayers and updated the directions on that page. https://kyleburke.info/sprouts/sprouts2026/sprouts2026ComputerTournament.php (Some of the notes were about last year's game, whoops!)
One of my students wrecked me in #FjordsGame today! #CombinatorialGames
Hi folks -- I mentioned in a previous post that I've been working for the past month or so on a new #pico8 project. I don't think I am quite ready to release it with full fanfare yet but I *do* think it's at a state now where I've got something worth showing off a bit and I'd be interested to hear any preliminary feedback that people may have about it.
The project in question is a little turn-based strategy game called Tetro Domain. It's a small turn-based strategy game about claiming territories on a board divided into territories that are mostly tetrominoes (hence the name), together with some smaller territories that contain the points you are actually fighting over.
Mathematically, this game grew out of my interest in exploring the strategy-stealing argument that applies to games like Chomp and Hex. All my previous games have had the property that their positions were guaranteed winnable for the player, but -- one way or another -- those games were essentially based on my having an explicit description of the winning strategy in hand. That's a harsh limiter on how complex I can actually make the game. Tetro Domain, on the other hand, is guaranteed winnable by a version of the strategy-stealing argument -- which is nonconstructive. So I don't need to work out an explicit winning strategy to know that one exists!
There are some more bells and whistles I'd like to add before releasing it in full, but if you're interested in playing the current build of it, you should be able to get access through this URL: https://puleo.itch.io/tetrodomain?password=RAWe7Ru68dg7DvhEbGkj
(Feel free to share it out to anyone you think might be interested!)
We have a date for #Sprouts2026: Saturday, April 11, 2026. Woo!
Sprouts is a #CombinatorialGames conference where undergrads give the contributed talks. Everyone can attend. Registration is free and we have great talks as well as human and computer tournaments.
This year we're playing #BattleSheep. Come join us at Sprouts! https://kyleburke.info/sprouts/sprouts2026/
#FjordsGame on the last #GameLunch of the semester. #CombinatorialGames (kinda)
At #Integers2025 this spring, I collaborated with a new group and proved that Misere Partizan Arc Kayles is PSPACE-complete. That paper just went up on the arXiv: https://arxiv.org/abs/2511.21888
For that paper we implemented two new playable games: Misere Partizan Arc Kayles itself (https://kyleburke.info/DB/combGames/miserePartizanArcKayles.html) and a Normal-Play version of Bounded Constraint Logic (https://kyleburke.info/DB/combGames/normalBoundedConstraintLogic.html).
I'm especially excited about how clearly we talked about using Constraint Logic to provide computational hardness.
My most recent game, Aces' Nim, is inspired by ideas from combinatorial game theory (and, in particular, the theory of impartial games). I like the idea of the game speaking for itself in order to convey those ideas, but I also think there's some value in making the connections explicit, so I've decided to start writing a couple of dev logs outlining some strategic ideas for the game and connecting them to established ideas in CGT. I've just posted one part of the first such post: https://puleo.itch.io/aces-nim/devlog/1128881/first-steps-on-strategy-part-13
(The standard theory of impartial games should, I think, give an essentially complete solution of the "optional burn" mode of the game. The "mandatory burn" mode is, I think, a bit more interesting and requires some extension of the standard theory.)
#combinatorialGames #godotengine #gamedev #indiedev #itchio #math
On Monday, November 17, at 3:30pm ET, I get to give the next VCGT talk on the computational complexity of the game #BattleSheep: https://sites.google.com/view/virtual-cgt/seminar
Abstract: Battle Sheep is a board game published by Blue Orange Games where players take turns moving stacks of sheep tokens around a hexagonal board, always leaving at least one sheep behind. In this talk we'll learn the basics of the game, play once, and finally show that determining the winnability of the game is PSPACE-complete. This talk assumes no prior knowledge of computational complexity.
Long overdue: I added TwixT to my table of combinatorial games: https://kyleburke.info/rulesetTable.php#Twixt #CombinatorialGames
Oh! This is a really fun! #CombinatorialGames
The #Sprouts2026 page is up: https://kyleburke.info/sprouts/sprouts2026/ We still don't know which day in April 2026 we'll hold it (probably a Saturday).
We're going to play #BattleSheep. We'll have a human tournament and computer player tournament. You can mess around with computer players here: https://kyleburke.info/sprouts/sprouts2026/sprouts2026ComputerTournament.php
Sprouts is a conference for undergraduates to present about abstract games, but everyone is welcome to attend.
See you in April! #CombinatorialGames
Solving a simple game here; it might be interesting to compute its Nim-value as a (nonpartisan) combinatorial game.
Players take turns filling in a 4x4 square; the first player to complete a 2x2 square loses. I think this is a second-player win (because they can guarantee 12 squares filled in without losing, hence the 13th move must lose.)
The second day of #Integers2025 was excellent! I heard some great talks, especially one from Carrie Finch-Smith. Me and the other three gamesters I know about here also took some time and I think we found a game to be #PSPACE complete, so we're definitely going to be writing that up!
Tonight we got to see a tree that owns itself. Cool stuff!
The organizers have been totally awesome. Great conference so far!
Day 1 of #Integers2025 just wrapped up! Integers is a #NumberTheory and #Combinatorics conference. There's historically a bit of CGT too. Here are my summaries of the #CombinatorialGames talks: https://combinatorialgametheory.blogspot.com/2025/05/integers-2025-cgt-talks.html
Two of the talks were the result of #UndergraduateResearch!
Here are my summaries of the keynote and afternoon session at #Sprouts2025: https://combinatorialgametheory.blogspot.com/2025/04/sprouts-2025-keynote-and-afternoon.html
A lot of other great things happened yesterday, so I wrote another post about that: https://combinatorialgametheory.blogspot.com/2025/04/sprouts2025-wrap-up.html
Thanks to everyone who came and made Sprouts great this year!
I wrote my summaries of talks for the early morning session of #Sprouts2025 last night: https://combinatorialgametheory.blogspot.com/2025/04/sprouts-2025-morning-talks.html
Client Info
Server: https://mastodon.social
Version: 2025.07
Repository: https://github.com/cyevgeniy/lmst