Wednesday, November 02, 2011

Using collaborative diffusion rather than path finding for the Google AI ant challenge.

For the 2011 Google Ants AI Challenge rather than doing the typical solution of choosing direction for each ant based upon the shortest path to some goal I used a diffusion based approach which was simpler, faster to code and resulted in some nice emergent behavior with very little work.


A while back I read the paper Collaborative Diffusion: Programming Antiobjects.  The 2011 Ants AI Challenge seemed like a perfect test for it.  Rather than having each ant, hill, water etc be its own object, the map is the only object.  The map computes the diffusion values for agents (such as food and searching) on each square and then each decide where to have each ant go not based upon any path finding algorithm, but simply based upon the diffusion values surrounding the square.

Each square on the board has several agents or diffused values (food, explore, hill, etc).  On every turn the program would loop through the map setting or diffusing all of the squares and then loop through the ants using the diffused values at the ant's square and some very basic logic to decide which way the ant should move.

When running it against the test bots even the simplest version would get neat emergent behavior such as in a maze when two ants follow each other down a hall when they reach a fork they will naturally go separate ways or when there are five bad guys against the one good guy the diffusion value wont say to attack until you have six guys.

The two simplest things ants want to do are get food and explore.  To make the ants go after food we first have to diffuse the food value and then have the ants go to the neighboring square with the highest FOOD value.

A snippet of slightly modified code from my diffusion function which is run on each square on the map.

