All the Best Games May Be NP-Hard

Catullus writes "Following in the footsteps of Tetris and Minesweeper, the simple yet addictive multiplatform game Flood-It is the latest puzzle to be proven to be hard — NP-hard, to be exact. This means that there's no way to write an efficient program to beat the game, unless P=NP. This research by computer scientists from Bristol University raises the intriguing question: are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"

Comments

Oblig XKCD

[Zocalo]

I'd say that this is most definitely NP, for humans and AI alike.

Re:Oblig XKCD

[Kingrames]

I don't think so. I believe that's O(0).

Re:Oblig XKCD

[bondsbw]

You can play it here. I'd say it's undecidable.

Re:Oblig XKCD

[Zocalo]

Cool. I have a strategy that might work, but it involves getting the first piece dead centre in the bottom such that it creates a level "base", then building a platform up from that on which you can actually complete rows, albeit on a reduced height playing field. The pre-requistite is that the first piece is suitable for creating the platform which, depending on whether the screen width is an odd or even number of boxes across, is a different subset of the available pieces. If you get a "Z" or "S" piece to start though, I think it's pretty much game over, no matter what you do.

Re:Oblig XKCD

[NoSleepDemon]

Already tried that, the game is made infinitely more difficult by the physics engine which treats each block as if they have minimal mass in an almost weightless environment, furthermore, the pieces continue to move after they are 'placed'.

Re:Oblig XKCD

[Crudely_Indecent]

I tied the top score!

0 (zero)

Re:Oblig XKCD

[Lord Bitman]

that is not tetris.

Re:Oblig XKCD

[Idiomatick]

The game doesnt have code the remove lines though.

Re:Oblig XKCD

[Anonymous Coward]

I doubled your score, Loser!

Re:Oblig XKCD

[PIBM]

I made a nice line yet got no points. I guess they weren't thight enough or they just never plugged in the points calculation :)

Re:Oblig XKCD

[lexDysic]

In fact, the screen width is almost exactly 9.5 boxes--I managed to make what looked like a perfectly horizontal row with two quarter-box gaps. A full row ain't gonna' happen.

Re:Oblig XKCD

[hoytak]

How did this get modded offtopic? It does belong, loosely at least, to a class of partitioning problems (e.g. knapsack problem) that are NP-hard. One such problem is optimally cutting a round log into boards to conserve the most wood. Adding different shapes, doing it online, etc. would make it harder...

It seems it's a counter example to the "NP-hard = fun" hypothesis, then.

Re:Oblig XKCD

[Anonymous Coward]

That... is... SPARTA!!!

Or...

That's a space station!

Or...

THIS is Tetris.

Re:Oblig XKCD

[tobiah]

That's awesome

Re:Oblig XKCD

[jimand]

That's fantastic - well done.

Re:Oblig XKCD

[geekoid]

He ruined it by making it bouncy. I think I could actually play it if it didn't bounce.

Re:Oblig XKCD

[Dogtanian]

That... is... SPARTA!!! Or... That's a space station! Or... THIS [tetris.com] is Tetris.

I notice that they're selling yet another of those endless contrived and gimmicky variants of Tetris they seem to churn out.

