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

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.

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.

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.

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.

Weird. That was his opening move every time on my system.

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.

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.

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...

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

All right... That's obscene.

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

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

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

and again with an executable compiled on solaris...

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

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

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

Has anyone played and figured out this game?

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

Peter

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

I also found a bug in the flash game.

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

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

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

You're right...cheating bastard.

johnmcd3 - you're insane!

- trs

you're insane!

thanks!

you guys are awesome! thanks for all the "research" and the solutions.

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

not sure if it's going to end... losing interest...

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.

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,

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.

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

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.

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.