void Map::diffusion(int r, int c) {
    std::vector goalsToDiffuse;

    Square *square = &grid[r][c];
    // water blocks everything
    if (square->isWater) {
        square->agents[EXPLORE] = 0;
        square->agents[FOOD] = 0;
            return;
    }


    // FOOD
    if (square->isFood) {
        square->agents[FOOD] = INT_MAX;
    } else {
        goalsToDiffuse.push_back(FOOD);
    }


    // EXPLORE
    if (!square->isVisible) {
        square->agents[EXPLORE] = INT_MAX - ((200 - square->lastSeen) * 300);
    } else {
        goalsToDiffuse.push_back(EXPLORE);
    }


    ...

        foreach (goal,  goalsToDiffuse) {

        double up = upSquare->agents[goal];
        ...
        square->agents[goal] = 0.25 * (up + down + left + right);
    }


To diffuse food when a square is water it should set the food diffused value to 0 so ants never want to go into the water when looking for food, otherwise when a square has food set the food diffused value to a large value.  This large value is the final goal for the ants.  Lastly if we are not water nor food we simply diffused value to the diffusion value of the neighboring squares.  

To diffuse exploration I include in the information of when we last saw the square into the diffusion value so my ants always go to the part of the map that has been least explored and where they can potentially find hills.  This prevents them from bouncing up and down, but always moving forward.


After diffusing you want to output the moves.  This is where the real logic comes into play.  My first version was similar to the following pseudo code:


foreach(ant, myants) {
    food = valueOfFoodAt(ant);
    if (food != 0)
        goal = FOOD;
    else
        goal = EXPLORE;
    outputMove(ant, goal);
}


outputMove will chose the neighboring square (N, S, E, W) with the highest goal value.  In effect the ants will move to the food/explore/hill/etc via the shortest route.


The results are are fun to watch and with just the above code the ants will explore maps of any shape be it mazes or open lands eating up food and and as more and more ants are born they will naturally separate across the board waiting for new food to appear always moving to the squares that it saw least recently.  Adding a HILL to the above diffusion would be similar to FOOD, and the logic for the ant movement is as simple as giving it a higher precedence than FOOD.  And once the diffused HILL value reaches the ants again the map doesn't matter be it a maze or open land, the ants will march to the hill via the shortest route.

The diffusion approach to the ant problem was simple to code (no shortest path algorithms) and I was able to get the first version up and working in about an hour.  The runtime is O(rows*cols) (notice it isn't dependent upon the number of ants), the cpu time is extremely small compared to other solutions, and the memory overhead is pretty much non-existant compared to other solutions.

Given both the ease at which this is implemented and the small number of lines it would be nice if a basic diffusion based solution with goals for food, explore and hill were included with the stock python bots that the aichallenge package includes.  It would be both a great starting point for making more advanced diffusion bots and as a stronger test bot, but one that still used very little cpu.

Anti-objects are a neat concept that I don't hear too much about and something I wish I had explored sooner.  If I was introducing someone to programming the ants problem combined with a diffusion solution would definitely be a small effort, huge reward way to go.  The simplicity of the algorithm combined with the low memory and cpu overhead also was an aspect that I had not looked at before and could probably be utilized to make some great cheap behavior for AI in games, demos and other places.

Sunday, October 16, 2011

The coming IT cloud revolution

Corporate IT departments will soon fail to exists as we know them today.  Any useful service that can exist on the internet will eventually be moved there.  IT departments that cling to systems that they maintain and will only be harming their company.  Companies that provide services on the internet that IT departments provide today will grow and prosper.

More than a decade ago when the KDE project was born a small group of individuals setup the necessary resources so the project could succeed.  The most important bit was the cvs server, where the source code actually lived.  But on top of that were countless other services such as a bug tracker, web servers, mailinglist server and more.  Part of the success of KDE was these services.  They were not just for one application, but they were setup in such as a way that if a young energetic developer wanted to contribute a new library or application it could be easily assimilated without the need for him to setup all of the services himself.  In trade for following the KDE way the application got fame, contributions and a host of services.

But there will never be another project like KDE and what allowed KDE to flourish and grow in the early days was one of the reasons I stopped contributed to it1.  For the past half a decade there have been more and more online services.  Today that same young developer wouldn't add his application to the KDE ecosystem when he could use any number of online services such as GitHub, Gitorious, SourceForce, GoogleCode, and the various Google apps.

A few weeks ago Jason over at 37signals wrote a blog about sneaking into the fortune 500.  It has been rattling around in my head ever sense.  In 2010 I created a GitHub clone called GitHaven for corporations intranet, but while there was interest and money in GitHub:Fi it is pennies compared to GitHub.com.  Chatting with a startup recently we were discussing how they were using GitHub, Dropbox and probably would use GoogleApps for email.  Just like services for open source projects there was now general services that startups have been taking advantage of and while they were kicking and screaming corporations were starting to use online tools too.

Five years ago there was a mad dash to create an online version of office.  While it didn't take off a quickly as so many predicted (it is still a success) the corporate version of GMail did what no one had been able to do for more than a decade, replace Exchange as the choice for mail server.  Once you can replace Exchange you can replace anything.

We are at the mist of a land grab for some extremely valuable property.  Anything generic that was once done by corporate IT departments will be moved to the web.  This means that IT departments will be shortly be going under a revolution and those companies that provide IT services could be very profitable as they scale services across many companies.

1 When I started developing my web browser Arora in 2007 I put my code on GitHub and used GoogleCode for the bugtracker, wiki (GitHub didn't have either of these back then), website, and Google groups for the mailinglist. There was no value in joining KDE's infrastructure and I saw being forced to use kdelibs as a downside as my application could no longer be distributed on Windows or OSX, the KDE release cycle was too long for my application, and to top it off while KDE had been one of the first groups to switch to SVN from CVS earlier in the decade it was not making the leap to Git in any hurried pace (they have sense switched).

Sunday, October 09, 2011

GitHaven

I am pleased to finally announce GitHaven which is a web interface for managing Git repositories.

GitHaven was created out of the need to be installed behind a firewall inside a corporate intranet or for personal use at home. GitHaven is packaged as a Debian package so it is extremely easy to install and keep updated.

Besides being open source the one feature that GitHaven has the GitHub doesn't is the ability to add top level tabs.  So if you want a tab called "Wiki" and it points to your wikipedia entry the Admin can add it.  This allows you to easily incorporate with other tools (mostly bugtrackers which are often Jira, Bugzilla or other)

While I still use it for my own personal use I am no longer permitted to develop GitHaven so it has been released under the AGPL in the hope that it can be useful for others.

Monday, April 11, 2011

Programming tool: The whiteboard marker

All through my programming career I have had a whiteboard, but beyond simply making sure I had one I have never thought much more about it. Recently I picked up a set of whiteboard markers that surprisingly made me more productive.

Back in college me and a friend went to Home Depot and picked up a 4x8 sheet of bathroom melamine for $16. This is like normal whiteboard melamine, only slightly thiner and sold to a different demographic that buys it by the sheet and not by the inch. Cut in half we for a grant total for $8 we each had a very large whiteboard. To go with the cheap whiteboard I would often grab the cheapest set of markers at the store (usually a set of four Expo's) and think nothing more about it.

Last week when looking for some more markers I stumbled across this set of low odor ultra fine whiteboard markers with eraser for a grand total of $8.99.
A number of very interesting selling points that convinced me to buy it. Here is a shot of one of the new markers next to one of the normal fat expo markers.



Over the years I have worked at a number of different companies all around the world, but they all had the same big Expo markers. I have used thin expo markers, but these were usually the cheapest ones bundled with small whiteboard that never worked very well. Between those experiences I never questioned if there was something better out there beyond the fat Expo markers. That is until now and after using these new markers for only a few days I know I can never go back.

The four features that sold me on these markers:

Eraser On the cap is a small eraser so when you make a small mistake you just flip the pen over and erase it. No more hunting for the eraser as it can causes you to take your eyes off of the code and loose your train of thought. The little eraser can also cleanly erase small lines, letters and words while using the big eraser often results in a mess.

Low Oder A small thing sure, but after any long time of thinking and drawing on a whiteboard a headache is the last thing you want.

Grip Another small thing, but having a rubber grip is way more comfortable when writing on a board for more than a few minutes (let alone multiple hours).

Fine tip With a fine tip you can simply fit more "stuff" on the whiteboard. Whether your whiteboard is 8x4 or as many offices have, only 2x3, space really matters. With a chiseled tip you end up writing in a larger font size in order to make it more legible (or is it the same size but bolded?). This results in taking up more vertical and horizontal space.

When standing up and writing on a board there is a vertical zone that a person can write best in. Outside of that zone your arm and wrist and not optimally placed resulting in sloppy handwriting or crouching down.* Using the fine tip I use less vertical space per line and can write more in this legible zone.

I did a test this morning writing out a binary search function using the fat (blue) and thin (blue) markers (click on the image to zoom). I tried to ignore the other side and just wrote whatever was comfortable. For horizontal comparison there is a red mark on the left hand side which shows where the width of the blue function would end. When viewing the image also notice how some of the loops in the e's written with the fat tip become a blob v.s. with the thin tip. Reading code written with the thin tip is just easier.



When talking about programmer tools usually compilers, debuggers and editors are the first things that come to mind. Asking some more you might hear about multiple monitors and chairs, but I have never heard whiteboard markers listed. At $8.99 this is one of the cheapest ways I have improved my productivity in a long time.

*Or mount your whiteboard on tracks so you can raise/lower it.

Thursday, March 17, 2011

Tablet TV Games

1) A lot of people have smart phone and some have tablets.
2) A lot of people today can browse the web on their TV. This is done via an internet enabled TV, an attached box like a Wii, XBox, boxee, or something else.

Both of the above will only be increasing as time goes by. What major unique situations does this present that has not been seen before and how can it be taken advantage of?

1) Each user has a screen that can be private while still being in the same room.
2) Not locked into only 2 or 4 players on split screen, how about 20 or 400 people?