There's a sort of depressing irony in that Alexey Pazhitnov created a game which was straightforwardly brilliant, that didn't require- nor benefit from- excess bells and whistles (I mean, you could probably write a version for the 1K ZX81 without losing much except the Game Boy version's catchy music).

Yet- particularly since he didn't get the right to profit from his own creation until 1996, his Tetris Company's continued ability to exploit and profit from the game that he created relies on exactly that- lots of gimmick-laden excuses to resell a game that didn't need it.

Re:Oblig XKCD

[jadin]

First Person Tetris

Re:Oblig XKCD

[Anonymous Coward]

MODS!!! How is an xkcd about extra hard tetris offtopic for this article?

Re:Oblig XKCD

[Jeremy Erwin]

My favorite Tetris derivative is Falling Up. In the words of the author, "The board will spin, flip, and dance".

Re:Oblig XKCD

[E IS mC(Square)]

Tetris in Stereogram 3D: http://3dimka.deviantart.com/art/3D-Stereogram-Tetris-36795242

Re:Oblig XKCD

[MaskedSlacker]

Even if it did, the thing doesn't have the code to remove rows and award points.

Re:Oblig XKCD

[jesset77]

I mean, you could probably write a version for the 1K ZX81 [wikipedia.org] without losing much except the Game Boy version's catchy music

What do you mean "probably"? I DID write a copy in Z-80 assembly language in 1994, you insensitive clod! :(

Re:Oblig XKCD

[jesset77]

First Person Tetris [firstpersontetris.com]

Crap, without having the enemy's gate to orient myself by, I'm skrewed! ;3

Re:Oblig XKCD

[jesset77]

Tetris in Stereogram 3D

Yep, it works. My eyes are bleeding all over the keyboard now. Thanks 8I

Re:Oblig XKCD

[Dogtanian]

What do you mean "probably"? I DID write a copy in Z-80 assembly language in 1994, you insensitive clod! :(

I'd have been very surprised if someone hadn't, I just didn't know off the top of my head. Though it's pretty unlikely that it's ever been done commercially, as by the time Tetris was being marketed in the West, the ZX81 market was long dead.

Re:Oblig XKCD

[pugugly]

I've enjoyed the Wii version (My cut of the $20 minimum purchase for downloadable Wii games).

For a simple elegant game, I've noticed it's easy to implement it badly; The Wii version is great. Even the gimmicky bits are fun 'occasionals'.

Pug

The fun is in the simplicity

[Pojut]

Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.

No other video game in history has that kind of audience. The fact that, although variations on the original have been released, the most popular version is still the original version (which has remain mostly untouched throughout its existence) just gives more credit to its simplistic genius.

Re:The fun is in the simplicity

[HarrySquatter]

I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.

Re:The fun is in the simplicity

[Azarael]

I'd like to point out though, that just because a game has simple rules, doesn't mean it isn't very complicated to play. Look at how long it too for someone to completely 'solve' the game of checkers (using a computer).

Re:The fun is in the simplicity

[Pojut]

Yes, but like checkers, just about ANYONE with basic cognitive functions can play Tetris...the concept itself very easy to understand.

A minute to learn, a lifetime to master comes to mind...

Re:The fun is in the simplicity

[eldavojohn]

Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.

No other video game in history has that kind of audience..

Wrong. The concept of a game being easy to begin playing but difficult to master dates back to Chess and even Go. As far as modern day video games are concerned there are a lot that actually fall into this category. I believe the phrase was first coined by Nolan Bushnell but I could be wrong.

You are free to say that in your opinion of "easy to learn, difficult to master" video games, Tetris is the ultimate. But even video games like Donkey Kong or Pac Man have the same simple laws that a novice understands which gradually become more and more restrictive until the true "mastery" title is nearly impossible to attain -- kill screen, anyone?

If you're designing a new video game, that seems to be one of the fundamental requirements so that you aren't too off-putting to new players. You can play World of Warcraft at your own pace and although the UI and input is infinitely more complex than Tetris, it exhibits this basic rule of thumb for game design -- quite successfully. That's why it enjoys a worldwide audience of 10+ million.

Tetris is legendary and fun but modern day video games (like the popular flash puzzle games) are building past Tetris while trying to maintain the principles that made it successful. I predict you're going to be upset that I might have just compared Tetris to Bejeweled but lets face it: they're both simple insanely popular video games that have a large swath of difficulties that seem to algorithmically scale in later levels.

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

Re:The fun is in the simplicity

[Pojut]

Not sure if I would agree with Minesweeper having a larger audience, however you are certainly correct in that Minesweeper also transcends gaming skill much in the same way as Tetris. I stand (sit?) corrected.

Re:The fun is in the simplicity

[Pojut]

Good points, all :-)

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

My definition would be when one starts to compete in tournaments...hence the "competitive level" and "pro" sandwiching the "hardcore" label.

Re:The fun is in the simplicity

[Azarael]

Yes, that was the point that I was attempting to make.

Re:The fun is in the simplicity

[theaveng]

I remember when I first played Tetris on a Nintendo Gameboy. I was unimpressed.

Later I tried it again, and determined it was more fun that I initially thought, but whenever I play Tetris I grow tired of it rather quickly (less than half an hour). My longterm gaming addictions are: Space Invaders (Atari 2600/VCS version), Asteroids, Missile Command, and Ms. Pac-Man (arcade). I can play these games hour after hour.

I also like to revist simulations like Tom Clancy's Red Storm Rising. Boring graphics but addictive gameplay.

Re:The fun is in the simplicity

[Anonymous Coward]

What's Mindsweeper?

Re:The fun is in the simplicity

[theaveng]

>>>Not sure if I would agree with Minesweeper having a larger audience

How many users of Windows are there? Approaching 1 billion homes? That's a bigger audience than even the best-selling console (~150 million PS2s) ever reached.

Re:The fun is in the simplicity

[Abcd1234]

Heck, Go is even simpler than checkers, and it's nowhere even close to being solved (the current, top-ranked computer program is roughly 2p, and easily defeated by a strong professional player).

Re:The fun is in the simplicity

[quantumplacet]

exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.

Re:The fun is in the simplicity

[coolsnowmen]

That doesn't mean they play mindsweeper. My mom has windows XP, but she uses my old gameboy to play tetris. Also, its not like there isn't a tetris clone made for every popular OS.

Re:The fun is in the simplicity

[coolsnowmen]

Have you played pac man C.E.? best pacman ever.

Re:The fun is in the simplicity

[Pojut]

Come on...not everyone that uses Windows regularly plays Minesweeper.

Re:The fun is in the simplicity

[somersault]

No, but you are inobservant. It's called Minesweeper.

Re:The fun is in the simplicity

[dskzero]

And I wonder how you were modded as a troll and he wasn't. Wait, Linux doesn't installs minesweeper, i guess?

Re:The fun is in the simplicity

[poetmatt]

even higher yet. the thing is on every OS that exists, basically.

Re:The fun is in the simplicity

[mqduck]

Tetris, to me, is the ultimate video game.

You're in very good company. Warren Spector, especially when discussing video games as art, calls Tetris to be the greatest game ever. Something to do with it exemplifying how games, like all other art forms, can do things the others can't, which he believes is what game developers should make it their mission to do.

Re:The fun is in the simplicity

[Anonymous Coward]

If your going to pull the ole "Windows is bigger and better" hat out you should REALLY think about it. MOST people who use windows for something besides gaming run to solitare for "game fun".

Re:The fun is in the simplicity

[theaveng]

I think my point is that Minesweeper has been sitting on nearly every desktop in the world, from Windows 3 (1990) to Windows 7 (2010). Other games have not. QED Minesweeper has far wider "coverage" to borrow a term from Nielsen television.

Re:The fun is in the simplicity

[jellomizer]

Is that what the army recruiter told you?

Re:The fun is in the simplicity

[DrVomact]

Come on...not everyone that uses Windows regularly plays Minesweeper.

That's because it's a lousy game—there's no guarantee that it can be solved by logic; often you reach a point where you must guess. There's a variant I had on my (now abandoned) Palm Treo that was guaranteed to be solvable by logic. Can't remember who made it now.

Thinking about this, I was at first tempted to say that the first (Windows default) variant of the game is more difficult to solve by a computer (i.e. via an algorithmic solution), while a program could easily solve the second variety. But that's trivial, really—nobody can "solve" the first variant because it involves guessing and guessing of this sort is not "solving"—it's just guessing. And you can write a program that emulates the human behavior of guessing...

Ah, what was I saying? Slow day in my brain today.

Re:The fun is in the simplicity

[mdarksbane]

There's a problem, though - both Go and Chess are generally multiplayer games. Tetris is in its purest form singular. Any sort of competitive game is much harder to get into for a novice, as it is only fun for them to be playing other novices, and you have the situation you see in general with Chess and Go - the few people who are really good, and the many who rarely play because they do not have the dedication to compete.

Look at the many addictive "casual" games - almost all of them are single player, and the ones that are multiplayer (such as farmville, or even wow) are multiplayer mostly in the social aspect than in the competitive aspect. There's a reason the majority of WoW players are on PvE. When you are facing a controlled computer opponent, you can apply a constantly ramping difficulty level that starts at a place a novice can still have fun. When you're playing competitively, the moment you have a significant skill imbalance the fun disappears.

Re:The fun is in the simplicity

[jpcarter]

I think my point is that Minesweeper has been sitting on nearly every desktop in the world, from Windows 3 (1990) to Windows 7 (2010). Other games have not. QED Minesweeper has far wider "coverage" to borrow a term from Nielsen television.

But if Windows users had the choice of the two, Minesweeper or Tetris, automatically available to them, I'm confident that Tetris would win hands down.

What was Peter playing in OfficeSpace? Not Minesweeper.

Re:The fun is in the simplicity

[Bigbutt]

Yep, I recall an interview with Bill Gates years ago regarding Minesweeper. He was asked what his best time was and it was something like 1 second. The interviewer asked how he did it. He said he'd just randomly click until he got the 1 second score.

[John]

Re:The fun is in the simplicity

[orgelspieler]

Go is simpler than checkers? Is that a joke? Have you played those two games? Go is on an entirely different plane of difficulty. It's more comparable to chess. In case you didn't know, checkers is solved.

Re:The fun is in the simplicity

[FunkyELF]

Minesweeper is sometimes NP-Hard, other times its NP-Impossible
Minesweeper can get stuck where there are multiple solutions.
I have been down to the point where I am 1 click away from winning or losing and either click would satisfy the numbers.

Re:The fun is in the simplicity

[NATP]

Look at how long it too for someone to completely 'solve' the game of checkers (using a computer)

Depends on your definition of 'solved' -- Samuelson's 'solution' was a brute force attack that relied heavily on position evaluation functions provided by human experts. [slightly off topic, I know, but...] Good discussion can be found in Dave Fogel's book, Blondie 24 The book discusses Samuelson's work in the background discussion, but its main subject is development of a checkers playing program from 'first principles' - only givens were the physics of the game (legal moves) and one heuristic: more pieces is better. Everything else was learned. The program was eventually playing at an expert level against human players on the web. My point, relevant to the post above: While simple games like checkers are considered 'solved' algorithmically by many in the AI community, those 'solutions' often actually rely heavily on the kind of human reasoning / intuition / learning -- combined with brute force evaluation of future move possibilities. [end off topic]

Re:The fun is in the simplicity

[Anonymous Coward]

exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.

Umm... was that supposed to be sarcastically funny or something?

You've been rated informative, so I'd like to point out that Tetris has been released on nearly every console & handheld gaming system ever created, as well as Windows, and probably several other computer platforms as well. And that doesn't even count clones, just true "Tetris".

Re:The fun is in the simplicity

[Anonymous Coward]

Tetris is certainly not beyond the ability of a computer to play. Even if it is NP-hard, there are still less than 100 possibilities to test. I mean, think about it, for each new piece, we just have to decide on one of 4 (or so) rotations, and one of (like 10?) columns. It doesn't really matter if Tetris would scale to be difficult if you had a million columns and a million rotations. No one plays it that way. Most likely, if you scaled it up to the point where being NP-hard was relevant, it wouldn't be fun.

A computer could play Tetris much better than a human. Tetris is fun because humans suck so much at making these decisions fast enough. It's fun when you f*ck up and then you have to try to come up with a semi-decent way to fix it.

Re:The fun is in the simplicity

[Anonymous Coward]

I don't understand how Minesweeper is NP-hard.
Choose random starting point. If it's not a mine, use calculations to figure out non-mines and click. If you run out of non-mines, click on a possible mine or a random point.

Even the best human player can click on a mine since there's a degree of luck in the game.

Re:The fun is in the simplicity

[iluvcapra]

"Simple" in the sense of its formal defintion -- its rules are very simple -- not in subjective complexity.

Re:The fun is in the simplicity

[Anonymous Coward]

It is funny though because I don't think Minesweeper is NP hard.

Re:The fun is in the simplicity

[geekoid]

That applies to farmville as well.

Re:The fun is in the simplicity

[geekoid]

One time my wife and I got into a minesweeper competition.
Whe got a good score, then I would beat it and so on.
Then she got so good I couldn't beat her, so I just edited the text file, shaving a second off her time. She still beat me three times before I made it a time of 1. Then I confessed my joke and we had a laugh.

Re:The fun is in the simplicity

[geekoid]

I think minesweeper would in, hands down.

What was Peter playing in Office Space? who gives a fuck.

Re:The fun is in the simplicity

[anomnomnomymous]

Unless you play the Hell-version ;-)

Based on this xkcd comic.

Re:The fun is in the simplicity

[paeanblack]

Go is simpler than checkers? Is that a joke?

It's not a joke. I can write a program to solve Go in about a dozen lines of code, without even trying to compress it. It's about as complex as tic-tac-toe.

Building the computer that can complete this program before the heat-death of the universe? That's merely a hardware issue.

Re:The fun is in the simplicity

[Nathrael]

When you're playing competitively, the moment you have a significant skill imbalance the fun disappears.

Not necessarily. In fact, in many online games, I quite enjoy playing against "the pros" every once in a while. Sure, I may get blown to pieces, but by carefully watching how my enemy manages to outskill me, I learn, and that's easily one of the most important aspects of competitive gaming.

Re:The fun is in the simplicity

[roman_mir]

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

-

Watch this to the end, you'll see.

Re:The fun is in the simplicity

[Fallingcow]

In the version of Minesweeper that comes with Windows, I don't think the first click can be a mine.

Re:The fun is in the simplicity

[smallfries]

Are you saying that you couldn't write a program to solve checkers in twelve lines of code?

Such a simple brute force solver still needs an executable specification of the rules that converts a board state and a move into a new board. For checkers this function is simple. For Go this function needs to check the freedoms of each cluster of stones and would thus require recursion. This alone would make it a more complex program than the checkers solver.

Re:The fun is in the simplicity

[Richy_T]

This can apply to a well designed game but equally, it might be impossible to improve in a game because the skill you are trying to hone requires you to get to a point that you are prevented from by other players simply outclassing you. This can be especially so if you are coming to a game relatively late and the majority of players have developed a fairly reasonable level of competence or simply because you don't have the transferable skills that many hardcore gamers take for granted.

I speak as a n00b who recently bought the orange box where my last real gaming experience was Doom II.

Re:The fun is in the simplicity

[pjt33]

Have you published your algorithm for determining liveness? Last I heard, that was considered a hard problem.

Re:The fun is in the simplicity

[Abcd1234]

I thought we were talking about rulesets here. GP:

I'd like to point out though, that just because a game has simple rules, doesn't mean it isn't very complicated to play.

The ruleset for Go is one of the simplest for any strategy game. It's definitely simpler than checkers, not to mention chess. And the result is a game of beautiful depth and complexity.

Re:The fun is in the simplicity

[mattack2]

That's discussed on the Wikipedia page
http://en.wikipedia.org/wiki/Minesweeper_(computer_game)#Elements_of_guesswork

Re:The fun is in the simplicity

[Impy the Impiuos Imp]

Actually, poking a random square is NP-easy, so to speak. It's just not guaranteed a solution.

Remember that NP-Hard means essentially there is no way to solve a problem short of basically trying all possibilities. And that's exactly what a human mind is doing in Minesweeper.

Re:The fun is in the simplicity

[Impy the Impiuos Imp]

And I take that back, even. Guessing is a guaranteed solution -- it's just not a guaranteed win.

Re:The fun is in the simplicity

[mdarksbane]

And obviously it doesn't deter *all* players, or none of these games would be so popular. But it does drastically reduce the number of people to whom the game appeals.

There's a reason that "casual" games tend to follow the tetris model while "hardcore" games are more similar to chess' competition.

I don't mind getting my face shoved in the dirt a few times as long as I feel I'm making some progress. But I'm a young man with an excess of testosterone and a competitive streak. My mother does *not* enjoy that learning experience. She is, btw, the best tetris player I've ever met in person.

Re:The fun is in the simplicity

[timster]

Depends on the rule set you use. Simplified rule sets used for mathematical analysis of the game usually do not require life/death analysis to determine the final score at the end. Rules used by human players in practice are much harder to score algorithmically, largely for historical reasons.

Re:The fun is in the simplicity

[ajrs]

nope, there are minesweeper knockoffs in the same menu with the teris knockoffs.

Re:The fun is in the simplicity

[migla]

With all due respect, the gp:s statement sounds sensiblish, and if you think you can knock it right out like that, please give an example of a game that is equally or more for "anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros", because chess, go and wow aren't it, not as much as tetris anyways. Ok bejeweled comes closer, but no banana, in my opinion.

And I'm not saying you're wrong. You're probably right, but my feeble mind needs a better example.

Re:The fun is in the simplicity

[jackchance]

Go has a very well defined and workable handicap system. I learned playing masters, but I would start 9 stones ahead of them.

Chess on the other hand does not. Whenever someone who is good at chess offers to play me i agree but request unconventional starting positions (like bishops and knights swapped) so that the game is actually interesting and not based on the memorization of kasparov games.

Re:The fun is in the simplicity

[adamdoyle]

agreed (and I won't post A/C)

Re:The fun is in the simplicity

[Abcd1234]

Huh? Which parts of life-or-death determination are "historical"? I mean, maybe I'm exposing my ignorance, here, but doesn't it come down to whether you can form two eyes with a group? Granted, there are a few complicated cases, like seki and double ko (a good page covering them is here), but none of them are "historical", and fall out straight from the basic ruleset.

Re:The fun is in the simplicity

[Anonymous Coward]

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

I would define this by the manner in which the player lays the blocks. Specifically, in that all the best players plan out where the next piece will go and will immediately drop the piece and THEN move the piece horizontally to the desired location (rotating the piece as needed). Beginners and seasoned non-pros, which I consider myself in, will mostly concentrate on the current piece (but still note the next piece) and position the piece horizontally before dropping. This latter method just doesn't work at the fastest speeds, except if you're playing Tetris DS which doesn't have a very fast top speed.

Re:The fun is in the simplicity

[omfgnosis]

Whether a winmine game can be solved by logic alone depends entirely on the mine placement, but it's worth noting that from the original (win 3.0) version on, there has always been a finite set of mine placements used (for the standard "beginner", "intermediate" and "expert" variants).

Even where guessing which board you're playing isn't an option (and there are enough boards that memorization would be impossible for most people), most places where you have to "guess" follow a certain pattern which can be recognized. As the boards begin to feel "familiar", so too do the "guesses", as well as opportunities to guess in areas that logic would suffice (in order to improve speed).

Winmine is "learnable" in that sense, and follows a certain logic by virtue of that.

Re:The fun is in the simplicity

[omfgnosis]

Presumably this is for "beginner", which has been solved in 1 second by numerous people. The current best known score for "intermediate" is 8 seconds, and the current best known score for "expert" is 33 seconds.

Re:The fun is in the simplicity

[xandroid]

Fuck me that is crazy.

Re:The fun is in the simplicity

[omfgnosis]

It can, but if it is the game will move it to the closest non-mine position to the top left corner (moving away horizontally).

Re:The fun is in the simplicity

[MrHanky]

Er, that's what TFS says defines a good game: it can't be solved by logic (i.e. a computer, or an autist) alone. There's an element of chance in it.

Re:The fun is in the simplicity

[CarpetShark]

No, but you are inobservant. It's called Minesweeper.

That's what we tell you after sweeping your mind.

Re:The fun is in the simplicity

[the phantom]

The standard handicapping system in Chess is to start the stronger player down a pawn or two (or more, if the skill disparity is that great---remember that knights and bishops are 3 pawns each, a rook is 5 pawns, and the queen is 9). There are also exchanges of pieces that could be made (i.e. the stronger player gives up their queen, while the weaker player gives up a rook), and one might let the weaker player play one or two moves first. These are the kinds of things that most chess players should recognize as forms of handicapping. Your idea of non-standard board positions is probably not what most good players would think of when attempting to handicap a chess game which may be why you meet so much resistance. That being said, if you are playing at a level that memorization of Kasparov games is useful, handicapping probably isn't going to help you that much.

Re:The fun is in the simplicity

[crono_deus]

Also, Emacs has Tetris, but not minesweeper: M-x tetris. ;-)

Re:The fun is in the simplicity

[David W. White]

-- Have you played pac man C.E.? best pacman ever. I've played countless pac man variants but the best pac man ever is Neil Roy's Deluxe Packman. Great sound and game play. My kids and I spend hours competing against each other, and sometimes my wife joins in too.

Re:The fun is in the simplicity

[camperdave]

Most people could beat me at chess even if I were given two queens.

Re:The fun is in the simplicity

[Lando]

I think your using a poor choice in words. Your saying that go has a simpler rule base than checkers, ie it's easier to determine whether a rule is valid or not, correct? Not the actual strategy and hence wining of the game.

Considering that checkers is a solved game with 10^31 moves. Chess being 10^50 and Go an estimated 10^80 if I recall correctly.

So figuring out a valid move may be easier in Go than in checkers; however, it's the gameplay/strategy that really counts.

Re:The fun is in the simplicity

[Ihmhi]

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

If you could beat this guy , I'd say you have a fair chance.

Re:The fun is in the simplicity

[jackchance]

That's interesting. I've never played anyone who suggested giving up a pawn or two as a handicap in chess. I would consider myself a very good novice chess player. I can beat pretty much anyone that doesn't play seriously, but if someone has studied book moves, i don't find it much fun.

With regard to the non-standard board positions, if i wan't clear, i meant that both of us start with non-standard board positions. So it isn't a handicap in the strictest sense, but it forces both players to be creative and not fall back on classic strategies.

Re:The fun is in the simplicity

[jesset77]

Tetris has a way shallower learning curve than minesweeper.

It is, literally, "fit the peg in the whole" as opposed to "deduce which mine is safe to trod on from these snarky numbers we've placed around"

It also has time pressure instead of "ZOMFG don't touch the sides" pressure, and fsckups can be heroically compensated for as opposed to A> never realizing you made a foolish risk, or B> *BOOM*

Re:The fun is in the simplicity

[jesset77]

Finite set of mine placements? You must be joking. Or if you're not, citation please.

Who would introduce finite mine placements when you've got a random number generator handy? 8I

Re:The fun is in the simplicity

[jesset77]

Er, that's what TFS says defines a good game: it can't be solved by logic (i.e. a computer, or an autist) alone. There's an element of chance in it.

Chance has zero import to the P=NP problem. What the article is referring to is there being no algorithm (thus, for example, no boring/safe process for a human to ergo-automate) that solves the puzzle in a predictably short time frame.

Minesweeper is still NP hard even if the "game server" secretly fiddles with the mines behind the scenes to destroy any combinations that force guesses. Even if the game can be deduced 100% of the time, that deduction itself can become gruelingly complicated and snake into a chain reaction all the way around the board (this spot depends upon this spot, which depends upon..) which leaves the game challenging enough that you'll never run out of surprises.

Re:The fun is in the simplicity

[jesset77]

1. His wife is smart
2. His wife has a sense of humor and is a good sport
3. He's on Slashdot and has mated

H44444444444XXXXXX!!!!1 DX

Re:The fun is in the simplicity

[jesset77]

Yes, but like checkers, just about ANYONE with basic cognitive functions can play Tetris...the concept itself very easy to understand.

A minute to learn, a lifetime to master comes to mind...

That's a funny way to play Checkers 8I

Re:The fun is in the simplicity

[jesset77]

Bwahaha, program could always go "Can I go hear?" and rely on the referee to say "No, UR dumb. Try again" xD

Re:The fun is in the simplicity

[omfgnosis]

http://www.minesweeper.info/articles/Shifts.html
http://www.minesweeper.info/articles/BoardCycleBug.pdf

Re:The fun is in the simplicity

[jesset77]

Oh, mylanta!

Thank you for citation sir, and mod parent informative. :3

Re:The fun is in the simplicity

[omfgnosis]

I would have been just as incredulous. It seems odd that it would be true. I'd hazard a completely unsubstantiated guess that it was more intentional than the others studying it have theorized, in order to add an element of "learnability" to an otherwise sort of opaque game.

Re:The fun is in the simplicity

[jesset77]

or to avoid guess pitfalls :>

Re:The fun is in the simplicity

[omfgnosis]

Meaning to avoid boards that require guessing to solve? Many boards do require guessing to solve. In my experience, if I had to hazard a guess, at least a handful of the "beginner" and "intermediate" boards I've solved required a guess, and probably every single "expert" board I've solved.

Unless I'm misunderstanding.

Re:The fun is in the simplicity

[jesset77]

I know, I mean the earlier iterations may have been "zomfg! we must avoid forcing a guess!" later replaced by "screw it, it'll put hair on their chests, use a random number generator" ;3

Re:The fun is in the simplicity

[andi75]

There's a good reason for the "standard" starting position. The other 959 (same colored bishops are such a stupid idea that we'll exclude them right away) are terribly broken, and not fun to play (that's why Chess-960 players are usually regarded as rather 'special' in the chess community).

Also, the games heavily favor the starting player (i.e. white). Games are often decided much faster, because there's so many traps that you can fall into early in the opening.

And if you think that chess these days is all about memorizing opening lines, you're totally wrong. Below Elo 2700 (about top 20 in the world rankings), the stronger player usually wins regardless of preparation. Just look at your own games, how many times have you and your opponent blundered *after* you left your book knowledge? That's where games are decided...

Re:The fun is in the simplicity

[smallfries]

No it couldn't. If you are talking about complex the game is then the program *is* the referee. If you don't believe that then every game in the world has the same level of complexity as they all have the same solver:

for move in validMoves() : try(move)

Re:The fun is in the simplicity

[omfgnosis]

Well, I don't know for sure how all the different versions' boards vary, but my (completely unscientific) observation has been that the versions from the original in Win 3.1 through the last version which was remotely similar, in XP, have very similar boards.

I play the 3.1 version exclusively (via WINE on OS X), and it certainly doesn't avoid requiring guesses.

So it seems that the guesswork is built in to the game.

Re:The fun is in the simplicity

[Anonymous Coward]

As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

Please take a look at "Tetris The Grand Master 3: Killer Instinct", a video can be found of someone beating it in "Shirase Mode".

Re:The fun is in the simplicity

[coolsnowmen]

This one?
http://home.cogeco.ca/~nroy15/games_index.html
Good for a free pac man clone, but still not nearly as good as pac man championship edition (I played it on the xbox 360 arcade)

Re:The fun is in the simplicity

[Anonymous Coward]

You're you're you're you're you're you're.
Not your.

Re:The fun is in the simplicity

[Anonymous Coward]

Granted. Missed that.

Re:Metaquestion

[GenP]

Well, they are stories.

Re:Metaquestion

[HarrySquatter]

Because it is tagged so automatically.

Sokoban

[am 2k]

FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...

Re:Sokoban

[NitsujTPU]

PSPACE-Complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41

Re:Sokoban

[amplt1337]

I'm seeing a pattern here...

..."People like puzzles"?

Re:Sokoban

[owlstead]

"I'm seeing a pattern here..."

Are you sure? Maybe determining if the pattern is correct is also NP-hard.

Re:Sokoban

[am 2k]

So you think there's a good game behind that? ;)

Re:Sokoban

[HTH NE1]

"I love humans. Always seeing patterns in things that aren't there." -- The Doctor (8th)

Re:Sokoban

[binkzz]

But how is minesweeper NP? It is pretty easy to write a script that plays it to best of any man's ability.

Re:Sokoban

[kvezach]

The minesweeper decision problem is actually: "Given these mine hints, is there any possible way mines could be set on the field so that you would get these hints when uncovering these squares?". It's a reduction from SAT. It's NP because given an answer, you can check if the mine hints would be what the problem states. It's NP-hard because SAT is. Together, NP and NP-hard makes NP-complete.

Note that NP-hardness isn't about the average case, it's about the worst case. Many proofs of puzzles being NP-hard essentially go: "I can make a playing field so that the puzzle is only solvable if a related Boolean circuit can be satisfied, and I can transform any Boolean circuit into a playing field in this manner". Such a proof only tells you that these "gadget puzzles" (transformed circuits) are as hard as SAT, it says nothing about the average puzzle.

As another example, consider a problem where the input is either 0, an integer, and a number of integers; or 1, and a number of integers. Then the decision problem is defined as "if the first number is 0, then true if the second is the sum of all the subsequent integers of the input; if the first number is 1, then true if the circuit defined (in some given format) by the subsequent integers can be satisfied". Obviously, this problem is NP-complete because you can turn any SAT problem into an instance of this problem; but if the first number is 0, the problem is trivially decided.

Incidentally, that's part of the reason why cryptosystems based on NP-hard problems have done so badly: while the cryptosystem might be hard to crack, worst case, it usually turns out most instances of encryption can be broken.

Re:Sokoban

[TempeTerra]

Briefly (and wrongly, but it will do for a slashdot reply), NP complete problems require the computer to actually calculate all of the possible solutions and see which one is best rather than than using an algorithmic shortcut. For every extra item that has to be computed the complexity increases by quite a large amount relative to the difficulty of the smaller problem. The traveling salesman problem is the classic example - adding another town to visit means you have to recalculate all the routes because there just might be a better solution using the new town in any part of the route.

Anyway, there's nothing impossible about NP complete problems - the issue is that they get very hard very quickly as you make the problem space bigger. Quickly the time required to find the best solution (not just a good one) would take longer than the remaining lifetime of the universe.

One of the tricks with NP complete problems is that if you're looking for a merely good solution, not the absolute best, humans can often use some heuristic tricks to home in on a good solution quickly while a dumb computer algorithm would still be chugging away looking exhaustively for the best solution. Studying the kinds of guesses that humans make in these situations is a notable area of study in artificial intelligence.

In summary, a computer will kick you ass at minesweeper, but it still won't be able to solve a 10^14 x 10^14 board before the end of time.

Re:Sokoban

[binkzz]

Thanks, that was pretty interesting. Imaginary mod points coming your way.

Re:Sokoban

[bstamour]

Your definition of NP-Complete isn't quite accurate. Np-Complete isn't made by NP and NP-Hard. NP-Hard IS NP-Complete for yes/no type problems. NP-Hard == NP-Complete, and both are a subset of NP.

Think of any NP-Complete problem, such as the famous Travelling Salesman Problem: given a weighted graph G, find a minimum cost Hamiltonian Cycle on it (visit every vertex exactly once, and do it while minimizing the cost of travel). We can convert this from an optimization problem to a yes/no problem. Given a graph G and a value K, is there a Hamiltonian Cycle in G with cost less than or equal to K?

The first problem is NP-Complete, the second is NP-Hard. Essentially they're the same problem, just one outputs a number, and other outputs yes or no.

Re:Sokoban

[kvezach]

Then consider a decision problem like: "given this initial chess setup, with White to move, can White force a win?". That's yes/no, and because it's at least as hard as other problems in NP, it's NP-hard. Yet, if this was NP-complete (as you say it would be, because it's NP-hard and a yes/no problem), then one could make a perfect chess AI if one could solve SAT. Given that chess itself is EXPTIME-complete, I think that would come as a surprise to most people.

