#combinatorialgames — Public Fediverse posts

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.

#CombinatorialGames #ComputationalComplexity #PSPACE

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!

#NumberTheory #CombinatorialGames

The third and final day of #CGTC 5 is in the books. We had both research talks as well as talks about different #CombinatorialGames texts that maybe not everyone knew about. Here are my summaries: https://combinatorialgametheory.blogspot.com/2025/02/cgtc-5-day-three-talks.html

I miss everyone already!

I didn't get the talk summaries out last night due to the #CGTC conference dinner, but I just finished the post: https://combinatorialgametheory.blogspot.com/2025/02/cgtc-5-day-two-talks.html

#CombinatorialGames

I got stuck in a bathroom stall today at #CGTC. Best pun: I had a PeeSPACE-hard problem.

This is a joke, but not a lie.

If you see a door handle like these photos, you push like so to release the lock.

#ComputationalComplexity #CombinatorialGames

Today was Day 1 of the Combinatorial Game Theory Colloquium (#CGTC) 5 talks! They were excellent! Want to find out why Carlos said: "I need to destroy these moons"? Here are my summaries:

https://combinatorialgametheory.blogspot.com/2025/01/cgtc-5-day-one-talks.html

#CombinatorialGames

I finally wrote a #CombinatorialGames piece I've wanted to write for a long time. It's about how Col's computational complexity went confusedly unsolved for over 35 years and how I got scooped at the end of that but still got a cool result. https://combinatorialgametheory.blogspot.com/2024/08/the-curious-case-of-cols-computational.html

#ComputationalComplexity #PSPACE

I just finished listening to the latest If Books Could Kill episode, this one about Michael Lewis' book on Sam Bankman-Fried: https://twitter.com/IfBooksPod/status/1786021820941963597

Saying that chess is too simple is a huge red flag for those aware that it's EXPTIME-hard. (https://www.sciencedirect.com/science/article/pii/0097316581900169) If you can solve Chess scenarios effortlessly, then you can solve all sorts of extremely heavy computational problems that elude us. #CombinatorialGames #ComputationalComplexity

@rottenindenmark

I'm going to be talking about Algorithmic CGT in India in a few weeks. I really want to start with the fundamentals of #PSPACE, so I want to present the Boolean Formula Game (https://en.wikipedia.org/wiki/Formula_game). Whenever I talk about a game, I like to play it with the audience.

So... I coded a working version: http://kyleburke.info/DB/combGames/booleanFormula.html

It's not particularly fun, mostly because it's often very easy to win as the True player. (I didn't implement any deep strategies to generate more interesting formulas. Advice is welcome!)

Nevertheless, I'm very excited to use this next week and in future talks. #CombinatorialGames #ComputationalComplexity #WebGames