addicting but annoying game

Posted by: njdboy

addicting but annoying game - 21/02/2003 17:04

Has anyone played and figured out this game? I know that mathmatically I should be able to figure this out but I am stumped.
Posted by: tanstaafl.

Re: addicting but annoying game - 21/02/2003 19:36

Has anyone played and figured out this game?

I know that our bad-boy troll d33zY knows and understands this game -- he sent the link to me a year or so ago in a PM.

Paul -- can you enlighten us?

tanstaafl.
Posted by: wfaulk

Re: addicting but annoying game - 21/02/2003 19:46

I believe that your fate is set from the first move, assuming that your opponent plays perfectly, which he does.

I could be wrong, but I believe that the only way to win is to get him to move first. Let's call the row of three ``row A'', the row of four ``row B'', etc.

He will always take three from row C. You take all three from row A. He will take one from row C, leaving 1. You take one from row D. He will take two from row D. Take two from row B. He will take another one from row B. Take two from row D, leaving three rows of one. He'll take one, you take another, and that's the only remaining pearl.

At each step, every move made by your opponent is the only one that doesn't allow defeat within two moves.

It's a very annoying game. There's only one possible way to win if your opponent plays correctly. It's like Tic-Tac-Toe, except ties aren't possible. Add to that the amount of time that the Flash interface wastes, and it becomes almost infinitely annoying.
Posted by: tfabris

Re: addicting but annoying game - 21/02/2003 20:10

Your pattern works, assuming that's his opening move. Only, on my system, his opening move is randomized, it's not always the same one.

I'd be curious to know the mathematics behind this, and what the winning strategy is. I wonder what the runtime algorithm uses to decide correct moves.
Posted by: genixia

Re: addicting but annoying game - 21/02/2003 20:26

Ach... won the first time. Beginner's luck

You have to think backwards. Simply put, you need to ensure that there are 2 pearls left for your last move, and take one.

The move before that ideally you want to leave 4, in a 2 by 2 block. At that point he's screwed.

I haven't worked further back than that, but it wouldn't shock me to discover that the person that goes second can always win.
Posted by: wfaulk

Re: addicting but annoying game - 21/02/2003 20:41

Weird. That was his opening move every time on my system.
Posted by: wfaulk

Re: addicting but annoying game - 21/02/2003 20:47

You can also win if there are 3, 4, 5, 6, or 7 pearls. Most of those are unlikely to happen.

You have to make sure that you end up with one row with one pearl and one row with any number of pearls.

The main endgames seem to be 0-0-1-2, 0-0-2-2 and 0-1-2-3. The problem, though, is that you've lost way before you get to those points.

Lemme work some more.
Posted by: wfaulk

Re: addicting but annoying game - 21/02/2003 21:54

All right.

It looks like there are a certain number of indefensible positions. If you can get to one of these, you're good. If not, just make a move that doesn't allow your opponent to saddle you with one. Taking one off of the longest row that wouldn't allow him to put you in one seems to be a good move.

The ones I've found so far are 0-2-4-6, 0-1-4-5, 0-1-1-1, 0-1-2-3, 2-3-4-5, 1-1-3-3, 0-1-1-3, 0-1-3-4, 0-0-a-b (where a+b is even), 1-1-5-5, 2-2-5-5. (I'm not sure about those last two.) Oh, and, obviously, 0-0-0-1.

The computer is a pretty bad first move player. Most of the time, you can get him into one of these predicaments in your first move.
Posted by: johnmcd3

Re: addicting but annoying game - 22/02/2003 18:43

Facinating. My inclination is that this games doesn't actually have very many states and could be easily solved completely. I wonder how hard it would be to exhaustively determine the states where you can force a win? It seems like you could program that pretty easily...
Posted by: johnmcd3

Re: deterministically solved! - 23/02/2003 09:23

I spent a few hours writing a program to deterministically solve the game. I represented the gamespace as a graph of interconnected nodes (unique game states) and marked the paths which led to certain victory or defeat.

