Astro log – Through the smog and light pollution

A month back I finally got a new stepper motor and got the tracking for my telescope working. One dark night I took it to a pretty dark spot close to Bergen and did some observations.

M42 – Orion Nebula

I have observed the Orion nebula under bad light pollution before, but this time I got to observe it with under better conditions. It was stunning. Very sharp.

The next day I took my first deep space photography ever from our apartment. The light pollution was really bad, and there was some smog as well. I also forgot that I could use a timed shot. So i think some blurring is due to the camera moving slightly after I started the exposure.

I think it turned out fine for a first:

M42 taken with a 5 – 10 seconds exposure. Very heavy light pollution. The left image is the raw image, the right ones are versions where i increased contrast and tried to remove the pollution. The latter is an attempt to make it look somewhat like what a visual observation of M42 looks like in my telescope (it is sharper when visually observed)

M1 – Crab Nebula

My original plan for the trip, was to observe M42 and the Andromeda Galaxy. I was also hoping to get to see the Flame Nebula since it was really dark. I sadly did not see any trace of the Flame Nebula so I started looking for some open clusters to look at in Taurus. While scanning for them I suddenly saw that the Crab Nebula was close, and I found it immediately. It is the first supernova remnant I have observed, and I think I saw some small amount of detail. Hoping to get a picture of it one of these days.

M31 and M110 – Andromeda Galaxy and a friend

Andromeda is a not that interesting to visually observe since it is so hard to see anything beyond the core. I think I saw some more since it was really dark, but it was very faint. These two are prime targets for a photo some day, since that should bring out some more detail.

Astro observation log

As a kid I was always very fascinated by astronomical objects. I vividly remember the first time I observed the Andromeda Galaxy in a pair of binoculars. I think I was around 14, and I had tried to find it several times before. I did not really know what it would look like in binoculars, and I remember freezing my hands off to keep it in view once I found it. Even if it was just a blurry blob it was amazing.

Fast forward 20 years, and I now have the knowledge, time and money to buy and use a telescope. I recently bought a 10 inch Dobsonian. I am still learning to to use it well, but it has so far been worth every NOK spent.

Last night was my first observing session with the telescope under not extremely badly light polluted skies. These are the objects I have observed so far.

M35 and NGC 2158 (Open cluster in Gemini)

M35 is huge, and looks great on low magnification. It was also not very hard to find by following the stars in Gemini. It would be useful with an even lower magnification eyepiece to observe this next time.

M37(Open cluster in Auriga)

Since it is far away from the closest clearly visible star, it was a bit hard to find even though it showed up pretty clear in the finderscope once I was in the right region.

M42 (Orion Nebula)

This is so far the only nebula I have been able to observe from the city. Sadly Orion was not visible when I observed in the less light polluted location. I have not yet tried filters for contrast, but M42 is still very visible, and it looks great. Looking forward to observe this with filters and less light pollution.

M13 (Hercules globular cluster)

M13 gave M42 a run for its money. M13 was easy to find (shows up clearly in the finder scope), and at low magnification it looked great. Increasing the magnification made it awesome. Suddenly thousands of starts exploded into view.

M65 and M66, part of the Leo Triplet

With the light pollution at the time, M65 and M66 were visible but with little detail. They were not visible in the finder scope, and I just randomly found them scanning from the stars in Leo. They pretty much both looked like Andromeda in binoculars. I am hoping to see some more structure next time.

I also observed some galaxy in Virgo, but I have no clue which. It seems the area is filled with galaxies, and I found one just scanning around. Pretty neat.

♥ Princesses versus giraffes ♥

TLDR; I’m writing a coop multiplayer game with my daughter, this is the current result! Works in Firefox and Chrome. Use arrows to move and space to fire. Share a URL to play with a friend.

Some years ago, my daughter figured out I made some computer games, and she even played one of them quite a bit. After a while she wanted something new, and we figured we’ll make a game together. She would draw concepts and come up with ideas, and I would try to make them happen in game.

The initial concepts she drew were these:

We then together made them into vector with some modifications.

