Play Atari 2600 Games for Science

glogoGames offer a predictable controlled environment to develop and test artificial intelligence algorithms. Tic-tac-toe is usually the first adversarial game people learned when young, and so is ideal for a class teaching the basics of writing game playing algorithms. Advanced algorithms tackle playing timeless games like Chess and Go.

While those games are extremely challenging, they fail to represent many of the tasks that are interesting to pursue in artificial intelligence research. For some of these research areas, researchers turn to video games.

I’ve seen research results presented for playing various classic Atari 2600 arcade games. One example was when Google’s DeepMind research algorithm played Breakout in a super efficient and very non-human way by hitting the bricks from behind the wall.

What I hadn’t realized until today was that there’s a whole infrastructure built up for this type of research. Anybody who wishes to dip their toes in this field (or dive in head first) would not have to recreate everything from scratch.

This infrastructure for putting AI at the controls of an Atari 2600 is available via the Arcade Learning Environment, based on a game emulator and making all the inputs and outputs available in a program-friendly (instead of human-friendly) manner. I learned of this while reading about Maluuba’s announcement of their Hybrid-Reward Architecture. They applied their system to an algorithm that learned how to get the maximum score in Ms. Pac-Man.

And if getting ALE from Github is still too much work to set up, people can go to places like the OpenAI gym which has built entire algorithm training environments. All it takes is a working knowledge of Python to access everything that is available.

I’m impressed how barriers to entry have been removed for anybody interested in getting into this field of AI research. The only hard parts left are… well, the actual hard parts of algorithm design.

 

Plastic Bottle Upcycling with TrussFab

csm_chair_FEA-nolable-02_ea4ad9b60f
Image from TrussFab.

A perpetual limitation of 3D printing is the print volume of the 3D printer. Any creations larger than that volume must necessarily consist of multiple pieces joined together in some way. My Luggable PC project is built from 3D printed pieces (each piece limited in size by the print volume) mounted on a skeleton of aluminum extrusions.

Aluminum extrusions are quite economical for the precision and flexibility they offer, but such capabilities aren’t always necessary for a project. Less expensive construction materials are available offering varying levels of construction flexibility, strength, and precision depending on the specific requirements of the project.

For the researchers behind TrussFab, they chose to utilize the ubiquitous plastic beverage bottle as structural component. Mass produced to exact specifications, the overall size is predictable and topped by a bottle cap mechanism necessarily precise to seal the contents of the bottle. And best of all, empty bottles that have successfully served their primary mission of beverage delivery are easily available at quantity.

These bottles are very strong in specific ways but quite weak in others. TrussFab leverages their strength and avoids their weakness by building them into truss structures. The software calculates the geometry required at the joints of the trusses and generates STL files for them to be 3D printed. The results are human-scale structures with the arbitrary shape flexibility of 3D printing made possible within the (relatively) tiny volume of a 3D printer.

Presented recently at ACM CHI’17 (Association for Computing Machinery, conference for Computer-Human Interaction 2017) the biggest frustration with TrussFab is that the software is not yet generally available for hobbyists to play with. In the meantime, their project page has links to a few generated structures on Thingiverse and a YouTube video.

 

Thread Tapping Failure and Heat-Set Threaded Inserts

Part of the design for PEM1 (portable external monitor version 1.0) was a VESA-standard 100 x 100mm pattern to be tapped with M5 thread. This way I can mount it on an existing monitor stand and avoid having to design a stand for it.

I had hand tapped many M5 threads in 3D printed plastic for the Luggable PC project, so I anticipated little difficulty here. I was surprised when I pulled the manual tapping tool away from one of the four mounting holes and realized I had destroyed the thread. Out of four holes in the mounting pattern, two were usable, one was marginal, one was unusable.

AcrylicTappedThreads
Right: usable #6-32 thread for circuit board standoff. Left: Unusable M5 thread for VESA 100 monitor mount.

A little debugging pointed to laser-cutting too small of a hole for the tapping tool. But still the fact remains tapping threads in plastic is time-consuming and error-prone. I think it is a good time to pause the project and learn: What can we do instead?

One answer was literally sitting right in front of me: the carcass of the laptop I had disassembled to extract the LCD panel. Dell laptop cases are made from plastic, and the case screws (mostly M2.5) fasten into small metal threaded inserts that were heat-set into the plastic.

