Thursday, January 31, 2019

Is AlphaStar what intuition without reason looks like?

Deepmind, a group owned by Google, has been making waves recently with their game playing AIs.  First there was the one that taught itself to play Atari games.  Then, most famously, they created AlphaGo which went on to beat the world champion at Go.  That really generated waves since nobody had been expecting a computer to crack Go any time soon.  They've also done a few other things such as figuring out what shapes proteins fold into just from their chemical composition.

Last Thursday they revealed their newest creation, AlphaStar the Starcraft 2 playing bot.  Starcraft 2 is the sequel to a game I played way back in high school.  It's an example of what is called a realtime strategy game or RTS.  The way these work is that you have a bunch of soldiers or other forces which you use to fight your opponent.  But at the same time you have other units under your command that can gather resources which you can use to create more units.  So you have to make tradeoffs between creating more resource gatherers to help you in the long run or more fighting units to help you right now.  And since you build your army as the game progresses you have to decide on its composition which will hopefully perform well against your opponent's composition.  Your giving orders to all your units in real time, your worker might be in the middle of gathering resources when you say "Hey, build this building there" and then it starts doing that instead.  Also, the way these generally work is that you can't see the entire map at once but only those places where your units can see, so there's an aspect of scouting out what your opponent is doing and also preventing them from scouting what you're doing.

All of this is very different from a game like Go or Chess where the entire board is known and the players take turns moving.

All this raises the question of how AlphaStar works.  The team has written a blog entry about this but it doesn't shed a whole lot of light.  We know that it uses a deep neural network like AlphaGo did and we know that it decides on a variable amount of time to wait between actions.  More information will presumably be available when they publish their journal paper but I'm going to go and do some speculation here.

AlphaGo was a combination of a deep neural network and an alpha beta search.  The way an alpha beta search works is that, at the top level you look at all the possible moves you can make and choose the one that gives you the best result.  How do you know which one gives the best result?  Well, for the board after each move you run an alpha-beta search from your opponent's position after you have made that move and assume that they make the best move from their position.  In chess you look at each of the dozen or so possible moves you could make, look at the dozen moves your opponent could make from each for 144 total, look at the dozen you could make in response to each of those for 1728 position total...  If you hit a victory condition for you or your opponent you can stop searching but usually the exponential explosion of possibilities will overwhelm the computer before that happens.  So a simple way to do it is search to some depth and have some metric of who is ahead, like assigning point values to pieces and totaling those.  More sophisticated chess programs have more sophisticated ways of determining how good a given board position is.  They also have ways of guessing what the best move is and only considering sensible moves rather than exploring down every path to the same depth.

AlphaGo's big breakthrough was using expertly trained neural networks to decide how good a board position was and which moves seemed promising and were worth exploring.  Neural networks work very well for that sort of thing.

 But as far as I can tell AlphaStar works entirely with neural networks and doesn't have anything like the alpha beta framework that AlphaGo used.  That seems to have left it with some vulnerabilities of the sort that AlphaGo didn't have.  It won most of its games but in the final exhibition game the player who goes by the nickname MaNa was able to beat it.  Partially this was just good play but there was a window where AlphaStar had the upper hand and was sending its army to go and destroy MaNa's base.  MaNa, to prevent this, sent a couple of its units in a flying vehicle to go and harass AlphaStar's production buildings.  AlphaStar saw this and turned its bit army around to head off this threat.  Then MaNa loaded up these units into their transport and retreated and AlphaStar moved its army back to the attack.

So far, so typical of a high level Starcraft 2 game.  But then MaNa did the same thing and AlphaStar responded the same way.  And it happened a third time.  Then a fourth.  At this point a human player would have seen that this would keep happening and adjusted their play.  But AlphaStar was, in a very robotic way, incapable of seeing the pattern and gave MaNa enough time to create a counter to its army and lost when MaNa finally attacked.

