GTX0 AnnouncementsFeedbackHelp | SandboxNewest Posts | Replies | Hottest
NIFE UpdatesRoadmapRequests | HelpDiscuss Game Worlds






So, a bit of backstory. Over christmas my sister and I invented a game where we tried to get all the fingers of a hand out. Pointing to a finger would toggle some number of other fingers, and you were supposed to figure out the pattern.

After christmas, I programmed a version of this where the rules were randomized (with a few obvious constraints) so you had about a million different puzzles you could try:
http://gtx0.com/projects/handgame/
You can also try specific puzzles by sharing that ?seed link.

The basic way the puzzles are generated works like this:

* Each finger can toggle between 1-4 fingers (toggling makes up fingers go down and down fingers go up)

* The script makes sure that any particular finger can be toggled by at least one other finger, but never by all five fingers.

The actual math puzzle here

Is there a mathematical way of figuring out which set of finger rules are solvable and which are not? I have a way of doing a deep search to figure it out manually, but that's not really practical when setting up new games randomly unless I go through all ~2^25 puzzles individually.

If it helps, the actual ?seed is set up like this:

* The seed is a decimal representation of a 5-bit binary number, ex -- 636580 = 10011011011010100100.
* This can be broken down into five chunks: 10011 , 01101 , 10101 , 00100
* Which then indicates which fingers each finger triggers (for example finger #2 triggers fingers 2, 3 and 5).

settingsOptions
There are 20 Replies

Fun game! I think the finger indicator should be more obvious, like a solid circle. Also, I think it's generating puzzles that can't be beaten? You can do a brute force check of all combinations from start to make sure the puzzle can be beaten before displaying.

Posted December 29th, 2018 by mariomguy

Fun game!


Thanks!

Also, I think it's generating puzzles that can't be beaten? You can do a brute force check of all combinations from start to make sure the puzzle can be beaten before displaying.


Or I could try to crowdsource a mathematical solution to that problem :)

Posted December 29th, 2018 by Xhin
Xhin
Fractal icious

You could figure out the maximum combinations required to solve any hand puzzle, then do a brute force check on all possible combinations. If the check finds no solution, the puzzle is discarded.

Or, as you said, you could just have your program report which puzzles were solved in an array. If you have a 100% unsolved rate for certain combinations, make those combos appear less frequently on a logarithmic scale.

:P

Posted December 29th, 2018 by mariomguy

I do have a tool that does this, but as I pointed out, there are around 33,554,422 possible puzzles that I'd have to comb through. I was hoping there would be some kind of mathematical principles I could work with instead.

Posted December 29th, 2018 by Xhin
Xhin
Fractal icious

I think there are too many combinations to deal with for a perfectly clean mathematical solution. Any finger can control any number of other fingers, and you can more or less have the same fingers affecting the same ones in the same ways while still having a solution.

The next best thing is to just keep a record of what works and suppress those that don't. You can give the option for a random combination specifically to test unconfirmed combos, and the option to play only the winnable combinations. I think the "crowdsourcing" method is used for the Android Solitaire game. Brute force checking can help with this as well. If you can multithread such a task, most CPUs are very good at brute force calculations these days. Running both systems simultaneously would very quickly get you a list of millions of winnable solutions.

You don't need to be perfectly clean, you just need to be good enough.

Posted December 29th, 2018 by mariomguy

@mariomguy:

The game is now solvable in all cases. You can also click "Show solution" to see the solution, although it'll subtract 2 from your score (a net of -1 after you solve it):



The new engine works like this:

* Four of the fingers get randomized rules (they each trigger 1-4 fingers each). One of them won't have anything to do yet.
* The hand starts out with all of the fingers up
* Then, the engine will trigger a random finger 3-7 times. It's set up to not trigger the same finger twice in a row (since that would be pointless).
* The last finger that didn't have anything to do yet will trigger whichever fingers are up after all this.

It could probably be improved beyond this, but at least all puzzles have solutions now. IIRC, this "backwards-solving" type of algorithm is used by things like sudoku / chess problem generators.

Posted January 7th by Xhin
Xhin
Fractal icious

Wow! This works so nicely! The only thing I suggest is make sure the animation ends with all fingers up. Sometimes I get all fingers up, but then I'm confused when the very next thing I see is a closed fist. All fingers go up, then the hand ascends to heaven.

Jeez, that's actually a brilliant solution. Well done!



Posted January 7th by mariomguy

The only thing I suggest is make sure the animation ends with all fingers up.