You may then say that "of course that problem isn't NP-complete - NP-complete problems can have polytime verifiable proof certificates of a 'yes' solution whereas for the hypothetical chess problem above, that's not true". However, that would merely be a restatement of NP, as a problem is in NP if there's a verifier that executes in polynomial time.

Re:Sokoban

[bstamour]

I think I may have been a bit mistaken then, either that or I was just talking out my ass. I really appreciate the clarification, especially with a good example like that one. So, NP-Complete problems are a subset of NP-Hard which are a subset of NP?

Re:Sokoban

[GargamelSpaceman]

Since every NP complete problem can be reduced to any other one, then maybe time spent on one NP complete problem can be applied towards solving others. Can one tabulate found solutions to one NP hard problem and apply the experience to other problems? Maybe the fun-ness is the joy in adding to our life's experience in a way we (perhaps instinctually) know is worthwhile. Or maybe not. Just wondering...

Re:Sokoban

[kvezach]

NP is the set of all decision problems where a "yes" answer permits a certificate (proof) that can be verified in polynomial time. For instance, factoring is in NP, because the question "does Q have at most n factors" can be checked in polynomial time by simply multiplying primes together. The certificate, in this case, would be "yes" and a list of prime factors. Very simple problems can also be in NP: for instance, the problem "does there exist an Y for a given X so that X + Y has exactly ten digits in base 10?" is in NP; a yes certificate just gives Y.
A problem in NP does not need to have a polynomial time verifiable certificate for "no" answers. Consider satisfiability: if a circuit can be satisfied (i.e. there are inputs that makes the output true), then there's a certificate: the input itself. On the other hand, if the circuit can't be satisfied (there is no input that makes the output true), it's not very clear how one would make a certificate showing this.

NP-hard is the set of all problems that are at least as hard as the worst problems in NP. To take a very easy example, the halting problem is NP-hard, but it is not in NP.
"At least as hard" has a specific meaning: it means that if you had a machine that could solve the problem in question, you could also solve all problems in NP by transforming the latter into the former in polynomial time. For the halting problem, this is easy: make a Turing machine that halts iff it finds a "yes" certificate for the NP problem instance in question. I think the chess problem is NP-hard as well.

Given the above, NP-complete is simply the intersection of NP and NP-hard. An NP-complete problem, like subset sum or 3-CNF-SAT, is in NP (you can prove an affirmative answer in polynomial time), and it is NP-hard (as hard as all the problems in NP). Thus, if you had a magical machine that would solve an NP-complete problem, you could solve all problems in NP. A corollary of this is that you can turn any instance of an NP-complete problem into an instance of another NP-complete problem. Such a reduction is usually employed to prove that some given problem X is NP-complete: one says "I can turn any and all SAT problem instances into instances of X, therefore if I could solve X I could solve SAT, therefore X is NP-complete".

To answer your question: no. NP-Complete is a subset of NP-hard, but NP-hard is not a subset of NP. It's actually the other way around. NP is a subset of NP-hard. The Wikipedia article on NP-hard has a good diagram showing the relation: http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg

For people without mobile platforms

[Anonymous Coward]

An essentially identical game, Drench, is available as a Flash game at Flash by Night.

Just to throw this out there

[NitsujTPU]

Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.

NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games. Additionally, you always have to generalize these games in order to make that claim. Since computational complexity is defined in terms of the length of the input, and certainly all of these games are being played on an input of fixed length.

However, there are effective approaches to solving NP-Hard problems. There are solvers for known NP-Hard problems. If you Google "sat solver" you'll find at least 5 that you can just download. SAT solvers are used in VLSI validation and other practical things. These solvers use heuristics to improve search performance, generally proposing answers and checking them (for NP-Complete problems).

Also, there are tons of games known to be NP or PSPACE complete. The reductions for those games are kind of a standard problem, since the AI community writes a bunch of these solvers.

Re:Just to throw this out there

[Anonymous Coward]

I have no idea what you just said. Can you use a car analogy?

Re:Just to throw this out there

[NitsujTPU]

I should caveat all of this. The "no polynomial-time algorithm" bit is only true if P!=NP. If P=NP, then there is a deterministic polynomial-time algorithm for NP-Complete problems. NP-Hard, however, just means that it's at least as hard as NP, so, it's possible that there's no algorithm for that harder problem. You have to be really really precise when talking about this stuff.

Re:Just to throw this out there

[Anonymous Coward]

Well to be pedantic, you aren't quite right either. NP-Hard means there is no KNOWN (deterministic) polynomial-time algorithm. If P==NP, then there will be some polynomial-time algorithm.

Re:Just to throw this out there

[Anonymous Coward]

I got there 2 minutes before you did.

Re:Just to throw this out there

[bondsbw]

Even more, you have to know what problem you're trying to solve. There are two obvious possibilities:

• What is the smallest number of moves I can make to complete a 14x14 puzzle?
• Can I complete a given 14x14 puzzle in 25 moves?

The first is NP-Hard. But the second may be much easier... if possible, come up with an algorithm to solve every puzzle of that nature in 25 moves. Then your answer would always be yes (a tautology), and the problem is no longer NP-Hard. It's the same as if I asked if every puzzle with at least 5 colors can be solved in 1 move. That's an obvious no (a contradiction), so that question is also not NP-Hard. (I don't know if every puzzle can be solved in 25 moves... perhaps so, but maybe not.)

Re:Just to throw this out there

[Bob Hearn]

Ah, it doesn't mean that either. :-)

If a problem is NP-hard, it means it is at least as hard as any other problem that can be solved in polynomial time on a nondeterministic computer.

It is an open question (P=NP) whether this is equivalent to saying that there is no deterministic polynomial-time algorithm.

Re:Just to throw this out there

[yariv]

Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.

NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games

Sadly, you seem not to understand the term yourself. NP-Hard means that given an efficient (deterministic polynomial-time) algorithm to this problem, one can devise an efficient algorithm for any NP problem, so any problem for which solutions can be verified. It might not mean that they aren't solvable (they are solvable efficiently iff P=NP), and a problem might not be solvable and still not NP-Hard. Discrete logarithm and factorization, for example, are suspected to be neither polynomial time computable nor NP-Hard (on classical models, not quantum).

In general, the idea that we are attracted to NP-Hard problem seems quite unlikely to me. We might be attracted to hard problems, but since humans are unable to run algorithms in their heads, why would we use the notion of computational complexity for this "hardness"? It seems more likely that generating problems in the way we do is likely to produce NP-Hard problems than to say we're interested in them as games...

Re:Just to throw this out there

[tepples]

The "no polynomial-time algorithm" bit is only true if P!=NP.

And to the best of human knowledge, it happens to be the case that P!=NP.

Re:Just to throw this out there

[Anonymous Coward]

Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.

NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games.

Wow. You proved your point rather nicely. NP-Hard means that if you solve it in (deterministic) polynomial time, then all NP problems can be solved in (deterministic) polynomial time. It doesn't mean that they are not in P (though, granted, it seems unlikely). A subset of NP-Hard is NP-Complete: the NP-Hard problems that are also NP. Wikipedia has pretty drawings about it.

Re:Just to throw this out there

[SomeJoel]

If you drive from Los Angeles to New York without using cruise control, it's hard to figure out exactly how many inches you'll drive (accounting for curves in roads on whichever route you choose), but there are ways, such as maps, to get pretty close approximations.

Re:Just to throw this out there

[jwietelmann]

Actually it happens to be the case that there is no mathematical proof that P = NP or that P != NP. Wikipedia article.

Re:Just to throw this out there

[jwietelmann]

Never mind, I now see that your point was to say that, for practical purposes, we basically just assume that P != NP, since no one's ever been able to solve one of these problems in polynomial time.

I wish Slashdot would introduce an "Edit" feature.

Re:Just to throw this out there

[tobiah]

We might be attracted to hard problems, but since humans are unable to run algorithms in their heads, why would we use the notion of computational complexity for this "hardness"? It seems more likely that generating problems in the way we do is likely to produce NP-Hard problems than to say we're interested in them as games...

The appeal of these puzzles is that they're hard to solve but easy to verify the solution. If the puzzle were easy you'd get bored, and if it was difficult to verify you'd get frustrated. That's why I always look for the "Certified NP-Hard" sticker on the side of my new board game purchases.

Re:Just to throw this out there

[yariv]

The point, of course, is that we believe that many problems are hard but not NP-Hard (I gave two examples, there are others). In fact, most of our cryptography (maybe all, but I'm not sure) is based on hardness of presumably non NP-Hard problems (but NP, of course). You can play the RSA-breaking game, it's not NP-Hard but it is hard... (as far as we know, of course)

Re:Just to throw this out there

[steveb3210]

Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.

NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games

Sadly, you seem not to understand the term yourself. NP-Hard means that given an efficient (deterministic polynomial-time) algorithm to this problem, one can devise an efficient algorithm for any NP problem, so any problem for which solutions can be verified.

You're wrong too.

Every problem in NP can be solved in polynomial time iif an NP-Complete problem can be solved in polynomial time.

There are also decision problems that are NP-Hard but not NP-Complete

Re:Just to throw this out there

[yariv]

You're right, I wasn't accurate. I meant the problems we're discussing, which are always NP, but didn't state it. In all games for a single player the requirements for a solution are local, so it is necessarily in NP, it can be verified in linear time (go over all of its parts, verify each based on local environment of fixed size, so you do it in fixed time). I should have said it. Of course, games that aren't NP does not make sense, how will you know that the solution you found is a good one? The ability to do so is the definition of NP.

Re:Just to throw this out there

[BigSes]

Is there a list somewhere on the net of some examples of the various games that fit into NP, PSPACE and NP-Hard? It'd be an interesting read.

Re:Just to throw this out there

[ganhawk]

* What is the smallest number of moves I can make to complete a 14x14 puzzle?
        * Can I complete a given 14x14 puzzle in 25 moves?

If you have an efficient algorithm to calculate if you can solve a given puzzle in n moves, then you can answer the question what is the smallest number of moves required by doing a binary search and calling your algorithm every time in the binary search.
In other words, you can call your algorithm for (2) polynomial number of times and find the answer for (1).

Re:Just to throw this out there

[David W. White]

[The "no polynomial-time algorithm" bit is only true if P!=NP. And to the best of human knowledge, it happens to be the case that P!=NP.] Actually, we don't know for sure if P!=NP (though most experts in the field of computational complexity beleive this is the case), and no one has been able to prove or disprove that P==NP.

Re:Just to throw this out there

[Anonymous Coward]

Yeah, if you enjoy reading lists!

Re:Just to throw this out there

[Anonymous Coward]

WAR genetic algorithms and hybrid heuristics

Re:Just to throw this out there

[bondsbw]

If you have an efficient algorithm to calculate if you can solve a given puzzle in n moves, then you can answer the question what is the smallest number of moves required by doing a binary search and calling your algorithm every time in the binary search.

Yes, but that's not my question. My question said "25 moves", not "n moves".

I know I can solve any 14x14 puzzle in 14x14 = 196 moves, because I can just loop over columns (i from 1 to 14) and rows (j from 1 to 14) and choose the next color to be the color at cell (i,j). Perhaps I can determine a variant algorithm to solve it in 195 moves. Perhaps then 194, and then 193, etc. But at some point, I assume there is some number of moves for which I can no longer vary my algorithm and come up with a solution every time... even if it's a low number like 10 or 5.

Your binary search algorithm will only work if we can that for n moves, where n is any number between 1 and 196, a solution either 1) can always be found, 2) can never be found, or 3) has a deterministic polynomial time decision algorithm. Do that, and generalize for any size grid, and you'll have solved P=NP.