Some other minor attributes of this type of setup:
- There is a common screen + sound device
- In person communication / same room BUT users can go to another room to discuss if needed and still have their controllers / private screens
- System can also involve some physical objects due to the fact that everyone is in the same house.

Some initial (mostly bad) ideas:

- Poker
- Football simulator (other person can't see what play you pick)
- Pictionary (pass around a device which people draw on which is shown on the screen)
- Each device is a first person car racing game, TV shows the track / location
- WW2 B52 Bomber simulator. Each tablet is a first person perspective of one of the jobs in the bomber. The TV would contain the radar etc requiring users look at the TV goes with the feel of the plane and the required real time communication works well.
- Multiplayer airport landing game (each ipad would control a set of planes and or airports and the TV would be a zoomed out view or the multiple airports)
- Any coop games where getting more people helps (chaos equals fun)
- Some turn based board games
- Presentation "software" (at is core tv + 1 controller)
- A Kitchen game where orders are shown on the tv and ach person is in charge of preparing part of orders. Lots of talking would hopefully result
- Train game where each person controls part of a subway/train system
- Snow plows. TV shows a city and each person drives a plow communicating where they are going to go to clear the snow.

Downsides:
- Sitting on a couch the tv is pretty far away so resolution isn't as good as a board to a board game one foot away
- controller screens are down in your lap, tv is up high, makes real time games a bit hard as they are on different eye levels.

Overall jumbled thoughts on this topic:

1) The distance to the TV from the users limits the usefulness of any game

