|Tuesday, June 12th, 2001|
". . . I can ask you about love . . . you'd probably quote me a sonnet. Bet you've never looked at a woman and been totally drawn to her. Known someone that could level you with her eyes. Feeling like God put an angel on earth, just for you. Who could rescue you from the depths of Hell . . . and you wouldn't know what it's like to be her angel. To have that love for her, and be there, through anything . . . And you wouldn't know about sleeping sitting up in a hospital room for two months holding her hand, because the doctors could see in your eyes that the term 'visiting hours' doesn't apply to you. You don't know about real loss, because it only occurs when you love something more than you love yourself, and I doubt you've ever dared to love anybody that much. I look at you, I don't see an intelligent, confident man. I see a cocky, scared, lonely kid."-Good Will Hunting
current mood: lost
(3 comments |comment on this)
1:39p - n-queens
Long entries recently. Hope nobody minds.
Today's entry: Going All The Way. There's a classic problem known as the 8-queens problem. Put 8 queens on a chessboard so none of them can attack each other. (normal definition of queen - they can attack diagonally and along lines for any number of squares.) It's not hard to write a program to solve this, though it might take a few minutes for it to run.
A variation of this problem is the n-queens problem. For some (positive) integer n, place n queens on an n by n chessboard. I'm pretty sure it's possible for all numbers but 2 and 3. However, the amount of CPU time it takes to calculate increases dramatically.
For a variety of reasons (one of which being the sheer challenge), I wanted to see if I could manage to calculate really high numbers on the queens problem - you know, 30 or 40 or so. So I browsed around sites and found some interesting things - someone had set up a program on his computer to calculate 20-queens, and it had taken a few days. But there was a solution. (I only really wanted one.) A few days? For a measly 20 queens? I could do better than that . . .
So I did. It took a lot of optimization, but I ended up with a program that would go up through 28-queens in under a second per puzzle, as I remember. It only started going really *slowly* around 34 queens . . . from there it started quadrupling runtime per 2 queens (odd-numbered puzzles are really easy, it's the even-numbered puzzles that are tough.) I got up to 40 queens - which took a few hours, though I was doing other stuff at the time - and stopped it.
And it was mainly because I didn't give up. Okay, this bit is slow - how can I speed it up? How can I make this test run faster? Why am I doing this loop repeatedly - can't I do it only once?
There was a puzzle at Tira's that I beat - the family had had it for six months or so, and nobody's managed it. I did it in maybe three minutes. How? I figured out a simple necessity of the solution and just started *doing* it. Talking to Tira later on, I realized she had been on the right track, she just hadn't kept on going. And later, watching her, she got stuck at a point that I recognized as being a point on the way to finishing it.
See, if you start from the easy end, there's this bit where, in order to keep going, you have to kinda take apart half of what you've done in order to swing one of the wooden bits into the right place - it threads through the middle, and you've already boxed off the middle pretty efficiently. When I was doing it, I just sorta said "okay, this needs to happen, so I'll make it happen" and did it. But most people seem to get to that point and say "well, this is tough, so it can't be the right way". Part of me being able to do these things appears to be the ability to just turn that part of my brain off and bull straight through even when it seems like a bad idea.
I'm not sure what this says about me though.
Since I know there are gonna be a few curious people, I'll now write instructions on how to make the Possibly World's Fastest Brute-Force N-Queens Solver. And I'll do it in a way that will hopefully be understandable to non-CS people. However, I will include it
( after this break.Collapse )
(12 comments |comment on this)
listening to techno reminds me of this game series called Crusader. There were two - Crusader: No Remorse and Crusader: No Regret. (They were making a third, titled Crusader: No Mercy, but it was canned, and with the effective death of Origin I doubt it'll ever be continued.)
The great thing about these games wasn't the graphics (though they weren't bad) or the plot (though it was effective) or the game technology (which was minimal). It was running around, killing bad guys, and making really big things blow up.
And everything blew up. I mean, everything. Everyone's joked about bad guys keeping these inexplicable stashes of explosives lying around - well, this place must have been the storehouse. You machinegunned a barrel, BOOM. You shot a *crate* - foomp. You shot a HANDRAIL and it would explode (though very little).
And the bad guys . . . you'd walk into a room and just spray the room with bullets. Bambambambam. And, ya know, you'd take out half a dozen computer consoles and some enemies. That's just the way the game worked.
The best part was when you started getting really good - everyone's seen jackie chan action movies, right? Roll to the left, leap off a balcony, etc. Well, you could actually *do* that. And the control was good enough that it worked. You could strafe, you could roll to the sides and forward and back, you could jump. You could dodge rockets.
And behind it all, it played good techno music.
And that's what's missing from games today, it seems. The ability to say "screw it all, let's just blow stuff up and call it a day." Games just do it halfway. They try to make a blow-everything-up game and don't do anything *new*. You *can't* blow everything up, you can't knock out entire areas of the level. Games have tried, and they've failed, they've just done same ol' same ol'. Another two dozen bad guys, another small explosion. When was the last time you watched half the screen explode and just *ran* from the shockwave?
It'll happen someday, but . . . not yet, it seems.
We need another Crusader game.
(Wonder if Origin would sell the rights? :P)
For some reason I seem to be holding up better here than I thought I would. Perhaps I'm just used to suppressing emotion here :/ Oh, and I realized something - I'm not Will Hunting. I'm his girlfriend.
(Well, I always *said* I'd make a better female.)
(2 comments |comment on this)