In his book, Thinking, Fast and Slow, Daniel Kahneman describes two different systems that seem to coexist in each of our brains.  There's system 1 which is fast, automatic, frequent, emotional, stereotypic, and unconscious.  Then there's system 2 which is slow, effortful, infrequent, logical, calculating, conscious.  We use system 1 most of the time, to quote Kahneman "We think much less than we think we think" but we also use system 2 for many tasks. 

When I look at AlphaStar's performance in that game it looks like a system with a finely tuned intuition for which moves will be best at any given moment, a superbly trained system 1.  But at the same time it seems to utterly lack any reflective capability or abstract reasoning, which is to say a system 2.  AlphaGo had the framework of the alpha beta search to fall back on when intuition failed and so effectively had both but AlphaStar doesn't, rendering it vulnerable to humans who grasp its weakness.

Deep neural networks have taken the AI world by storm for good reason.  They seem to be able to duplicate basically anything a human system 1 can do.  But they can't substitute for system 2.  This is maybe a bit ironic since partial substitution for system 2 is what computers have historically been best at.  Still, it looks like we're at least one paradigm short of an AI that can fully replicate human intelligence.

Tuesday, January 1, 2019

Drones still need license plates

wrote earlier about how we need to figure out some way to give drones some equivalent of license plates to let their users be identified.  Anonymity is all fine and dandy online but far less so when someone is interacting with the real world.

Well, recently a drone shut down a major UK airport for a day.  Police were entirely unable to find out who was responsible.   Hopefully the manhunt will scare people off trying similar things in the future but, well, the person responsible did get away so maybe not.

Sunday, December 30, 2018

A new charity for 2018

I'd previously written about year end charitable giving.  This year I'm giving money to a new organization, though I'm giving a lot to Givewell too.  The Alliance to Feed the Earth in Disasters, or ALLFED, is researching ways to rapidly scale up food production in the case that traditional means might suddenly become less viable.  Say a super-volcano erupts, or a huge meteor strikes, or a nuclear winter happens, or something along those lines.  Humanity would have to get through years of reduced sunlight that would make growing plants very hard.

Crop failures would naturally lead to massive starvation but ALLFED is looking into ways to turn biomass we might have laying around into edibles via routes such as fungus or methane eating bacteria.  Food produced this way wouldn't be especially tasty but it would hopefully be enough to keep people alive until the dust settles out of the atmosphere and normal farming can start back up.

The idea here is to research the technology needed ahead of time with emphasis on techniques that can be ramped up quickly in an emergency.  This is an area that nobody has really looked into before so small donations can go a long way.  And while we should hope to never need any of this technology this sort of insurance for our civilization isn't something that should be neglected.  So a portion of the 10% of my pre-tax income that goes to charity every year is going to ALLFED.

Also, I'm going to be moving to monthly charitable donations going forward since I'm not going to be doing the tax year shenanigans I was up to previously.  Charitable organizations say that makes it easier for them to plan, and it will make it easier for me to budget too.

Sunday, December 16, 2018

Ways of thinking and remembering names

So, imagine someone is walking along, down a street.  They see the store their going to and they enter through the shop door.  So, when you were imagining this, did you see it?  Which direction was the person walking, relative to your mind's eye?  Did they turn to the left or right to enter the store?  What color was everything?

When someone first did this exercise with me they were walking away from me and turned to the left.  I could still see them inside the shop through the wall because nothing in my visualization had any color.  For other people they might be imagining it more like a video where things have color and you can't see people after they move behind walls.  Some people don't form mental images of the scene at all, here's a widely shared Facebook post by someone who was surprised to discover that other people actually did form mental images in their minds.  Francis Galton was the first person to study this in 1880.

A related topic is the notion of how people go about their thinking.  That is, some people will talk to themselves inside their head when they're thinking about a problem and other people won't.  According to this article this is another property of people that varies quite a bit between individuals with some people having no inner monologue and some people talking inside their head almost all the time.  For myself, I do have an inner monologue sometimes but mostly only when I'm thinking of what I'm going to say - for example I've done quite a bit of it in organizing this blog post.  Other than that I mostly just use single words inside my head when I need the concept behind the word but I'm not practiced with it enough to just use the concept directly.