I thought the relatively small number of unique game states was interesting. Only 164 in all.

More analysis and statistics to come shortly after I clean some stuff up and generate some tables.

John
Posted by: lectric

Re: deterministically solved! - 23/02/2003 16:52

All right... That's obscene.
Posted by: johnmcd3

Re: addicting but annoying game - 23/02/2003 23:45

but it wouldn't shock me to discover that the person that goes second can always win.

I originally thought so too, but it turns out that the person who goes first can always win. (That is, if he makes a move to 0-3-5-6, 1-3-4-6, or 2-3-4-5. Those positions are unwinable if the game is played perfectly.)

John
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 00:10

It looks like there are a certain number of indefensible positions.... The ones I've found so far are 0-2-4-6, 0-1-4-5, 0-1-1-1, 0-1-2-3, 2-3-4-5, 1-1-3-3, 0-1-1-3 [ed. incorrect], 0-1-3-4 [ed. incorrect], 0-0-a-b (where a+b is even) [ed. incorrect], 1-1-5-5, 2-2-5-5. (I'm not sure about those last two.) Oh, and, obviously, 0-0-0-1.


Yeah, I thought it was interesting how that worked out so I wrote the program to figure out these positions. It turns of that of the 164 total positions, 24 are indefensible. If you are not in one of these positions, it is guaranteed that you can get to one, and if you are in one, it is impossible to win if the game is played perfectly, as your opponent can get to one.

MAP LEVEL with 1 pearls left
position (0-0-0-1) cannot win.
MAP LEVEL with 2 pearls left
MAP LEVEL with 3 pearls left
position (0-1-1-1) cannot win.
MAP LEVEL with 4 pearls left
position (0-0-2-2) cannot win.
MAP LEVEL with 5 pearls left
MAP LEVEL with 6 pearls left
position (0-0-3-3) cannot win.
position (0-1-2-3) cannot win.
position (1-1-2-2) cannot win.
MAP LEVEL with 7 pearls left
MAP LEVEL with 8 pearls left
position (0-0-4-4) cannot win.
position (1-1-3-3) cannot win.
position (2-2-2-2) cannot win.
MAP LEVEL with 9 pearls left
MAP LEVEL with 10 pearls left
position (0-0-5-5) cannot win.
position (0-1-4-5) cannot win.
position (1-1-4-4) cannot win.
position (2-2-3-3) cannot win.
MAP LEVEL with 11 pearls left
MAP LEVEL with 12 pearls left
position (0-2-4-6) cannot win.
position (1-1-5-5) cannot win.
position (2-2-4-4) cannot win.
position (3-3-3-3) cannot win.
MAP LEVEL with 13 pearls left
MAP LEVEL with 14 pearls left
position (0-3-5-6) cannot win.
position (1-2-5-6) cannot win.
position (1-3-4-6) cannot win.
position (2-2-5-5) cannot win.
position (2-3-4-5) cannot win.
position (3-3-4-4) cannot win.
MAP LEVEL with 15 pearls left
MAP LEVEL with 16 pearls left
position (3-3-5-5) cannot win.
MAP LEVEL with 17 pearls left
MAP LEVEL with 18 pearls left



Given this list, the game is solved. It's no more complex than tic-tac-toe, but where you must think further ahead.

John
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 01:34

The attached program can tell what moves force a loss from any position. Below is an example of the run from one simulated game.


Please enter a sorted game state (e.g. "0-4-4-6")
(hit Control-D to break): 3-4-5-6

Moves to force loss from 3-4-5-6:
0-3-5-6
1-3-4-6
2-3-4-5

normalized game state: 1-1-4-6

Moves to force loss from 1-1-4-6:
1-1-4-4

normalized game state: 1-1-1-4

Moves to force loss from 1-1-1-4:
0-1-1-1

normalized game state: 0-0-1-1

Moves to force loss from 0-0-1-1:
0-0-0-1

normalized game state: ^D



