Unoffical empeg BBS

Quick Links: Empeg FAQ | RioCar.Org | Hijack | BigDisk Builder | jEmplode | emphatic
Repairs: Repairs

Page 1 of 2 1 2 >
Topic Options
#144911 - 21/02/2003 17:04 addicting but annoying game
njdboy
member

Registered: 07/01/2002
Posts: 151
Loc: San Jose, CA
Has anyone played and figured out this game? I know that mathmatically I should be able to figure this out but I am stumped.

Top
#144912 - 21/02/2003 19:36 Re: addicting but annoying game [Re: njdboy]
tanstaafl.
carpal tunnel

Registered: 08/07/1999
Posts: 5539
Loc: Ajijic, Mexico
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.
_________________________
"There Ain't No Such Thing As A Free Lunch"

Top
#144913 - 21/02/2003 19:46 Re: addicting but annoying game [Re: njdboy]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
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.
_________________________
Bitt Faulk

Top
#144914 - 21/02/2003 20:10 Re: addicting but annoying game [Re: wfaulk]
tfabris
carpal tunnel

Registered: 20/12/1999
Posts: 31563
Loc: Seattle, WA
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.
_________________________
Tony Fabris

Top
#144915 - 21/02/2003 20:26 Re: addicting but annoying game [Re: tfabris]
genixia
Carpal Tunnel

Registered: 08/02/2002
Posts: 3411
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.
_________________________
Mk2a 60GB Blue. Serial 030102962 sig.mp3: File Format not Valid.

Top
#144916 - 21/02/2003 20:41 Re: addicting but annoying game [Re: tfabris]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
Weird. That was his opening move every time on my system.
_________________________
Bitt Faulk

Top
#144917 - 21/02/2003 20:47 Re: addicting but annoying game [Re: genixia]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
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.
_________________________
Bitt Faulk

Top
#144918 - 21/02/2003 21:54 Re: addicting but annoying game [Re: wfaulk]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
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.


Edited by wfaulk (21/02/2003 21:59)
_________________________
Bitt Faulk

Top
#144919 - 22/02/2003 18:43 Re: addicting but annoying game [Re: wfaulk]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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...
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144920 - 23/02/2003 09:23 Re: deterministically solved! [Re: johnmcd3]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144921 - 23/02/2003 16:52 Re: deterministically solved! [Re: johnmcd3]
lectric
pooh-bah

Registered: 20/01/2002
Posts: 2085
Loc: New Orleans, LA
All right... That's obscene.

Top
#144922 - 23/02/2003 23:45 Re: addicting but annoying game [Re: genixia]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144923 - 24/02/2003 00:10 Re: addicting but annoying game [Re: wfaulk]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144924 - 24/02/2003 01:34 Re: addicting but annoying game [Re: njdboy]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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


Attachments
143229-pearls.tgz (22 downloads)

_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144925 - 24/02/2003 01:37 Re: addicting but annoying game [Re: johnmcd3]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
and again with an executable compiled on solaris...

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


Attachments
143230-pearls(exec).tgz (22 downloads)



Edited by johnmcd3 (24/02/2003 01:54)
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144926 - 24/02/2003 02:25 Re: addicting but annoying game [Re: johnmcd3]
trs24
old hand

Registered: 20/03/2002
Posts: 729
Loc: Palo Alto, CA
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
_________________________
- trs

Top
#144927 - 24/02/2003 02:30 Re: addicting but annoying game [Re: trs24]
trs24
old hand

Registered: 20/03/2002
Posts: 729
Loc: Palo Alto, CA
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
_________________________
- trs

Top
#144928 - 24/02/2003 03:30 Re: addicting but annoying game [Re: njdboy]
peter
carpal tunnel

Registered: 13/07/2000
Posts: 4172
Loc: Cambridge, England
Has anyone played and figured out this game?

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

Peter

Top
#144929 - 24/02/2003 03:53 Re: addicting but annoying game [Re: trs24]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144930 - 24/02/2003 03:54 Re: addicting but annoying game [Re: trs24]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
I also found a bug in the flash game.


Interesting. I haven't actually played the flash game much, just on paper.
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144931 - 24/02/2003 05:16 Re: addicting but annoying game [Re: peter]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144932 - 24/02/2003 05:20 Re: addicting but annoying game [Re: johnmcd3]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
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
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144933 - 24/02/2003 07:34 Re: addicting but annoying game [Re: trs24]
genixia
Carpal Tunnel

Registered: 08/02/2002
Posts: 3411
You're right...cheating bastard.
_________________________
Mk2a 60GB Blue. Serial 030102962 sig.mp3: File Format not Valid.

Top
#144934 - 24/02/2003 09:09 Re: addicting but annoying game [Re: genixia]
trs24
old hand

Registered: 20/03/2002
Posts: 729
Loc: Palo Alto, CA
johnmcd3 - you're insane!

- trs
_________________________
- trs

Top
#144935 - 24/02/2003 09:58 Re: addicting but annoying game [Re: trs24]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
you're insane!
thanks!
_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144936 - 24/02/2003 11:28 Re: addicting but annoying game [Re: johnmcd3]
njdboy
member

Registered: 07/01/2002
Posts: 151
Loc: San Jose, CA
you guys are awesome! thanks for all the "research" and the solutions.

Top
#144937 - 07/07/2003 18:30 Re: addicting but annoying game [Re: njdboy]
jbradshw
journeyman

Registered: 20/02/2002
Posts: 72
Loc: Atlanta, GA
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
_________________________
One of the last MK2's from SonicBlue... Blue/60gig S/N: 030103111

Top
#144938 - 10/07/2003 21:04 Re: addicting but annoying game [Re: jbradshw]
johnmcd3
enthusiast

Registered: 19/04/2001
Posts: 369
Loc: Seattle, WA (formerly Houston,...
not sure if it's going to end... losing interest...


Attachments
168373-level11.JPG (56 downloads)

_________________________
1998 BMW ///M3 30 GB Mk2a, Tuner, and 10 GB backup

Top
#144939 - 12/07/2003 10:06 Re: addicting but annoying game [Re: johnmcd3]
Anonymous
Unregistered


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.

Top
#144940 - 12/07/2003 10:27 Re: addicting but annoying game [Re: ]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
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,
_________________________
Bitt Faulk

Top
Page 1 of 2 1 2 >