Mark Frauenfelder at 9:54 am Fri, Nov 30, 2007
ADVERTISE AT BOING BOING!
Link (Via Neatorama)
My cat, Jack, expressing her dismay at my successful victory, can be seen at:
Chat Noir, from the makers of Real Cats.
Nex: I hadn’t played the game yet when I posted the comment :) Didn’t realize it was a 1-cat.
And one other thing, as an easy exercise, show that a winning strategy for the angel on the square grid implies a winning strategy for the angel on the triangular grid. (I suspect this is a QI http://en.wikipedia.org/wiki/Quasi-isometry invariant. Perhaps you have to make the angel slightly more powerful…)
Gosh, I should really read more carefully. On page 17 Bowditch answers my QI question. I’ll stop now.
This is no longer an open problem. (Well, at least there is a published solution.) It is a win for the angel.
and scan down to “The angel game in the plane”
After playing for a while, and now losing rarely,
seemingly only after making a mistake, I suspect
but can’t yet prove that all presented games
are winnable. That is, on a board of this
particular size, if you are given at least
four squares at some minimum x distance from
the center that you can win every time, which
is what I’m guessing the algorithm gives you.
My method (roughly) is to imagine the largest
perimeter that can be efficiently constructed
that includes all outlying given squares, and
then halve the largest gap in that perimeter
with my first move. Whatever remaining gap the
cat moves towards on its first move, I then
halve that gap with my next move. And so on.
If flawlessly played, this appears to always
give you the one-step-ahead you need to win.
I wish of course I could select the four-squares-
given-at-the-start games, and replay them if
I lost, to inductively “confirm” my suspicion.
A deductive proof is beyond my abilities.
OMG this game destroyed hours of my life last month. The frustration is oddly compelling. My wife and I would sit in silence in our living room, laptops open, and experience long stretches of silence broken by occasional “Damn you, cat!” exclamations as the filthy beast made its escape… again.
The same game company makes a simple Risk-like flash game called Dice Wars that is a regular progress bar eater for me.
Oh! I had missed the QI part myself.
Primitif’s approach looks promising. The answer to the question of which Chat Noir starting conditions lead to a winnable game could actually be brute forced quite easily, as the playing field is small enough. In theory, this would lie within my abilities, but … I don’t think I’ll feel like doing such a boring programming excercise anytime soon ;-/
However, I don’t think it’s likely that you can win every game. We know for sure that it would be impossible if there were no pre-darkened spots, and just now I had to start out with just three dark spots, all in one corner, separated only by gaps one spot wide. This situation is pretty much hopeless; however you’d have a chance if there’s some flaw in the cat’s pathfinding algorithm and you knew how to exploit it. *shrugs*
Reminds me of “Hunt the Wumpus”. Of course, in that game, the Wumpus isn’t trying to escape, he’s trying to eat you.
Can’t you just win by not clicking on any of the dots, so that the kitty can never move? XD
My thoughts precisely … considering that this is suppsed to be a fun time-waster, it may be a bit peculiar to think about the game in this way, but at least I’m not alone :-)
This came listed as a recent “Web Zen” on BB and I’ve been obsessed with it ever since. I wish there was a better payoff, is all.
This is a translation of an open problem – see Conway’s paper for instance.
Does it get progressively harder? Or is it always just a random collection of pre-colored dots?
Play Chat Noir and become two stones stronger! :-)
I need a smite button.
I wasted some time with this last month as well ;-) Tips: Start as far away from the cat as possible, and create a wall leaving one opening until the cat is one dot away, then seal his fate. It’s a win almost every time!
Tip: The Flash version is OK, but the real-life version (marketed in the U.S. as “Get Your Kitty Into the Carrier to Take Him To The Vet For His Weekly Glucose Reading”) is much, much more challenging, and the graphics are better.
The other I was just thinking about a Win 3.1 game involving a mouse, blocks and cats that turn to cheese if you trap them: Rodent’s Revenge
Long live Windows 3.11!
@sidhebaap: Thanks ! The first thing I thought of (after getting to the point of a near-guaranteed win) was “Is it always possible to catch the cat ? Can the cat always escape ? How many dots need to be removed initially for that to happen ?” But yeah, Conway has done way too much fun stuff =) Thanks for the link !
@Larsbars (#23): The cat can move one field per turn, so in the terminology of the interesting paper you linked to, it would be a 1-angel, whereas the player would be called the devil. The paper does mention that the devil has a winning strategy (for those who don’t know: this means a strategy that will always always make you win, for all possible starting conditions and opponents) against the 1-angel, but only on boards bigger than 35×35. This finding doesn’t apply to Chat Noir, as the Chat Noir board is siginificantly smaller, and it isn’t made up of square tiles, but hex tiles instead. In fact, the paper doesn’t mention hexagonal connectivity at all, so it’s quite beside the point.
Even if you had a theory that addressed exactly the board layout and rules of Chat Noir, you wouldn’t need a winning strategy for these conditions! It is easier: as you always play against a CPU opponent with a fixed AI algorithm, all you need is a winning strategy against that one AI. So, does one exist? I don’t think so, but I can’t quite prove that position.
Lost my interest right away. I’m hooked on < http://www.freerice.com>, but I’m afraid I’m increasing my carbohydrate footprint.
That’s http://www.freerice.com. Excuse me for not previewing.
Fun, but once you do manage to corral the lil phecker you don’t “win” anything.
If you really like this game, I would also suggest learning to play Go (weiqi). The game reminds me of life and death situations and other certain traps in that classic game.
Figured it out after a few minutes. The trick is to herd the cat–possible, despite the clichÃ©. Click far away from it but in the direction it’s going and create channels it’ll head for, them close them off.
Virgil @16 has made the same connection I immediately made. This is remarkably like the early, strategic-phase, part of a game of Go.
Fun, but very easy once you make the connection.
Looks like a new variation on these old themes:
Some more info for Nex and anybody else who might
be following along (and it’s a shame if nobody
else is, because this is a way-above-average
1) I have won three of the four 3-spot games
that have showed up since my last report, by
exploiting flaws I now know about in the cat’s
2) The one 3-spot I lost was not really a 3-spot,
since one of the spots was towards the center,
where it is of no help (to me anyway, with my
current knowledge). So I consider that game
3) Also, both a 2-spot-sorta-1-spot and *OMG*
an actual 1-spot game have showed up, both of
which I lost badly. Makes me wonder now if
a holy-grail zero-spot game exists.
Where does this all leave me?
1) I know for sure that there are certain
consistent mistakes that the cat makes, which
allow me to win actual and sorta 3-spots, games
that could not, in my opinion, be won without
knowing these flaws in the cat’s thinking.
In other words, there are ways to bait the cat.
2) I know that there are other mistakes that
the cat makes which I do not yet understand.
Are they randomly inserted muck-ups of no
real utility to a player? Or am I provoking
these mistakes without yet knowing how?
3) If these “other” mistakes turn out to
be ALL random, then I would certainly still
put Chat Noir in the “evil” pile.
4) If these “other” mistakes are not ALL
random, that is, at least some of them are
consistent flaws in the cat’s thinking, yet
together still insufficient to win all
presented games, then yes of course, the
game still goes into the “evil” pile.
5) But what if, as I still guess, there turns
out to be enough consistent-type flaws to win
every presented game? Would I then consider
the game not-evil? I think that would depend
on just how ridiculously subtle those flaws
might be. For example, if the only way I could
win a one-spot or zero-spot game (as well as
all other games of course) was to make my first
three moves in the upper-left-hand corner, no
matter what the cat did, because then the cat
would follow me anywhere, I would consider the
game definitely evil, even if always winnable.
6) But if all remaining necessary-for-solving-
the-really-hard-games flaws turn out to be of
the type I already about, that is, relatively
simple, aesthetically pleasing, in fact kinda
feline-appropriate ways to bait the cat into
mistakes, then Chat Noir will be in my opinion
way-not-evil, but rather way-inspired-genius.
I wish I had a few more IQ points. The
required pattern-recognition at this point
might be (way?) beyond mine.
1) I just won my first 3-spot game (out of
about ten played), although the given spots
weren’t all in one corner.
2) Out of the 2000 or so opening positions I’ve
viewed so far, in addition to the ten 3-spots,
there have been two 2-spots. I didn’t come
close to winning either of the 2-spots.
3) Nonetheless, my guess is still that all
presented positions are winnable, if, as you
I think correctly guessed, one sufficiently
understands the cat’s peculiar logic.
That’s my hope anyway. If I’m right, then
Chat Noir is a wonderful game that will live
forever. If I’m wrong, and there are indeed
unwinnable positions (which is what everybody
else besides me on the internets is guessing),
then it’s just an evil piece of time-wasting
shit. Still fun though.
I don’t think it’s possible to win every game. I have just tried several games and won about half of them; one of them started out with just four dark dots, which were all pretty much in one corner. AFAICT, the cat always heads for the shortest path out, and if you can predict that path, you can exploit that. But I doubt that there always is a way to win; I guess the programmer just fooled around with the random play-field generation until she/he was able to win most of the games, and left it at that. Of course, if it really is like that, the game is very unfair and poorly designed; therefore I’m quite interested in the question whether there might be a strategy that always wins, after all. Maybe a bb reader with too much spare time can figure that out? ;-)
Mail (will not be published) (required)