Given the distance from the couch to the TV I wonder if for many games what is shown on the monitor could just as well be shown on the tables/smartphones. A monitor on the dining room table two feet away can provide a much bigger map than a TV 6 feet away. The monitor also solves the browser compatibility problem. The monitor could also display from an ipad etc. Also given that a TV doesn't have a touch screen the user has to some how interact with what is shown on the TV which results in some representation of the screen data also being shown on their device. More thought needed....

2) Private displays are the key, but when each user has a rich tablet display why not just skip the whole TV requirement and just make a bunch of co-op games for the ipad?

3) Barriers to entry on the TV
While TV's might have browsers it isn't the latest and greatest chrome. Much more likely to find an older opera etc and slow javascript engines. Requiring everyone log into a site tvgames.com adds one more chance for people to not bother and do something else. Compared to ipad's that find each other with no user work required.

4) Tried before?
Back when the wii first got a browser a number of Wii browser games were in the news, why didn't that take off? Maybe all of those DVD games just get bought, but never played? Some Wii game sites on the first page of google show less then 400K hits in the past several years combined... ouch

Update: Looks like the Wii2 scheduled for 2012 will have some sort of touch screen. No doubt it will be able to take advantage of the above items.

Monday, February 21, 2011

Book Review: "Making Software : What Really Works, and Why We Believe It"


Last week I received Making Software : What Really Works, and Why We Believe It. From the first moment I heard about the book I couldn't get the idea out of my head. Throughout the years I have read many books and many more blogs discussing how X is better than Y, but here was a book that was going to go through listing what we really know with studies to back it up. Rather than just claiming office cubes are bad or pair programming is good the essays present research, evidence and credibility to what they are saying. I couldn't wait to read it.

Just a few of the many questions that it tries to answer:
  • How much time should you spend on a code review in one sitting?
  • Is there a limit to the number of LOC you can accurately review?
  • How much better/faster is pair programming?
  • Does using design patterns make software better?
  • Does test-driven development work as well as they say?
  • How much do languages matter?
  • What matters more: How far apart people are geographically, or how far apart they are in the org chart?
  • Can code metrics predict the number of bugs in a piece of software?
  • Which is better: offices or cubes?
  • Does code coverage predict the number of bugs that will be later found?
  • What is right/wrong with our bug tracking systems today?
  • Why are graduates so lost in their first job?
  • Many more...

Short trailer for "Making Software" by one of the two editors Greg Wilson:


The book is broken out into two somewhat different sections. The first eight chapters discuss "The Quest for Convincing Evidence". It presents the how and what to collect and lists some existing data that is available. It also talks about when to know your are convinced, how to get your ideas reviewed etc. I was sold on the book for the chapters 9-30 which each cover specific ideas/theories so found this first part a little annoying to wade through as I was unprepared, but it gave the book a solid foundation and set your expectations of what the rest of the book was made up of.

Starting at chapter 9 it is broken out into a number of different essay's each written by a different author. Go skim the Table of Contents for a complete list of chapters. I can bet you that there is at least one chapter you would be very interested in reading this very moment.

Disclaimer: Before getting into some of the results many (if not all) of the chapters had nice big disclaimers about all of the possible issues and places their data gathering or testing could have failed. Any of the below statements are my take away from reading the book and things I am going to do differently. And if anything the book very much encourages (and teaches) you how to generate your own data review/publish your results.

Chapter 11 on Conway's Corollary really drove home the point that software is social.
Any organization that designs a system (defined broadly) will produce a design whose structure is a copy of the organization's communication structure.
If you have a large number of modules and you wanted to know which one was the most buggy the best predictor is what module has been modified by the most number of groups in the company. Code coverage, testing, edits, code churn, dependencies, number of pre-release bugs etc all give lower precision. I would love to see a script that took in a git repo and outputted a org chart. Then you can compare it to the real org chart to discover where things are probably a complete mess. Communication structor, developers leaving, number of engineers working on a project are all discussed. But it isn't all bad. The chapter also discusses how you can exploit this to leverage the corollary.