Princess and "giraffe"
A princess and a giraffe… I guess

Tips on kid friendly vector drawing programs would be very much appreciated, throw me an email or post a comment. We used Sketch, but Sketch is a bit overwhelming and distracting with all its features. I want a program which only have bezier patches and transformations on them, as well as fill, stroke and possibly opacity settings.

Going from concepts to a prototype

I had been wanting to try compile to JS with Kotlin for a while, so I started a project in IntelliJ and quickly threw something together using a plain HTLM5 Canvas.

We drew some more concepts, and after some evenings implementing we had an infinite randomly generated castle, an arrow firing princess, a hyperactive bow carrying giraffe, and a bunch of collision detection bugs (yay for rolling your own).

Wriggling out of hard requirements

After a lot of fun triggering bugs, my daughter came up with some new requirements.

I want to play with my friends, and we should all be princesses!

These are sort of hard to implement, disregarding networking, it would mean a total rewrite of how the world generation and camera worked. It would also need a solution for how to avoid someone getting stuck due to the camera movement of others and so on.

Those giraffes are in for a surprise.

After some bargaining we made some new concepts, and we agreed to add a player controlled cloud, and a bunch of new giraffes.

Adding networking

For me this meant that I would need to add some kind of networking to the game. For browser games, the choices are:

  1. Communicate with a server using WebSocket and have that relay state, or run the game on the server.
  2. Negotiate a WebRTC datachannel, and send communication directly between the browsers.
  3. Have players install a browser extension like netcode.io,and use it instead of WebSocket.

Since the game is cooperative, there is little reason to run the game on a server. Actually I really, really do not want to run the game on server, for a bunch of reasons, mostly for abuse and scaling troubles.

Using a server as a relay of state or input is also a bit funky, since it will introduce a lot of unnecessary latency. Since I am also willing to sacrifice some poor kids behind a symmetric NAT, I decided for option 2 and I have not regretted that.

I was cautious about doing this initially, since I had read this Gaffer on Games post which deemed WebRTC too complex, though that was in the context of server based architectures.

Having some more experience with WebRTC now, I agree a bit about the complexity, though I think it has gotten way better, especially with a more stable standard and more complete alternative implementations like rawrtc. I also ♥ how WebRTC abstracts away most of the P2P complications behind a very nice API.

Autorative peer or GGPO?

To share state in the game, I needed to come up with an architecture for networking. Initially I evaluated using something like GGPO, but in the end I chose to go with using the princess peer as an autorative peer, and sync the state to the cloud playing peer continuously, while the cloud peer only sends input. I chose this mostly for simplicity and time constraints. Since the game is cooperative, a lack of fairness is also not really a problem.

For the amount of work i put in, I am very pleased with how the networking worked out. Right now it is not tuned at all, just JSON over the datachannel, but even without tuning and no extra speculative integration, it has worked fairly well.

Where to go from here.

While the game is in a state of continuous updates, I think it is mostly just going to be small changes from now on. Maybe some sound effects and new graphics when we feel like it.

Rendering is currently also quite slow, and takes a lot of the frame budget. I would like to migrate to a framework with a WebGL based renderer. But sadly that seems like quite a bit of work, mostly due to using SVGs for graphics.

For future projects game projects, I will for sure start with a WebGL based framework, or possibly Unity tiny, and raster based images.

That is all for now, go and see how far you can get in our game!

Solving Get1000 continued…

In one of my previous posts, I laid out a plan to solve the Get 1000 game. It turns out that plan was wrong.

My expectiminimax based solution works well for a game with random elements and perfect information, but it is not very useful for a game with imperfect information. Get1000 is played simultaneously by the players, and the opponents choices are hidden until the end of the game.

This meant I had to go back to find a new strategy for solving the game. I decided to try and find the correct brute force way first, and then see if that could be made faster in some way.

Exploring brute force

A solution to the game involves finding a Nash equilibrium from all the pure strategies of the game. A brute force solution could be done by creating a matrix where all pure strategies are pitted against all the other pure strategies.

The full payoff matrix needed for a normal form brute force solution.