To be fair, I left "3)" out of the discussion the first time. But adding that as a possibility, my second question may be polynomial-time solvable even if the answer is not always "Yes". Also, to be fair, the first question could be in P because of the 14x14 limitation. But the general problem without such constraints is NP-Hard.

Re:Just to throw this out there

[metaforest]

Ah tilting at windmills.

Years ago, I spent a lot of time working on the Knight's Tour problem. http://en.wikipedia.org/wiki/Knight's_tour

A straight-forward solver (no heuristics) will not find a single tour in thousands of hours of searching, even if it's code is highly optimized. However if you code in a simple heuristic,(Warnsdorff's rule) even a bone-headed implementation will easily find thousands of solutions per second on a single (100MHz) CPU. To be fair, finding all possible solutions (open and closed) to the problem, took a very large and fast MPP well over a month.

Ah well.... maybe I'll try to write a solver that runs on a GPU to get a solution set that doesn't require a bazillion dollars of hardware and millions of watt hours of energy to generate.

 

Re:Just to throw this out there

[NitsujTPU]

I've never seen one, but that doesn't mean that it doesn't exist.

Re:Just to throw this out there

[NitsujTPU]

I actually threw in the caveat in a follow-up post (since I wasn't very atomic about it) that this was if P!=NP. Nothing that I said affects class inclusions once that caveat is thrown in.

Re:Just to throw this out there

[NitsujTPU]

You know, I just shouldn't have chimed in. I'm beginning to regret that I did.

Thank you for speaking down to me. Now, lets get to business.

I get it. I actually understand computational complexity very well. Had you read the follow-up post, which was posted well before your post, you would see that I added the caveat "if P!=NP", long before you had a chance to talk down to me.

"human creativity"?

[martas]

sorry to burst your bubble, but there are many poly-time approaches to solving NP-hard/complete problems that are "good enough" for many purposes. and vice versa - many (most? all?) problems that are poly-time, humans solve using heuristics that lead to often sub-optimal solutions. so what exactly is new here?

Re:"human creativity"?

[HarrySquatter]

Nothing really. It's just further proof that kdawson is even more incompetent than Jon Katz.

Re:"human creativity"?

[KahabutDieDrake]

Easy there kiddo. Katz may be many things, but we do not speak ill here.

Why?!

[RyuuzakiTetsuya]

Probably because like any other good problem, they both offer a problem and they help start the solving process.

-1 obvious

[waddgodd]

the conclusion drawn is pretty much one that you're taught in basic-level game theory. If its easy to solve, nobody wants to play it

Re:-1 obvious

[somersault]

If its easy to solve, nobody interesting wants to play it

Fixed that for you..

chess and go aren't np-hard, but they are also fun

[darkeye]

so where is the pattern?

Search Space

[Anonymous Coward]

Sufficiently large search space makes it possible to invent a heuristics suitable for the personality of the player. This way the game becomes a way of self expression and continual reinvention.

Re:MetaMetaquestion

[HarrySquatter]

Because they are made from recycled tacos?

Humans are *not* good at such games--see Sudoku

[mutualrecursion]

NP-hard just means you (most likely) need an exponential search. Maybe you want to take this as evidence that human creativity is needed, but that's a stretch. Humans don't do better than computers on NP-hard problems. In fact, they almost certainly do worse, because if you cannot skip the search part, computers are tremendously faster at that. See how quickly a human solves a sudoku, vs. a computer. Even though it's NP-hard (for arbitrary dimensions).

Of course the whole thing depends on the base of the exponent. It's true that many hard problems are hopeless for computers while humans do detect some patterns and make some progress. (E.g., searches for mathematical proofs.) But the games listed have pretty well-defined, fairly small search spaces.

Plus, the proof for NP-hardness is for arbitrary sizes, not the usual dimensions that humans play the game at. Computers are hands down better at that.

No.

[Hatta]

are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"

No. The human mind is created by the brain which is governed by the laws of physics. The laws of physics are mathematical, so fundamentally the human mind is an algorithm. Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot. It's not easier for humans to solve NP-hard problems. We just come with better software for it.

Re:No.

[Dunbal]

The human mind is created by the brain which is governed by the laws of physics.

      Rubbish. While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc. The brain is receiving inputs from every possible sensory organ and responding to it - modifying it's actual structure because of it, and also responding to factors in its internal environment - chemical and electrical concentration gradients.

      This is why even identical twins raised in identical environments will respond differently to the same stimulus - if only because on is sitting on the left and the other one on the right. Physics cannot explain why I, at this instant, choose to think about a magenta capybara and why you, having never heard of this creature I just made up, actually imagined one when you read it.

      We are more than the sum of our parts.

Re:No.

[Hatta]

While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc.

All of which are fundamentally governed by the laws of physics. Math.

Physics cannot explain why I, at this instant, choose to think about a magenta capybara and why you, having never heard of this creature I just made up, actually imagined one when you read it.

Sure it can. Chaos theory. Sensitive dependence on initial conditions. Physics can't predict exactly where the next tornado will touch down either. That doesn't mean weather is independent of the laws of physics.

We are more than the sum of our parts.

I agree. We are the product of our parts.

Re:No.

[mrnobo1024]

The laws of physics are mathematical, so fundamentally the human mind is an algorithm.

That does not follow. There are plenty of things one can describe mathematically but which are nevertheless uncomputable. The obvious example: A function defined as f(p,i) = { 1 if p halts on input i, 0 if not }, where p ranges over programs in some Turing-complete language.

Re:No.

[MobyDisk]

We just come with better software for it.

We also come with better hardware for it. For now...

Re:No.

[amplt1337]

The laws of physics are mathematical, so fundamentally the human mind is an algorithm.

This is where your logic breaks down. The laws of physics are mathematical, but that does not imply that the things they govern are algorithmic. The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you? (if you are, cut me in, let's go make billions in Monaco, sound good?)

Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot.

...love?

Re:No.

[yariv]

Well, your argument assumes something about equivalence of computational models (or, actually, to which model the brain is equivalent). It is believed that quantum computability > probabilistic computability > deterministic computability (I mean efficient computability in all models, of course), to which one is the brain equivalent?

Furthermore, the brain is not designed to run algorithms, it's not a universal turing machine. The vast majority of humans are unable to grasp the idea of algorithm, and running one properly in your head for non-trivial amount of data is, well, non-trivial. If you disagree I suggest doing some code reviews, it should convince you. So, I don't think there's any connection between the notion of computational complexity and what's hard for humans, but we might learn some things about the way we devise problems, maybe about some sort of "typical hardness" when sampled by human design.

Re:No.

[Anonymous Coward]

Thanks for simplifying that for us. If you're interested in a more nuanced view google 'the qualia problem'.
There is no satisfactory physical account of consciousness yet. Epiphenomenalism [wikipedia.org] and emergentism are attempts that leave us wanting more.
Your faith in the all-explaining power of physics is just that: faith.

Re:No.

[BlueBoxSW.com]

The idea the human mind is best understood as a physical object acting on itself, has always rubbed me the wrong way.

While having a basis in fact, it is not the most USEFUL model of the human mind.

It is like a book review that focuses on the number, length, and repetition of words in a book.

Based in fact, yes. But useful? No.

Re:No.

[abolitiontheory]

All of which are fundamentally governed by the laws of physics. Math.

I think you're equivocating here. Governed by physics, yes, but not by math. Math is the language of description, not the laws themselves. So the equivocation here is between description and causation. Mathematics describes in a human/machine cipherable language the seemingly immutable physical principles of the universe. This type of sensual observation falls prey to Hume's complete skepticism, that we cannot say something is fundamental just because our experience of it has never been controverted. That's an impossible jump of logic, no matter how high the mound of evidence piles.

The response to Hume's skepticism is Kant's transcendentalism, a notion which de facto attempts to escape Turing completeness. Even if our divine spark doesn't come from an actual deity, Kant's claim is that we are in some way divine, he sets the plane of divinity within us. While Kant's claims need not be accurate, successive thinkers continue to ground 'humanness' (what makes us self-aware and makes our life meaningful) in something beyond chemeo-physical determinism/reactionism. Heidegger's 'being-towards death,' Levinas' 'Otherness,' and Derrida's 'differance' all point to this, arguing in the very structure of cognition (i.e. the very reasons why science is interesting to us and why we carry it out) extends beyond Turing complete determinism.

For me this questions bends back the fundamental possibility/intelligibility of AI. Can a thorough (i.e. Turing complete) description of the physical laws ever be reverse-compiled into that seemingly 'divine' spark of human awareness and intentionality. Description, codification, transition of sensation into intelligibility is the first step, but I'm doubtful that it can ever be translated 100% back.

Re:No.

[Hatta]

The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you?

Of course there is. It's just incredibly complex. We could not possibly measure all the variables with enough precision to predict a dice roll. Doesn't mean there's not an algorithm.

Re:No.

[bkaul01]

No. The human mind is created by the brain which is governed by the laws of physics.

You're veering into philosophy there, and begging the question while you're at it. While it's plausible that this could be the case, it's far from the only possibility, and is not the conclusion that most philosophers have arrived at. You may have faith that the mind is an illusion or a mere product of deterministic phenomena. Many of us disagree and believe that the mind does exist and, while it uses the brain, it isn't a mere product of it. Neither position can be scientifically proven, as it is a philosophical/metaphysical question rather than a scientific one, but the position that the mind is more than a mere product of physical phenomena has been far more convincing to most people throughout human history. Even if I didn't agree with it, I don't think I could work up the hubris to dismiss it out of hand.

Re:No.

[CorporateSuit]

All of which are fundamentally governed by the laws of physics. Math.

I believe you have it backward. Physics uses math, but it is not governed by it. Math and physics are simply our understanding of things. When we take one leaf and place it next to another leaf, then having two leaves, math is accomplished, but it's not because of math that we put two leaves together. Math doesn't GOVERN anything. At most, it can suggest, but it's physics' use of math that will push things in motion. That, then, climbs to biology/chemistry to use math to determine proper manipulation of physics. Math is simply man's grasp of universal limitations. To say that math governs everything would be similar to saying that harddrive and RAM chip manufacturers are the ones that have programmed everything ever written on a computer. Perhaps the programmer couldn't do his job without them, but it's the use of the RAM chips and harddrives that matters, and until then, they are useless voids.

Re:No.

[Hatta]

Well, your argument assumes something about equivalence of computational models (or, actually, to which model the brain is equivalent). It is believed that quantum computability > probabilistic computability > deterministic computability (I mean efficient computability in all models, of course), to which one is the brain equivalent?

I don't think it matters. All that matters is that it's sufficiently complex to pass the turing completeness threshold. Then it's fundamentally equivalent to any other computer.

Furthermore, the brain is not designed to run algorithms, it's not a universal turing machine.

Notepad is not designed to run algorithms, it's not a universal turing machine. That doesn't mean it can't be run on a universal turing machine.

Re:No.

[amplt1337]

This is the old "is the universe deterministic" debate that's been raging for thousands of years.

My personal suspicion is that we would need to measure the variables to a sufficient degree of precision that we would hit the realm where physics is no longer strictly deterministic, i.e. that changes at the subatomic level could potentially alter the result. That's probably an overbold claim for dice (unless I want to throw in a "for sufficiently well-constructed dice" weasel), but even so, it may be the case for neurons, for which the normal level of operation is a lot smaller; a sufficiently accurate model would need to account for a lot of movement at the molecular level...

Either way, I think that in the absence of more data, the kind of strong determinism you're proposing is really just an article of faith.

More to the point, you aren't responding to my claim that brains can generate minds, something computers have never been shown capable of doing. I think that the ability to create a mind, and the ability to create concepts with "aboutness" through conceptual metaphor, both present in brains but not computers, are two fundamental hurdles to be overcome before we can really say that a brain is reducible to an algorithm/computer.

Re:No.

[Idiomatick]

It is a big ass rat. And physics will explain all these things given enough time and research.

Re:No.

[professionalfurryele]

Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot.

...love?

This kind of reasoning always worries me. If I build an AI which has emotions and is functionally indistinguishable from a human in terms of emotional response will you still make this claim. Will we one day use this kind of argument to deny sentient beings their fundamental rights?

The human mind is a complicated neural network with some chemically adjustable parameters. Nothing more. While the parent was a little clumsy with their language that is the upshot of their assertion. If you can get a human to do it, you can get a computer to do it and it's obvious this must be the case. A simple thought experiment, consider a supercomputer (it would have to be more powerful than anything that exists today by several orders of magnitude) simulating the workings of a brain. Assuming we choose appropriate initial conditions. Is this simulated brain not a sentient being?

Re:No.

[AndersOSU]

I agree that the weather is no more independent of the laws of physics than are our brains.

I however also think that like the weather and the complete universe, and other non-determinant systems, the smallest complete model of an animal brain is the brain itself. Because of chaos and quantum uncertainty and the vagaries of analog and digital it may be that while there is no one thing human brain can do that a computer cannot do, it may also be true that there are dependencies in the system such that it becomes impossible for any human brain model to do exceed the capability of the human brain in certain multiple tasks simultaneously.

It is also possible that Turing completeness is necessary but not sufficient to model a human brain.

Re:No.

[amplt1337]

No, what I mean is computers, at present, cannot love. They do not have strong AI. AI researchers are committed to this idea that brains are computers, therefore strong AI is just around the corner. It isn't -- and it won't be, because the field is still driven by the attempt to recreate in silicon something other than what exists in meat. The fundamental problem is the hand-waving that happens around the assertion that "the human mind is a complicated neural network with some chemically adjustable parameters. Nothing more." All right... This is a tremendously bold claim. Where's your proof? What's your evidence? Your statement is an axiom held dear by people who are much more familiar with computers than with human minds, but reasserting that "it's obvious this must be the case" is just retrenchment of your beliefs.

If you build an AI which has emotions and is functionally indistinguishable from a human in terms of emotional response, I will be very impressed. You haven't done that, though, have you? Nor has anyone else. Call me when you do. (Better give your great-great-grandson my phone number.)

As for your thought experiment, it's not a new one to me. AI research, if it's ever going to get anywhere near strong AI, is going to have to go this route. If you can effectively simulate a human brain, yes, I agree you have a sentient being on your hands (and a major problem when the next brownout rolls along). That said, you won't be able to do this unless you also simulate sensory connections to the world, basic physical needs, the ability to move around and experience the world, centralized location in space, and a lifetime of lived experience (the latter would probably be accomplished by providing the simbrain with a lifetime in which to experience things through its sense simulations). You would, of course, need to simulate the brain's development from infancy through childhood through puberty. But do all those things, and yes, eventually you probably have some sort of simulated human life.

But your thought experiment assumes the conclusion in its terms. You have posited that you have computing resources and know-how to assemble something that's indistinguishable from the brain of a conscious person, a brain that can generate a mind, and then asked if it can generate a mind. Well... yes. If it didn't, it wouldn't meet the terms of your assumptions. Beyond that, it's a thought experiment. I do not believe that such a thing could come close to being assembled in practical reality. Thought experiments of the form of "if my aunt had balls, she'd be my uncle" don't really demonstrate much.

That also still doesn't demonstrate that the life in question is algorithmic within any pragmatic definition of the term; determinism that requires a supercomputer larger than the universe to calculate isn't really determinism worth talking about...

Re:No.

[yariv]

You're missing both of my point.

A) a quantum machine can (presumably, of course) do more than a probabilistic turing machine, which in turn can do more (again, presumably) than a deterministic turing machine. That is, BQP > BPP > P, or so we believe. So it is possible that a quantum computer can solve NP-Hard problems in polynomial time and still P!=NP, as weird as it might sound. The point in this context is that simulating quantum behavior in a classical machine takes exponential memory (if I remember correctly, exponential time, in any case).

B) The fact that an efficient algorithm exist doesn't make the problem easy in human terms. In fact, most of the games we talk about, in the standard sizes, can be solved easily by naive algorithms on modern computers (and not so modern computer), but they are still hard for humans, despite the fact that the human brain is much bigger/faster/efficient in many operation (vision, for example). The reason is the brain is not designed to learn general algorithms, but for specific uses. Therefore, even if we're interested in hard games the hardness we seek for isn't computational complexity but difference from the structure of the brain, the hardness is in using the brain in different ways. If this wasn't the case, we could process natural languages all day, looking for local ambiguities and deciding them based on global structure, but most people do not enjoy this stuff...