This is all interesting and has led me into some speculation.  Do people who use words inside their heads use people's names when they're thinking about that person?  I almost never do but it makes sense that that would be common.  And if so then does this correlate with people's abilities to remember names?  It seems that if you're using a name inside your head all the time you should have an easier time remembering the name.  This seems like just the sort of thing an enterprising grad student could create a study for and I hope someone does.  Or it might just be that someone already has and I haven't heard of it.  If any of you reading know or have your own related experiences please let me know.

Saturday, December 1, 2018

The Danger of Going Up

Every year people climb up Mount Everest.  Generally the number keeps growing.  Not everybody makes it up.  Some people turn back.  Other people die on the mountain.  Generally around 1 in 100 of the people who attempt to climb it.  K2 is another mountain nearby.  For a little bit people thought it might be taller than Everest.  It isn't taller, but it is deadlier and about 1 in 10 of the people who try to climb it die.

Why do people climb dangerous mountains?  To test themselves.  For the sense of achievement.  And despite the danger nobody is seriously proposing that we stop people from attempting these summits.  If they want to risk their lives they can.  They know the risks.  We should stop people who don't know what they're doing but you'll never even get to base camp without serious dedication and preparation.

If we allow mountain climbers to face severe dangers for the sake of achieving something few others have why don't we allow this with astronauts?  We did once, it was almost amazing that none of the Mercury 7 were killed in accidents.  Gus Grissom nearly was and the Apollo 1 astronauts were killed in a fire during spaceflight tests.  When we were locking in competition with the Soviets these risks seemed bearable but they don't any more.

Certainly astronauts are as aware of the dangers present as any mountaineer contemplating K2.  NASA requires them to toe the safety first line to remain in the program but it's clear to everyone watching that if riskier missions were offered there would be no shortage of volunteers.

Perhaps the difference is that astronauts are doing something for us.  They're exploring the cosmos on our behalf in a way that people looking to climb some mountain aren't.  And that instills in us a sense of obligation to shield them from risk even if they would bear that risk willingly.

Tuesday, November 27, 2018

What do all those transistors do?

The CPU in your laptop or desktop has a lot of transistors in it.  The Core i7-6700HQ that I'm typing this on has 1.35 billion of the little guys.  Buck back in the day on of the earliest computers, ENIAC, had only 20 thousand vacuum tubes which more or less fufilled the same role as transistors do now.  So what do all those extra transistors we've added accomplish, if we were able to do useful mathematical operations with just 20,000?  Most of the increase in the speed at which we run computers, the clock rate, has come from replacing large and slow transistors with smaller and faster transistors after all.

Well first, what was ENIAC doing with it's transistors?  A single transistor isn't very useful.  If you're willing to use a resistor too you can perform an operation like making an output the logical and of one input and the inverse of a second input, call it AND(A, NOT(B)).  But that circuit is a very jury rigged thing which will be slow, unreliable, and fairly power hunger.  You can make much more solid and-ish circuit, NOT(AND(A,B)) or NAND, from a couple of transistors and a resistor if you don't mind being power hungry.  But given that Moore's Law has made transistors cheaper and cheaper relative to resistors anybody these days would use a four transistor NAND circuit which is faster and more power efficient than the resistor and transistor equivalent.

What if you want to add two numbers together?  Digital circuits output zeros and ones so first you have to decide how many base 2 digits you want to be able to represent since you need enough output wires for the largest number the machine can handle.  In a modern all-transistor design you'll be using 16 transistor for every bit of the addition.  On a 32 bit adder which many processors used around 2000 and which is roughly equivalent to what ENIAC used this'll be 512 total.

