computer science
Latest
Scientists develop algorithm to solve Rubik's cubes of any size
A computer solving a Rubik's cube? P'shaw. Doing it in 10.69 seconds? Been there, record set. But to crack one of any size? Color us impressed. Erik Demaine of MIT claims to have done just that -- he and his team developed an algorithm that applies to cubes no matter how ambitious their dimensions. Pretty early on, he realized he needed to take a different angle than he would with a standard 3 x 3 x 3 puzzle, which other scientists have tackled by borrowing computers from Google to consider all 43 quintillion possible moves -- a strategy known simply as "brute force." As you can imagine, that's not exactly a viable solution when you're wrestling with an 11 x 11 x 11 cube. So Demaine and his fellow researchers settled on an approach that's actually a riff on one commonly used by Rubik's enthusiasts, who might attempt to move a square into its desired position while leaving the rest of the cube as unchanged as possible. That's a tedious way to go, of course, so instead the team grouped several cubies that all needed to go in the same direction, a tactic that reduced the number of moves by a factor of log n, with n representing the length of any of the cube's sides. Since moving individual cubies into an ideal spot requires a number of moves equal to n², the final algorithm is n²/log n. If we just lost you non-math majors with that formula, rest assured that the scientists expect folks won't be able to apply it directly, per se, though they do say it could help cube-solvers sharpen their strategy. Other that, all you overachievers out there, you're still on your own with that 20 x 20 x 20.
Computer learning and computational neuroscience icon Dr. Leslie Valiant wins Turing Award
We've seen recently that computers are more than capable of kicking humanoids to the curb when it comes to winning fame and fortune, but it's still we humans who dole out the prizes, and one very brainy humanoid just won the best prize in computer science. That person is Leslie Valiant, and the prize is the fabled A.M. Turing Award. Dr. Valiant currently teaches at Harvard and over the years developed numerous algorithms and models for parsing and computer learning, including work to understand computational neuroscience. His achievements have helped make those machines smarter and better at thinking like we humans, but he's as of yet been unsuccessful in teaching them the most important thing: how to love.
Working 16-bit computer built inside Minecraft
Sure, lots of players are building memories and geek tributes in the incredibly popular indie sandbox game Minecraft, but here's something actually functional: a working 16-bit ALU (arithmetic logic unit) designed entirely in the game. The "wires" are made from Redstone, a unit in the game that can carry a fiery charge. So to calculate numbers, creator "theinternetftw" just lights torches representing binary numbers on one end, and then waits to see which torches (representing binary digits) light up on the other; giving him the mathematical answer he's looking for. Crazy? Yes. Nerdy? Very. Awesome? Indeed. All the hard work must have been worth it -- theinternetftw has been posting about the project on Reddit and reportedly got a job offer out of it. But he's not done yet: He wants to add some memory to the computer and even make it "Hack" compatible, which means it would compile and run actual code (albeit very, very slowly). Said Minecraft creator Markus Persson via Twitter last night, "I saw the ALU, and I wet myself! Seriously, I got a hose and wet myself. With pee."
HP labs researcher thinks he might have proof of P≠NP, has another Millennium problem been solved?
If you don't know the major problems facing mathematics and computer science, you might not be familiar with the problem of P versus NP. In short, it's a problem which asks, "if 'yes' answers to a yes or no question can be quickly verified, can they also be computed quickly?" Many computer scientists have long suspected that P≠NP, and it's been listed by The Clay Mathematics Institute as one of the Millennium Problems (another of which was solved earlier this year), carrying a 1 million dollar prize if solved. Apparently, HP researcher Vinay Deolalikar has been working on the problem in his spare time, and it seems that he's emailed his preliminary paper in support of P≠NP to the committee tasked with judging the Millennium Prize. His HP profile says he's received several preliminary confirmations of his draft, and that a final paper is currently in preparation. We wish him luck, and we'll keep you updated.
MMOrigins: Life's funny like that, page 2
What started as simple forum posts on tanking and a little number crunching bloomed into a full guide in Issue 2 of EON, EVE's official magazine. When the article was finally in print, EON editor Richie 'Zapatero' Shoemaker came to me with a work proposal. After writing several more articles for EON and acting as editor on countless others, university work began piling up and I had to stop.
MMOrigins: Life's funny like that
We all got started gaming somewhere. For a lot of people, it was the Sega Mega-drive, the Atari 2600 or the NES that signaled their first steps into gaming. For me, it was the Commodore Amiga, a machine that was more a complete home computer than a games console. It was on the Amiga that groups like Team 17, Ocean, Electronic Arts and Blizzard first really made their mark on gaming and it was a great time of innovation in the industry. I recall long nights spent playing Frontier: Elite II, scooping hydrogen fuel from the corona of a star or wormholing into deep space. Another favourite that I still play occasionally was K240, an early space 4x game and still one of the best I've ever played. It was the public domain market on the Amiga that really caught my attention. It's one thing to play a game, but here was the opportunity to make one and sell it via a page in CU Amiga magazine or a PD order disk. I've always been more interested in making games than playing them but being young with no programming experience, I was limited in what I could do. I tooled endlessly with the "Shoot 'em up Construction Kit" and "Reality Game Creator" packages, making countless primitive prototype games that only I ever played.
EVE Online coding honcho profiled in 'Master of the Universe'
Most gamers probably aren't familiar with IEEE Spectrum, but it's a publication of the Institute of Electrical and Electronics Engineers (IEEE), the world's largest professional technology association. Fans of EVE Online who are curious about the people behind the sci-fi title might be interested in checking out IEEE Spectrum's piece on CCP Games and the man who directs the EVE Online Software Group: Erlendur Thorsteinsson, also known to players as CCP Explorer. The profile is written by Erico Guizzo, titled "Erlendur Thorsteinsson: Master of the Universe." Guizzo's piece sheds some light on what brought the Computer Science Ph.D. to CCP Games in order to tackle the myriad challenges of improving EVE's single world environment. The article also gives mention to the work done behind the scenes on the title's more ambitious projects, including adding wormhole exploration to the game with the Apocrypha expansion, and the forthcoming Walking in Stations where player avatars will step out of their ships for the first time. [Via CrazyKinux]