The animation ends with all the fingers down because a new puzzle gets generated.

Posted January 7th by Xhin
Xhin
Fractal icious

Perhaps you can play the animation first, then generate the puzzle. Or generate the puzzle without changing the finger positions (use temp variables if you have to). Figure out the generation using temps, then just swap the current state with the temps after the animation is done and the hand comes back.

Posted January 8th by mariomguy

Perhaps you can play the animation first, then generate the puzzle.


That's what happens currently. What am I missing here? It works like this:

* You get all five fingers up.

* The hand fully turns blue

* The hand ascends to heaven

* The hand comes back, a new puzzle is generated and starts off with all the fingers down. There's also a slight fadein effect like when you click "New Puzzle".

What needs to be changed here exactly? @mariomguy:

Posted January 9th by Xhin
Xhin
Fractal icious

Oh I see what you're saying here, you want the hand to come back blue when it reappears, right? And then turn all the fingers off again for the next puzzle.

Posted January 9th by Xhin
Xhin
Fractal icious

It took a bit of getting used to with how the arrows on the fingers worked, but overall fun game. My score is 9 so far. :P

Posted January 9th by Castrael

The instant you click the winning combination, the hand goes to a fist, and then opens to 5 fingers. Just skip the fist part and go straight to 5 fingers.

Posted January 9th by mariomguy

Oh yeah that's weird, that's a glitch.

Posted January 9th by Xhin
Xhin
Fractal icious

I'll start thinking about the math behind what rules are solvable.

Posted January 12th by EN
EN

By the way, Xhin, this reminds me a lot of Starmaze: http://www.cartania.com/starmaze/intro.html. I think you would really get a kick out of that game/site. The guy goes into this whole artistic/metaphysical exploration of a simple puzzle game.

Posted January 12th by EN
EN

Time for hand sex!

Posted January 12th by Weid man

Just off the top of my head, in essence what we're really doing is XORing some binary vectors together some number of times and trying to get a certain other binary vector.

In this case, we're trying to achieve the vector 11111 (all fingers being up). Since XOR is commutative and associative, it doesn't matter what order we activate the fingers. Also, since it takes place in a binary field, we only need to activate each finger at most once.

For example, http://gtx0.com/projects/handgame/index.php?seed=11598496 suggests an answer of 1,2,3,1,5. Since we can commute the moves, we can rewrite the moves in order to get 1,1,2,3,5. The two 1s will cancel out, giving us just 2,3,5. And if you actually look at five, we see that it doesn't change any of the fingers, so we can ignore it. Clicking 2 then 3 (or 3 then 2) gives us the right answer.

With 2 written as 00001 and 3 written as 11110, this is equivalent to saying 00001^11110 = 11111 (where ^ means XOR).

I'll think more about conditions for solutions next.

Posted January 12th by EN
EN

Another quick thought. Working over F_2 (the field of size 2), XOR is the same as addition in the field. That gives us some linear algebra tools.

If all five vectors(fingers) are linearly independent, they can be made to add up to any vector you want. In particular, 11111. And again, you'll only have to add at most each one once.

So how can you test if they are all linearly independent? One way is to put your vectors into a matrix and use Gaussian elimination to see if you can create the identity matrix. If you ever end up with an all zero row, you know that they are not linearly independent.

Not being LI doesn't mean you can't have a solution, however. It's sufficient, but not necessary. The vectors I gave in my last reply were not LI since they contained the zero vector. But there was still a solution.

You can also just use brute force, since in this case you either use a finger or you don't. That gives 2**5 = 32 different possibilities (really just 31 since you know you have to activate at least one finger). Very easy to test each one and see if you ever get 11111.

There's probably something else clever you can do, but I'll have to think some more.

Edited January 12th by EN
EN

http://gtx0.com/projects/handgame/index.php?seed=15545630 gives solution 5, 4, 2, 5, 4, 5, 4, 1, 5, 1, 3. Using the logic described above we can reduce this to just 2,3,4. Cool, huh?
To test all 31 possibilities you can also just have it cycle through this de Bruijn sequence that will give you every possible 5-bit string by starting with the first five bits then shifting your window to the right:

00001000110010100111010110111110000

That might be a slightly niftier way of checking all of the numbers 1-31.

@Xhin:

Edited Thursday by EN
EN
Reply to: A puzzle (a hand game)
Enter your message here

Site Rules | Complaints Process | Register Complaint Facebook Page
GTX0 © 2009-2017 Xhin GameTalk © 1999-2008 lives on