Chapter 17 discussed pair programming which is something I have been debating trying to do and now I know I will. In one example cited while one person would take 10 hours to complete a task two people pair programming only 5 hours and 45 minutes, but the expected 10 hours. Not only does it take about half as long, but the resulting software was of higher quality and you get cross training in the process. They also discuss one v.s. two keyboards, experience levels and more.

Chapter 19 provides you with the evidence to convince your VP that you should go to offices, war rooms or some combination and get rid of your cubes. Don't just say you will be more productive, show him the chapter so he/she can read and decide for themselves.

Chapter 24's report on bug trackers was more interesting than I thought it might be. The biggest 'discovery' (in my opinion) found was that marking a bug as 'Duplicate' in a bug tracker causes data to be lost. The duplicate bug's often contained rich information that would have helped a programmer solve a task quicker, but by marking it as duplicate developers often don't see it. I would love to see bugzilla and other bug trackers get a Merge feature rather than Duplicate so reports are not lost.

Chapter 26 discusses how the problem many employers have with hiring collage graduates where they are not able to utilize them as quickly as they would hope. I have seen various thing tried, but wasn't sure what worked best. Microsoft tackled this by following around some new developers and wrote down every single thing they did. Like a UI review where you can only watch a user and can't say anything as they fumble around I was frustrated reading the reports of what the new developers did. They would get assigned to projects (not very well documented) working in groups (v.s. on their own like in school) using internal tools that they have never heard of. It is no surprise it takes some time to get up to speed and for the most part they were just really confused by a lot of things. Close mentoring and giving the mentor actual time to mentor is very important. The chapter includes more tips on changes companies can make.

Chapter 27 discusses how to look at your own code and evaluate it. After investigating some of my own open source projects it became clear that I need to do a better job of being able to distinguish what a change does, but even with just some basic dumb analysis on the repository it showed interesting results.

Chapter 28 "Copy-Paste as a Principled Engineering Tool" was very surprising to read. I have always been an advocate of the DRY principle, but never thought about it as much as they did. Here they take apart DRY and even break down and can classify DRY violations into different types and end up arguing that while many are bad a select few are good/necessary.

Chapter 29 is "How Usable Are Your APIs?" It tells the story of designing an API at Microsoft and just how very important it is and tips and tricks you can do. All throughout reading the chapter I kept thinking that if only the author had read The little manual of API design [pdf] it would have saved them a lot of work. If you haven't read the little pdf I highly recommend taking the next twenty minutes and going through it.

The book is filled with more more discussion points. Each chapter can be broken down and discussed in rich detail. There is so much in this book it is hard to give any sort of summary that does it justice. Each section comes backed by a ton of references so you can look up the data and not just take the authors word. The book reminds me of Diffusion Of Innovations which also reads a bit like a text book but is overflowing with information where whole books can be written on just one small part. Developers, Managers, Testers, Human Resource, the reach of those who can get value out of the book is large. There were a number of sections I held beliefs on and didn't think I would learn anything, other sections I was very curious to know what it might say and others that completely surprised me. This book now sits on my shelf next to Mythical Man Month (dare I say replaces it?). If you only read one technical book this year make it this one.

Edit: Some more links including a webinar discussion on third-bit.com.

Monday, January 17, 2011

Playboy for my birthday

This year for my birthday one of the presents from my wife was my first issue of Playboy. Not just any issue, but the November 1972 issue which contains the Lenna Sjööblom centerfold. A small portion of this centerfold is a very well known image in computer science. In 1973 Alexander Sawchuk tired of test lines and tv patterns grabbed a playboy from someone walking by and scanned the top 5.12 inches (the image seen on the right) to be used on a colleagues paper. This scan went on to be used in countless times in all sorts of image related research such as compression, watermarking, line detection and more. It is one of those images I have come across many times when reading papers.

Last year when watching Pawn Stars someone dropped off some boxes of Playboy's only to find out most of them were not worth anything and how the only issue that people want is #1. I made a comment to Jen about how the only issue I would want would be the one with the Lenna, explained its history and how it must be worth a lot because everyone knows about the Lenna image and reads image papers ... right? Jen secretly wrote that down and later on was able to find the issue, acquired it and stashed it away until my birthday. That issue was Playboys' best selling issue ever so it isn't rare at all and while it might not be the most valuable it is one cool birthday present to get from your wife.

Popular Posts