Different plastics have different behavior, so I thought I should experiment with heat-set inserts in acrylic before buying them in quantity. It doesn’t have to be M5 – just something to get a feel of the behavior of the mechanism. Where can I get my hands on some inserts? The answer is again in the laptop carcass: well, there’s some right here!

Attempting to extract an insert by brute force instead served as an unplanned demonstration of the mechanical strength of a properly installed heat-set insert. That little thing put up quite a fight against departing from its assigned post.

But if heat helped soften the insert for installation, perhaps heat can help soften the plastic for extraction. And indeed, heat did. A soldering iron helped made it far easier to salvage the inserts from the laptop chassis for experimentation.

See World(s) Online

NASALogoOne of the longest tenure items on my “To-Do” exploration is to get the hang of the Google Earth API and learn how to create a web app around it. This was very exciting web technology when Google seemed to be moving Google Earth from a standalone application to a web-based solution. Unfortunately its web architecture was based around browser plug-ins which eventually lead to its death.

It made sense for Google Earth functionality to be folded into Google Maps, but that seemed to be a slow process of assimilation. It never occurred to me that there are other alternatives out there until I stumbled across a talk about NASA’s World Wind project. (A hands-on activity, too, with a sample project to play with.) The “Web World Wind” component of the project is a WebGL library for geo-spatial applications, which makes me excited about its potential for fun projects.

The Java edition of World Wind has (or at least used to) have functionality beyond our planet Earth. There were ways to have it display data sets from our moon or from Mars. Sadly the web edition has yet to pick up that functionality.

JPL does currently expose a lot of Mars information in a web-browser accessible form on the Mars Trek site. According to the speaker of my talk, it was not built on World Wind. He believes it was built on Cesium, another WebGL library for global data visualization.

I thought there was only Google Earth, and now I know there are at least two other alternatives. Happiness.

The speaker of the talk is currently working in the JPL Ops Lab on the OnSight project, helping planetary scientists collaborate on Mars research using Microsoft’s Hololens for virtual presence on Mars. That sounds like an awesome job.

The Cost for Security

In the seemingly never-ending bad news of security breaches, a recurring theme is “they knew how to prevent this, but they didn’t.” Usually in the form of editorializing condemning people as penny-pinching misers caring more about their operating cost than the customer.

The accusations may or may not be true, it’s hard to tell without the other side of the story. What’s unarguably true is that security has some cost. Performing encryption obviously takes more work than not doing any! But how expensive is that cost? Reports range wildly anywhere from less than 5% to over 50%, and it likely depends on the specific situations involved as well.

I really had no idea of the cost until I stumbled across the topic in the course of my own Rails self-education project.

I had designed my Rails project with an eye towards security. The Google ID login token is validated against Google certificates, and the resulting ID is salted and hashed for storage. The code for this added security were deceptively minor, as they triggered huge amounts of work behind the scenes!

I started on this investigation because I noticed my Rails test suite ran quite slowly. Running the test suite for the Rails Tutorial sample app, the test framework ran through ~120 assertions per second. My own project test suite ran at a snail’s pace of ~12 assertions/second, 10% of the speed. What’s slowing things down so much? A few hours of experimentation and investigation pointed the finger at the encryption measures.

Obviously security is good for the production environment and should not be altered. However, for the purposes of development & test, I could weaken them because there would be no actual user data to protect. After I made a change to bypass some code and reducing complexity in others, my test suite speed rose to the expected >100 assertions/sec.

Granted, this is only an amateur at work and I’m probably making other mistakes doing security inefficiently. But as a lesson to experience “Security Has A Cost” firsthand it is eye-opening to find a 1000% performance penalty.

For a small practice exercise app like mine, where I only expect a handful of users, this is not a problem. But for a high-traffic site, having to pay ten times the cost would be the difference between making or breaking a business.

While I still don’t agree with the decisions that lead up to security breaches, at least now I have a better idea of the other side of the story.

Limiting Google Client ID Exposure

google-sign-inToday’s educational topic: the varying levels of secrecy around cloud API access.

In the previous experiment with AWS, things were relatively straightforward: The bucket name is going to be public, all the access information are secret, and none of them are ever exposed to the user. Nor are they checked into the source code. They are set directly on the Heroku server as environment variables.

Implementing a web site using Google Identity got into a murky in-between for the piece of information known as the client ID. Due to how the OAuth system is designed, the client ID has to be sent to the user’s web browser. Google’s primary example exposed it as a HTML <meta> tag.