Re:No.

[Anonymous Coward]

The laws of physics are mathematical, so fundamentally the human mind is an algorithm.

Explain qualia and intentionality, please.

Re:No.

[Anonymous Coward]

But for all intents and purposes, we might as well say that humans have free will.

Re:No.

[Impy the Impiuos Imp]

Your mind exists, and therefore is caused by something, somehow. And that something seems to be real-world physics, even if the details escape us at the moment.

Secondly, there are two issues:

1. What can the human mind, with consciousness involved or not, calculate?

2. How does the conscious experience arise, presumably from real-world physics? If you wish to introduce a dualist or spiritual world for parts or all of it, I'm not going to argue it -- the same principle applies to that world, too. Conscious somehow arises from it. Spirit atoms, if you will.

Do not get confused between the two issues.

As for the former, Penrose suggested there were certain things (a particular tiling problem) that a human mind could solve but that a Turing machine could not. This implies, from the Church-Turing Thesis, that either the human mind is a more powerful, but finite computation device, or has some hint of the infinite in it.

Please note that said computation by the human mind does not necessarily have to involve consciousness per se (which is another error people make.)

More importantly, his examples are not generally accepted as valid, in that a properly programmed Turing machine (or computer) could not also do such a computation.

As for the second, the conscious experience itself, which may or may not have anything whatsoever to do with the mind as a computational device (or at least anything vital w.r.t. this Turing-equivalency issue) is, as Searle suggests, a real phenomenon, and thus arises, somehow, from real stuff "out there". In other words, it is not a purely informational thing that arises from symbol-pushing itself.

Hence a computer simulation of physics would not yield a conscious entity per se, were a brain to be created in it, though it may be able to create a human-level intelligence (and this is where the vitalness of the conscious phenomenon itself comes in. Recent research suggests it may just be an afterburner interpreting ideas and decisions already made, for the purpose of storing those back into the brain device, rather than being actively involved in immediate decision making.)

And, of course, if one figured out how conscious as a phenomenon arose from real-world physics, you could simulate that physics and get a simulated, functioning fake consciousness in a computer, the way a big simulation of chemistry and physics could simulate a flame or a tire rolling or an electric circuit, for that matter. But the simulated consciousness would not actually be conscious, though it would (as a computational device) pump out the exact same kind of data and for exactly the same reasons.

Re:No.

[Impy the Impiuos Imp]

While at the deepest level, the universe, because of QM, may have true randomness, that does not mean it percolates upward to have a direct effect on dice rolls, which are classical ignorance.

It would be a pretty rare event where the degeneration of one nucleus or proton or neutron shifted or removed an atom that made a difference in a roll, though of course that would be theoretically possible.

So, too, there's no evidence that the conscious experience necessarily has anything to do with QM. I see no reason to suppose that based on its capacity. Such suggestions largely revolve around the inability, for now, to explain consciousness based on known physics. It's a romantic mysticism of sort. Two hard-to-comprehend things -- they must be related!

Re:No.

[Anonymous Coward]

Ah, but you need a really long tapeworm to become Turing-complete.

Re:No.

[Impy the Impiuos Imp]

IIRC, a quantum device is not, in fact, more powerful than a Turing Machine. It's just a hell of a lot faster due to the incredibly massive parallelism ALA "the particle takes every possible path". I could be wrong, but I used to think this, too, until someone corrected me.

Does anyone know for sure?

Re:No.

[Impy the Impiuos Imp]

Francis Crick & Koch blew off "the position that the mind is more than a mere product of physical phenomena has been far more convincing to most people throughout human history" by simply suggesting the time to start the analysis is now. The time for philosophizing is over.

Once the NCCs are fully mapped, insofar as they can be, then people can start looking for additions to physics, as need be, and if necessary

Re:No.

[Hatta]

My personal suspicion is that we would need to measure the variables to a sufficient degree of precision that we would hit the realm where physics is no longer strictly deterministic, i.e. that changes at the subatomic level could potentially alter the result.

Sure, at the bottom it's probabilistic. Probabilities are still constrained by the laws of statistics.

More to the point, you aren't responding to my claim that brains can generate minds, something computers have never been shown capable of doing.

I can't accept or reject that as a premise, since it's the very point we're arguing here. To do so would be begging the question. Just because it's not technically feasible to implement a brain on a computer doesn't mean it's not possible in principle. Knowing that the brain is the physical substrate for the mind, and that we can model the laws of physics on a computer I think it's very hard to argue that it's impossible.

Re:No.

[amplt1337]

As I said, unlikely for dice. When we're working on the level of neurotransmitters and electrical impulses, these are much smaller relative to the size of quantum effects; still, it's a thought, not an assertion. I don't mean to say it's definitely going on.

But with that said, there is also no evidence that conscious experience is the result of a strictly deterministic universe. (Step one of that claim would be to prove that the universe is strictly deterministic, which seems a pretty ambitious proposition, though if proof exists I'd like to hear it.) Even if it were, it likely doesn't do us much good, since any underlying determinism is likely to be so detailed and complicated that it will always be outside our computational abilities to make meaningful use of it. And even if it were, that doesn't mean that a brain is suddenly identical to a computer.

I am less concerned with making positive assertions about the nature of consciousness (I do not claim to have those answers) than with questioning the foundations upon which others embrace an easy reductionism that denies any interesting characteristics to the phenomenon of consciousness. Call it one big "citation needed" to the claim that human minds readily reduce to computers.

Re:No.

[Richy_T]

To claim that the human mind is not governed by the laws of physics, that is, the laws which underlie nature, is to claim for the mind a supernatural property. That veers into superstition and mysticism.

Which is not to say that determinism is the way to go. But if the laws of physics as we understand them do not apply, that is a failure in our understanding of physics, not because the human mind is in someway outside of them.

Re:No.

[Hatta]

This is the most interesting response I've gotten yet. I'm not quite sure how to respond to it, because I'm not quite sure it's entirely relevant. The algorithms that represent the components of the brain must halt because physics occurs. If it took an infinite amount of time to determine (or express probabilistically) what was going to happen to an atom from one moment to the next, physics wouldn't happen.

Re:No.

[jackchance]

....fundamental hurdles to be overcome before we can really say that a brain is reducible to an algorithm/computer

There is no hurdle to overcome in saying that the brain is reducible to an algorithm. Unless you are a religious person who believes in a magical metaphysical mind/soul. The statement "this process can be described algorithmically" is a tautology. The hurdles to overcome are figuring out what the algorithm is.

You can have a deterministic algorithm or a stochastic algorithm. If it turns out that stochastic processes are important for neural computation (which they probably are) then there is an algorithmic description of that stochastic process. If brains are deterministic (highly unlikely) then there is an algorithm for that.

One of the big differences between normal computers (like my mac) and my brain, is that my brain is a dynamical system which is generative. That is, given noisy inputs or no inputs my brain with fill in the blanks and make shit up. This turns out to be useful but also makes me susceptible to illusions, biases, prejudices, etc. We have designed and programmed computers, for the most part, to be very reliable and unprejudiced. But I think we'll see that these noisy generative processes are what make us fast and good at object recognition and speech recognition.

Re:No.

[amplt1337]

Yes. I assumed OP meant "algorithm" as "deterministic algorithm."

I do still think it's unfair to use the term at all when you're describing a stochastic process which is likely too complex for humans ever to characterize. "There are rules for it -- we aren't capable of discovering them, but darnit there are rules!" -- just doesn't seem like a very meaningful assertion. It certainly doesn't follow that "anything a brain can do, a computer can do" -- they operate, and the latter is designed to operate, in fundamentally different ways, and we aren't capable of writing the software that will let the latter simulate the former.

Re:No.

[Dunbal]

Sure it can. Chaos theory. Sensitive dependence on initial conditions. Physics can't predict exactly where the next tornado will touch down either. That doesn't mean weather is independent of the laws of physics.

      It is precisely this inability to predict that I am referring to. While the human brain is running along on well established science, there is no way you can use said physical laws to predict what my response will be to, say, tonight's news. We are the aggregate result of aggregates of aggregates, from the brownian motion of the ions and proteins floating along in our water-based bodies, to the slightly skewed thought pattern arising from the microscopic brain infarct we suffered during that minor car crash 10 years ago (due to a freak hailstorm) with, apparently, no injury (at least macroscopically), to the mood we feel today because we ate one too many chili peppers last night.

      You can trace everything back to its origins. However you may not use the origins to tell me what's going to happen tomorrow with any degree of certainty. Probability might tell me that the chance of rolling a "5" on a dice is 1/6th. However it cannot tell me what my next roll will be.

Re:No.

[Burnhard]

Indeed but one of the philosophical problems to overcome is the fact that our only means of enquiry here (the scientific method) may well preclude classes of hypothesis or conclusions it is incompatible with. What I mean to say is that given you can in principle discover all laws, particles, fields and forces in nature, it does not follow that once you have done so there is nothing left to explain. What you call superstition and mysticism can also be described as transcendent. It may well be that consciousness/mind falls into this class of problem.

Re:No.

[David W. White]

If you build an AI which has emotions and is functionally indistinguishable from a human in terms of emotional response, I will be very impressed. You haven't done that, though, have you? Nor has anyone else. Call me when you do. (Better give your great-great-grandson my phone number.) This is what the turing test is hoping to determine, but so far no (AI creation) has been able to pass it though some have reportedly come close. When considering if passing the Turing test is proof that "computers can think and reason in exactly the same way people do", it interesting to note Searle's conclusion compared to Turing's in http://en.wikipedia.org/wiki/Turing_test. And by the way, I'm a real human, not an AI.

Re:No.

[kvezach]

An "ordinary" quantum computer is no more powerful than a Turing machine. It probably can't even solve NP-complete problems quickly because there's no way of directing the observation step (where you pull the answer out of the numerous universes) in such a way as to make the right answer show up often enough. This is, technically speaking, an open problem (just like P vs NP), but most believe the answer is a negative (just like P != NP).

I said "ordinary" quantum computer because there have been attempts at making quantum hypercomputers (i.e. computers more powerful than a Turing machine). The best known is Kieu's adiabatic quantum hypercomputation scheme, but that appears to have been refuted. Quantum adiabatic algorithms can be useful (they're a bit like genetic algorithms, only on the quantum level), but apparently they can't bring quantum computers above Turing power; a bit like the Brownian ratchet in this manner, in that it's not as powerful as thought, but still useful.