The code has been coded and tested on a solaris box, but it should work with reasonably compilant C++ compiler with a semi-recent version of the STL.

John
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 01:37

and again with an executable compiled on solaris...

Edit: bitten by the bbs software's filesize limit. not useful to many anyway.
Posted by: trs24

Re: addicting but annoying game - 24/02/2003 02:25

Well, this game has kept me up for far too long - and I'm way to tired to follow all the possible moves that johnmcd3 has graceously posted. But I did figure this... If you always go first and take all but two from the bottom row - you'll never lose. If you do it every time, he'll vary on how he makes his first move, but as long as you always get the board down to a 1-2-3 or a 1-4-5 on your second move, you're guaranteed to win.

- trs
Posted by: trs24

Re: addicting but annoying game - 24/02/2003 02:30

I also found a bug in the flash game.
If you emilnate all but 2 from the last row - then on his first move he emilinates all but 1 from the 3rd row, then you eminate all from the second row to make the board 3-0-1-2, then he skips a turn! What a cheater! Try it enough times and he'll do it.

- trs
Posted by: peter

Re: addicting but annoying game - 24/02/2003 03:30

Has anyone played and figured out this game?

Isn't the game just Nim? (Spoilers.)

Peter
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 03:53

If you do it every time, he'll vary on how he makes his first move, but as long as you always get the board down to a 1-2-3 or a 1-4-5 on your second move, you're guaranteed to win.


Yes, removing 4 from the bottom row creates a 2-3-4-5 set up from which he cannot recover from if you continue to play correctly.

In addition to taking four from the bottom row, taking four from the other two rows are also safe moves, because they also create "safe" positions. (0-3-5-6 and 1-3-4-6).

John
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 03:54

I also found a bug in the flash game.


Interesting. I haven't actually played the flash game much, just on paper.
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 05:16

Has anyone played and figured out this game?
Isn't the game just Nim? (Spoilers.)

Wow, that's cool how elegant that solution is.

After generating the networks of various game states, I was just starting to look the patterns of why certain moves led to the indefensible positions. I had no idea that people had already analyzed the same game before. Thanks very much for linking that solution, now I know how to search for other literature on the game ("Nim").

From that link I find it cool that finding the next "safe" state from a given game state can be done in O(n) time (where n is the number of rows in the game state), even though the number of game states grows exponentially with n.

This semi-log plot shows that exponential growth. This plot is generated under the premise that the first row contains 3 pearls and every added row contains one additional pearl. Note that n = 3 is the case for the first "Pearls or Swine" game and n = 4 is the case for the one linked above. "Losers" are those states that are indefensible, while "Totals" are the total number of states.






(The asymtotic growth of number of unique game states is still exponential if the additional rows are of a constant size, the above graph is just chosen to match the pearls of swine problem. Below is the exponential growth when each row is of constant size (5). Not that this is not a semi-log plot like above.)




I'll be interested to read more about this problem later, but ironically I need to get ready for a class in algorithm analysis in a few mins.

John
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 05:20

I guess I should have mentioned that by changing the vector labeled max_pearl_set in the main function you can simulate any Nim-style problem. The default is, of course, for pearls or swine 2.

John
Posted by: genixia

Re: addicting but annoying game - 24/02/2003 07:34

You're right...cheating bastard.
Posted by: trs24

Re: addicting but annoying game - 24/02/2003 09:09

johnmcd3 - you're insane!

- trs
Posted by: johnmcd3

Re: addicting but annoying game - 24/02/2003 09:58

you're insane!
thanks!
Posted by: njdboy

Re: addicting but annoying game - 24/02/2003 11:28

you guys are awesome! thanks for all the "research" and the solutions.
Posted by: jbradshw

Re: addicting but annoying game - 07/07/2003 18:30

Looks like they came out with another version of this game. It progresses now. I couldn't use your handy little chart to beat the computer after about round 3 or 4.

http://www.transience.com.au/pearl3.html
Posted by: johnmcd3

