Hello there.. Im working on a shanghi style game...(some people call it mahjongg) Basically you have a pyramid of tiles and you can take 2 matching tiles away at a time. Ok.. so if you know what im talking about.. here''s the problems. #1) I want to be able to guarentee the game is ''able to be won'' if they make the correct moves. This means I can''t just randomly place the tile, but I to semi-randomly place the tiles so it''s a differnt game every time you play. #2) I need to come up with a quick way for the computer to tell you how many ''possible'' moves there are left. It''s a 3-d array for the tiles in x/y/z. Im open for any suggestions..because im pretty stumped. Thanks in advance. Cygor (this msg is also being posted in the AI forum since it''s kinda ai''ish.)

AFIK:

-the only "unwinnable" situation in the game is if you have the same tile stacked 4-deep (i.e. in the middle). Everything else should be winnable in some way. The odds of this happening naturally are fairly astronomical.

-If you want to make an "always-winnable" game (you''re going to kick yourself this is so easy), fill the board in pairs from the bottom-up. You can start at random positions in each horizontal row, and you just have to follow the rules in reverse: only place tiles adjacent to existing tiles, and only place tiles on the next level when the tile beneath it exists.

-IMHO, the "# of possible moves left" algorithm is intractable, since the game can be played and solved so many different ways.

HTH

The number of possible moves left is not intractable. There are at most N^2 possible different moves at any given time, where N is the number of remaining tiles, so its, at most, an O(N^2) operation to determine how many are legal moves.

As for a fast way to calculate that, I would guess that each turn simply subtract one from the last number of possible moves, and then exam each tile that was made free by the move and check how many possible moves they have. Add that number to the last count. That should run in O(N) in the number of tiles.

Thanks for the input and help guys!
I figured out a good way to keep track of what tiles
can be moved. But still could use any input for laying out
the tiles with a good chance to win. I am currently tossing them out at random.. and so far I have gotten stuck in the following ways. (each letter = a tile)

A B <--- there were 4 tiles left these 2 were on top of 2 more.. so I coudln''t see under neath.
A <-- actually finished with 2 tiles! and it was ontop of the other!

ABAB <--- this sucked! all 4 tiles showing.. but I couldn''t remove 2. Remember the tiles can only be cleared from the left and right. =(

So im still open for more suggestions.
Thanks so much!

Cygor

Just because you ended up in an unwinnable situation does not mean that it was unwinnable to begin with. In the case of the ABAB scenario, you need to remember that you started out with four of each tile (I think that''s how this works... correct me if I''m wront), so if you''d removed things differently earlier in the game, you probably would have had the ability to remove these tiles. This is likely the case in all of these situations. Your initial layout may have had only one winnable path (not likely) and you missed it.

One way to tell is to save every layout and move combination so that you can back up and try a different way if you think you had an unwinnable situation. Even better, you could set your computer up to do the work for you. It might take it a while, but you could have it try every possible move to find out if what you think is unwinnable really is. Automated testing is great (especially if you have idle computers).

Your correct.. there were 4 of the tiles at one point in the game. I guess I just feel that randomly throwing the tiles out means that it''s possible the game may not be winnable.
Im gonna work on having the computer solve the games for me.. or try to. But I''d like to be able to create the layout on the fly so that every time you play it''s different.
If the computer had to try and play every combination to see if that board''s winnable before letting the player play.. they may have a long wait. I was told by a friend that they once had a shanghai game.. and it actually gave the option of ''random'' board or ''winnable'' that guarenteed that there was atleast one path to clearing it.

Thanks again for the response! I''ll keep plugging away!

Cygor

I didn''t mean that you would have your game verify the board before they played. There would be much to long of a wait and that would annoy the user.

What I meant to suggest was that you write an option into your game (that you might or might not remove for the release version) that would have the computer solve it. This way, you could satisfy yourself before you release it that your algorithm for creating boards is working the way you want it to.

You could even write it so that once it finished a board, it would create another and start all over. If it found a board it could not solve, it could write out the board to some sort of file so you can look at it later. You could have your computer do this all night long while you slept, and all day while you''re at work or school. If, after several days of this, it never reports a board it can''t solve, then your probably safe enough.

One thing to watch out for when doing this kind of thing, however, is that the error can be in your test code. Start there first when looking for problems.

Mark Fassett
Laughing Dragon Entertainment
http:\\www.laughing-dragon.com

Cygor, I don''t know why you ignored my suggestion. Maybe I didn''t make it clear. If you fill the board in random tile pairs from the bottom up, following the rules of the game in reverse, then the game MUST be winnable by at least the same pattern in reverse. It is only slightly slower than filling in the whole board purely randomly, and you don''t need any complicated algorithm to figure out how many moves are left.

There''s yet another unwinnable game: the game where there is no possible first move.

SiCrane: as I understand it, he wanted to know how many possible moves there are left in the entire game. This, I believe, is untractible.

True, that would be intractable. However, it also wouldn''t be very useful to the player either. IMO, the player would only be concerned with: Number of current legal moves and number of pairs of tiles left.

Stoffel: actually I did mean how many moves are currently available. And I think I have a way of doing it. So that should be fine. As far as the layout... you said "fill the board in random tile pairs from the bottom up". Well Im definatly filling it from the bottom up. As far as the ''pairs'' go. You mean....
Randomly pick a tile.
Place it on the board,
then place it''s matching tile somewhere else on the board.
That I understand.. and planned on doing. The part that confused me was:
"you can start at random positions in each horizontal row, and you just have to follow the rules in reverse: only place tiles adjacent to existing tiles,"

Why would I need to place tiles adjacent to existing ones?
If that were the case.. I''d always have in the center of my board.. the 4 matching tiles like:
AB
BA?
Can you explaine that part again? I must be working to many hours or somthing!

Thanks a ton guys!
Cygor