Announcement: Be excellent to each other.


Caravel Forum : Other Boards : Electronic Games : Tametsi (Minesweeper evolution)
New Topic New Poll Post Reply
Poster Message
Dischorran
Level: Smitemaster
Avatar
Rank Points: 3406
Registered: 09-10-2005
IP: Logged
icon Tametsi (+4)  
I mentioned this briefly in chat, but it could use a general writeup.

Tametsi is a tricky logic puzzle game. Depending on one's point of reference, one might call it a deterministic evolution of Minesweeper, a harder and more expansive version of Hexcells, or a series of puzzles in the Nikoli/Grandmaster Puzzles vein.

It's a great game, and very (too?) reasonably priced. Go play it.

____________________________
Click here to view the secret text

03-17-2019 at 11:13 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
uncopy2002
Level: Smiter
Rank Points: 431
Registered: 07-28-2014
IP: Logged
icon Re: Tametsi (+2)  
Huh. I actually have played it quite a long while ago because someone recommended it in r/hexcellslevels subreddit.

Basically, if you like Hexcells Infinite and think it's too easy, Tametsi will completely kick your butt. In a good way. After finishing this fiendish game you aren't going to have problems with most Minesweeper games. I also like Tatetsi in that it helped me understand the fundamental nature of Minesweeper problem much better than before (hint: it's all about cover sets) and relate it to the very obscure but powerful "Sledgehammer technique" in Sudoku, which is a specialized form of set-theoretic approach that's being used in Minesweeper:

https://onigame.livejournal.com/18580.html
https://onigame.livejournal.com/20626.html

[Last edited by uncopy2002 at 03-28-2019 09:31 AM]
03-18-2019 at 04:15 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
uncopy2002
Level: Smiter
Rank Points: 431
Registered: 07-28-2014
IP: Logged
icon Re: Tametsi (+7)  
Since I taught Pearls in chat these days how do use the covering sets method, I might as well post here too:

Minesweeper is, fundamentally speaking, a constraint satisfaction problem. It means there are two approaches to solve them, which while seemingly completely different, are actually equivalent:

1. Suppose a random cell's empty/flagged. If it ends up with a contradiction at the end, the cell must be in the other state. Rinse and repeat.

This is the typical approach used by most people, which transforms the problem into a simple depth-first search problem (simple as in, brute force is dumb but it will always work :P).

2. Transform every clue into their relevant covering sets. Merge and subtract covering sets to get more covers until covers of "n tiles contain (0 or n) mines" appear, whose state can be immediately determined.

Actually lots of people who've played enough Minesweeper has vague ideas about this in their mind, but never actually realize that they're using it. It's actually a very powerful tool.

Let's look at a simple example:



Suppose I haven't told you how many mines are there. There is nothing we can immediately solve without taking assumptions!

Or is it? Let's look at it this way:

Click here to view the secret text


We see that the red 1 covers the 2 red tiles, which means there's a covering set of 1 mine on those 2 tiles. Similarly, the blue 1 gives another covering set of 1 mine on the 3 tiles.

Then we subtract the red set off the (bigger) blue set, and get the green set. The mines total is 1-1 = 0. So we've proven that the green set has no mines!

Similarly, let's look at the 2:

Click here to view the secret text


The 2 spans a covering set of 2 mines that covers all tiles in this section besides 1 tile. This tells us that the total amount of mines must be 2 or 3, and the lone tile at the bottom left will be empty/flagged depending on this number.


Combining cover sets together is simple:

- Adding two non-overlapping covers adds the possible number of elements together, taking the largest possible range (e.g 1 to 2 mines + 3 to 5 mines = 4 to 7 mines)
- Subtracting a proper subset from a cover subtracts the possible numbers of elements, also taking the largest possible range (e.g 3 to 5 mines - 1 to 2 mines = 1 to 4 mines)
- Adding overlapping covers and subtracting non-proper subsets from another cover are slightly more complicated since it also depends on the the size of interesction and non-intersection, but it's still quite easy to derive the range of the result.

(Technically speaking it's the Cartesian product of two sets with the appropriate operator applied. Of course, in almost all situations in minesweeper the range is always consecutive, so you don't have to do this.)


That is the gist of this method. Now, why is it better when we can always brute-force, you say? To illustrate the point, let's try solve this with the 1st method:



Done? Now watch how the 2nd method can perform deduction without all the blind guesses:

Click here to view the secret text


This set-theoretic approach is the basis of the obscure "sledgehammer technique" in Sudoku mentioned above,(Sudoku is a special form of Minesweeper where covers can only have 0 or 1 member). It is sort of equivalent of using an integer linear programming solver but it's not exactly a very common technique: the only notable place I've seen is in a Hexcells solver. Of course, Minesweeper is still NP-hard with this covering sets approach, since the amount of power sets is exponential in respect to number of elements.

There are several advantages of covering set approach over brute-forcing:

1. In hard levels there can easily be 20 to 30 unknown tiles at once. Are you going to try that many combinations randomly until it works? :P On the other hand, there could only be (usually) a maximum of 10 covers for 20-30 unknown tiles.
2. It clearly tells you which covers are needed to derive a specific tile's state. And you can work on the minimal covers that can derive that state. or determine if there are redundant hints. This allows you to tighten your puzzles to make really brutal levels (yes, people have done that with the assistence of Sixcells in Hexcells custom levels). You cannot obtain this information with the 1st approach.
3. It encodes the dreaded chains (like a line of 2s) neatly, and also all branches of assumptions that you'd make in method 1 by ranges, which is much easier to keep track of. Instead of doing "assume these 2 tiles have 0, 1 or 2 mines" and search for each sub-case, you just say the cover has 0-2 mines, and then do covering set methods with it, so it's cleaner IMO.
4. This method generalizes to other forms of constraint problems very easily, and will instantly give you the basic patterns in those problems as well; e.g all known Sudoku techniques featured in Sudokuwiki are applications of the sledgehammer.

All that said, method 1 is still useful for its simplicity and it can help verify your covering set Cartesian product is done correctly (doing this on non-proper subsets are not trivial). But for the advanced puzzle in Tametsi, it's very hard to make progress to even mid-game levels without extensive use of method 2. After finishing the entire game I can truly say I've kinda mastered how to do covering sets, and it's a good skill to have.

[Last edited by uncopy2002 at 03-27-2019 02:27 AM]
03-22-2019 at 05:27 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kalin
Level: Master Delver
Avatar
Rank Points: 175
Registered: 01-25-2016
IP: Logged
icon Re: Tametsi (+1)  
I bought this on sale a couple months ago and finally finished it yesterday. Steam says it took me nearly 80 hours, which is pretty good value for the money.

@uncopy2002
It's interesting you say most people use trial and error with Minesweeper, because I don't think I ever did. I played it a lot when it came out (enough to have dreams about it), but I never used the question mark feature (too awkward to use, and didn't seem to add anything). Instead I just used simple coverage techniques, and when that wasn't enough I clicked randomly in blank areas until I died or got useful clues.

After Minesweeper, I learned the finer points of coverage from PrismaPix. Anyone else play this? It actually uses coverage to define its difficulty levels.

Ironically, I never used trial and error in this sort of game until the hardest levels of Tametsi. Uncopy, did you beat all of the bonus levels using just coverage? I would love to see your walkthrough for some of those levels, like maybe Tubes' Revenge (last "Box" level).

PS. The images in your second blog post are broken. And don't know enough about Sudoku to follow all the jargon.
09-02-2019 at 09:03 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
zex20913
Level: Smitemaster
Avatar
Rank Points: 1721
Registered: 02-04-2003
IP: Logged
icon Re: Tametsi (+1)  
Every puzzle can be solved without trial and error.

It's definitely hard sometimes, but always possible.

____________________________
Click here to view the secret text

09-07-2019 at 04:00 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Kalin
Level: Master Delver
Avatar
Rank Points: 175
Registered: 01-25-2016
IP: Logged
icon Re: Tametsi (0)  
When I said "trial and error" I meant uncopy's method 1, not the undo feature. (I've already completed every puzzle without mistakes.)

Example: "If this is true, then these two are false, so one of these two is true, so this is false, so two of these are true, but that contradicts a clue, therefore that first cell has to be false."

Can you beat the puzzles without using the drawing tool?
09-07-2019 at 02:03 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Other Boards : Electronic Games : Tametsi (Minesweeper evolution)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.