To sum all of that up: it's unknown whether it's possible to make a quantum computer solve NP-complete in polytime, but most think it's unlikely. It's unknown whether it's possible to make a quantum hypercomputer as well, but most think it's even less likely (although if consciousness would disprove this, that would be... interesting).

Re:No.

[professionalfurryele]

You have the burden of proof mixed up here. I am asserting nothing more than that which is supported by the currently available evidence. That is that the human brain is nothing more than a collection of connected neurons (and some structures for delivering chemicals to said neurons). This is all we have seen of the brain. There is no evidence for anything more to the brain and as far as I'm aware no where else to look for more material that would form the brain.

If you are claiming there is more to the brain that just the components we can see then you are the one who must provide evidence to support this assertion. Incidentally by evidence I don't mean hand waving arguments like 'qualia' I mean real, solid, empirical evidence.

That said, you won't be able to do this unless you also simulate sensory connections to the world, basic physical needs, the ability to move around and experience the world, centralized location in space, and a lifetime of lived experience (the latter would probably be accomplished by providing the simbrain with a lifetime in which to experience things through its sense simulations).

Now if we are talking about claims made without evidence this is a big one. I see no evidence to suggest that the formation of a sentient mind necessitates these things. I will grant you all the minds we know of require these things but we certainly haven't exhaustively searched the space of possible sentient brains.

Strong AI may be hard. It may be harder than we can imagine. It may even be technically impossible without supercomputers beyond the scope of that which human kind could ever achieve. I will grant you all of those, although I think all these are very pessimistic assessments. However given that there is nothing more to the brain than the physical components that make it up, and these components form a recognised computational structure, there is absolutely no reason at present to presume that an artificial life form could not one day love. As for this being algorithmic, the structure of the brain itself is computational or at least forms a recognised computational structure. By definition is is only capable of algorithmic processes when viewed in this light. That is what computational structures do. It is all they do. Even randomly programmed computers are following an algorithm.

Re:No.

[yariv]

A lot faster, in this context, is more powerful. The reason being it's not faster by a constant (as a modern computer is faster than a not-so modern one), but in a more complicated way. The point is, we're talking about complexity, not computability, so "possible" means "possible in an efficient way". The notion of efficiency we use is poly-time, is there a polynomial p(n), such that the algorithm will always stop after p(|x|) steps on input x. A problem is NP if it can be solved in poly-time by a non-deterministic turing machine, which we might describe as a machine that tosses coins in a weird way. If the coins might get you to a positive result, they will get you there, if not they won't. For example, you can check if there is a Travelling Salesman short path by choosing a random path and checking it, in a non-deterministic machine you'll get a short one if it exist. You can describe it a "the computation goes through all possible paths, giving the OR of the results". P=NP means for any such problem you can solve it with a real machine (deterministic machine), and it seems unlikely. However, quantum computers, which we don't have and don't really know if they are feasible, seem like something in between. Loosely speaking, you get some sort of parallelism this way, but not the powerful non-deterministic sort. There are some problems, integer factorization and discrete logarithm for example, that have an efficient quantum algorithms but we don't know of any efficient classical algorithm.

By the way, I wrote BQP > BPP > P. This means:
BQP - bounded error quantum polynomial time, quantum poly-time algorithms with randomness that are significantly more probable to give the right answer than a wrong one.
BPP - bounded error probabilistic polynomial time, classical poly-time algorithms with randomness that are significantly more probable to give the right answer than a wrong one.
P - polynomial time, classical poly-time algorithms, no randomness.
It is believed each one is strictly bigger than the next, and we rely on this. IT is well known that factorization and D-log are in BQP. And most of the existing cryptographic protocols (authentication, encryption, etc.) rely on the hardness of these problems. We can solve problems in BPP, so if those are in BPP those cryptographic protocols are insecure, we hope this is not the case...

Re:No.

[Anonymous Coward]

First off, I was originally asserting something on the order of "Pigs can't fly" or "Cats can't do geometric proofs" -- to which the response "But they could be made to!" is not only not contradictory, it's not even relevant. But, since we've gone there...

I never asserted that the human brain is something other than its physical components. But if you will investigate your own statements, you claimed that the human mind is nothing more than a neural net (with the apparent implication that all neural nets of sufficient complexity will produce minds). The mind is the product of a neural net, a function of a specific physical artifact (viz. the human brain) which can be modeled, imperfectly (though in principle perfectly), on computing machinery. But I argue that the mind depends on what that neural network is doing. I.E. mind is a "software" problem, not a "hardware" one. Moreover, it "runs" on a different kind of "hardware" which, though it can be emulated on a computer, is not itself a computer. I would also suggest that a neural net, in the CS sense, may not be a perfect model/emulation of an actual network of neurons (though you'll say it's perfectible in theory, which I'll grant). The brain is made of only physical components, but we do not have perfect understanding of how they work and thus may be simulating them incorrectly or simplifying our models in a way that precludes the development of mind/consciousness effects.

I've already granted that a perfect mechanical simulation of a human brain would have to have a human mind (though that's tautological). My perspective on strong AI is that without a radical redefinition or reimagining of what computers are and how we use them and the contents of their programming, we will never be able to produce a mechanical simulation of a human brain with sufficient fidelity to produce a mind. We have some form of simulated neural net, but that doesn't mean we understand the process/function of that neural net (or are capable of understanding it) sufficiently well to simulate it, even if we can write an emulator for its hardware. Computers can model anything; but that doesn't mean that one thing reduces to another (as OP claimed). Models are not reality. The claim that "the brain is a computer" is a facile truism in computer science (and biology!), but it's a metaphor, and no less fundamentally true than the claim that the weather system is a computer. The brain can be modeled through computation, but that doesn't mean it reduces to a finite set of steps producing a determined result. Using algorithm as you do above -- asserting that any process which can be computationally modeled is an algorithm -- seems to me to be stretching the definition of algorithm to the point that it becomes meaningless.

As for my claims about the requirements to form a sentient mind, they're my expectation, not a law; I'm open to being proven wrong, but the prospect doesn't exactly keep me up nights. Since no one has been able to form an artificial sentient mind under any circumstances whatsoever, obviously we don't have proof of what's required, but I am rather shocked that "all the minds we know of require these things" does not constitute evidence of some kind to you. I think it quite reasonable to ground expectations in universally uncontroverted experience.

Re:No.

[professionalfurryele]

My perspective on strong AI is that without a radical redefinition or reimagining of what computers are and how we use them and the contents of their programming, we will never be able to produce a mechanical simulation of a human brain with sufficient fidelity to produce a mind.

I consider this a position that requires evidence. You have not provided any. Of course I will grant you that we will need to 'write' the 'software' for a model of the human brain, a task which may be incredibly difficult. However since nature has done it in that humans are evolved creatures the notion that humans cant is absurd. It is merely a question of difficulty and I've already granted you that it may be far harder than we imagine.

The brain can be modeled through computation, but that doesn't mean it reduces to a finite set of steps producing a determined result.

It does if your definition of the 'output' of the algorithm is how the brain manipulates those outputs connected to it. By demanding that an AI respond in a manner we would recognise as love you have defined an output function which is computable and finite by definition. If a response we would recognise as love is defined as one output state then the process is definitely algorithmic as the brain is by definition effective. You can claim defining the algorithm this way is meaningless since it applies equally well to saying the cloud formation process is an algorithm for the making of rain (assuming clouds always result in precipitation of some kind) but as far as I'm concerned that is an algorithm.

I am rather shocked that "all the minds we know of require these things" does not constitute evidence of some kind to you.

It's not evidence because we haven't even begun to eliminate vast swathes of the search space. If you saw 3 sheep it is not reasonable to conclude all sheep are white just because all the sheep you had seen were white unless I tell you that the number of sheep in the entire universe is 3, maybe 4 or 5. If the number of sheep in the world is 7 billion many of which are in inaccessible locations this evidence is sufficiently flimsy that no conclusion can be reasonably obtained.

Re:No.

[bkaul01]

The laws of physics apply if the mind is physical. If it is indeed "supernatural" or otherwise transcendent, then the laws of physics are not the driving force behind it. Certainly, to the significant extent that the mind interacts with the brain, physics will have an effect on the mind, but that doesn't mean that the mind is itself a mere artifact of physical phenomena. The question is philosophical in nature.

Re:No.

[amplt1337]

I consider this a position that requires evidence. You have not provided any.

You're welcome to think that, but as I said, it's a prediction. If I tell you I think it's going to rain tomorrow, what evidence could there possibly be to support that assertion? Either it does or it doesn't. If you disagree, make a strong AI using current computational and programming models...

However since nature has done it in that humans are evolved creatures the notion that humans cant is absurd.

Explain. Why is it absurd to think that there are limits to human capability? There are all kinds of things that humans have never done and likely will never do.

By demanding that an AI respond in a manner we would recognise as love you have defined an output function which is computable and finite by definition.