The fact the client ID is publicly visible led me to believe the client ID is not something I needed to protect, so I had merrily hard-coded it into my source and checked it into Github.

Oops! According to this section of the Google Developer Terms of Service document, that was bad. See the sections I highlighted in bold:

Developer credentials (such as passwords, keys, and client IDs) are intended to be used by you and identify your API Client. You will keep your credentials confidential and make reasonable efforts to prevent and discourage other API Clients from using your credentials. Developer credentials may not be embedded in open source projects.

Looks like we have a “secret but not secret” level going on: while the system architecture requires that the client ID be visible to an user logging on to my site, as a developer I am still expected to keep it secret from anybody just browsing code online.

How bad was this mistake? As far as security goofs go, this was thankfully benign. On the Google developer console, the client ID is restricted to a specific set of URIs. Another web site trying to use the same client ID will get an error:

google-uri-mismatch

IP addresses can be spoofed, of course, but this mitigation makes abuse more difficult.

After this very instructional detour, I updated my project’s server-side and client-side code to retrieve the client ID from an environment variable. The app will still end up sending the client ID in clear text to the user’s web browser, but at least it isn’t in plain sight searchable on Github.

And to close everything out, I also went into the Google developer console to revoke the exposed client ID, so it can no longer be used by anybody.

Lesson learned, moving on…

Behavior Driven Development

cucumberlogoMy new concept of the day: Behavior Driven Development. As this beginner understands the concept, the ideal is that the plain-English customer demands on the software is formalized just enough to make it a part of automated testing. In hindsight, a perfectly logical extension of Test-Driven Development concepts, which started as QA demands on software treated as the horse instead of the cart. I think BDD can be a pretty fantastic concept, but I haven’t seen enough to decide if I like the current state of the art in execution.

I stumbled into this entirely by accident. As a follow-up to the Rails Tutorial project, I took a closer look at one corner of the sample app. The image upload feature of the sample app used a gem called carrierwave uploader to do most of the work. In the context of the tutorial, CarrierWave was a magic black box that was pulled in and used without much explanation. I wanted to better understand the features (and limitations) of CarrierWave for use (or not) in my own projects.

As is typical of open-source projects, the documentation that exists is relatively thin and occasionally backed by the disclaimer “for more details, see source code.” I prefer better documentation up front but I thought: whatever, I’m a programmer, I can handle code spelunking. It should be a good exercise anyway.

Since I was exploring, I decided to poke my head into the first (alphabetically sorted) directory : /features/. And I was immediately puzzled by the files I read. The language is too formal to be conversational English for human beings, but too informal to be a programming language as I knew one. Some amount of Google-assisted research led me to the web site for Cucumber, the BDD tool used by the developers of CarrierWave.

That journey was fun, illuminating, and I haven’t even learned anything about CarrierWave itself yet!

Cache is King

15Puzzle

C is an old familiar friend, so it is not part of my “new toolbox” push, but I went back to it for a bit of refresher for old time’s sake. The exercise is also an old friend – solving the 15-puzzle. The sliding tile puzzle is a problem space that I studied a lot in college looking for interesting things around heuristic search.

For nostalgia’s sake, I rewrote a textbook puzzle solver in C using the iterative-deepening A* (IDA*) algorithm employing the Manhattan Distance heuristic. It rubbed off some rust and also let me see how much faster modern computers are. It used to be: most puzzles would take minutes, and the worst case would take over a week. Now most puzzles are solved in seconds, and the worst case topped out at “merely” few tens of hours.

Looking to further improve performance, I looked online for advances in heuristics research since the time I graduated and found several. I decided to implement one of them named “Walking Distance” by the person credited with devising it, Ken’ichiro Takahashi.

From the perspective of algorithmic effectiveness, Walking Distance is a tremendous improvement over Manhattan Distance. It is a far more accurate estimate of solution length. Solving the sliding tile puzzle with the Walking Distance eliminated over 90% of duplicated work within IDA*.

On paper, then, Walking Distance should be many orders of magnitude faster… but my implementation was not. Surprised, I dug into what’s going on and I think I know the answer: CPU cache. The Manhattan Distance algorithm and lookup table all would easily fit within the 256kb L2 cache of my Intel microprocessor. (It might even fit in L1.) The Walking Distance data structures would not fit and would spill into the much-slower L3 cache. (Or possibly even main memory.) It also takes more logical operations to perform a table lookup with Walking Distance, but I believe that is less important than the location of the lookup table themselves.