A strategy here refers to a function S \rightarrow Pl which given any game state S gives a Get1000 placement Pl. Below is an illustration of what i mean by a state. A state could also include the history (order of placement), which would increase the count a lot, but that is hopefully not needed for a solution.

gamestate
A gamestate

A gamestate can be represented as the current number (in this case 1), the entries in hundres (7), tens (5) and ones (12) as well as the amount of free positions for hundreds (1), tens (2), ones(2).

The total amount of such states is 211248 but in at least 27648\cdot3 the choice is forced. This means there are at most. 211248 - 27648\cdot3 = 128304 relevant states, probably quite a bit fewer.


Each state has at most 3 choices, therefore there is an upper bound of M = 3^{128304} unique pure strategies.

This is of course not that helpful, since a 3^{128304}\times3^{128304} matrix is enormous, and for each cell in the matrix all possible 6^9 games would have to be played to find the payoff P for the pure strategy pairs. On top of that, the best mixed strategy would then have to be calculated.

Subgame perfection and backwards induction

Modeling this in normal form as above seemed to get me nowhere, I therefore turned to extensive form, and something called subgame-perfect nash equilibria, and backwards induction. In the normal form solution I need to look at all possible strategies. Using subgame perfection, I hoped to get away with only looking at a very small subset.

While this sounds straighforward in theory, I found it quite hard to figure out where my information sets are, and whether I could consider each choice node in Get1000 a subgame. After struggling for a while, I ended up with an extensive form structure looking like this. Players are P1 and P2, and “move by nature” is the dice roll.

Extensive form of a game with the same structure as Get1000. As players do their choices, the information sets get larger and larger. Since the “moves by nature” are known by all, they do not increase the information sets.

This structure means that only the roots of the tree are subgames, since all other nodes are part of larger information sets.

Attempting backwards induction

The above structure means that it is not practical to naively use subgame perfection and backwards induction to solve the game, but taking inspiration from it could still be useful to get a good strategy.

The algorithm for subgame perfection goes like this:

  1. Consider the final subgames (those with no further subgames), pick a Nash equilibrium as solution there.
  2. When considering the next subgames up the tree, the payoffs in the subgames already considered are used to create the payoff matrix.
  3. Iterate step 2 until the root node of the extensive form tree is reached.

To get something working, I pretend that the other player is at the same state as me always. This means I can only focus on the branches below that state. To keep memory in check i also recalculate payoffs instead of storing the result for each combination of states and games. The final algorithm I ended up with works like this:

  1. Consider the final subgames and pick a Nash equilibrium as solution.
  2. When looking at subgames higher up the tree, I use the choices (not payoffs) computed in 1, and use those choices to play out the game. Then I compare end results to get the payoff matrix for that subgame.
  3. As before, I iterate step 2 until I reach the root node.

This seems intuitively pretty reasonable.

Experimental results

The above method gives me a strategy that partly takes the imperfect information nature of the game into account. At many states it detected mixed strategies that had much higher payoffs compared to the pure versions. The strategies smashes all my previous best strategies by winning 1.75% more games.

The mixed strategy seems to play even more aggressively for results close to a 1000, and allowing heavy overshoot.

At this point, I was not really sure how to approach the game in a better way. In fact I was pretty ready to admin defeat for quite some time. Of course, immediately after i wrote that, I found this thesis, and this report.

Lots of new concepts to learn!

Scape – a very ninja scripting language


I made a small scripting language that runs in the browser. It is very ninja. To see the ninja, first open Javascript console and write:

function recur() {recur()};recur();

Hopefully it blew the stack. Then type this into the Scape REPL:

def recur() recur(); recur();

When you are convinced it will infinitely loop without blowing the stack, hit ctrl-c to stop further processing.

Rincewinds rave, that is black magic! Also called tail call elimination. Scape code is not evaluated by snarfing functions from Javascript (JS functions do not have tail call elimination before ECMAScript 6), but instead is compiled to its own set of instructions, which are then run on a stack machine (running in the Javascript VM). During parsing Scape functions are checked for whether they can use tail call elimination. If they can, they get different instructions that reuse the existing stack frame.