At this point you're just restating your premise (i.e. that everything is by definition computable). What exactly does it mean to compute love as a result? What objective-but-not-brain-bound definition do we have for love as an output state? You're instead evoking a subjective perception ("we would recognize as love") as the standard, which seems inappropriate, given that different people will disagree on what constitutes love.
You also appear to be relying on a functionalist interpretation of mind, which is a position I find inadequate. I know you reject the notion of qualia (and yet I'm guessing you have them, and that everyone you know will assert that they do too)... but I would argue that when asking whether a computer can love, it is less important that we believe it does, and more important that it believe it does. IE a mind's subjective experience of its existence is a necessary condition for a mind to exist. Obviously that raises an underlying problem, which is how can we assign credibility to a claim that a machine believes something. We can do that pretty easily for people because we know from personal experience that beliefs, feelings, etc. are an expected product of certain neurological structures (the brain), but I don't know that I'd write the same pass for claims made by inorganic constructs. I would be willing to accept the claim eventually, but I'd want a bit more evidence than SmarterChild telling me I'd hurt its feelings. [I'd want to see it react spontaneously to unexpected stimuli in a way consistent with it having feelings, and I'd want to see those feelings (as evidenced by reactions) in a variety of circumstances to show at least human-level consistency of emotional response. But I digress.]

As far as algorithmicity goes, at this point you're essentially saying that "algorithm" is a synonym for "process." I view this as a poor definition, but I respect your right to disagree.

Regarding what is required for minds, again, I view this as a prediction, rather than a provable canonical statement. Call it a hypothesis: "I predict that the following are essential to the development of human-like minds: needs, ability to act to meet them, ability to perceive an objective reality, a unitary locus of perception, and a collection of historical experiences." At present I am not sure how to even begin falsifying this claim, except perhaps (for some parts of it) doing something horrible like raising a child in a sensory-deprivation box, or replacing its senses with an artificial perspective from somewhere else, ideally one over which it has no control. As we know of (or have documented the historical existence of) over ten billion minds, all of them human*, humans seem like the obvious experimental choice, but I'm sure you appreciate the difficulties.

* or other sentient mammal, if your definition of mind swings that way, but that's again a whole host of issues & we cannot have the same direct empathy for an elephant as we can a person...

Re:No.

[professionalfurryele]

Explain. Why is it absurd to think that there are limits to human capability? There are all kinds of things that humans have never done and likely will never do.

I'm looking to wrap up this discussion since I think we have both said our pieces but I wanted to address what you said here as you asked me to explain.

I don't question that there are limits to what humans can do. My point was that since there exists a mind (the human mind) capable of doing all the things we have discussed and we understand the process that resulted in that end point (evolution) if nothing else humans could use the same process to create a mind capable of doing what you describe. I granted you that this may be difficult (like go to another planet, add the right microbes and wait 500 million years difficult) but there is very little preventing us from doing this right now. The end result we are looking for has been done, it has been done by nature. It is therefore possible and within the material reach of humans at least in principle. I've little doubt you would admit that this somewhat extreme thought experiment could easily be sped up by human manipulations, although we may debate by how much. I will grant you there would be some debate as to whether this constitutes 'artificial' intelligence but I see no distinction between organic and inorganic computers other than the chemicals their components are assembled from.

Of course it depends on what you mean by achievable and reasonable. Given theoretical limits on computing power and existing rates of development we will have machines with comparable computing capability to the human mind in the next few decades. As far as I am concerned the challenges are then software related because the only empirical means we have for differentiating a mind capable of love from one that is not is how the mind behaves. Your objections to the notion that we could test such a mind just for a response congruent with experiencing love are entirely correct and we would require the corroborating tests your describe. Notice however that all of your tests are of the same essential nature ('does the brain behave as we would expect', essentially they are all functional tests of the brains behaviour). The philosophers are welcome to their debates as whether this functional notion of love is 'real' in some meaningful sense but unless I can measure it with a multimeter or a question which is responded to by a speaker it wont do me a lot of good. Given this position in my opinion there is no compelling argument to suggest that computers cannot behave in a manner we would recognise as love.

Fun == uncertainty

[arielCo]

Part of "fun" is uncertainty, a sense of challenge and the subsequent realization when you succeed, when there is no threat to more basic needs. Such feelings would be lessened if solving the problem was a sure thing (or if on the other extreme it looks unlikely to solve, but that's off the topic), and that's why we pick games/levels according to our skill.

Indeed, to me Minesweeper quickly becomes boring, since most of the clicking obeys pretty simple rules ("2-3-2 along an edge - that's clear-3mines-clear"); then at the end it often becomes undecidable and it's eeny-meeny-clicky-boom.

Re:Fun == uncertainty

[Anonymous Coward]

Since we're in theory land, I think you meant "ambiguous" instead of "undecidable," which means that a proposition cannot be either proven or disproven from axioms.

Re:Fun == uncertainty

[d474]

Part of "fun" is uncertainty, a sense of challenge and the subsequent realization when you succeed, when there is no threat to more basic needs. Such feelings would be lessened if solving the problem was a sure thing

That's what my wife said when I asked her why she cheated on me.

Re:Fun == uncertainty

[iamthelaw]

For what it's worth, many of the positions which you think may be undecidable are in fact solvable. Check out this paper (warning, PDF) from the guy who proved that it was NP-complete; it has a bunch of examples of non-trivial setups that appear to be unsolvable without guessing, but actually are. You don't necessarily encounter these in every game, but you might be surprised if you do some analysis before you make a guess.

Regardless, the paper is a good read.

WoW

[Aragorn DeLunar]

What does this say about WoW, if it can be played quite successfully by a bot?

Re:WoW

[Myria]

What does this say about WoW, if it can be played quite successfully by a bot?

I'm sure that many NP-hard problems exist in WoW. Obviously, farming gold and leveling are not NP-hard. But other questions such as, "Can this raid boss be defeated?" would be extremely difficult in the general case.

Something that hasn't really been mentioned yet is that in NP-hard games played by humans, the difficulty has been dumbed down for humans. The versions played by humans have a very small problem space (Tetris, Sudoku) or avoid the nasty cases that are NP-hard (Picross). Some others like Minesweeper avoid nasty cases by randomness: the nasty cases are simply unlikely.

Re:WoW

[somersault]

It says what I've always thought: RPGs are easy and relatively boring. It's the social experience that makes them interesting though. Still doubt I'm ever going to play it, if I want to play an RPG I'll go play a MUD.

Re:WoW

[Idiomatick]

It provides the same attraction as T.V. which requires no interaction. Numbs your brain. (assuming you are talking about level building)

But wow also can provide this simple game (can be played by a bot) that can become quite difficult (high end arena pvp). So it provides both options.

Re:WoW

[TheLink]

Tic-tac-toe and checkers/draughts can be played quite successfully by computers.

People still play these games.

P=NP?

[Anonymous Coward]

Plug equals Not Play?

Tetris is hard to solve?

[bluefoxlucid]

What? The game can be theoretically played forever on an imperfect generator as long as you don't hit an endless stream of Z and S blocks. It's possible to roughly categorize the blocks and sort them efficiently as they come, perpetually lining up for a full Tetris every time a line comes down. Every piece that shows up has a computationally obvious columnar location under this strategy, but orientation is still obvious but less naively computable; it's pretty boring to play that way though.

Re:Tetris is hard to solve?

[tepples]

The game can be theoretically played forever on an imperfect generator as long as you don't hit an endless stream of Z and S blocks.

In fact, it's against the rules for the game to give you a long stream of blocks. Tetris games since 2001 dish out pieces 7 at a time, and the most snakes in a row that you'll ever get is four: xxxxxSZ|ZSxxxxx. This leads to an easily computable strategy for playing Tetris forever.

Re:Metaquestion

[ZERO1ZERO]

Why is every story tagged story? The answer is in your question...

I'll just have to prove P=NP then.

[tjstork]

Look, I'll fire up a few smokes and toss back a cold one and sort out this whole P=NP problem for you.... I'm sure that I can come up with it right away... how hard can it really be? Tongue firmly in cheek!

Re:I'll just have to prove P=NP then.

[clone53421]

Proving that P = NP is easy... you just have to start with contradictory premises.

Re:I'll just have to prove P=NP then.

[Idiomatick]

N = 1, problem solved folks.

Re:I'll just have to prove P=NP then.

[Anonymous Coward]

You just described the proof of Halting Problem/Incompleteness theorem actually.

The whole theorem states that in every system of maths, there is at least one statement which says that "This statement is wrong" or its equivalent.

Re:I'll just have to prove P=NP then.

[Anonymous Coward]

Exactly... see http://estatis.coders.fm/falso/

Book on the Complexity of Games and Puzzles

[jefu]

There is a fun book on this topic called "Games, Puzzles and Computation" by Hearn and Demaine that is well worth a read if you're interested in puzzles or complexity.

Re:Book on the Complexity of Games and Puzzles

[Anonymous Coward]

Yeah, I know. He left a comment above plugging his book.

Re:Book on the Complexity of Games and Puzzles

[Phrogman]

Yes, Hearn just posted a link to it on Amazon (and a link to his PhD Thesis which is free) in a conversation above your post

Re:Book on the Complexity of Games and Puzzles

[Anonymous Coward]

In fact Hearn posted on this story and linked to his PhD thesis.

http://games.slashdot.org/comments.pl?sid=1613036&cid=31791308

Re:chess and go aren't np-hard, but they are also

[NitsujTPU]

The generalizations of both games are NP-Hard. They're only constant time because of the fixed number of pieces and places for those pieces to go.

Re:chess and go aren't np-hard, but they are also

[Anonymous Coward]

I think you're underestimating the difficulty of these games. They are definitely np-hard (actually a bit harder even)

http://www.ics.uci.edu/~eppstein/cgt/hard.html

Are there examples of games that AREN'T NP-hard?

[Dr. Spork]

It seems to me that earning the title of being NP-hard is very easy for games. As someone said before, even sudoku is NP-hard, but intuition-less computers are still much faster at it than humans with all their intuition. So where is the list of the "boring" games that aren't NP-hard? If there aren't any such games, then this story is pretty trivial.

Re:chess and go aren't np-hard, but they are also

[Bob Hearn]

Chess and Go are actually EXPTIME-complete, even harder than NP-complete problems and PSPACE-complete problems.

In general, one-player games of bounded length (like Flood-It, or Sudoku) tend to be NP-complete; one-player unbounded games (like sliding-block puzzles, or Sokoban) tend to be PSPACE-complete; two-player bounded-length games (like Hex, or Amazons) also tend to be PSPACE-complete, and two-player unbounded games (like Chess, Checkers, and Go) tend to be EXPTIME-complete.

I can't resist here a plug for my book (with Erik Demaine), Games, Puzzles, and Computation, which discusses all these issues in detail. A theme running throughout the book is the same as the view expressed in this paper: most interesting games and puzzles seem to be as hard as their "natural" complexity class, outlined above.

P = NP, eh?

[clone53421]

I already wrote a solver for this exact game. It just isn’t efficient.

Re:P = NP, eh?

[thijsh]

If you want efficiency you should just have made N = 1. :-)

Re:P = NP, eh?

[clone53421]

My solver actually finds the set of every possible sequence of the next 5 moves, chooses the best scenario from this set, executes the first move (of the 5-move sequence), and recurses.

I have no idea how to calculate the big-O of this. It’s been a while since I was in college. All I know is that using every possible next 5 moves it was able to solve the problem in a reasonable amount of time, although it occasionally didn’t find a solution of as few moves as I needed it to... in which case I increased the search to every possible sequence of 6 moves, which took quite a bit longer.

Re:P = NP, eh?

[MortimerV]

I always personally solve this sort of game by working my way towards all four corners, then spreading out. Seems to work 99% of the time, and I maybe look two moves ahead, if that. It'd be even easier to make a solver that did that, though it'd be even less optimal than the way you did it.

Re:P = NP, eh?

[thijsh]

I would have thought that since the board remains fixed you could easily brute force the entire game for an optimal solution... You can optimize the search by grouping colors and discarding branches if you know it's less optimal than another one you already found. The way I would go about this is try to tweak an algorithm that finds the same result as the brute force search with 99% accuracy.

I once wrote a program that could play Bejeweled, but that board changes unpredictably because new jewels keep falling, so the best I could do was calculate the highest combo I could make with the current state of the field. It worked very successful because you would normally start to get in trouble at 10.000 points, but my program kept playing until over 100 million until I stopped it. :)

Re:P = NP, eh?

[clone53421]

You could. That’s basically what I was trying to do. Brute force takes a while, though.

Other than just brute forcing a fixed number of moves ahead and then throwing out all of the moves except the one that seemed most optimal from the position at that many moves out, I don’t know how you’d optimize it any further.

Re:P = NP, eh?

[thijsh]

There are some ways to optimize, even when you brute force. For example the small Flood-it board has 14 × 14 = 196 squares. The total search space is 196 ^ 25 = 2×10^52 (a lot). But when you consider that clicking a neighboring same-color square is logically equivalent the average moves per turn is much lower, I would estimate about 50 (100 on the first, 2 on the last move). You also never have to complete the full 25 moves, because you will find a shorter solution fast enough and you can discard any longer solution, so the average is around 18 moves to finish the game... The total moves to calculate are 50 ^ 18 = 4×10^32, that is some massive saving (but still takes years on a regular CPU). But you can of course optimize further...

When you are time limited you can always modify a brute force algorithm to choose the most promising branches first (like largest number connecting squares first). When you need to make the move in under 1 minute you can calculate until you hit 59 seconds and then return the best result you've found until now. In my experience when you have a good decision algorithm you can get near-optimal results with a partial time limited brute force search.

I wonder when we'll start seeing Flood-it bots competing against each other in an international competition. :-)

Re:P = NP, eh?

[clone53421]

Have you played the game in question? The upper-left square, and all neighbouring squares of the same colour as it, can be changed to any colour by clicking one of the tiles from the colour palette. You can’t click the colour it already is (nothing will happen), so there are really 5 possible moves at any given point. The contiguous region of the same colour as the upper-left square will change colours, merging into squares neighbouring it of the colour that you are changing to, creating a larger region of contiguous colour.

So, for a board with c colours, on any given move you can choose any of the colours except the colour of the upper-left square, so the total search space, assuming a 25-move play, is (c - 1)^25.

(For c = 6, that equals 298,023,223,876,953,150 possibilities.)

For instance, this board. For the 15th move, you could choose any colour except pink, leaving 5 possible moves (purple, blue, green, yellow, or orange).

One obvious optimization is that of these 5, choosing orange makes no sense because no adjacent squares are orange. So, you should eliminate that entire branch where the next move is orange. My solver tries only the colours that are actually adjacent to the same-colour region.

Furthermore, note that in this example game, the board will be fundamentally identical after the plays blue, yellow or the plays yellow, blue (note that it should read step 16 at that point), so only one of those branches need be played out.

Tetris and Minesweeper fun?

[wisnoskij]

I do not know about anyone else, but I never really got how anyone considered these games fun.

Re:Tetris and Minesweeper fun?

[KingAlanI]

There's just something about straightforward addictive arcade games.
(Playing the arcade-game over-and-over is somewhat different from some other game that takes a long time to play through one round, or games with an indeterminate end)

Re:Tetris and Minesweeper fun?

[Richy_T]

Not for some of us though. Which could have potentially interesting psychological implications.

However--

[bill_kress]

I think discussing your new iPhone game on slashdot is an NP-Easy way to get a substantial popularity boost.

Tetris lasts five minutes now

[tepples]

whenever I play Tetris I grow tired of it rather quickly (less than half an hour).

That's why new versions of Tetris take five minutes to play through: either they're two- or three-minute time trials, or they speed up so fast that you're dead after 5 minutes. Watch this video all the way through.

Tetris need creativity?

[Cheburator-2]

Not a chance, you can play it half asleep without a single thought, just as easy as writing or talking. I've written a relatively simple algorithm for a computer to play tetris, it enumerates all possible options of placing a piece and compares certain properties of resulting landscape (number of holes, smoothness of surface, etc). Of course it is not perfect, but it can easily outplay most human players without any problems.

Re:Tetris need creativity?

[owlstead]

"Not a chance, you can play it half asleep without a single thought, just as easy as writing or talking. I've written a relatively simple algorithm for a computer to play tetris, it enumerates all possible options of placing a piece and compares certain properties of resulting landscape (number of holes, smoothness of surface, etc). Of course it is not perfect, but it can easily outplay most human players without any problems."

They probably tried to find an algorithm to actually *win* Tetris and failed. Then they decided to input infinite size of blocks, infinite size of the playing field, infinite speed over infinite time and decided it to be NP-complete :)

Re:Tetris need creativity?

[tepples]

They probably tried to find an algorithm to actually *win* Tetris and failed.

In fact, all they really had to do was wait for The Tetris Company to change the rules. Modern Tetris is trivially playable forever.

I don't get why...

[rm999]

I don't get why people talk about NP hard in games that generally have fixed-sized worlds. The whole point of complexity in computer science is to talk about how an algorithm can scale up with N, but when N is fixed I would argue that the algorithm's complexity doesn't even matter; it is fixed for that game.
For example, who cares if an AI takes 10x longer every time you add 1 to the width of a tetris world? 99.999% of people play on a 10x20 board. When I hear someone say "blah" is NP hard, I always ask "what is N?" You'd be amazed how many people can't answer that question.

Also, calling games like these NP-hard misses the more important point of how good heuristic algorithms are, which is the way most humans and current AIs attempt to solve them. A game is not more fun because is it NP-hard, it is often more fun because finding, learning, and applying the heuristics on the game is fun.

Re:I don't get why...

[Bob Hearn]

The reason that fun games tend to be NP-hard (or harder) is that if a game's "physics" supports interesting constructions requiring complex reasoning to solve, then probably that same physics can be used to build computational gadgets, which is how you show hardness of the generalized version. This quality expresses itself even on small, fixed-size board.

Great, another color-blind insensitive game

[Anonymous Coward]

At least why can't game designers stay away from the "problem" colors like reds/greens, blues/purples etc.??

Re:Great, another color-blind insensitive game

[Anonymous Coward]

Why can't you just get a better X chromosome? Selfish jerk.

Can you beat colour_thief?

[tepples]

I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

Usually that happens once you get into the 8000s on Tetris DS or you can get M in Master or Death on TGM2+. Then you get to the tournament (i.e. "competitive level") and find that this ni**a can still steal your colour. Two places where the hardcore players hang out are harddrop.com and tetrisconcept.net.

Floodit record

[Notquitecajun]

Math, math, blah, blah. Post your record people.

24 turns, but I'm a beginner.

"Easy to Learn, Hard to Master”

[imnotanumber]

It is another way of saying “Easy to Learn, Hard to Master” .

If a game with simple rules poses a problem that is complicated enough so that you can't find a trivial solution, that is half way to have a fun game.
There are other aspects like some randomness, enough to create variety but not to make it a luck game, etc...

Re:"Easy to Learn, Hard to Master”

[Anonymous Coward]

Whatever, Greg Gutfield.

Re:chess and go aren't np-hard, but they are also

[TheKidWho]

Get me a kindle version of that book and I'll consider purchasing it!

Re:Metaquestion

[somersault]

Well, I think in the end he means something more along the lines of "why is the story tag visible on the front page". I find it annoying too sometimes.

Co-op minesweeper

[tepples]

Indeed, to me Minesweeper quickly becomes boring, since most of the clicking obeys pretty simple rules ("2-3-2 along an edge - that's clear-3mines-clear"); then at the end it often becomes undecidable and it's eeny-meeny-clicky-boom.