Re: addicting but annoying game - 10/07/2003 21:04

not sure if it's going to end... losing interest...
Posted by: Anonymous

Re: addicting but annoying game - 12/07/2003 10:06

In reply to:

From that link I find it cool that finding the next "safe" state from a given game state can be done in O(n) time




In a finite game that doesn't involve luck or information that's hidden from either player, there is always a safe state on every move, unless it is possible to tie. The game just becomes one giant math puzzle. Either player A is in a position to force a win or player B is in a position to force a win, or in a game with possible ties both players could be in a postion to force a tie.

In that pearls game the first player is in a winning position and able to force a win, but if you don't play it right then you put yourself in a losing position and the computer forces a win. Pearls is a theoretical win for player A [EDIT: Pearls 1 is. It looks like Pearls 2 is a win for player B.] Tic Tac Toe is a theoretical tie - both players can force a tie every game, regardless of who goes first. Chess is finite and doesn't involve luck or hidden information (eg. scrabble), so it is possible to solve the game of chess, just as someone solved the game of Nim. As I understand it, someone found a winning strategy for the game of Nim a hundred years ago more or less by chance and observation, and I could be wrong but I think it is still not fully understood why it works like it does. Perhaps it is, but I certainly don't understand it.

Chess and Checkers have too many possibilities to be solved by brute force, like you did with Pearls, but perhaps one day someone will stumble upon a winning (or drawing) strategy for Chess. Maybe that person won't tell anyone, and he'll play in international tournaments and never be defeated and win millions of dollars and then write AI programs that take over the world while people clone Secretariat and Seattle Slew and then all the nations of the world set off their nuclear payloads all at once and just finally get it over with. who knows....

I suppose my point is that in any game state, always one of the two players is in an indefensable position.
Posted by: wfaulk

Re: addicting but annoying game - 12/07/2003 10:27

Untrue. To take the simple example of Tic-Tac-Toe, there are many defensible positions, the empty board being the most obvious.

In addition, his argument was about the complexity involved in determining safe states, not the existence of them,
Posted by: Anonymous

Re: addicting but annoying game - 12/07/2003 10:31

Tic Tac Toe is a game that can end in a draw. So in any Tic Tac Toe game state, either one of the two players can force a win or both players can force a draw. On an empty tic tac toe board, both players can force a draw, so the game is a theoretical draw.

In the game of Nim, there are no ties, so there is always one player in a position capable of forcing a win. I should have made it clear in my last statement that i was refering specifically to non-tie games, such as Pearls/Nim.

In addition, his argument was about the complexity involved in determining safe states, not the existence of them,


Yeah, sorry, i misread that.


By the way, in John's posts where he uses [ code ], some of his post is cut off.
Posted by: Anonymous

Re: addicting but annoying game - 12/07/2003 10:43

I think we should all collaborate and devise a strategy for forcing wins in Chess.
Posted by: wfaulk

Re: addicting but annoying game - 13/07/2003 14:22

Tic Tac Toe is a game that can end in a draw.
Sorry. I misread your original post as ``any game's state''.

Regardless, it's still untrue, as any game's initial position has neither side in an indefensible state. If it did, it wouldn't be a very good game.
Posted by: Anonymous

Re: addicting but annoying game - 13/07/2003 19:06

Regardless, it's still untrue, as any game's initial position has neither side in an indefensible state. If it did, it wouldn't be a very good game.


I beg to differ. Pearls II starts out with the 2nd player in a winning position. That means player 1 cannot win no matter how he plays as long as player 2 plays perfectly.

Chess perhaps may start out with player 1 in a winning position. Nobody knows. But if it does, then the first player can win every single time as long as he knows how to go about forcing his win. And you're right, once you have a game solved, it's no fun playing - I suppose that's why most adults don't bother playing Tic Tac Toe, since with a little a practice you can force a draw every single game.

If you're interested, I have a math book that has a proof of the theorem that in games of this nature either one of the two players must be in a position to force a win or both players must be in a postion to force a tie.