But you don't want a computer that only adds numbers. You want a wide variety of instructions you can execute, you want some way of choosing what instruction you execute next, and you want to interact with memory. At this point you're up to 10,000s of transistors. That will give you a CPU that can do all the things ENIAC could do.

Now lets say you don't want your entire operating system to crash when there is a bug in any program that you run. This involves more transistors. And you probably want to be able to start one multi-cycle instruction before that last one finishes (pipelining). This might get you up to executing one instruction every other clock cycle on average. That'll cost transistors as well. This will grow your chip up to 100,000s of transistors and will give you performance like the Intel 386 form the mid 80s.

But this will still seem very slow compared to the computers we use nowadays. You want to be able to execute more than one instruction at a time. Doing that isn't very hard but figuring out which instructions can be executed in parallel and still give you the right result is actually very hard and takes a lot of transistors to do well. This is what we call out of order execution like what the first Intel Pentium Pro had in the mid 90s and it will take about 10 million transistors in total.

But now the size of the pool of memory that we're working with is getting bigger and bigger. Most people these days have gigabytes of memory in their computers. The bigger the pool is the longer it takes to grab any arbitrary byte from it. So what we do is have a series of pools, a very fast 10kB one, a slightly slower 100kB, a big 10MB one on the chip, and then finally your 8GB of main memory. And we have the chip figure out what data to put where so that the most of the time when we go to look for some data it's in the nearby small pool and doesn't take very long to get and we're only waiting to hear back from main memory occasionally. This and growing the structures that look forward for more instruction to execute are how computers changed until the mid 2000s. Also going from 32 to 64 bits so that they could refer to more than 4GB of memory, the biggest number you can say in only 32 bits is 4294967296 so any memory location over that number couldn't be used by a 32 bit computer. This'll get us up to 100 million transistors.

And from the mid 2000s to the mid 2010s we've made the structures that figure out which instructions to execute next even bigger and more complicated letting us execute even more instructions at once. As we grow performance this way the number of transistors we needs grows as the square of the performance, on average. And we've added more cores on the same chips letting us grow performance linearly with transistors as long as software people can figure out ways to actually use all the cores. And now we're up to billions of transistors.

All this raises the question of whether you could just take a design 10,000 transistor cores you would have used back in the day and put 100 of those cores in a CPU instead of the 4 you'd normally buy.  To some extent you can do that.  If you want to have them all talk to each other and with a good amount of memory you have to increase their width to 64 bits but that doesn't take so very many transistors if the rest of the design stays simple.  And they'll be slower individually but each of the 10x transistor steps causes something like a doubling of performance rather than a 10x increase in performance.  The problem is that it's hard to write software in such a way the work can be broken up neatly into 100 different threads of execution.  And some operating systems, such as Windows, tend to problems dividing up work efficiently between more than 30 or so threads.

In theory you could have 2 large cores for cases where the software doesn't support a lot of division of work and another 30 tiny cores to handle cases where the work can be divided easily.  The operating system would have to be aware of this, though, and prefer running tasks on the fast cores first before less tasks trickle down to the slower cores.  Something of the sort has been done on mobile phones where you might have 2 fast cores and 4 slow cores.  But on your laptop you mostly see this sort of thing with a few large cores running your applications and a gaggle of small cores in the GPU doing the graphics processing.

Sunday, November 18, 2018

Book Review: Radical Abundance

Eric Drexler is the person who came up with the name "nanotechnology" and is probably the one most responsible for public awareness of the idea.  After a pretty long haitus he's published a new book and I thought I'd take a look but before I get to the new book I think I should provide some history.

