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?
ChichiriMuyo posted... "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.
I'm not actually sure if the parentheses there are representing something that previously happened in text.
*does some searching*
No, no actually, I'm pretty sure BP I represents a state (kind of like liquid and solid) whereas body-centered cubic generally gets acronymatized to BCC and represents the crystalline structure, is not associated with BP I in particular (I found another paper where it was associated with BP II, for instance).
So uhh...actually, this "example" that you thought you found is actually a counterexample, I'm pretty sure.
ChichiriMuyo posted... 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.
...Oh yes...EXCEPT they just provided you with five terms that they don't explain (and which mean something quite technical in the context of the Big Five, and not precisely what you'd assume based on the English use of the word). Specifically, all five of these categories represent SIX subcategories, which were NOT broken down.
Turtles. Turtles all the way down.
--
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
That's it. Just link that wiki article with the paper and all your problems go away. Now, can't we expect an intelligent adult to just look up unfamiliar terms on their own? Is that so hard (LOL SEE WHAT I DID)?
-- _foolmo_ 'Illegal activities is a slight misnomer, most of it is not related to material that is actually illegal.' - nintendogrl1
red sox 777 posted... 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.
Amazingly it only took between 200 and 400 years for people to figure this out. I will never be that good at go...
Also, University of Arizona is a great school... my friend is going there for aerospace engineering or whatever you do to make ballistic missiles. I can only conclude that your friend is dumb.
"So uhh...actually, this "example" that you thought you found is actually a counterexample, I'm pretty sure."
Ya got me there.
"...Oh yes...EXCEPT they just provided you with five terms that they don't explain (and which mean something quite technical in the context of the Big Five, and not precisely what you'd assume based on the English use of the word). Specifically, all five of these categories represent SIX subcategories, which were NOT broken down"
Yes, but the introduction of the term Big Five indicates what to look up. Not the individual items listed in the parenthesis, which I assume will be used in the broad text as if the reader knows what they are, but "Big Five personality dimensions" which is a term that will probably not be used after it is introduced the first time. And I hardly need to be told it covers six aspects once I know that term, but if they just threw all of those technical aspects at me without indicating that their is a broader topic to look into. Especially, if as you say, there are six subcatagories covered by the big five. How counter-intuitive would that be?
@Foolmo - it doesn't address even half the terms used in the paper. And again, there are terms in there that aren't as easy to find as NP-hard.
LordoftheMorons posted... 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.
Is 8x8 Go actually harder than 8x8 Chess, though?
Chess can loop game states much more than Go can. The entire set of possible moves in Go for an 8x8 board is like...about (64!) assuming people don't place a piece in the same square more than once.
Hmm...yeah, ok, so that's roughly 64^64 = 2^(6*64) = 2^(384). Haha, ok, yeah, no, you're not searching the entire decision tree by brute force.
--
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
ChichiriMuyo posted... Yes, but the introduction of the term Big Five indicates what to look up. Not the individual items listed in the parenthesis, which I assume will be used in the broad text as if the reader knows what they are, but "Big Five personality dimensions" which is a term that will probably not be used after it is introduced the first time. And I hardly need to be told it covers six aspects once I know that term, but if they just threw all of those technical aspects at me without indicating that their is a broader topic to look into. Especially, if as you say, there are six subcatagories covered by the big five. How counter-intuitive would that be?
...This is a bit of a tangent, but...I've clearly done a bad job of explaining the big five.
The big five has five subcategories (the ones listed in parentheses) Each of these, has six subcategories (so 30-sub-subcategories in total)
--
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
How can you conclude that? AS I've mentioned twice now, when I went back and talked to him more explicitly (after doing more research myself) he knew what I was talking about and indicated it just didn't matter in terms of what he does. I threw a few terms at him once, he blanked, I came back and talked to him with some modicum of knowledge and he knew what I was talking about.
Also, those ballistic missile guys, a lot of them get jobs here with Raytheon. They offered my roommate a job and he passed. He can't be that dumb if they were willing to hire him on to program missile guidance systems or some equally high-tech thing.
I guess the real problem here is that, by not being explicit, I as a layman could not begin to reiterate what I had read and had to do more research. More of a fail on my part, still calling a fail on their part for not being explicit as most other formal research papers would be.
LordoftheMorons posted... 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.
I would very much hope you cannot solve the problems of suffiient size to give computers pause by pattern recognition. Because what a computer can figure out in a few minutes would probably be the size of 4-5 levels at least? Like, I remember implementing tetravex as a SAT problem and a hundred literals and (some very long) clauses took like 5-10 minutes (and I considered that terrible because I had a python script that could so similar sized problems in seconds). I'd suspect it'd take a few hundred clauses to do what I did in 3-SAT, so what a computer can do in 5 minutes would span the patterns shown in the paper repeated a few hundred times.
No, what they've said is:
SMB is at least as hard as 3-SAT, because we can implement 3-SAT in SMB. (ergo, if you could "solve" SMB in a reasonable amount of time, you could solve 3-SAT)
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.
3SAT should probably be expanded out. However, I would like to note that:
a) Google is really bad with caps (unfortunately, this is not well-known), and it's really clear caps matters. b) Wikipedia is better with caps because it has a human element (and for the same reason is much better if you know you are searching for a decently known topic), and if you type 3-SAT or 3SAT into there, you get taken to the 3-satifiability problem immediately.
metroid composite posted... ChichiriMuyo posted... Yes, but the introduction of the term Big Five indicates what to look up. Not the individual items listed in the parenthesis, which I assume will be used in the broad text as if the reader knows what they are, but "Big Five personality dimensions" which is a term that will probably not be used after it is introduced the first time. And I hardly need to be told it covers six aspects once I know that term, but if they just threw all of those technical aspects at me without indicating that their is a broader topic to look into. Especially, if as you say, there are six subcatagories covered by the big five. How counter-intuitive would that be?
...This is a bit of a tangent, but...I've clearly done a bad job of explaining the big five.
The big five has five subcategories (the ones listed in parentheses) Each of these, has six subcategories (so 30-sub-subcategories in total)
And regardless of that fact, being introduced to the term big five tells me where to look. Being introduced to the term 3SAT does not. Big five, should I look it up (I assume), gives me a broad overview and it will link to many relevant terms. 3SAT doesn't mean ****, basically, without familiarity with the term. AS I mentioned before, reading a little further makes it apparent that it's a term related to boolean searches. Great. Knowing that I could have much more information at my disposal, and much more clear direction as to what is related to the topic, if I knew to search for "3 satisfiability" after the fact is irritating.
Also, I may incriminate myself as a total moron here, but I was so lost that it didn't occur to me that boolean formulas would be related to the topic until it was specifically introduced... after the term 3SAT. So yeah, I've gone and found lots of links to help me out, but the author didn't make that easy or intuitive at all. Which, again, is a terrible way to write a research paper.
He explains what 3-SAT is in the paper though (he probably could have defined more explicitly Push and PushPush, but you can pretty much figure out the rules, and there's a paper referenced if clarification is needed). I still see no reason to define NP-hard in a CS paper.
-- No I'm not a damn furry. Looney Tunes are different. - Guiga I wanted Sonic/Shadow romance at that time, not sex. - MWE
"a) Google is really bad with caps (unfortunately, this is not well-known), and it's really clear caps matters. b) Wikipedia is better with caps because it has a human element (and for the same reason is much better if you know you are searching for a decently known topic), and if you type 3-SAT or 3SAT into there, you get taken to the 3-satifiability problem immediately."
I will contend for all time and eternity that Google's slogan only applies to everyone but them. Evil *******s.
I don't think you need to be that good at Go to recognize that. At least at the 1-dan level, I can say that looking at a 17x17 board, I can feel that the strategy would be quite different and the center influence would be worth much much less. I wouldn't want to play on it- it feels cramped, like a whole dimension of the game has been sharply reduced.* I don't feel the same way about 21x21 and would be interested in playing on it, but perhaps that's natural because 21x21 must be more complex than 19x19, even if it's not as balanced between center and edges. I might also just be somewhat biased due to liking to use central influence.
*It's true that skill (among humans) on 17x17 would probably be very similar to skill on 19x19, because 90%+ of skill in Go is tactical fighting skill. Or rather, it's a limiting factor. If you have the greatest strategic play in the world but the fighting skill of a 5k, your rank will be something like 3k. On the other hand, you could know nothing about opening theory and it probably wouldn't hurt you more than 1 or 2 ranks- because your opening or strategic play would have to be amazingly bad to be worse than just letting your opponent play 2 handicap stones. But the strategy is probably where the majority of the fun and creativity comes from, so it's painful to lose it.
Is 8x8 Go actually harder than 8x8 Chess, though?
Chess can loop game states much more than Go can. The entire set of possible moves in Go for an 8x8 board is like...about (64!) assuming people don't place a piece in the same square more than once.
Hmm...yeah, ok, so that's roughly 64^64 = 2^(6*64) = 2^(384). Haha, ok, yeah, no, you're not searching the entire decision tree by brute force.
I believe 7x7 Go has been solved. I don't know if 8x8 Go would be easier to solve than Chess, but computers could probably crush humans on it at least. 9x9 Go is already for humans much less "hard" a game than Chess, but that could be a consequence of how humans think.
--
Congratulations to SuperNiceDog, Guru Winner, who was smart enough to pick your 7 time champion, Link.
LordoftheMorons posted... He explains what 3-SAT is in the paper though (he probably could have defined more explicitly Push and PushPush, but you can pretty much figure out the rules, and there's a paper referenced if clarification is needed). I still see no reason to define NP-hard in a CS paper.
Because you should never assume that the reader has any expertise in the field. I see no reason to ever write out "The United Nations" when far more people know the term "The UN" than the term "NP-Hard," yet I do it out of common courtesy to the reader even if I assume they are very likely to use the acronym far more often than the full name. I hear "The UN" far more often than "The United Nations" in informal conversations regardless of the speaker or the listener's knowledge of politics and virtually all academic publications will use the full name at least once for clarification. Honestly, I see no reason why any field should be exempt from that basic rule, let alone one where the terminology is far from wide-spread and common.
This topic 1) reminds me why I never wanted to major in computer science, and 2) reminds me why I drastically prefer games of personal interaction like Diplomacy to games like chess.
--
SubDeity wants to vote for Calvin Coolidge. [Evil Republican] Play Der Langrisser.
Yes, but the chances of me reaching 1-Dan level of play is slim as it is, and it most certainly wouldn't have happened when the game was that new. If, for example, I had only ever seen a 17x17 board (as early players had), it would take very extensive playing (more than I've done as of yet) to even consider the possibility that the 19x19 board was better for the nuanced reasons you have mentioned. I mean, really, I've read it and I know what you're saying, but as a Go player (a very bad go player) it's harder for me to translate that into actual game experience.
ChichiriMuyo posted... Because you should never assume that the reader has any expertise in the field. I see no reason to ever write out "The United Nations" when far more people know the term "The UN" than the term "NP-Hard," yet I do it out of common courtesy to the reader even if I assume they are very likely to use the acronym far more often than the full name. I hear "The UN" far more often than "The United Nations" in informal conversations regardless of the speaker or the listener's knowledge of politics and virtually all academic publications will use the full name at least once for clarification. Honestly, I see no reason why any field should be exempt from that basic rule, let alone one where the terminology is far from wide-spread and common.
That's not really the rule in science papers though. If this paper was not about video games, the chances of a layperson reading it would be very low. It's certainly not standard in physics papers to explain stuff covered in the normal undergraduate curriculum; in fact, you leave out large pieces of your derivations (as the professor I was working for last summer said, you only leave enough information that the interested grad student could rederive the results) because journal space it at a premium. This paper is in fact very easy to read compared to the average paper.
-- No I'm not a damn furry. Looney Tunes are different. - Guiga I wanted Sonic/Shadow romance at that time, not sex. - MWE
I can totally see why that would apply for mathematical formulas. Even if I was interested, I would have to invest a great deal of time studying math to recreate the process. As a lay person I have a much better understanding of the results and the implications, and I can ignore the mathematics entirely. So that really shouldn't take much of the space. For example, I do not need Einstein to walk me through the process of how he figured out E = MC^2. I do need to know what E, M, and C stand for though. These days I know I can just search "mathematical constant E" and... oh dear god that's not right...
So, yeah, even though a paper can be written explicitly for a select group, taking a small amount of space to explain terminology goes a long way in making it readable for the people who do read it even if it's not meant for them. I mean, it's not like I'm going to have to take a class to understand the paper, let alone get a degree in it, but 15-20 words devoted to clarifying terms would have helped and I highly doubt that'd be the threshold between printable or not due to length concerns.
Note: I've obviously never read any of Einstein's papers, so even if he didn't outline these things because his contemporaries would have known don't bother pointing it out.
I see no reason to ever write out "The United Nations" when far more people know the term "The UN" than the term "NP-Hard," yet I do it out of common courtesy to the reader even if I assume they are very likely to use the acronym far more often than the full name.
The difference between the two is I have seen the UN written as the United Nations. I have never seen NP-hard written as non-deterministic polynomial-time hard outside of wikipedia. And it is telling that when you google it with quotations, it isn't written:
non-deterministic polynomial-time hard (NP-hard)
Which would be standard for an initialism. It's written:
NP-hard (non-deterministic polynomial-time hard)
NP-hard and NP-complete are the standard ways to write it.
This is great and all but nobody has addressed the most interesting question yet:
We prove NP-hardness results for five 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. In addition, we observe that several games in the Zelda series are PSPACE-complete.
For whatever it's worth, I have a math degree with a computational focus that started off as a computer science major, and I've got NFC what the terms being bandied about are (just from reading over the paper.) Never heard of them. I've heard of p vs np, but not in the context of any of my coursework.
So yeah, screw you guys who are saying this is basic stuff that everyone who has even dabbled in the field should know. Or screw Penn State for sucking horribly. Probably both.
And to those who say "just look it up," I have no idea why, but as good a reader I am and as fast a learner I am, I seem to lack the ability to understand anything technical in written form. So unless somebody explains it to me, sadly, I probably never will understand it.
So yeah, screw you guys who are saying this is basic stuff that everyone who has even dabbled in the field should know.
Even if we make the argument that a CS major should graduate without dealing with complexity theory at all (which is a shame, but oh well), this paper was written to be read by complexity theorists, every single one of whom knows what NP, NP-hard, 3-SAT, etc. are. It wasn't written to be read by lay people, so complaining about its use of jargon seems kind of silly. It'd be like, say, walking into the LoL topic and complaining about people talking about jungling, ganks, lanes, etc. without any explanation what those words mean. Every LoL player knows what those words mean, so of course they aren't explained every time they're used.
--
Oh, a big machine with flashy lights. A big machine like that has me written all over it. Well, okay, it doesn't. But give me time... and a crayon --11th Doctor
metroid composite posted... Chess can loop game states much more than Go can. The entire set of possible moves in Go for an 8x8 board is like...about (64!) assuming people don't place a piece in the same square more than once.
Hmm...yeah, ok, so that's roughly 64^64 = 2^(6*64) = 2^(384). Haha, ok, yeah, no, you're not searching the entire decision tree by brute force.
So it occurs to me...approximating 64! as 64^64 isn't remotely accurate, and I can get a better estimate than that!
Approximating it as 32^64 would at very least be more accurate.
1*64 < 32*32 2*63 < 32*32 3*62 < 32*32
And so on. But I'm pretty sure I can do better than that, too.
What I really want to do is approximate the exponent, which means I can reduce this problem to...
ln(1) + ln(2) + ln(3) + ... + ln(64)
So...the obvious thing to do here is to approximate this sum with the integral of ln. What I'm really looking for is not actually the closest approximation, but the upper bound, so I will approximate ln(r) = integral(ln(x)) over the interval x = (r...r+1). Which means all I need for the above would be to integrate ln(x) over the interval x = (1...65).
So...what is the integral of ln(x)? And note that I'm barring myself from using google here--google is for weaklings! Actually, let's go stupidly hardcore and bar myself from using a calculator, too (what could possibly go wrong?)
My first guess for the integral of ln(x) would be something like...
x * ln(x)
The derivative of that is...
ln(x) + 1
Ok, so the integral I'm looking for is...
x*ln(x) - x
So what I need to estimate is...
(65*ln(65) - 65) - (1*ln(1) - 1) = 65*ln(65) - 64
which brings us to the question, what is ln(65). And this is where I'm going to seriously regret my bold "I don't need a calculator, lol"
2^6 = 64, so it's safe to say ln(65) < 6 3^4 = 81 so...hmm...let's try 2.7^4, that might actually be in the right ballpark. 2.7^4 = (4 + 2.8 + 0.49)^2 = (7.29)^2 Ok, this is going to be an underestimate, because 8^2 = 64 > 7.3^2
Well...actually, screw base e, I'm switching to base 10.
(Actual value I should have had: ~ e^207. Meh, approximations. Actual value of the sum, rather than the integral: ~ e^205. So...yeah, two digits of accuracy, instead of just one. Definite improvement).
--
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
azuarc posted... And to those who say "just look it up," I have no idea why, but as good a reader I am and as fast a learner I am, I seem to lack the ability to understand anything technical in written form. So unless somebody explains it to me, sadly, I probably never will understand it.
I can sympathize with this. There are definitely ways in which my brain just does not learn effectively. I actually got out of academic mathematics for similar reasons--I just didn't like reading research papers--not that I could never understand them, but math research papers are a whole new level of special where you need to spend about an hour on every paragraph to understand it, even if you know the field very, very well. I decided "screw that" and now I make videogames.
But if your brain works like that...WHY are you reading research papers? Research papers are BY DEFINITION technical results in written form.
--
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
For whatever it's worth, I have a math degree with a computational focus that started off as a computer science major, and I've got NFC what the terms being bandied about are (just from reading over the paper.) Never heard of them. I've heard of p vs np, but not in the context of any of my coursework.
So yeah, screw you guys who are saying this is basic stuff that everyone who has even dabbled in the field should know. Or screw Penn State for sucking horribly. Probably both.
Math that uses computers is quite different from CS. In fact, this is the EXACT area where it is different from CS now that I think of it. Unless you are in graph theory (because it feels like EVERY interesting problem in graph theory is NP-complete or NP-hard), there's a good chance you may never deal with these sorts of things.
That said, if you took at least 2 years of CS I would expect you to know the following (in terms of complexity theory).
1) Basic runtime analysis on P. Selection sort is best, worst, and average case n^2 work. Merge sort is BC n (maybe n log n, depends on implementation), WC/AC n log n. Quick sort is BC/AC n log n, WC n^2, but still typically outperforms merge sort. (you may know a potential problem with a system is a "quicksort attack")
2) Undetermined areas. There exists a class of problems that we believe is "hard", but cannot prove. We call it NP-hard. Examples include: general boolean satisfiability, 3-satisfiability, graph coloring, Hamiltonian cycle, travelling salesman problem, subset sum. All known solutions take exponential time. Examples do NOT include 2-satisfiability. (in general, a more constrained problem may be able to be solved in reasonable time)
3) Definitely hard. You are vaguely aware there exists problems which are known to be harder than the problems in 2. You might not know any examples or names of complexity classes, but if you do, you probably know generalised chess, checkers, and go (with the superko rule) are EXPTIME-complete.
4) Impossible. There exist problems which cannot be solved by a computer, ever. The classic example is the halting problem (will the given program ever hang?).
Also, as I noted, the paper contains nothing of actual value to the public and is at best of marginal interest to those in the field, so yeah, only there for novelty.
Phase posted... That said, if you took at least 2 years of CS I would expect you to know the following (in terms of complexity theory).
I did. I was into my junior year when I switched because I wasn't liking the comp sci program. I had taken one too many classes that seemed electronics-oriented for my liking, and didn't want to do hardware integration for a living. My primary reason for picking that particular math option was because since I was changing majors anyway, I didn't want to change to something that would cost me two years worth of credits...in fact it was fewer credits remaining to graduate with the math. Somehow.
Anyway, I am not familiar with those terms, as stated. I learned about Big-O notation, but that was about as much as we discussed in terms of complexity. Solvability was never discussed in the lower division courses.
Hey MC, quick question: how easy or hard was it to get a job in the "real world" after leaving academia (and did you get a PhD or leave with a masters?)
-- No I'm not a damn furry. Looney Tunes are different. - Guiga I wanted Sonic/Shadow romance at that time, not sex. - MWE