#pspace — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #pspace, aggregated by home.social.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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!
-
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
-
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