Board 8 > Mario, LoZ, Pokemon, etc. are apparently NP-hard

(+) Yeah! (+)

http://arxiv.org/abs/1203.1895

Pretty cool stuff.

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

explain

--
Which Movie is Better 6? http://www.misterpoll.com/polls/373097

since I have no clue what NP-hard or PASPCE-completenesss are this was worthless to me even after viewing the PDF since they don't explain it

--
http://i49.tinypic.com/anio39.gif

WazzupGenius00 posted...
since I have no clue what NP-hard or PASPCE-completenesss are this was worthless to me even after viewing the PDF since they don't explain it

Same. Which, all things considered, is the sign of a terrible report. Utter rookie mistakes that should never, ever occur.

--
SuperNiceDog had a super nice bracket too.

These gadgets are amazing.

But I don't understand what they were saying in the intro... if they limit the screen/room size, the state space is only polynomial? I don't get that.

--
_foolmo_
'I love you so much' - SineNomine

Uh, it's a CS paper, which means it's perfectly reasonable to assume the reader knows what computational complexity is. It's a research paper, not a text book.

--
_foolmo_
'You are obviously intelligent and insightful' - Sir Chris about me

Heads up some of the stuff I'm saying may not be completely rigorous, I'm a physics student not a CS student

Okay so in computer science you have this concept called computational complexity; we say that something can be solved in polynomial time if we can find some polynomial p(n) (where n is the size of the input (say the number of elements in a list we're sorting, or the number of bits in some number we're factoring, or whatever) such that for all n greater than some constant N, the number of basic operations it takes to solve our problem is less than p(n).

A problem is NP-hard if it can be reduced in polynomial time to a problem in this class of problems called "NP-complete" (in other words NP-hard problems are "at least as hard" as NP-complete problems); if I have what I think is a solution to an NP-complete problem, I can verify that it is a solution in polynomial time, but if, as is commonly believed (but not yet proved!), P does not equal NP, I can't find such a solution in polynomial time.

tldr: NP-hard problems are those that computers most likely can't solve efficiently

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

We prove NP-hardness results for ve of Nintendo's largest video game franchises: Mario,
Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario
Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1{3; all Legend of Zelda
games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing
games. For Mario and Donkey Kong, we show NP-completeness.

Assuming "generic" games and provably optimal solutions, yeah, that's kinda obvious? It comes down to "can you express a boolean formula in game terms?" I mean, it's not TOTALLY obvious it's possible, but your intuition would say "yeah, almost certainly".

In addition, we observe that several games in the Zelda series are PSPACE-complete.

... What? I gotta see this.

--
assert(!hotterThan(foo, "Hot Nymphomaniacal Lesbian Mind-Controlling Dominatrix Fairy Doctors with glasses"))

Research papers still give the meaning of an abbreviated term before introducing it as a matter of course. Saying it's a CS paper does not excuse it from completely ignoring basic tenants that research papers in every other field follow. If I were to read a physics research paper the author clearly expects me to have a basic understanding of physics, but they still tell me what their odd jumbles of letters stand for up front so that I can at least look them up if I don't know. Neither of the terms mentioned by Wazzup can be found easily on the internet because there is no indication whatsoever what they stand for.

Oh, also, my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant, so even if your logic was valid, and it is not, the terms aren't even clear to people who have an advanced understanding of the field in general. You would literally need to present it to someone who already had very advance understanding of the very specific topic of computational complexity for it to have any meaning whatsoever which, I will again assert, makes it a terrible research paper (though perhaps very good research, I cannot tell) filled with mistakes that even a rookie in any other field would avoid like the plague.

--
SuperNiceDog had a super nice bracket too.

From: ChichiriMuyo | #009
my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant

That.... is really damn sad

--
_foolmo_
'Illegal activities is a slight misnomer, most of it is not related to material that is actually illegal.' - nintendogrl1

ChichiriMuyo posted...
Research papers still give the meaning of an abbreviated term before introducing it as a matter of course. Saying it's a CS paper does not excuse it from completely ignoring basic tenants that research papers in every other field follow. If I were to read a physics research paper the author clearly expects me to have a basic understanding of physics, but they still tell me what their odd jumbles of letters stand for up front so that I can at least look them up if I don't know. Neither of the terms mentioned by Wazzup can be found easily on the internet because there is no indication whatsoever what they stand for.

This is way more readable than the physics papers I've had to read for my research projects. Also, you can find the definitions of NP-hard and PSPACE-complete via the first result in a google search for either term. You may not UNDERSTAND the definitions, but it would be unreasonable for every research paper to double as a review paper.

Oh, also, my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant, so even if your logic was valid, and it is not, the terms aren't even clear to people who have an advanced understanding of the field in general. You would literally need to present it to someone who already had very advance understanding of the very specific topic of computational complexity for it to have any meaning whatsoever which, I will again assert, makes it a terrible research paper (though perhaps very good research, I cannot tell) filled with mistakes that even a rookie in any other field would avoid like the plague.

I don't know about PSPACE-completeness, but I find it hard to believe a CS major hasn't at least heard the term NP-hard.

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

From: ChichiriMuyo | #009
Oh, also, my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant

xfd

That's like 3rd year CS stuff, not even that advanced

--
No problem!
This is a cute and pop genocide of love!

Not a CS major, but I've heard of both those terms, though I don't admittedly understand them very well.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

Phase posted...
We prove NP-hardness results for ve of Nintendo's largest video game franchises: Mario,
Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario
Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1{3; all Legend of Zelda
games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing
games. For Mario and Donkey Kong, we show NP-completeness.

Assuming "generic" games and provably optimal solutions, yeah, that's kinda obvious? It comes down to "can you express a boolean formula in game terms?" I mean, it's not TOTALLY obvious it's possible, but your intuition would say "yeah, almost certainly".

In addition, we observe that several games in the Zelda series are PSPACE-complete.

... What? I gotta see this.

Looking more into the terms, I'm not shocked they would make such a statement. While at first glance they would all seem more complex than a "simple" game like go, let alone less complex games like tic-tac-toe, yet they have become such stream-lined, hand-holding games that it's only slightly harder to die in Kirby's Epic Yarn than in a modern 3D Zelda while the 2D ones are in a dramatically simpler world despite their relative unwillingness to force you in the right direction every time, all the time.

--
SuperNiceDog had a super nice bracket too.

The modified crossover gadget for Mario games fails, at least under SMB3 mechanics (haven't played enough SMW to say anything there). Though you could trivially make a working gadget to replace it using doors to warp across another path.

--
GotD Contest Champ

I assume you mean a complex game like go and a simple game like tic-tac-toe right?

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

Lopen posted...
From: ChichiriMuyo | #009
Oh, also, my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant
xfd

That's like 3rd year CS stuff, not even that advanced

I am not a CS guy, but I'm going to guess that would have a lot to do with what aspect you are focusing your studies on. At least that is how it goes with other subjects. For example, I know in MBA programs there isn't one pre-select set of one-size-fits-all courses but instead several focuses one can choose from. So unless ever CS student ever had to learn these things, my roommate did not. Though it's possible he forgot (he's done mostly database stuff in the field, except his current job where he works on apps and websites), I'd imagine if it was that basic he wouldn't have said "it has no real meaning to me" when I said "non-deterministic polynomial-time hard" to clear it up.

So again, as is proper ettiquite in EVERY field the author should have made it clear with the first usage what each term stands for - because that's how EVERYBODY else in their right mind does these things - and failing to do so is the mark of a poorly written paper. Again, the reasearch may be very good, I'm still making heads or tails of it.

--
SuperNiceDog had a super nice bracket too.

red sox 777 posted...
I assume you mean a complex game like go and a simple game like tic-tac-toe right?

"Simple" does indeed translate to complex (thanks quotation marks!) and less complex would imply simple, yes.

--
SuperNiceDog had a super nice bracket too.

Hmm, Wikipedia says Go under the Japanese ko rule is EXPTIME-Complete, but it is yet to be shown whether it is under the Chinese rules. I'm guessing that's because of the superko rule, which eliminates the possibility of triple ko.

Some people think superko is elegant, but I'm not sure why you would want to a ruleset that gets rid of triple ko- it's the rarest of rare things in Go, that almost never arises in a real game. If one in 10,000 games ends in triple ko resulting in a result of "no result," that seems like a good thing to me.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

ChichiriMuyo posted...
Oh, also, my roommate has a BA in CS and he didn't recognize either term and had no idea what they meant

Ahahahahaha wow, either your roommate is an idiot, or he or she went to a terrible university.

ChichiriMuyo posted...
You would literally need to present it to someone who already had very advance understanding of the very specific topic of computational complexity for it to have any meaning whatsoever

Seriously, dude, I've known first years who knew about "P = NP???" It's like...not QUITE as famous as E = mc^2, but it's still literally the most famous equation in computer science.

PSPACE, I'll grant you, I didn't hear about in first year.

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

From: ChichiriMuyo | #017
I am not a CS guy, but I'm going to guess that would have a lot to do with what aspect you are focusing your studies on.

That's the thing, though. This is one of the most fundamental concepts in CS. It's like capital in economics or something. Is there a focus of economics where you don't need to know what capital is?

I can understand not knowing what it is if you have self-taught yourself how to program and all you do is write programs and stuff, since you probably wouldn't learn the theory behind CS, but this guy has a 4-year education in CS.

--
_foolmo_
'You are obviously intelligent and insightful' - Sir Chris about me

Oh wait, I got it

Your roommate went to community college, didn't he?

--
_foolmo_
'he says listen to my story this maybe are last chance' - ertyu quoting Tidus

After reading: Oh right, ice blocks. Duh.

Yeah, pretty obvious stuff. The Mario stuff is a bit interesting (the only problem I could come up with going in would be that it'd be hard to hook up stuff in Mario), but the rest is sort of obvious.

At least, obvious from the perspective of someone who considered doing their master's work in this area. <_<

That.... is really damn sad

This. So damn hard. Not knowing what NP-hard is and having a degree in CS is unacceptable. Not knowing any other complexity classes is okay, but you need to know P and NP. Not knowing P and NP is the same as not knowing what kind of problems you cannot solve in a reasonable amount of time. Like, you might not UNDERSTAND why NP-hard/complete problems are, well, hard, but you need to know the class of problems exists and can name a few prototypical examples. Because there's a huge quagmire of problems out in the real world that contain a canonical NP-hard one as a subproblem and you simply can't promise that those problems can be solved in a reasonable amount of time without some sort of constraints.

Knowing things like this is the difference between going to technical school and learning "programming" and getting a CS degree.

... Your friend knows what the halting problem is at least, RIGHT?

Looking more into the terms, I'm not shocked they would make such a statement. While at first glance they would all seem more complex than a "simple" game like go, let alone less complex games like tic-tac-toe, yet they have become such stream-lined, hand-holding games that it's only slightly harder to die in Kirby's Epic Yarn than in a modern 3D Zelda while the 2D ones are in a dramatically simpler world despite their relative unwillingness to force you in the right direction every time, all the time.

I think you misunderstood me. It's only interesting because there's not a bunch of "nice" problems to reduce from in PSPACE. (SAT and 3-SAT are the obvious NP ones, but there's a HUGE wealth of others, graph coloring, Hamiltonian cycle, etc. etc.)

But it turns out it just includes a component which is PSPACE-complete already, which is not really interesting.

--
assert(!hotterThan(foo, "Hot Nymphomaniacal Lesbian Mind-Controlling Dominatrix Fairy Doctors with glasses"))

At what point in time have community colleges awarded bachelors degrees? Now, I'm not going to say the University of Arizona is the most prestigious of schools (unless you're studying astronomy, then it very well is, thank you very much), but I'm pretty sure it's a fairly decent school. Also, based on how much he makes and the salaries of the classmates he keeps in touch with, I'd have to conclude that employers think the same.

Again, he knew what the term meant when I was more explicit, it just wasn't something that mattered to him. If it is that basic, and I'll take MC's word for it that it is, then my hyperbole was unwarranted. The fact still remains, proper research paper etiquette demands that acronyms and abbreviations be written out fully in their first use and not doing so, even when the intended audience is expected to know the term, is quite simply poor writing and a terrible mistake that should never be made.

The fact of the matter is, as has been shown tonight, people who are not of your intended audience can and often will get a hold of your research papers and making them as intuitive as possible should be a basic, common courtesy.

--
SuperNiceDog had a super nice bracket too.

I think this is a case where the acronyms are more recognizable than the full written out form.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

Not if you don't know either to begin with! And while some of them were actually easy to look up on google, some were not so intuitive at all, and I came across them more by their relation to the other terms.

But again, that's not an excuse. The UN may actually be more recognizable than The United Nations, it still didn't excuse the use of The UN without first identifying it as the united nations in any political science research paper I wrote. This is a very common practice across most academic fields, even when it is expected the audience will be as familiar with the abbreviation or more so than its elongated form and even if they are expected to not think of any other similar terms from other fields because they are outside their area of study.

--
SuperNiceDog had a super nice bracket too.

can we stop arguing about how good or not good ChuchiriMayo's roommate is at computer science and could somebody just translate TC's link into ****ing english

--
"Sorry pop music lyrics don't use ancient Hebrew religious imagery as an illusion to the class struggle in French Indochina as you grind on a girl."

firebotslash posted...
can we stop arguing about how good or not good ChuchiriMayo's roommate is at computer science and could somebody just translate TC's link into ****ing english

Computers would be very bad at playing games you or I probably think of as being rather easy

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

ChichiriMuyo posted...
So again, as is proper ettiquite in EVERY field the author should have made it clear with the first usage what each term stands for - because that's how EVERYBODY else in their right mind does these things - and failing to do so is the mark of a poorly written paper. Again, the reasearch may be very good, I'm still making heads or tails of it.

But more to the point, even if you were right about NP not being one of the most famous things in Computer Science, you're STILL COMPLETELY WRONG.

Bear in mind, I have no degrees in CS, and I understood the above abstract just fine. Which is highly surprising, because most abstracts aren't like that to me.

A quick google search:

http://www.nature.com/nphys/journal/v6/n2/abs/nphys1504.html

Bear in mind, I basically have a dual bachelor's degree in math and physics, and my Graduate thesis was in algebraic topology. I really couldn't tell you what's going on in that abstract.

http://www.astro.sunysb.edu/lattimer/PHY599/abstracts/abstract_Tien.pdf

This one is a little better, but I'd certainly need to google multiple terms if I wanted any hope of understanding everything in this abstract.

http://www.nature.com/nature/journal/v436/n7053/abs/nature03932.html

This is moving into physical chemistry now, so I'm a little more out of my depth; actually able to pick up the gist of it, but certainly missing a lot of major terms.

http://onlinelibrary.wiley.com/doi/10.1348/096317905X26183/abstract

Actually, I completely understood this abstract. But I wouldn't have if I hadn't just gone to a talk on the big five.

http://www.medscape.com/viewarticle/567897

Yeah, this one isn't too bad. Definitely a couple terms there I don't know, granted.

http://www.computer.org/csdl/trans/td/2011/12/ttd2011121978-abs.html

Wasn't even searching for a CS one. Oh hey, they mention polynomial time!

http://math.unc.edu/Faculty/assani/ErgWork07/DMauldin07.pdf

There's one or two terms there I don't understand for sure, but most of it is pretty clear.

http://www.cs.man.ac.uk/~pt/ASD/dedras.pdf

Ooooh, that paper looks sexy, I kinda want to read it. Though again, one or two undefined terms there I don't recognize. "Overt" jumps to mind, here. Also, it references "Moore" without saying who he or she is (presumably someone else who had a different computational construction?)




So...all things considered, I find the abstract linked in the topic title to be ridiculously simple and easy to read. I don't know what magical Christmasland you live in where abstracts are supposed to be easier than that--that's like...ridiculously easy and straightforward by abstract standards.

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

From: ChichiriMuyo | #017
I am not a CS guy, but I'm going to guess that would have a lot to do with what aspect you are focusing your studies on.

n

This is general knowledge pre focus stuff. No excuse to not know it, basically.

--
No problem!
This is a cute and pop genocide of love!

From: firebotslash | #027
can we stop arguing about how good or not good ChuchiriMayo's roommate is at computer science and could somebody just translate TC's link into ****ing english

Of course not. This is Board 8!

--
Ace Detective in Sir Chris' Police
http://img89.imageshack.us/img89/5763/cliftoncartoon.jpg

LordoftheMorons posted...
firebotslash posted...
can we stop arguing about how good or not good ChuchiriMayo's roommate is at computer science and could somebody just translate TC's link into ****ing english

Computers would be very bad at playing games you or I probably think of as being rather easy

So is it trying to say like, there's so many different possibilities for moves that Mario/Zelda/etc could make that a computer would have extreme difficulty determining which moves are necessary to complete the game?

(as opposed to a game like Chess or something, where computers have essentially mastered the game)

--
"Sorry pop music lyrics don't use ancient Hebrew religious imagery as an illusion to the class struggle in French Indochina as you grind on a girl."

There might be a difference of standards here between hard math/science fields and other fields.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

So is it trying to say like, there's so many different possibilities for moves that Mario/Zelda/etc could make that a computer would have extreme difficulty determining which moves are necessary to complete the game?

(as opposed to a game like Chess or something, where computers have essentially mastered the game)

Fairly sure that according to this paper, Mario/Zelda are not shown to be harder for computers than Chess. Just harder than one might expect.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

firebotslash posted...
LordoftheMorons posted...
firebotslash posted...
can we stop arguing about how good or not good ChuchiriMayo's roommate is at computer science and could somebody just translate TC's link into ****ing english

Computers would be very bad at playing games you or I probably think of as being rather easy

So is it trying to say like, there's so many different possibilities for moves that Mario/Zelda/etc could make that a computer would have extreme difficulty determining which moves are necessary to complete the game?

(as opposed to a game like Chess or something, where computers have essentially mastered the game)

Yeah more or less (though chess is actually pretty hard, and I would assume that for a board of arbitrary size it would also be NP-hard)

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

Computers would be very bad at playing games you or I probably think of as being rather easy

No. You'd consider the "games" they're "playing" pretty stupid and hard too. (because it's essentially solving whether a boolean equation is satisfiable in an extremely obtuse way)

It's more accurately... You can make games based off the engines of these games that are hard for computers and people to solve.

Yes, this is basically completely pointless outside of novelty, why'd you ask?

--
assert(!hotterThan(foo, "Hot Nymphomaniacal Lesbian Mind-Controlling Dominatrix Fairy Doctors with glasses"))

Phase posted...
Computers would be very bad at playing games you or I probably think of as being rather easy

No. You'd consider the "games" they're "playing" pretty stupid and hard too. (because it's essentially solving whether a boolean equation is satisfiable in an extremely obtuse way)

It's more accurately... You can make games based off the engines of these games that are hard for computers and people to solve.

Yes, this is basically completely pointless outside of novelty, why'd you ask?

But they're doing that by reducing problems you or I can solve using human pattern recognition (playing a video game) to 3-SAT or whatever, right? I don't mean to say that we could easily solve the reduced games.

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

firebotslash posted...
So is it trying to say like, there's so many different possibilities for moves that Mario/Zelda/etc could make that a computer would have extreme difficulty determining which moves are necessary to complete the game?

(as opposed to a game like Chess or something, where computers have essentially mastered the game)

Not quite.

Chess is actually a fairly hard problem, in that let's say you went up to a 9x9 board and added more pieces (two on each side). Now the amount of computation time a computer needs would go waaaaaaaay up, because the number of possible optimal moves just went waaaaaay up.

NP is measuring a more general "how much more computation would we need to do if you made this game slightly longer?"


Which...isn't actually very useful in the case of games. It's useful when we're talking about how much more computation you need to handle a database with 1000 people in it compared to a database with 2000 people in it, though.

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

Now hold up there, playa! We're going to settle this with a match. foolmo and LordoftheMorons... versus ChuchiriMayo and his roommate! And that match starts right now!

--
http://img165.imageshack.us/img165/8263/theodorelongkristalfc9.gif

so it's saying that the harder you make Mario, the level of difficulty for a computer to play Mario increases exponentially?

also on a side note holy **** i remember your username from years ago just cause i thought your sig (which is still the same) was the funniest thing ever when i was like 10 (i'm 18 now)

--
"Sorry pop music lyrics don't use ancient Hebrew religious imagery as an illusion to the class struggle in French Indochina as you grind on a girl."

How about a Go match? Computers still can't beat good human players at it, though they're improving pretty fast. They play such strange moves too (from a human point of view).

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

firebotslash posted...
so it's saying that the harder you make Mario, the level of difficulty for a computer to play Mario increases exponentially?

Well....let's go into specifically what P and NP are.

P means we can find a solution pretty quickly with a computer program.

NP means we can't find a solution all that quickly, BUT we can check whether a solution is true pretty quickly.

red sox 777 posted...
How about a Go match? Computers still can't beat good human players at it, though they're improving pretty fast. They play such strange moves too (from a human point of view).

Go is hard for computers primarily because the board is huuuuuuge. Do Go on an 8x8 board and I suspect computers would just crush humans.

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

Well generally for a game like Go or Chess you're not going to compute every possible remaining game state (that would take way too long), but you can use a number of different strategies to make good moves. Like, you could look a few moves into the future and choose the move that results in the best game state for you assuming your opponent plays optimally (minimax), or do a genetic algorithm where you "train" a computer with various sample games (this is what they did with IBM's Watson to train a computer to play Jeopardy).

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

tag

--
Boko United - MenjiTMFan267
Guru Taken Miraculously by SuperNiceDog

LordoftheMorons posted...
Well generally for a game like Go or Chess you're not going to compute every possible remaining game state (that would take way too long), but you can use a number of different strategies to make good moves. Like, you could look a few moves into the future and choose the move that results in the best game state for you assuming your opponent plays optimally (minimax), or do a genetic algorithm where you "train" a computer with various sample games (this is what they did with IBM's Watson to train a computer to play Jeopardy).

Right, but this is different from a question of NP-completeness. When you take these shortcuts, you're not "solving" these games. You're getting a good approximation.

Physics simulations are NP complete if you do things properly, and yet a whole lot of videogames have physics simulations running at 60 FPS, because they're willing to make some approximations.

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

firebotslash posted...
also on a side note holy **** i remember your username from years ago just cause i thought your sig (which is still the same) was the funniest thing ever when i was like 10 (i'm 18 now)

Yep, I decided to go on a long streak of not changing my sig; guess it's been the same for about 10 years now?

--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision

Well yeah that's why I said "good moves" rather than "the optimal moves" >_>

But afaik we still can't "solve" a standard 8x8 chess match in an amount of time short enough to be of use to anyone, let alone Go.

--
No I'm not a damn furry. Looney Tunes are different. - Guiga
I wanted Sonic/Shadow romance at that time, not sex. - MWE

Go is hard for computers primarily because the board is huuuuuuge. Do Go on an 8x8 board and I suspect computers would just crush humans.

Go is pretty much never played on 8x8, but it is sometimes played on 9x9 by beginners, people looking for a fast game, and people who want to just have one tactical battle only. Computers are indeed very good at 9x9 already, as in professional level (= grandmaster level in Chess).

Well generally for a game like Go or Chess you're not going to compute every possible remaining game state (that would take way too long), but you can use a number of different strategies to make good moves. Like, you could look a few moves into the future and choose the move that results in the best game state for you assuming your opponent plays optimally (minimax), or do a genetic algorithm where you "train" a computer with various sample games (this is what they did with IBM's Watson to train a computer to play Jeopardy).

The newer Go programs use a "monte carlo tree search" which involves taking candidate moves and playing out the rest of the game randomly (with some pruning I'm assuming) many, many, times. The program then chooses the move that maximizes the probability of winning. This seems to work a lot better than brute force minimax searching. It's probably also what leads to a lot of the really strange-looking moves (for example, if the computer thinks it is ahead, it will play an uber safe move that results in it winning by 0.5 points rather than something that a player of its level could easily read out as leading to a 20 point victory).

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.

MC, I've looked at some of those abstracts, and I fear you've missed my point entirely. For example, the first one you posted. I'm not going to pretend I understand it, but I'm also not arguing all papers should be written so that I can understand them. I'm arguing that I should be able to know what the terms are and have the ability to find them on the internet with relative ease.

Spelling out every term, as that abstract does, makes it very easy to search for those things online. Having to figure out which link is valid for which acronym based on a context you don't understand is harder to do than searching for the full and proper term. So, while I don't get a lot out of searching for optical vortex knots (well, I do get the link to that abstract...) it's still a lot better than searching for OVK would be even if it were commonly used as an acronym in physics. The reason for this is other fields can, and possibly do, use it for other meanings.

So again, the point isn't that I should be able to understand the terms when I don't have a background in the field, it's that terms should always be clarified at least once up front so that the thing is readable by anyone. I should be able to look at a research paper and, without knowing anything about the field, be able to do quick and simple research that allows me to at least follow along and get a general idea of what they are doing.

For example, the term 3SAT is used in the paper. I did not know what that meant, and without doing any research on the other terms used it wouldn't necessarily occur to me which of the many options google came up for the term was actually relevant. Yes, the word boolean in the same sentence tipped me off, but searching before hitting anything past that colon leaves it fairly open since a search on "3sat" doesn't come up with anything that'd immediately tie it to the paper.

Do take note of snippets from the examples you yourself provided, such as the following:

"Here we report a generic family of liquid crystals that demonstrate an unusually broad body-centred cubic phase (BP I*) from 60 °C down to 16 °C."

They assume I don't know what the hell they are talking about when they use the term BP I* (because I don't), so they throw it into parenthesis in its first usage.

And again, you provide another result the next link down that confirms what I'm saying:

"The current study reports a meta-analysis of the relationship between accident involvement and the Big Five personality dimensions (extraversion, neuroticism, conscientiousness, agreeableness, and openness)"

They didn't assume the reader knew what the Big Five personality dimensions were, though they certainly targeted an audience that would care about those things (why read it if you didn't). They still spelled things out for the audience by throwing additional information in the parentesis.

So really, what you've done here is laid out my point exactly and forgot to address it whatsoever. You've given examples that do exactly what I'm saying this paper did not. Thank you, I guess, for proving my point.

--
SuperNiceDog had a super nice bracket too.

Also, the choice of 19x19 for Go is not arbitrary from a game design point of view, though it's difficult to say how it got there historically. There are good reasons the board should be 19x19 rather than 17x17 or 21x21. And that is that with 19x19, the corner/sides of the board balance the center just about perfectly. With anything smaller, the center is worth less than the edges, and with anything more, the center is bigger (and what happens on one side of the board also has less impact on the other side). The balance results in fun, strategically interesting games in which players have a lot of viable whole board strategies.

--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick
your 7 time champion, Link.