In any case: with my implementation and running on my computer, it takes about 225 processor cycles to examine a node with Manhattan Distance. In contrast, a Walking Distance node averages over 81 thousand cycles. That’s 363 times longer!

Fortunately, the author was not blind to this. While building the Walking Distance lookup table, Takahashi also built a table that tracks how one lookup state transitions to another in response to a tile move. This meant we perform the full Walking Distance calculation only on startup. After the initial calculation, the updates are very fast using the transition link table, effectively a cache of Walking Distance computation.

Takahashi also incorporated the Inversion Distance heuristic as support. Sometimes the inversion count is higher than the walking distance, and we can use whichever is higher. Like walking distance, there’s also a set of optimization so the updates are faster than a full calculation.

Lastly, I realized that I neglected to compile with the most aggressive optimization settings. With it, the Manhattan Distance implementation dropped from ~225 cycles down to ~75 cycles per node.

Walking Distance was much more drastic. By implementing lookup into the transition table cache, the per-node average dropped from 81 thousand cycles to ~207 cycles per node. With fully optimized code, that dropped further to ~52 cycles per node. Fewer cycles per node, and only having to explore < 10% of the nodes, makes Walking Distance a huge winner over Manhattan Distance. One test case that took tens of hours with Manhattan Distance takes tens of minutes with Walking Distance.

That was a fun exercise in low level C programming, a good change of pace from the high-level web tools.

For the curious, the code for this exercise is up on Github, under the /C/ subdirectory.

Minor Derailment Due To Infrastructure

One of the reasons I put Node.js education on hold and started with Ruby on Rails is because of my existing account at Dreamhost. Their least expensive shared hosting plan does not support Node.js applications. It does support Ruby on Rails, PHP, and a few others, so I started learning about Ruby on Rails instead.

The officially supported version of Ruby (and associated Ruby on Rails) is very old, but their customer support wiki assured me it could be updated via RVM. However, it wasn’t until I paid money and got into the control panel did I learn RVM is not supported on their shared hosting plan.

RVM Requires VPS

At this point I feel like the victim of a bait-and-switch…

So if I want to work with a non-ancient version of Ruby on Rails (and I do) I must upgrade to a different plan. Their dedicated server option is out of the question due to expense, so it’s a choice between their managed Virtual Private Server option or a raw virtual machine via DreamCompute.

In either case, I didn’t need to pause my study of Node.js because it’d work on these more expensive plans. Still, Ruby is a much more pleasant language than JavaScript. And Rails is a much better integrated stack than the free-wheeling Node.js. So it wasn’t all loss.

Before I plunk down more money, though, I think I should look into PHP. It was one of the alternatives to Ruby when I learned NodeJS wasn’t supported on Dreamhost shared hosting. It is the server-side technology available to Dreamhost shared hosting, fully managed and kept up to date. Or at least I think it is! Maybe I’ll learn differently as I get into it… again.

Dreamhost offers a 97-day satisfaction guarantee. I can probably use that to get off of shared hosting and move on to VPS. It’s also a chance find out if their customer service department is any good.

UPDATE 1: Dreamhost allowed me to cancel my hosting plan and refunded my money, zero fuss. Two clicks on the web control panel (plus two more to confirm) and the refund was done. This is pretty fantastic.

UPDATE 2: I found Heroku, a PaaS service that caters to developers working in Rails and other related web technologies. (It started with Ruby on Rails then expanded from there.) For trial and experimentation purposes, there is a free tier of Heroku I can use, and I shall.

Neural network in JavaScript

When I was first introduced to neural networks, they were considered algorithms with extremely expensive computational requirements. Even the most trivial network required a high-end PC with lots of memory and floating-point math capability.

Of course, at the time a high-end PC processor ran at 90 megahertz, 32 megabytes of RAM is considered a lot, and floating point math required a separate (and expensive) floating-point co-processor.

Now the cell phones we have in our pockets have faster processor and more memory than those powerful PCs of old. Every current processor has floating-point math capability, no extra chip required.

Which means what used to be the domain of specialized programmers, running on expensive hardware, is now possible everywhere: running in a web browser like the TensorFlow playground.

But it’s still hard for a human to grasp what’s going on inside a neural network as it learns and adjusts. While the accessibility of the technology (meaning how easy it is to obtain) has improved, the accessibility of the knowledge (meaning how easy it is to understand) hasn’t.

Computer brains have made great advances in the past years…

Human brains have not.