More magic

Scape has forward mode automatic differentiation as a language feature. Automatic differentiation allows you to compute the derivative of a function, without having to define the derivative explicitly.

Without automatic differentiation, this would be the way to compute the partial derivative of the function f(x,y) =  x^{2}y^{2} for x and y:

def fun(x,y) * (* x x) (* y y);
def diff_fun(x,y) [* (* 2 x) (* y y),* (* 2 y) (* x x)];
diff_fun(4,5);
[200, 160]

With automatic differentiation in Scape, this is how it is done:

def fun(x,y) * (* x x) (* y y);
diff(fun(4,5));
[200, 160]

This is very useful for a number of numerical methods involving derivatives. The feature is currently experimental, it might interact with non-double types in funky ways.

Wai?

Mostly just for fun. I also started toying with the idea to make a safe scripting language for use in networked games. A language and runtime that would allow the player to define custom logic during gameplay without being able to ruin the experience for other players.

A dream would be a personalized Starcraft where it is you and your custom control scripts versus the other player and his scripts.

I hope to create a simple real time multiplayer game to show how I imagine it working. For now, playing with the Scape REPL is the only way to try the language.

Sayōnara

Pear pram construction

My 3 year old daughter’s current favourite book is Jakob Martin Strid’s Den utrolige historien om den kjempestore pæra. In the story a giant pear is made hollow, and eventually turned into a boat. I decided to try and make a similar upright floating pear-boat out of a normal pear. One that my my daughter could play with once finished. Off I went to buy a pear and tools, the pear I ended up with have these specs:

  • Weighs around 238 g.
  • Displaces approximately 225 ml of water. This means it is slightly more dense then water since the weight of that water would be approximately 225 g.
  • Judging from the pears available in the shop, the one I chose was slightly more symmetric then most pears.

In addition to the pear, the tools I used are shown in the image below:

pear-tools
Pear, knife, melon baller (the MVT in pear pram construction), coins, thread.

The first step in pear pram creation, is to cut the windows using a knife. Once that is done carve out the inside using the melon baller. I recommend making the windows close to the top of the pear. If you make them too low they will result in water intake when launched. It is better to create the windows high initially and expand them downwards once you have a feeling for how the pear floats.

After carving out the core and flesh.
After carving out the core and flesh.

Another great reason for making the windows high up is lowering the center of mass. Pears have not yet been cultivated to float upright, and the center of mass is way too high for that. Having a too high center of mass on a ship is catastrophic. In its unmodified form a hollow pear will most likely perform worse then the Vasa on its maiden voyage.

To lower the center of mass even more, it is important to carve out as much as possible of the “roof”. Since the stalk extends into the pear this is difficult. It is easy to ruin the pear if you use too much force; be careful.

Even with the windows high up and a very light roof, the center of mass is still too high. Initially I added coins on the inside as ballast, this worked if I put the pear very carefully into the water, but it was still prone to capsizing.

Pear in bowl
Coins on a thread prevents capsizing. The pear is finally approved for transport of Lego men

To remedy this I moved the center of mass even lower by adding ballast on a thread below the pear. This was done by creating a knot on the thread and using a needle to get it through the bottom of the pear. Then the coins were added as shown in the picture. To ensure that water would not leak along the thread into the pear, I greased the entry points.

In its finished form the pear is quite stable, it could hold a surprising amount of Lego men without capsizing. I never got around  to test adding a sail, but I think it might be stable enough to support a small sail.

Sadly rot is an inevitability facing all pear prams. If you have a great idea for prolonging pear pram life, please leave a comment.

 

 

Superb toy!

This toy is incredible. It is reasonably easy to construct things, while still providing a challenge once you get the basics. It is suitable for nearly all ages. It says 3+ but if you remove the smaller parts it is suitable for much younger children even though they might just enjoy tearing down your constructs. The absurd thing is that when they do, you wont hesitate to make another one, since building these are way too much fun.

WEDGiTS
WEDGiTS