That's when you start playing games that slowly solve the boring stuff for you. My own Luminesweeper is one of them: a line periodically sweeps across the screen and solves squares using the single-point method. So it almost feels like you're playing co-op, and the goal is to do as much as you can to promote a healthy alternation between the hard stuff (your task) and the easy stuff (the CPU's task).

Re:chess and go aren't np-hard, but they are also

[Bob Hearn]

I'll mention it to my publisher, but honestly it would lose a lot without all the color figures.

The book is based on my Ph.D. thesis, which you can download for free:

http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf

Is it just me...

[Anonymous Coward]

Or does the Wikipedia article introduction for NP http://en.wikipedia.org/wiki/NP_%28complexity%29 contradict itself??
It says that NP is the set of decision problems for which the 'yes' answers are verifiable by a non-deterministic Turing machine in polynomial time. Then it goes on to say that NP also includes NP-complete problems, which have no known polynomial-time solution algorithm. So, how come they know NP-complete belong in NP, if there are no known solutions???

nonsense

[pydev]

This means that there's no way to write an efficient program to beat the game, unless P=NP.

All these games are small finite size in practice, so asymptotic complexity results tell you nothing about how difficult it is to solve them. In addition, the idea that "P = efficient program" is utter nonsense; for large problems, even quadratic complexity is a serious problem. A realistic notion these days is that a reasonable asymptotic complexity for "efficient programs" is no worse than n log^k n for small k. Anything larger than that and it won't scale. The converse is also nonsense. Just because a particular problem is NP hard in general doesn't mean that the problem instances you encounter in practice are hard cases. Furthermore, the assumption that you need to find an optimal solution is also wrong. In fact, in any competitive game, all you really care about is beating the other guy.

P=NP is a neat theoretical issue in computer science, but its practical significance has been completely overstated.

Re:nonsense

[Krahar]

What he said. +inf insightful over lots of computer science professors who don't know what asymptotic complexity means and does not mean, or at least don't care to admit it.

Re:nonsense

[thoughtsatthemoment]

Totally agreed. There are the mod points when I needed it the most?

Re:nonsense

[TheTurtlesMoves]

While i agree with you in general, especially in this case. However knowing something about NP etc is helpful. There are a lot of real problems that are NP hard that we want to solve with large n. An example is tool paths in CNC milling. Knowing that you can't realistically find the optimum solution already gives a good hint to not try, and stick with heuristics. ie good enough is enough. There are other examples too, but don't throw the baby out with the bathwater.

I solved it

[jimbolauski]

P=N*P
N=1

P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1

Now where in my Nobel Peace Prize.

Re:I solved it

[Jake Griffin]

(P-1)! = 1
P = 1

Now where in my Nobel Peace Prize.

You don't get a Nobel Peace Prize. Because P = 1 or P = 2. Now where is MY prize?

Re:I solved it

[Anonymous Coward]

But P could be equal to 1 or to 2. That's why this problem is so hard, nobody knows which it is : )

Re:I solved it

[Frequency Domain]

No Nobel for you, you overlooked the other solution.

P=NP when N==1 or P==0.

Re:chess and go aren't np-hard, but they are also

[timeOday]

Generalizing chess past an 8x8 board doesn't make a lot of sense, since the number and types of pieces and their initial placement are so integral to the game. Practically the only people who do generalize it are computational theorists. It's like arguing about what football would be like if the field could by 1000 km long.

Re:Metaquestion

[camperdave]

They're not tagged "tagged" when they're tagged. They're not tagged "english" when they're english. What's the point of tagging an article with "story"? It doesn't aid in any search. It doesn't provide any additional information. It's pointless, so why have it?

Re:chess and go aren't np-hard, but they are also

[TheKidWho]

I think the kindle can recieve color information, just not display it! At least the kindle app on the iPad seems to be able to.

You know what would be really cool? If you made a digital interactive version of the book, where players can actually see the games progress and maybe even try to play them in the "book!" Probably not justifiable considering all the programming you would need for something like that and the cost of such work.

Just an idea.

Re:Metaquestion

[AshtangiMan]

If everything is tagged story, then the tag becomes meaningless as a filter. I am under the assumption that someday it is foreseen that there will be a posting that is not a story, and will not be tagged as such (probably will be tagged !story) thus making whoever thought tagging everything as story look like a genius. It's like you have a car dealership, and you are involved in inventory. All you sell is cars, in many shapes, sizes, colors, makes, models, etc. You want to have a database that tracks sales in those categories (where a single vehicle will have values in more than one category). Does it make sense to have a category (let's call it vehicle) that every piece of inventory fits into?

Rip-off

[Anonymous Coward]

Interesting how Flood-It is a complete rip-off of a much earlier game called "7 Colors" - http://en.wikipedia.org/wiki/7_Colors
They're not even the first ones to make for the iPhone: http://ketara.ca/7colors.html

I like how none of it is ever mentioned.

Re:chess and go aren't np-hard, but they are also

[Bob Hearn]

It's on my list...

Re:Metaquestion

[somersault]

No, I think it's just the fact that there are many many more posts submitted as potential stories to the firehose or whatever it's called, and then the ones that are chosen for the frontpage are tagged as stories. Sorry to spoil your hypothesis.

The tag is useful in some cases, but not as a visible entity on the front page. It's about as pointless as tattooing your name on both sides of your face, just in case someone suddenly wonders if you're really you when you turn sideways.

I'm reminded of the Telecrapper 2000

[MyFirstNameIsPaul]

Green; red; yellow; red; blue; green...

Chess and Go *are* NP-hard

[Anonymous Coward]

The generalized versions, that is. They are in fact PSPACE-hard, which is even harder than NP-hard (i.e. a Go solver could also solve any problem in NP). The PSPACE-hard problems are a superset of the NP-hard problems. Any PSPACE-hard problem is also NP-hard.

What you were thinking is that they are not *NP-complete*. NP is a certain class of problems, and "Problem X is NP-hard" means "if you have a polynomial-time subroutine that solves problem X, then you can solve any problem in NP in polynomial time by calling the subroutine". "X is NP-complete" means two things are both true: 1) X is NP-hard, and 2) X itself is a member of NP. The NP-complete problems are the hardest problems that are still inside NP, but you can get even harder problems by going -outside- of NP.

That seems to be the situation with Chess and Go: they are NP-hard (this is proven) but they also appear to be so hard that they are completely outside of NP (this is an unsolved conjecture like P vs NP). The defining characteristic of NP is that if you are shown the answer to an NP problem, you can verify it efficiently. Just show the factors of the big composite number; show the sequence of moves that solves the tetris puzzle, etc. Finding the answer is hard, verifying it once you know it is easy.

With chess, you can't do that. Given a complicated chess position that you want to evaluate, maybe the answer is "white is winning", but you can't easily prove that. You can't say "the winning sequence is: white goes here, black goes there, white goes here, etc" because you have to also account for other possible responses of black. Finding the answer is difficult, but verifying the answer after you know what it is, is also difficult.

Re:Metaquestion

[Red Flayer]

They're not tagged "tagged" when they're tagged. They're not tagged "english" when they're english. What's the point of tagging an article with "story"? It doesn't aid in any search. It doesn't provide any additional information. It's pointless, so why have it?

Look at the firehose and you'll see why the "story" tag makes sense. It's to differentiate the submissions that have graduated.

Re:chess and go aren't np-hard, but they are also

[mrybczyn]

Speaking of Erik Demaine, he has an excellent algorithms course on OCW: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/

Well worth watching on video!

Some of the lectures (such as the first one) are by Leiserson, but Demaine's are a treat.

Re:Are there examples of games that AREN'T NP-hard

[Anonymous Coward]

tic tac toe.

Re:chess and go aren't np-hard, but they are also

[kalirion]

Chess and Go are actually EXPTIME-complete.

So how much time do I need to spend on XP grinding before I can complete them?

Was "Snake" the most popular game of early 2000s?

[Dogtanian]

How many users of Windows are there? Approaching 1 billion homes? That's a bigger audience than even the best-selling console (~150 million PS2s) ever reached.

There's always the question of availability vs. how much people actually play it- I don't play Minesweeper much myself personally, but I'm sure a lot of people still do.

At any rate, it reminds me of something I wondered (in the early 2000s) as to whether Nokia's "Snake" game was the most played computer game in the world. Sure, not everyone had a Nokia, but their 3210 et al were one of the most popular phone lines back then, and those that *did* have them probably played that game casually quite a lot.

Not sure the "computer solvable" part matters ....

[King_TJ]

If anything, perhaps the issue is simply that some of the non NP-hard games have discernible patterns in them that human players pick up on? For example, I can remember one of my friends who loved console sports games, back when we were all in college. Often, though, he'd buy a new one for Sega or what-not, think it was *awesome* for a while, and then suddenly just quit playing it. His reason was inevitably one of having figured out some pattern that he could always score a goal with - making the game no longer a challenge. Same reason I quit playing Starcraft and several other "resource management" type games.... Once I (or in my case, my opponents) all started figuring out the "optimal" ways to use their characters, it became more a game of following exact patterns of "create this unit, then this and this one as quickly as possible, followed by using first unit to make 4 of these.... etc. etc.". If all players knew the optimal strategies, it boiled down to who clicked with the least "lag time" between clicks, or who made a mistake by mis-clicking. BORING!

I'm sure NP-hard games have an inherent "advantage" in that they're proven not to have such "possible to memorize" strategies to win consistently ... but many other factors determine if they're "fun to play" or not, beyond that. (I know quite a few people who really dislike playing chess, even though it's both NP-hard AND considered one of the "all time great games ever invented". For some folks, it probably just seems too dull and dry. I'm sure that's why they sold so many copies of "Battlechess" years ago. It was still chess, but all the 3D animations and creative "kill moves" when you captured pieces added something the original lacked.)

Re:Metaquestion

[AshtangiMan]

I see your point, hadn't considered that. But it still seems useless, surely the firehose submissions are separable from those that make it to the front page via another method, but perhaps not one that can or will be exposed in the same manner as tag filtering. But I was just looking for a way to work in a car analogy.

Re:Are there examples of games that AREN'T NP-hard

[netsavior]

All you have to do is google "cheap game gold"
you will come up with a pretty good list of games in which people will actually pay money to other people in order to have computers play a game for them.

hands up...

[drsquare]

Who has no fucking idea what any of this means, and is only further confused by the wikipedia articles written by nerds who have no communication skills.

Re:hands up...

[Anonymous Coward]

Thanks for your insightful comment.

Re:hands up...

[Phrogman]

Yo

Re:hands up...

[Anonymous Coward]

Dude, this is not string theory or the Poincaré conjecture. It's a graduation-level concept that any programmer worth his salt should know.

Re:hands up...

[phantomfive]

To be fair, there's not really a good way to explain it, even if you have good explanation skills. It's just really hard and complicated.

Earlier proof http://ithat NP-Hardness of floodit.

[FalafelXXX]

Elad Verbin proved that floodit is NP-Hard more than a year ago. See the comments here: http://valis.cs.uiuc.edu/blog/?p=2005".

Artificial Intelligence Implies P = NP?

[Anonymous Coward]

Check out: http://jasonlind.wordpress.com/2010/03/25/p-np-probably/.

Seems to be in line with the conclusions of this thread.

Re:Metaquestion

[somersault]

Yes indeed, they were separate before the tagging system ever existed AFAIK. As for the car analogy.. tagging each story with story is like writing "car" alongside the manufacturer's logo on every car you make ;)

Dunno if NP-completeness is relevant Tetris ...

[Anonymous Coward]

Doubt that Tetris being NP-hard matters for the usual player. Ok, I've only played some clone, where you need to rotate/move your current tile to fit in, while it's falling and you also know the shape of the next tile already and can consider that, too.
Due to the time restriction, I doubt that many people do a lot more deep thinking there.

If you had a lot of time for your decision, you'd consider not only the next tile that you already know, but also the possibilities for the following tiles that come after that and all the ways you could rotate and move them to fit in and on that you'd base your decision about how to fit the current tile.
In practise due to the time contraint, I doubt that anyone thinks more than one or two steps ahead.
That stochastic calculation to do the best bet would just be too complex and rather take hours on paper than seconds, I suppose. lol.

Re:Dunno if NP-completeness is relevant Tetris ...

[Anonymous Coward]

Despite that a computer would be a much better Tetris player than a human, because it can do those calculations quite fast and it's pretty much straight forward in contrast to chess, so even a 'weak' computer would be great at it.

Traveling Salesman

[fotbr]

Insert traveling salesman problem here. Assume salesman uses a car.

Obligatory Shogi Comment

[Princeofcups]

http://en.wikipedia.org/wiki/Tai_Shogi

NP Hard is not AI Complete

[jonadab]

Tetris and Minesweeper may be NP Hard, but that doesn't mean a computer program can't beat a human player. Heck, the reaction time alone would make a computer player WAY better at Tetris than a human. Chess is NP Hard under the rules printed on the inside of the lid of most cheap chess sets ("Hoyle rules" -- there are no limits on stuff like how many turns you can go without a capture or pawn move), but computers still easily thrash all but the best human grandmasters.

The category for games that computers aren't smart enough to play as well as a human is "AI Complete". Stuff like Freeciv and Wesnoth, where strategy is subjective, are MUCH harder to write decent AI for than Tetris and Minesweeper.

Premise is wrong

[Anonymous Coward]

The premise in the OP doesn't make much sense - I don't think a typical instance of Minesweeper is particularly hard computationally, you can generally solve them without having to think more than a few moves ahead. Worst case it is I'm sure, with denser boards particularly. But I don't think the game is enjoyable because it is especially challenging.

Minesweeper is not NP-complete

[Anonymous Coward]

Minesweeper is not NP-complete. The "Minesweeper consistency problem" is. It's not the same, solving the game is P (much easier).

Re:Was "Snake" the most popular game of early 2000

[icebraining]

I know I did when I was 13 or so. What pissed me off was when I got my second phone: although it was much more powerful and had Snake with colors and a much greater resolution, it could only ran a more or less half the speed the other could, taking away most of the challenge.

Minesweeper in 12s using a program

[Anonymous Coward]

Here is a vid of my Minesweeper-Cheater program completing the Minesweeper game in about 12 seconds http://www.youtube.com/watch?v=wCGV8jYc3RE

Re:chess and go aren't np-hard, but they are also

[NitsujTPU]

Okay, but in the sense that any of the games in the original submission are NP-Hard, so are Chess and Go.

"Fun"? "Best games"?

[Databass]

I want to disagree that Tetris and Minesweeper are the immediate candidates for "Best Games". I've played both, but only about 5 hours each. They are ultra-simple. Compare that to games like Civilization, Knights of the Old Republic, or World of Warcraft, all in the hundreds of hours.

I guess the "problem" with Tetris, Minesweeper, even things like Pac*Man is to me they are way too sparse and limited. Inorganic. They just play like a limited algebra problem with a slightly prettier graphical interface. That comes across as mental busywork to me, emphasis _work_, not play. I perfer games with either more story to them, or else complicated, open-ended strategy that can bloom outwards into choices wider than "Hmm, should I put this piece in column 1 or 8? And if so, which of 4 rotations?" Or "Which X,Y coordinate should I click on next using deductive, sudoku-like reasoning?" I prefer "What is my grand strategy for this next entire phase of the game?"