Today I'm rewriting this entire post (minus the code - it's very ugly code in retrospect). So I'm trying to solve the "to add or multiply" problem from the ACM 2011 finals. My hunch last week was that it could be solved in linear time. This week I explored what I thought would be a linear solution and came back with some interesting notes.
Before I jump into the subject; the problem gives two ranges of integers (start and end), and two constants 'a' and 'm'. Find arbitrary positive integers [i1, i2, i3, ... in] such that the following is contained within the range 'end':
(((start+i1*a)*m^i2 + i3*a)*m^i4 + i5*a) ....
(where arithmetic on ranges is identical to operations on a 2-vector. a range consists of a start-value and end-value)
First, I now believe that there is no linear-time solution. Intuitively, the reason is because there is a destination range and not a destination number.
Consider the inclusive range [a,b]. Now, there's a number 'x' that I can multiply an integer 'j' to get a value between a and b. I also want 'j' to be minimal. This is quite simple - if 'a mod x = 0' then the answer is a/x else it is 1+a/x. Recall the computer always floors integer data, we would want the ceiling.
Within the problem, there's a point at which both j=a/x and j=1+a/x should be explored. Below I'll try to informally explain this:
For the problem, it is possible to find a value 'a' that is the maximum number of multiplications that may be applied to [p,q] (the start range) until the values exceed [r,s] or the number of integers within the range of [p,q] exceeds that of [r,s].
The maximum number of multiplications is invariant no matter how many addition operators are present. Simple example ('x' is a starting value, 'a' and 'm' are integers):
(x+a)m = xm + am
'am' will shift values a constant amount regardless of the starting value 'x'. This is important, look at a range [2,3] -- [2,3] has 3 digits, [2,3]*4 = [8,12] has 5 digits. We can add integers before the multiplication and the number of digits will not change. This allows us to compute another value -- the minimum number of additions needed until a solution.
If it is not possible to find a series of additions that satisfies the start range and end range, then we can not conclude that there is no solution. Consider that the increments of addition is 100,000 and multiplication is 2 with start range [1,2] to [5,20].
Neither is it possible to rely solely on multiplication. Consider addition of 1 and multiplication of 7, start range [1,2] and end range [14,21]. The following is contained within the range: ([1,2]+1)*7
Knowing these two values helps us when searching for a solution. The solution becomes:
x*m^j + i1*a*m^0 + i2*a*m^1 + ...
It's a matter of finding i1, i2, i... (j-1 unknowns). If multiplication is 1 or 0, or if addition is 0 then the solution can be directly computed in constant time (depending upon your implementation of log - or if you decide to loop over values for multiplication -- which makes it O(n)).
Anyhow, a good strategy is to attempt to maximize the i for the m with the largest exponents. Think of this as a heuristic. When the number of integers can be in the tens of thousands, doing a brute-force search will be slow and memory consuming (simple arithmetic, just it will look like a mess here).
I'll continue playing with the numbers, maybe something interesting will pop out.
For historical purposes, here's a very slow / bad implementation of "to add or multiply":
import Data.Monoid
import Data.Char
-- AddOrMultiply
-- Given the ability to add 'a' or multiply 'm', see if there is a sequence
-- that starts in range [p,q] and ends in range [r,s]
data Operation = A Integer | M Integer
instance Show (Operation) where
show (A v) = " " ++ (show v) ++ "A"
show (M v) = " " ++ (show v) ++ "M"
apply :: Operation -> Integer -> Integer
apply (A v) a = (v+a)
apply (M v) a = (v*a)
data Partial = Partial (Integer,Integer,Integer) [Operation] deriving (Show)
applyl :: (Integer,Integer) -> [Operation] -> Partial
applyl (min,max) os = Partial (foldr apply min os,foldr apply max os,0) os
incrementMul :: Operation -> Integer -> Integer
incrementMul (M m) v = 1
incrementMul _ v = v
combineOps :: Operation -> [Operation] -> [Operation]
combineOps o [] = [o]
combineOps (A a) ((A as):xs) = (A $ a+as):xs
combineOps (M m) ((M ms):xs) = (M $ m+ms):xs
combineOps o xs = o:xs
add :: Operation -> Partial -> Partial
add o (Partial (min,max,mul) os) = Partial (apply o min, apply o max, incrementMul o mul) $ combineOps o os
validAdd :: (Integer,Integer)->Partial -> Bool
validAdd _ (Partial (_,_,0) _) = True
validAdd (a,m) (Partial _ ((A a1):_)) = a1 < (a*m)
validAdd _ _ = True
valid :: (Integer,Integer) -> (Integer,Integer) -> Partial -> Bool
valid am (r,s) (Partial (min,max,mul) os) = if (max <= s && max-min <= s-r && (validAdd am $ Partial (min,max,mul) os)) then True else False
iteration :: (Integer,Integer) -> (Integer,Integer) -> Partial -> [Partial]
iteration (a,m) rs ptl = filter (valid (a,m) rs) [add (A a) ptl, add (M m) ptl]
-- concatMap :: (a -> [b]) -> [a] -> [b]
startCondition :: (Integer,Integer) -> [Partial]
startCondition (p,q) = [Partial (p,q,0) []]
success :: (Integer,Integer) -> Partial -> Bool
success (r,s) (Partial (min,max,_) _) = if (min >= r && max <= s) then True else False
iterationl :: (Integer,Integer) -> (Integer,Integer) -> [Partial] -> [Partial]
iterationl (a,m) rs ps = concatMap (iteration (a,m) rs) ps
everything :: (Integer,Integer) -> (Integer,Integer) -> [Partial] -> [Partial]
everything _ _ [] = []
everything am rs ps = ps ++ (everything am rs $ iterationl am rs ps)
solutions :: (Integer,Integer) -> (Integer,Integer) -> (Integer,Integer) -> [Partial]
solutions am pq rs = filter (success rs) $ everything am rs $ startCondition pq
type Ampqrs = (Integer,Integer,Integer,Integer,Integer,Integer)
reformat :: (Integer,Integer) -> [Operation] -> [Operation]
reformat _ [] = []
reformat am ((A a1):(A a2):xs) = reformat am $ (A $ a1+a2):xs
reformat am ((M m1):(M m2):xs) = reformat am $ (M $ m1+m2):xs
reformat (a,m) ((A a1):xs) = ((A $ a1 `div` a):(reformat (a,m) xs))
reformat (a,m) ((M m1):xs) = ((M $ m1 `div` m):(reformat (a,m) xs))
solutionPartial :: Ampqrs -> [Partial]
solutionPartial (a,m,p,q,r,s) = take 1 $ solutions (a,m) (p,q) (r,s)
operationFromPartial :: Partial -> [Operation]
operationFromPartial (Partial _ o) = o
solution' :: (Integer,Integer) -> [Partial] -> Maybe [Operation]
solution' _ [] = Nothing
solution' am xs = Just . reverse . (reformat am) . operationFromPartial . head $ xs
solutionOp :: Ampqrs -> Maybe [Operation]
solutionOp (a,m,p,q,r,s) = solution' (a,m) $ solutionPartial (a,m,p,q,r,s)
solutionOp' :: [String] -> Maybe [Operation]
solutionOp' [a,m,p,q,r,s] = solutionOp (read a, read m, read p, read q, read r, read s)
parseLine :: String -> Maybe [Operation]
parseLine s = solutionOp' $ words s
display :: Integer -> [String] -> String
display _ [] = []
display _ [a] = []
display i (x:xs) = ("Case " ++ (show i) ++ ": " ++ (show $ parseLine x)) ++ ['\n'] ++ (display (i+1) xs)
main = do
contents <- getContents
putStr . (display 1) $ lines contents
Sunday, November 27, 2011
Sunday, September 4, 2011
Sonic 4 EP 1 iOS Impressions
The price for Sonic 4 EP 1 has invariably dropped following the trend of most applications on iOS. Sell for the maximum that the consumer will allow then drop to catch the cheapskates. Others take the route of giving away a base application (or charging at probably a loss) and recuperating on paid extensions.
First, this game has 17 levels + special stages for each. Ignoring the boss-fights and the shorter levels, that's about 11 levels. Let me put the price of this game in perspective ($4.99) for 4 zones and 11 long levels (disclaimer, I didn't research anything about the profit margins of this game). The first sonic game had about 8 zones, or 24 levels. Just shy of double what this game offers. And for much more than double the cost. My point: people who say it's worth ($0.99) ... wake up and look at the development effort! The levels appear to be huge + multiple sound-tracks -- and testing such levels is no small feat. The two previous published iOS games I worked on would need to be more than ($0.99) to recuperate the investment given a target market. (For those saying it appeared on multiple consoles -- it's not up to the other machines to finance the development for the iOS version).
For those complaining about bugs / crashing. Email SEGA. Complaining on the Apple store ratings page might not help. I had problems with Civ. Emailing (convoluted process) Firaxis gave me the answer I was seeking.
Most of the game reviews already cover every aspect of the game. I shouldn't need to go into more details there.
What I'm about to rant about is that it's a cross-platform game. A game designed for game consoles as well as iOS. And that's the main fault I find with it.
The developers (to save time) probably (I'm guessing here) had separated the game from everything else. All platforms support getting input. It is the semantics of accessing the input device that changes for each platform. XBox will go through XNA (there might have other options), Wii through (who knows what, it's proprietary), iOS through UIKit. (Graphics, file access, used meshes, etc. may vary depending upon the platform but I'd guess that the game itself is portable C/C++/(other?) and what changes is glue that makes the whole thing run.)
So, you have a game. It wants left-press, right-press, up-press, down-press, and action. That's it. That's how multiple input schemes become possible. Don't like pressing the virtual D-Pad on the iOS device? Then use the tilt sensor and swipe! A myriad of other options could be presented with little effort (normally inundating the user with frivolous options is a bad idea -- power users may like it but they aren't representative of the whole however vocal they may be).
This works perfectly on the systems with physical controls. The Wii, XBox, and PS3. This fails on iOS (not miserably, but it's an issue). If you don't realize that they are just mapping controls, confusion may ensue.
Why confusion? Let's take a special stage for example. They say tilt left and right to turn the world. That's confusing, but it's part of the game. Where it fails is -- wait if I'm holding the iOS device parallel to a table? Should sonic act like a ball in a labyrinth game and slow down? That might actually be more intuitive. Further still, why rotate the world when the whole device can be rotated? The game was programmed for left/right, it gets left/right from tilting left and right. (I've done some testing with accelerometer controls, my conclusion being that they are the hardest to do right)
Jumping is also a bit jarring. The button is statically placed. It's a region. It might be easier if the region covered the whole right-side of the screen.
Moving is also difficult with the D-Pad. To conserve screen-space, it's on the left-hand side. Pressing right can be done by pressing from the end of the go-left button to the middle of the screen (from basic testing). I couldn't feel a neutral position (this is probably just me complaining for nothing).
Later on there are cannons to shoot sonic to a specific spot. It may make more sense to tap in the direction the cannon should face, but it's again press left/right to turn and action to shoot.
Game-wise, Sonic should be on the left of the screen when moving right and vice-versa. This gives the player the ability to anticipate what will happen when running (memorizing the level is fun and all...)
Actually, I had fun playing through the first half of the game. It's not a bad game, they mapped controls in a very coarse way which takes away from the game a bit. And I don't complain given the price, the older games cost much more even after release.
What I want to bring to light are the challenges of cross-platform development. The game was perfectly abstracted away to work on the traditional consoles. iOS is a different beast. Certain changes might actually be too drastic and require too much reworking of the levels (the special zones are difficult since Sonic has a continual pull of gravity in a given direction. Removing that may require rethinking of the levels. It's more nostalgic this way though!) You might want to aim the cannon towards one of the on-screen buttons, etc.
First, this game has 17 levels + special stages for each. Ignoring the boss-fights and the shorter levels, that's about 11 levels. Let me put the price of this game in perspective ($4.99) for 4 zones and 11 long levels (disclaimer, I didn't research anything about the profit margins of this game). The first sonic game had about 8 zones, or 24 levels. Just shy of double what this game offers. And for much more than double the cost. My point: people who say it's worth ($0.99) ... wake up and look at the development effort! The levels appear to be huge + multiple sound-tracks -- and testing such levels is no small feat. The two previous published iOS games I worked on would need to be more than ($0.99) to recuperate the investment given a target market. (For those saying it appeared on multiple consoles -- it's not up to the other machines to finance the development for the iOS version).
For those complaining about bugs / crashing. Email SEGA. Complaining on the Apple store ratings page might not help. I had problems with Civ. Emailing (convoluted process) Firaxis gave me the answer I was seeking.
Most of the game reviews already cover every aspect of the game. I shouldn't need to go into more details there.
What I'm about to rant about is that it's a cross-platform game. A game designed for game consoles as well as iOS. And that's the main fault I find with it.
The developers (to save time) probably (I'm guessing here) had separated the game from everything else. All platforms support getting input. It is the semantics of accessing the input device that changes for each platform. XBox will go through XNA (there might have other options), Wii through (who knows what, it's proprietary), iOS through UIKit. (Graphics, file access, used meshes, etc. may vary depending upon the platform but I'd guess that the game itself is portable C/C++/(other?) and what changes is glue that makes the whole thing run.)
So, you have a game. It wants left-press, right-press, up-press, down-press, and action. That's it. That's how multiple input schemes become possible. Don't like pressing the virtual D-Pad on the iOS device? Then use the tilt sensor and swipe! A myriad of other options could be presented with little effort (normally inundating the user with frivolous options is a bad idea -- power users may like it but they aren't representative of the whole however vocal they may be).
This works perfectly on the systems with physical controls. The Wii, XBox, and PS3. This fails on iOS (not miserably, but it's an issue). If you don't realize that they are just mapping controls, confusion may ensue.
Why confusion? Let's take a special stage for example. They say tilt left and right to turn the world. That's confusing, but it's part of the game. Where it fails is -- wait if I'm holding the iOS device parallel to a table? Should sonic act like a ball in a labyrinth game and slow down? That might actually be more intuitive. Further still, why rotate the world when the whole device can be rotated? The game was programmed for left/right, it gets left/right from tilting left and right. (I've done some testing with accelerometer controls, my conclusion being that they are the hardest to do right)
Jumping is also a bit jarring. The button is statically placed. It's a region. It might be easier if the region covered the whole right-side of the screen.
Moving is also difficult with the D-Pad. To conserve screen-space, it's on the left-hand side. Pressing right can be done by pressing from the end of the go-left button to the middle of the screen (from basic testing). I couldn't feel a neutral position (this is probably just me complaining for nothing).
Later on there are cannons to shoot sonic to a specific spot. It may make more sense to tap in the direction the cannon should face, but it's again press left/right to turn and action to shoot.
Game-wise, Sonic should be on the left of the screen when moving right and vice-versa. This gives the player the ability to anticipate what will happen when running (memorizing the level is fun and all...)
Actually, I had fun playing through the first half of the game. It's not a bad game, they mapped controls in a very coarse way which takes away from the game a bit. And I don't complain given the price, the older games cost much more even after release.
What I want to bring to light are the challenges of cross-platform development. The game was perfectly abstracted away to work on the traditional consoles. iOS is a different beast. Certain changes might actually be too drastic and require too much reworking of the levels (the special zones are difficult since Sonic has a continual pull of gravity in a given direction. Removing that may require rethinking of the levels. It's more nostalgic this way though!) You might want to aim the cannon towards one of the on-screen buttons, etc.
Saturday, July 30, 2011
First Day of 10.7
I decided it might be worth updating Mac OS to 10.7. First, for anyone thinking of updating, double-check all of your apps. I was surprised by the number of applications that I had that were PowerPC. I think the machine was spending more time running Rosetta than x86 binaries... The important apps I found newer versions and trudged forward. My scanner will only be usable with an older Power Mac.
So. How does the OS fare? Here are the positive and negative features on a per-app/feature basis in my opinion.
Mail.app
Mail.app's interface update is great! The application is now designed for wider screens. On the far left is the side-bar as it was there before (hidden by default but click on "Afficher" -- I guess that's "Show" in English). Organized like it is, stretch the application and there is plenty of room for the previews and other information. The preferences allow for plenty of customization.
iCal
I like the way it looks. Where Mail.app got a massive functionality upgrade, iCal seems to suffer. The problem is that things normally aren't neatly split up between months. So if I'm trying to schedule something it won't be for a specific day but some time-range. So I want to quickly jump between weeks (if possible see multiple weeks) and not be stuck in groups a day/week/month/year. (the option to scroll a day at a time is silly - it renders the velocity scrolling of the magic mouse useless)
For example, if in the week view it scrolled continuously and could display multiple weeks in it's columnar view I'd be very happy. For the day view, for a sufficiently wide screen multiple months can be seen. Even multiple days. On a small 1024x768 screen the spacing is elegant, however I'd argue there is space for two more monthly calendars in day and week view.
Finder
Overall, it's as usable as ever. I can't complain, it feels normal. A few settings I had to re-enable, but it's as I expected. The overall view of all my files is... pointless. It seems to be randomly picking stuff I downloaded -- such as a picture generated by Doxygen.
I'm happy that the library is now hidden. To many things could go wrong by having that exposed to the user. Those of us that wish to muck with system stuff can hit Command-Shift-G. The icons are much clearer.
Terminal
Works. Happy. Why can it go fullscreen?!
LaunchPad
I don't know what to make of this. LaunchPad attempts to present a nicer view of the applications. Sure, that's great! The question that's running around my head is: why isn't LaunchPad's view synchronized with the Application folder?
For example, a folder in Applications becomes a folder in LaunchPad. Of course there are issues with nesting folders but I don't see why folders nested more than one couldn't just be collapsed. Certain applications would be dangerous to move (bad developers)... However organizing my applications once is, in my opinion, preferable.
Actually, I would have loved LaunchPad if it just opened a fancy view of my Applications folder.
Apart from that, it's a great idea. Only if I didn't use the dock to store often-used applications and Spotlight for everything else. (StarCraft II? Spotlight!)
Mission Control
A very good update to Exposé. It unifies all the window management features into one nice spot. One button to see all my windows from all the apps with all the desktops + fullscreen apps. Then, windows from the same application are grouped. It's very nice.
Fullscreen Apps
Really. I wanted to love this. I have a small-ish monitor on the side where I tend to throw documentation, iTunes, Mail, and the web browser. The main monitor is reserved for work (XCode, iOS Simulator, etc.). Never doubt having the documentation on a second monitor!
Fullscreen apps grey out the second monitor. As in, they don't use it! And I can't put floating windows on it if applications on the main monitor are full screen. XCode, which I thought would actually use both monitors (put the Organizer on the second!) spawned the Organizer as a new full-screen window.
Use multiple monitors? You'll go further running the applications in windows.
Safari
The download window is gone and replaced with a pop-up... Thanks Apple!
Unfortunately flash videos skip now when the system is under load...
XCode
The documentation within the Organizer is still a mess. It's more convenient browsing to Apple's site since the side-bar should be synchronized to the documentation (or a viewable side-bar should be there).
No, I don't want Quick Help. Quick Help doesn't even pick up on the Doxygen comments littering my code.
Last Impressions
The Mac OS / iOS hybrid seems to be an odd beast. The ability to quit and resume applications is wonderful. But the addition of fullscreen applications and launchpad feel like kludges. (LaunchPad especially feels like it's tacked on rather than integral).
The scroll-bars... This is minor. Use it for a day or two with the default settings. Within a few minutes I was already used to the scrolling. The elimination of scrollbars didn't affect me: I never used them anyhow. Give it a chance for at least a day.
Autocomplete -- it's annoying when it fails.
Those are my comments from one day with the system...
So. How does the OS fare? Here are the positive and negative features on a per-app/feature basis in my opinion.
Mail.app
Mail.app's interface update is great! The application is now designed for wider screens. On the far left is the side-bar as it was there before (hidden by default but click on "Afficher" -- I guess that's "Show" in English). Organized like it is, stretch the application and there is plenty of room for the previews and other information. The preferences allow for plenty of customization.
iCal
I like the way it looks. Where Mail.app got a massive functionality upgrade, iCal seems to suffer. The problem is that things normally aren't neatly split up between months. So if I'm trying to schedule something it won't be for a specific day but some time-range. So I want to quickly jump between weeks (if possible see multiple weeks) and not be stuck in groups a day/week/month/year. (the option to scroll a day at a time is silly - it renders the velocity scrolling of the magic mouse useless)
For example, if in the week view it scrolled continuously and could display multiple weeks in it's columnar view I'd be very happy. For the day view, for a sufficiently wide screen multiple months can be seen. Even multiple days. On a small 1024x768 screen the spacing is elegant, however I'd argue there is space for two more monthly calendars in day and week view.
Finder
Overall, it's as usable as ever. I can't complain, it feels normal. A few settings I had to re-enable, but it's as I expected. The overall view of all my files is... pointless. It seems to be randomly picking stuff I downloaded -- such as a picture generated by Doxygen.
I'm happy that the library is now hidden. To many things could go wrong by having that exposed to the user. Those of us that wish to muck with system stuff can hit Command-Shift-G. The icons are much clearer.
Terminal
Works. Happy. Why can it go fullscreen?!
LaunchPad
I don't know what to make of this. LaunchPad attempts to present a nicer view of the applications. Sure, that's great! The question that's running around my head is: why isn't LaunchPad's view synchronized with the Application folder?
For example, a folder in Applications becomes a folder in LaunchPad. Of course there are issues with nesting folders but I don't see why folders nested more than one couldn't just be collapsed. Certain applications would be dangerous to move (bad developers)... However organizing my applications once is, in my opinion, preferable.
Actually, I would have loved LaunchPad if it just opened a fancy view of my Applications folder.
Apart from that, it's a great idea. Only if I didn't use the dock to store often-used applications and Spotlight for everything else. (StarCraft II? Spotlight!)
Mission Control
A very good update to Exposé. It unifies all the window management features into one nice spot. One button to see all my windows from all the apps with all the desktops + fullscreen apps. Then, windows from the same application are grouped. It's very nice.
Fullscreen Apps
Really. I wanted to love this. I have a small-ish monitor on the side where I tend to throw documentation, iTunes, Mail, and the web browser. The main monitor is reserved for work (XCode, iOS Simulator, etc.). Never doubt having the documentation on a second monitor!
Fullscreen apps grey out the second monitor. As in, they don't use it! And I can't put floating windows on it if applications on the main monitor are full screen. XCode, which I thought would actually use both monitors (put the Organizer on the second!) spawned the Organizer as a new full-screen window.
Use multiple monitors? You'll go further running the applications in windows.
Safari
The download window is gone and replaced with a pop-up... Thanks Apple!
Unfortunately flash videos skip now when the system is under load...
XCode
The documentation within the Organizer is still a mess. It's more convenient browsing to Apple's site since the side-bar should be synchronized to the documentation (or a viewable side-bar should be there).
No, I don't want Quick Help. Quick Help doesn't even pick up on the Doxygen comments littering my code.
Last Impressions
The Mac OS / iOS hybrid seems to be an odd beast. The ability to quit and resume applications is wonderful. But the addition of fullscreen applications and launchpad feel like kludges. (LaunchPad especially feels like it's tacked on rather than integral).
The scroll-bars... This is minor. Use it for a day or two with the default settings. Within a few minutes I was already used to the scrolling. The elimination of scrollbars didn't affect me: I never used them anyhow. Give it a chance for at least a day.
Autocomplete -- it's annoying when it fails.
Those are my comments from one day with the system...
Friday, July 29, 2011
Software: From Simple to Complicated
A few years ago, I started a small software library. A set of common routines. Seeing how useful it was, I decided to expand it -- make it more general. Apply good software development techniques so that it may prove to be more flexible.
For example, at the beginning I hardcoded the ability to use a single 1024x1024 texture for everything. This meant I had no need to worry about which texture was currently bound (only one) and no need to manage memory (one fixed amount of memory used). Then I expanded this system to load multiple textures using a plist for the parameters.
For the added flexibility, I was able to create textures and use them as objects. Yet; as far as making prototypes go it didn't speed things up. Memory became an issue to manage. And now mipmapping and other little technological ideas for the sake of technology start to creep in when ideas should be driving the technology.
In the end; I should conclude the organization for generic code is only needed when called for. If it works, and works well, why change it?
Wednesday, July 27, 2011
StarCraft II: Beating the AI on Hard
Watching others play StarCraft is the best way to learn. And I have successfully beat the AI on hard using all of the races (1 vs 1). And the pattern is actually quite simple (on Blizzard's maps at least).
First; we should realize the harvesting is the main bottleneck. If you have to wait a second to build a unit (unless the game has just started) then something is wrong.
The other bottleneck is production speed. If you have too many resources and can't spend them on units, something is wrong.
So; here's the overall build order:
1. Get up the 20 units harvesting the mineral fields provided at the beginning.
2. Zerg: get Zerglings (also, build a queen as soon as possible), Terrain: get marines (build two barracks), Protoss: Zealots (build two warp gates).
3. Set up a second base (no air units at this time). Get 20 units harvesting the second mineral field (while producing a steady stream of offensive units -- your first test is surviving the first wave).
4. For Zerg start focusing on roaches and move towards hydralisks (air defence) -- if all goes well you have so many minerals to waste that building a third or fourth hatchery for extra unit production is worth-while. For terrain, build a factory for stronger units, however you should be able to afford 4-5 barracks producing a continual stream of marines. Similarly, for protoss, 4-5 warp gates can produce plenty of units (but the zealots won't be enough, vary it a bit with them.)
5. Send waves of units (if there are enough) into enemy territory (scouting may be needed). I let them die off and focus on preparing the next wave. If you have the talent, you might want to call back weak units.
6. Prepare a final wave composed of tougher units (ultralisks, for example).
And victory should follow. This just rushes the AI with too many units. It can fail, but it tends to succeed. If you aren't sure why things went wrong, look at the replays and see how the AI played.
First; we should realize the harvesting is the main bottleneck. If you have to wait a second to build a unit (unless the game has just started) then something is wrong.
The other bottleneck is production speed. If you have too many resources and can't spend them on units, something is wrong.
So; here's the overall build order:
1. Get up the 20 units harvesting the mineral fields provided at the beginning.
2. Zerg: get Zerglings (also, build a queen as soon as possible), Terrain: get marines (build two barracks), Protoss: Zealots (build two warp gates).
3. Set up a second base (no air units at this time). Get 20 units harvesting the second mineral field (while producing a steady stream of offensive units -- your first test is surviving the first wave).
4. For Zerg start focusing on roaches and move towards hydralisks (air defence) -- if all goes well you have so many minerals to waste that building a third or fourth hatchery for extra unit production is worth-while. For terrain, build a factory for stronger units, however you should be able to afford 4-5 barracks producing a continual stream of marines. Similarly, for protoss, 4-5 warp gates can produce plenty of units (but the zealots won't be enough, vary it a bit with them.)
5. Send waves of units (if there are enough) into enemy territory (scouting may be needed). I let them die off and focus on preparing the next wave. If you have the talent, you might want to call back weak units.
6. Prepare a final wave composed of tougher units (ultralisks, for example).
And victory should follow. This just rushes the AI with too many units. It can fail, but it tends to succeed. If you aren't sure why things went wrong, look at the replays and see how the AI played.
Tuesday, July 26, 2011
Fast Integer Square Root
Here's my attempt at writing a fast square root function for integers. It's not as fast as the built-in sqrtf function (even with type conversions) but it's decent. In the worst case it was twice as slow -- but that would downplay the significance of the learning experience.
First, I try to estimate a point near the root. Consider a number in binary, it's square root will be between two to the power of half of the length of the binary string rounded up and double that value. The lower bound can be made more accurate, but this is sufficient.
Then, with the maximum and minimum, the midpoint should be a good starting point or guess that I feed into Newton's method. Newton's method is used to increment or decrement the initial guess to something a bit saner.
More speed can be obtained by replacing some division by bit-shifting (but that's dangerous). The fastest (and smartest) way would be to use the built-in SSE functions to do the square root and inverse square root (properly pipelined).
First, I try to estimate a point near the root. Consider a number in binary, it's square root will be between two to the power of half of the length of the binary string rounded up and double that value. The lower bound can be made more accurate, but this is sufficient.
Then, with the maximum and minimum, the midpoint should be a good starting point or guess that I feed into Newton's method. Newton's method is used to increment or decrement the initial guess to something a bit saner.
More speed can be obtained by replacing some division by bit-shifting (but that's dangerous). The fastest (and smartest) way would be to use the built-in SSE functions to do the square root and inverse square root (properly pipelined).
//! Same, but this time do Newton's method
int sqNewton(int in_val)
{
int c = in_val;
if (c <= 0) return 0;
int lower = 1;
if (c >= (1 << 16))
{
c >>= 16;
lower <<= 8;
}
if (c >= (1 << 8))
{
c >>= 8;
lower <<= 4;
}
if (c >= (1 << 4))
{
c >>= 4;
lower <<= 2;
}
if (c >= (1 << 2))
{
c >>= 2;
lower <<= 1;
}
//Hit mid-bound
lower = lower*3/2;
//printf("%li %li %li\n", lower, in_val, lower*lower-in_val);
int numerator = lower*lower + in_val;
int denominator = 2*lower;
return numerator/denominator;
}
Monday, July 25, 2011
Rant on P versus NP
The weekend spent on absorbing information relating to P's relation to NP, I shall now solidify my understandings through regurgitation of what I've understood.
First, the types of texts that I've found either went deep into the topic (from the theoretical perspective) or brushed lightly upon it (the way a book on programming treats mathematics). I'll try to walk a fine line between both while maintaining clarity. Hopefully it works.
What are P and NP?
These have to do with timing. Not in seconds, but in 'effort'. For example, consider sorting books in a book-shelf. You could scan through the 'N' books to sort, find the smallest one (or whatever sorting criteria you want), and put it at the beginning of the shelf. This operation could be repeated for the remaining books. So, to sort 'N' books, you'd look at (on average) 'N/2' books to find the next one to place to the left of the shelf. That involves looking at 'N^(N/2)' books. In the big picture, we say 'N^N' (N to the N) operations will be needed. As the number of books increase, this method of sorting will be excruciatingly slow. It is left as an exercise to the reader to translate looking at book titles to actual time.
They also have something to do with 'polynomial time'. That is, a number that can be expressed in the form of 'N^x' where 'N' is the number of elements to work on and 'x' is a constant. Sorting books according to our previous example takes much longer than polynomial time (think of very large 'N').
P looks at problems that take polynomial time. Specifically, deterministic problems. Typically involving Turing machines (but I don't want to go into the details of tapes). Essentially, any problem whose solution expressed as a series of unambiguous steps takes polynomial time is in P.
And NP also looks at problems that take polynomial time. This time, problems whose solution is expressed non-deterministically. Back to our book sorting problem, we looked at 'N/2' books (on average) to find the next book to place on the shelf. But what if we just 'looked at all the books at once' and happened to pick the right one. Something similar goes on with 'Oracle machines'. However, NP is easier to understand as the time it takes to verify the problem. In other words, our book sorting would take 'N' time in non-deterministic polynomial time (NP-time)
And why is P versus NP important?
The crux of the problem: are all the problems in NP also part of P? Essentially, NP problems are easy to verify but can be hard to compute. Like our sorting problem, we only need to inspect each book once to confirm that they are sorted. Similar ideas are used in cryptography -- a very difficult problem must be solved by the person who attempts to intercept the message.
Problems in P are those that are practically solvable (well, practically this is debatable, theoretically this is true). There are problems that are much more difficult. Let's call these NP-Complete (ok, technically NP-Complete problems are a class of problems where if one is easily solved then all of them can be easily solved. They are very difficult to solve though). For example, given a series of numbers, find the subset whose sum is the greatest. Short of attempting every possible combination of numbers, a solution is hard to find (programmers may chime in with 'dynamic programming' rolling off their tongue. But, that just stores intermediate results, all potential combinations are still evaluated.).
Back to encryption, if P = NP then there is a way to easily decrypt data. From what I read, a lot of things would become much easier.
But that is the essential nature of P = NP as far as I can tell for now. I might change my mind as I become more informed.
First, the types of texts that I've found either went deep into the topic (from the theoretical perspective) or brushed lightly upon it (the way a book on programming treats mathematics). I'll try to walk a fine line between both while maintaining clarity. Hopefully it works.
What are P and NP?
These have to do with timing. Not in seconds, but in 'effort'. For example, consider sorting books in a book-shelf. You could scan through the 'N' books to sort, find the smallest one (or whatever sorting criteria you want), and put it at the beginning of the shelf. This operation could be repeated for the remaining books. So, to sort 'N' books, you'd look at (on average) 'N/2' books to find the next one to place to the left of the shelf. That involves looking at 'N^(N/2)' books. In the big picture, we say 'N^N' (N to the N) operations will be needed. As the number of books increase, this method of sorting will be excruciatingly slow. It is left as an exercise to the reader to translate looking at book titles to actual time.
They also have something to do with 'polynomial time'. That is, a number that can be expressed in the form of 'N^x' where 'N' is the number of elements to work on and 'x' is a constant. Sorting books according to our previous example takes much longer than polynomial time (think of very large 'N').
P looks at problems that take polynomial time. Specifically, deterministic problems. Typically involving Turing machines (but I don't want to go into the details of tapes). Essentially, any problem whose solution expressed as a series of unambiguous steps takes polynomial time is in P.
And NP also looks at problems that take polynomial time. This time, problems whose solution is expressed non-deterministically. Back to our book sorting problem, we looked at 'N/2' books (on average) to find the next book to place on the shelf. But what if we just 'looked at all the books at once' and happened to pick the right one. Something similar goes on with 'Oracle machines'. However, NP is easier to understand as the time it takes to verify the problem. In other words, our book sorting would take 'N' time in non-deterministic polynomial time (NP-time)
And why is P versus NP important?
The crux of the problem: are all the problems in NP also part of P? Essentially, NP problems are easy to verify but can be hard to compute. Like our sorting problem, we only need to inspect each book once to confirm that they are sorted. Similar ideas are used in cryptography -- a very difficult problem must be solved by the person who attempts to intercept the message.
Problems in P are those that are practically solvable (well, practically this is debatable, theoretically this is true). There are problems that are much more difficult. Let's call these NP-Complete (ok, technically NP-Complete problems are a class of problems where if one is easily solved then all of them can be easily solved. They are very difficult to solve though). For example, given a series of numbers, find the subset whose sum is the greatest. Short of attempting every possible combination of numbers, a solution is hard to find (programmers may chime in with 'dynamic programming' rolling off their tongue. But, that just stores intermediate results, all potential combinations are still evaluated.).
Back to encryption, if P = NP then there is a way to easily decrypt data. From what I read, a lot of things would become much easier.
But that is the essential nature of P = NP as far as I can tell for now. I might change my mind as I become more informed.
Subscribe to:
Posts (Atom)