Way back in 1986 Drexler published Engines of Creation.  In it he outlined a vision of a world remade by the ability to engineer chemicals the way we engineer widgets today, assembling them precisely using mechanical arms placing bits in position rather than waiting for the random thermal motion of molecules to bring parts into contact where they can stick.  In the book he envisioned tiny robots called assemblers constructed with atomic precision using tiny arms to assemble other devices - and also replicate themselves.  That ability to replicate could potentially be a big danger if an error in programming caused them to replicated without bound like a cancer.  The cells that make up our bodies are contained by having to have had a clear evolutionary path from point to point.  It took a billion years for mitochondria to evolve since that required multiple things adjusting in a cell at once.  There are quite plausibly ways to drastically increase the efficiency of self-replicating organisms that could be designed by engineers which evolution wouldn't find before the Sun consumes the Earth.  Specifically, you could have these nanobots made out of much stronger molecules and life could use and also, thanks to placing things deliberately rather than wait for random motion to put things into place, they could potentially replicate much more quickly.  So it's possible that, if you can make good enough self-replicating nanobots and they have a fault you might see them end up consuming Earth's biosphere and turning it into grey goo.

After this publication Drexler went off to do some doctorate work which he later published at Nanosystems in 1992.  Rather than conceptualizing molecular manufacturing in terms of tiny robots he wrote about it in terms of molecular factories and assembly lines.  There are a lot of advantages to this approach.  Encasing a molecule in a tube as some operation is done to it limits its range of thermal motion much more effectively than trying to hold it it at the end of an arm.  By having the structure of a conveyor line encode a sequence of operations you don't need a nano-scale general purpose computer which made up the bulk of the atoms in the back-of-the-envelope design for a nanobot in Engines of Creation.  And you don't have to worry about a factory replicating itself in the same way you do with a tiny robot.

And that brings us to Radical Abundance published in 2013.  The book is a policy book like Engines of Creation was but the engineering in it is very much all post Nanosystems; looking at construction in terms of assembly lines rather than craftsman nanobots.  There's also a large segment on the public perception of nanotechnology and how it has changed over time.  Because of excitement about nanotechnology in the late 90s and early 00s a lot of chemistry tried to re-brand itself as nanotechnology to absorb nanotechnology research dollars.  This would involve molecules smaller than 100nm created by normal thermal motion chemistry rather than through forcing molecules together with external guidance.

Additionally, a lot of the public thinks of nanotechnology in terms of tiny nanobots instead of in terms of factories made out of atomically precise parts.  This is, of course, because that's how Engines of Creation conceptualized it and because Engines is a much easier to read book than Nanosystems is.  I was expecting some sort of mea culpa from Drexler on the matter and maybe an explanation on what he'd gotten wrong in his first book.  But Radical Abundance never seems to let slip that the ideas Drexler now finds so annoying were spread by his younger self.  I think a section going into a bit of detail on why nanobots aren't workable would have been a useful addition to this book but Drexler just dismisses them here with eye rolling.

But because of these two ways in which the word "nanotechnology" no longer means what he intended it to back in '86 he is now promoting "Atomic Precision Manufacturing" or APM as a term for the technologies he's interested in.  I wish him good luck with that but I'm doubtful he'll succeed.

What seems more likely to succeed are attempts to build these "APM" capabilities, at least eventually.  Our science of the nanoscale is currently imperfect but engineering practice can let us proceed anyways.  It's very hard to look at a protien and figure out how it will fold when placed in water.  I currently have my desktop give some spare cycles to figuring out some medically important proteins.  But that doesn't mean we can't just design proteins to fold understandably if we're willing to be a bit less efficient than evolution is.  We don't understand how every molecular surface interacts but we can restrict ourselves to the surfaces we do understand.  We can't predict the exact strength of every structure but we can design in sufficient safety factors to cover our uncertainty.  There's a lot of scientific work being done pointing towards APM and Drexler gives a good high level over view of it.

I'm going to say that I don't have any firm idea of what sort of time scale progress on APM/nanotechnology will happen on.  But I think I'm persuaded that it will happen eventually.

And just because I saw it recently, here's A Capella Science's song about current research in nanobots.

Is AlphaStar what intuition without reason looks like?

Deepmind, a group owned by Google, has been making waves recently with their game playing AIs.  First there was the one that taught itself t...