When I was a Christian, one of the biggest comforts was having a well defined purpose to life. The greatest thing was to glorify God. That's easy to do on Sunday, but I figured that if God was as incredible as Christianity claimed, it was worth honoring God every day of my life. After thinking about this for a while, I decided God must care an awful lot about humanity, and seeking the advancement and peace of human civilization was the primary method of bringing God glory on a daily basis. This kind of thinking is supported by Bible texts such as "If you love me, feed my lambs", the parable of the talents, and the parable of the sheep and goats.
Psychologically, losing meaning in life was one of the three hardest parts about converting from Christianity to Atheism. However, I soon realized that removing God from the equation didn't have to change anything. I could still find meaning through the advancement of human civilization.
As a result, I've become interested in the origin and destiny of civilization. I consider a group of people to be a "civilization" when there exists a caste of the population that spends a large portion of time in activities other than the acquisition of food and reproduction. So a group of hunters living in caves wouldn't be a civilization until there is some kind of a chieftain or shaman who is supported through food from the other villagers. Civilization can't advance until people have leisure time to spend on art and science, so the beginning of civilization is when some people first have this free time.
Humans have made three major discoveries that were necessary for civilization to begin. They are language, fire, and agriculture. Language is required to share the complex, learned concepts that are the basis of civilization. Fire is required for cooking, which increases the nutritional value of food, thereby increasing the lifespan and health of the population. And farming is the most crucial of all. Through farming, a group of people can produce more food than they can consume. This both provides a buffer against years of famine and allows a segment of the population to spend time on things other than food production.
Once those three things were in place, the stage was set for the rapid advancement of technology, resulting in a far higher standard of living and population than humans had ever seen. The past 10,000 years of life on Earth have put the previous millions to shame. Of the many things humans have invented and discovered, however, I'd like to list what I consider the most important discoveries. All of these you use on a daily basis, probably without even thinking about it. They are:
Writing:
Creating a writing system is not as easy as most people would think. There's an excellent discussion of why this is hard in the book Guns, Gems and Steel. The basic issue is that pictorial systems (like the Chinese alphabet) require memorizing a different symbol for each word, so learning the system difficult. And phonetic systems require a stronger understanding of phonetic units than most people have, to the extent that most people learn English spelling without even understanding the phonetic backing.
The Wheel and Roads:
These two inventions together are necessary to move large quantities of goods over long distances, and is a crucial part of trade with other cultures. Trade is the mechanism by which different cultures share their discoveries.
Currency:
In trade and barter systems, it's easy for a baker who wants meat and a butcher who wants bread to work out a deal. But what happens when the butcher instead wants a knife, the blacksmith wants a table, and its the carpenter who wants bread? Now you have to orchestrate a four way trade. When you expand this problem even to a town of just 1000 people, its complexity as an NP complete problem becomes apparent. Money provides a linear time solution. Every trades what they have for money, then trades the money for what they want.
Mathematics:
Most of the time, having directions or instructions is meaningless unless they are precise. Understanding the relationships between numbers is required for measurements, trades, and general mechanics.
Plumbing:
Once you have even 10,000 people living in the same general area, getting fresh water and removing sewage becomes a genuine problem. Without a good system of moving water, the population is much more likely to contract and spread diseases. Sewers make cities less susceptible to plagues.
The Printing Press:
Even if you have a written language, the production of written documents is time consuming without a printing press. The press allows for mass production of books, which in turn puts written materials in the hands of the common person. That makes it the precursor of widespread education. Historically, the printing press was also one predecessor of the Protestant Reformation, as it enabled the Bible to be translated out of Latin and into a language the average person understood (at least if it were read to them).
Electricity:
Fire is a powerful source of energy, but it's difficult to use. Contrast this with electricity, a power source that can be transmitted over large distances and even stored for later use. Among its many uses, electricity provided more efficient means of lighting buildings. This in turn meant humans could be productive for more hours in the day. It also created more efficient climate control systems for buildings, which allowed humans to live in harsher climates. And it enabled the creation of more efficient factories using the assembly line for production.
Radio Communication:
Three thousand years ago, kings were happy that their exact instructions could be written down and sent to another place in the kingdom within a month or less. But due to the discovery of radio waves, encoded messages can be broadcast across thousands of miles in mere seconds. With radio communication, decisions require crucial information can be made in minutes rather than weeks or even months.
The Internet:
I am convinced that the internet is by far the greatest invention of our generation. While radio and television allowed rich corporations and governments to communicate quickly and easily, the internet has put that power in the hands of the everyone. Massive amounts of data can be send anywhere on the entire planet in a matter of seconds due to the power of the internet. It has brought about an era in which anyone with access to a computer can express their thoughts. And if Twitter is any indication, almost none of it is worth reading. But I hope that this blog can be one corner of the internet where the information is worthwhile.
When I see how far humans have come, I'm excited for the future. Some other week I'll write about some options for what The Next Big Thing(tm) might be. But given the increasingly rapid pace of technology development, it could be something we see in our lifetime. You might notice that everything on this list has to do with more efficient movement of ideas, matter, or energy, so that's a clue for what kinds of technology this next century could bring.
Showing posts with label architecture. Show all posts
Showing posts with label architecture. Show all posts
Monday, May 18, 2009
Monday, October 20, 2008
Groupthink
There is a psychological concept known as groupthink, where members of a group discussing a topic gravitate towards a consensus based on a desire to minimize conflict rather than rationally discussing the subject. The play and film 12 Angry Men is a famous view of groupthink in action. A jury must decide whether a man is guilty or innocent, and the general group consensus is that he is guilty. But one juror refuses to ignore his intuition, even though it differs from the other jurors. The drama of the film is primarily based on how the other 11 jurors come to change their minds and eventually find the man innocent. Groupthink is a dangerous phenomenon because it can cause rational people to make irrational choices purely because it is the most common choice made by other group members. Just because a decision is right for everyone else in the group doesn't mean it's right for you.
Surprisingly, groupthink can be a problem in video game AI as well. This seems counterintuitive, as a bot must be programmed to follow logical rules. How can following logical rules produce illogical results? The issue is one of scope. In a teamplay game variant like capture the flag, each bot might be doing the best thing without knowing what the other players are doing, but not coordinating as a team. Suppose one bot does some logical deductions and concludes the optimal strategy is for him to guard the flag. Since all other bots have roughly the same understanding of the game state, some poorly designed AI code could cause all of them to defend the flag. It's optimal for more than zero players to defend, but having no players attack is clearly the wrong choice.
So bots that don't take into account the overall strategy of the team are likely to fall into a groupthink scenario. This results in a poor strategic choice even if each individual choice is "optimal" when consider without knowledge of the other choices. The solution is for bots to make teamplay decisions as, well, a team. Each bot's decision needs to take into account the likely decisions of other players, bots and humans alike.
The good news is that if bots are good at general combat tactics, the amount of additional logic to handle a teamplay scenario is minimal. It's not like players have better or worse aim when they're fighting in a team, or suddenly some weapons are sigificantly worse when you're playing capture the flag. None of that has to be rewritten to handle play in a group. Teamplay logic is just a question of priorities: when an enemy player has your flag, it's a lot more important to kill that player than any other opponent, and guarding your own base is a lot less important than attacking theirs. And in almost all situations, the choice is between defending and attacking. How the bot attacks and defends doesn't really change.
So BrainWorks can get away with some extremely simple logic to handle team games and still produces reasonable results. One bot becomes the defacto leader for choosing the strategy the bots will take-- exactly how offensive or defensive it is. Some number of players are slotted for defense and the rest for offense, but never 0% in either category. Then the bots are sorted based on how close they are to the two bases. If there are 5 bots on a team and the leader decides on a 2-3 split of defense to offense, then the two bots closest to the home base are assigned with "defense" and the three bots furthest from home are the "offense". Any human players in the game have no assignments, obviously.
It's worth noting that "offense" and "defense" depend on the context of the game. In capture the flag, for example, the defenders guard your team's flag when it's in the base, but they also track down the enemy flag carrier when it's been taken. Attackers try to take the opposing flag, but once someone has the other flag, the attackers need to escort their flag carrier. Once the concept of whether to defend is separated from how to defend, the actual algorithm to defeat groupthink is simple.
Surprisingly, groupthink can be a problem in video game AI as well. This seems counterintuitive, as a bot must be programmed to follow logical rules. How can following logical rules produce illogical results? The issue is one of scope. In a teamplay game variant like capture the flag, each bot might be doing the best thing without knowing what the other players are doing, but not coordinating as a team. Suppose one bot does some logical deductions and concludes the optimal strategy is for him to guard the flag. Since all other bots have roughly the same understanding of the game state, some poorly designed AI code could cause all of them to defend the flag. It's optimal for more than zero players to defend, but having no players attack is clearly the wrong choice.
So bots that don't take into account the overall strategy of the team are likely to fall into a groupthink scenario. This results in a poor strategic choice even if each individual choice is "optimal" when consider without knowledge of the other choices. The solution is for bots to make teamplay decisions as, well, a team. Each bot's decision needs to take into account the likely decisions of other players, bots and humans alike.
The good news is that if bots are good at general combat tactics, the amount of additional logic to handle a teamplay scenario is minimal. It's not like players have better or worse aim when they're fighting in a team, or suddenly some weapons are sigificantly worse when you're playing capture the flag. None of that has to be rewritten to handle play in a group. Teamplay logic is just a question of priorities: when an enemy player has your flag, it's a lot more important to kill that player than any other opponent, and guarding your own base is a lot less important than attacking theirs. And in almost all situations, the choice is between defending and attacking. How the bot attacks and defends doesn't really change.
So BrainWorks can get away with some extremely simple logic to handle team games and still produces reasonable results. One bot becomes the defacto leader for choosing the strategy the bots will take-- exactly how offensive or defensive it is. Some number of players are slotted for defense and the rest for offense, but never 0% in either category. Then the bots are sorted based on how close they are to the two bases. If there are 5 bots on a team and the leader decides on a 2-3 split of defense to offense, then the two bots closest to the home base are assigned with "defense" and the three bots furthest from home are the "offense". Any human players in the game have no assignments, obviously.
It's worth noting that "offense" and "defense" depend on the context of the game. In capture the flag, for example, the defenders guard your team's flag when it's in the base, but they also track down the enemy flag carrier when it's been taken. Attackers try to take the opposing flag, but once someone has the other flag, the attackers need to escort their flag carrier. Once the concept of whether to defend is separated from how to defend, the actual algorithm to defeat groupthink is simple.
Monday, September 1, 2008
Needle In A Haystack
For a long time, I kept all my important documents in a single box. That would be stuff like my passport, car title, insurance information, and so on. After my wife and I bought a home, we had enough papers to file that our simple box wasn't sufficient. We bought large filing cabinet and it's served our needs ever since.
It's not that we needed to look up stuff any more frequently than before. But when we went from 100 pieces of paper to 1000, we didn't want it to take 10 times longer to find anything. To find stuff in the box, I riffled through it until I found the paper I needed, sometimes searching the entire thing. More stuff means the search takes longer.
A filing cabinet solves this problem by providing a natural structure for organizing the papers. For example, all the papers on the home can go in one file folder, all the car information in another, and all the identification documents like passports in a third. Then the lookup process becomes simpler, as I can ignore everything that's not part of the folder that keeps whatever I'm looking for.
This is a real savings in time. Imagine you have 100 different pieces of paper. You can either stuff them all in one box or you can organize them into 10 folders, each containing 10 papers. What's the average number of papers you'll have to look at to find any given piece, assuming you always know what folder should contain that piece of paper?
When looking through the box, you could look at anywhere between 1 and 100 pieces with equal probability. So you'll average (1 + 100) / 2 = 50.5 pieces before you find it. When looking through the folders, you have to find the correct folder from 10 options and then the correct paper of the 10 pieces in that folder. It will take between 1 and 10 tries to find the folder, or 5.5 on average. And similarly it takes on average 5.5 tries to find the paper in the folder. That's 11 tries total for the folder compared to 50.5 for the box. The filing system can be searched roughly five times faster!
Or is it really five times faster? What happens if you have 1000 pieces of paper instead of 100? When you have this much information, you could create folders and subfolders to further organize the papers. If you have 10 main folders, each of which contain 10 subfolders, and each of those contain 10 papers, then it will take 5.5 + 5.5 + 5.5 = 16.5 tries to find any one of the 1000 papers. It would take 500.5 tries if they were in a box. So in this case the filing system is about 30 times faster.
The more data there is to store, the more efficient the filing system is compared to the box. That's because the filing system is a whole order of magnitude more efficient. In mathematical terms, searching through the box takes linear time. When you add ten times as much stuff, it takes ten times as long. But searching the filing system takes logarithmic time. Adding ten times as much stuff just means it takes one more search step. Very roughly speaking, searching is proportionate to the number of zeros on the size of the data. Searching 100 things takes twice as long as 10 things, and searching 1000 things takes three times long. Want to search 1,000,000 things? That's six times longer than searching 10 things.
You might be wondering what all of this has to do with artificial intelligence. At the heart of almost all AI is data, and data doesn't mean anything if you can't find it when you need it. That means efficient data storage is the required foundation for artificial intelligence. An algorithm is only as good as the data it has access to, and good AI needs a lot of data. If all the data were just shoved in a box, there's no way the computer could run the AI's thought process fast enough. Indeed in almost all computer science, the way in which data is organized is just as important as the actual data being stored. After all, what good is information if you can't find it? Next week I'll give a concrete example of how BrainWorks puts this concept to use.
It's not that we needed to look up stuff any more frequently than before. But when we went from 100 pieces of paper to 1000, we didn't want it to take 10 times longer to find anything. To find stuff in the box, I riffled through it until I found the paper I needed, sometimes searching the entire thing. More stuff means the search takes longer.
A filing cabinet solves this problem by providing a natural structure for organizing the papers. For example, all the papers on the home can go in one file folder, all the car information in another, and all the identification documents like passports in a third. Then the lookup process becomes simpler, as I can ignore everything that's not part of the folder that keeps whatever I'm looking for.
This is a real savings in time. Imagine you have 100 different pieces of paper. You can either stuff them all in one box or you can organize them into 10 folders, each containing 10 papers. What's the average number of papers you'll have to look at to find any given piece, assuming you always know what folder should contain that piece of paper?
When looking through the box, you could look at anywhere between 1 and 100 pieces with equal probability. So you'll average (1 + 100) / 2 = 50.5 pieces before you find it. When looking through the folders, you have to find the correct folder from 10 options and then the correct paper of the 10 pieces in that folder. It will take between 1 and 10 tries to find the folder, or 5.5 on average. And similarly it takes on average 5.5 tries to find the paper in the folder. That's 11 tries total for the folder compared to 50.5 for the box. The filing system can be searched roughly five times faster!
Or is it really five times faster? What happens if you have 1000 pieces of paper instead of 100? When you have this much information, you could create folders and subfolders to further organize the papers. If you have 10 main folders, each of which contain 10 subfolders, and each of those contain 10 papers, then it will take 5.5 + 5.5 + 5.5 = 16.5 tries to find any one of the 1000 papers. It would take 500.5 tries if they were in a box. So in this case the filing system is about 30 times faster.
The more data there is to store, the more efficient the filing system is compared to the box. That's because the filing system is a whole order of magnitude more efficient. In mathematical terms, searching through the box takes linear time. When you add ten times as much stuff, it takes ten times as long. But searching the filing system takes logarithmic time. Adding ten times as much stuff just means it takes one more search step. Very roughly speaking, searching is proportionate to the number of zeros on the size of the data. Searching 100 things takes twice as long as 10 things, and searching 1000 things takes three times long. Want to search 1,000,000 things? That's six times longer than searching 10 things.
You might be wondering what all of this has to do with artificial intelligence. At the heart of almost all AI is data, and data doesn't mean anything if you can't find it when you need it. That means efficient data storage is the required foundation for artificial intelligence. An algorithm is only as good as the data it has access to, and good AI needs a lot of data. If all the data were just shoved in a box, there's no way the computer could run the AI's thought process fast enough. Indeed in almost all computer science, the way in which data is organized is just as important as the actual data being stored. After all, what good is information if you can't find it? Next week I'll give a concrete example of how BrainWorks puts this concept to use.
Monday, August 11, 2008
Project Planning
As BrainWorks is a complete rewrite of the Quake 3 AI code, it was a relatively daunting project that required a lot of effort in many areas. First person shooter AI requires aiming and firing decisions (not the same thing!), item pickup, weapon selection, movement, visual and auditory awareness, and high level strategy to give a non-exhaustive list. Simply put, there's a lot of things to write and they all have to work together. When the project is this large, it's hard to even know where to begin. How do you prioritize such a wide list of features when, quite frankly, everything is required?
For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.
So if Art of War is so great, why have you never heard of it before?
Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.
The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...
When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.
Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.
Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.
I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.
For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.
So if Art of War is so great, why have you never heard of it before?
Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.
The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...
When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.
Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.
Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.
I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.
Monday, June 16, 2008
Give It A Go
While my primary area of expertise is First Person Shooter AI, I still get a number of questions about other AI applications. One of the hardest game AI problems to date, if not the hardest, is the game of Go. What's so surprising is that Go has simpler rules than Chess, but Go AI is several orders of magnitude more complicated than good chess AI. Now consider that the best chess AI to date has only beaten a grand master, Kasparov, when it was specifically trained to counteract Kasparov's play style. In the first set of games, which Kasparov won, he commented that he did better when he started making what he considered the second best move instead of the best move. Apparently the first AI was so hyper-tuned against Kasparov's play style that it defeat other similarly good plays that it did not think Kasparov would make.
Yes, that's the best the world has done for Chess AI: A program that can defeat one really good player. But Go? The best AI programs just rank as decent amateurs. And listen to how simple the rules are:
Nevertheless, in the past few years there have been a few significant advancements in the field of Go AI. Rather than trying to solve Go in the same way Chess would be solved, some Monte-Carlo algorithms have shown a lot of promise. In particular, in 2006, "Upper Confidence Bounds applied to Trees" (or UCT) was developed. I'm not an expert on this subject, but in brief, the concept works like this.
While it's very hard to determine which space on a 19x19 board is the best, it's very easy to compute the score of a Go board. Contrast this with Chess where the actual pieces in play are secondary to question of whether or not a King has been captured. So the very rough idea is to try most options (pruning the obviously bad plays) and play a semi-random game for each of them (again, pruning obviously bad plays). Far less time is spent at each stage of the tree. If there are 50 possible moves that aren't terrible, one of them is just selected at random. There's no aggressive search to determine which of those 50 is the best. When the test game is done for a given play, that provides an estimate of how good that particular initial placement is. Other placements are tried and the one with the highest estimated score is selected as the computer's official move.
Of course, the actual algorithm is quite a bit more complicated than that, but that's the general idea behind the innovation. The crucial lesson here for AI designers is this:
Focus on your goal.
In the end, Go is just a score maximization problem. It's very easy to get bogged down in the details of whether a move nets 5 points or 7 points, quickly producing a state where far too many calculations need to be done. Often the best solution involves determining how much processing time you can actually spend, and then working backwards to figure out what methods will give you the most information for the amount of time spent. In Go, calculating the board's score is relatively fast, so latest algorithm that exploited this fact had a major advantage over those that did not.
Yes, that's the best the world has done for Chess AI: A program that can defeat one really good player. But Go? The best AI programs just rank as decent amateurs. And listen to how simple the rules are:
- Players take turn placing stones of their color (black or white) on a square board (usually 19x19 but sometimes 9x9).
- Stones of the same color that are adjacent vertically or horizontally are part of the same group and live or die together.
- When a group is completely surrounded (no plays exist that add a stone to the group), that group is captured. Each lost stone is -1 point at the end of the game.
- If a play is made that would cause both the placed stone and an opposing group to be surrounded, the place stone lives and the opposing group is captured.
- You may not make a play that results in a previous board position.
- The game is over when both players consecutively pass, opting not to play a stone. Each player scores 1 point for each empty space that is enclosed only by their color of stones.
Nevertheless, in the past few years there have been a few significant advancements in the field of Go AI. Rather than trying to solve Go in the same way Chess would be solved, some Monte-Carlo algorithms have shown a lot of promise. In particular, in 2006, "Upper Confidence Bounds applied to Trees" (or UCT) was developed. I'm not an expert on this subject, but in brief, the concept works like this.
While it's very hard to determine which space on a 19x19 board is the best, it's very easy to compute the score of a Go board. Contrast this with Chess where the actual pieces in play are secondary to question of whether or not a King has been captured. So the very rough idea is to try most options (pruning the obviously bad plays) and play a semi-random game for each of them (again, pruning obviously bad plays). Far less time is spent at each stage of the tree. If there are 50 possible moves that aren't terrible, one of them is just selected at random. There's no aggressive search to determine which of those 50 is the best. When the test game is done for a given play, that provides an estimate of how good that particular initial placement is. Other placements are tried and the one with the highest estimated score is selected as the computer's official move.
Of course, the actual algorithm is quite a bit more complicated than that, but that's the general idea behind the innovation. The crucial lesson here for AI designers is this:
Focus on your goal.
In the end, Go is just a score maximization problem. It's very easy to get bogged down in the details of whether a move nets 5 points or 7 points, quickly producing a state where far too many calculations need to be done. Often the best solution involves determining how much processing time you can actually spend, and then working backwards to figure out what methods will give you the most information for the amount of time spent. In Go, calculating the board's score is relatively fast, so latest algorithm that exploited this fact had a major advantage over those that did not.
Monday, April 21, 2008
Parallel Evolution
There is a biological concept called parallel evolution which refers to the phenomenon by which the same trait is evolves in the same manner in two different species. For example, all eyes came from the same base creature. But eventually marine and vertebrate animals both evolved the same set of eye advancements, despite lacking a common ancestor that had all those advancements. There are also cultural examples of parallel evolution for concepts like writing and the wheel. In each case, these concepts fit three basic criteria:
So I often wonder what an alien life form would be like, evolved totally independent of life on Earth. What concepts are there about life that really only have one good solution? For example, the structure of the carbon atom makes it highly likely that all life would be carbon based. It's theoretically possible to have silicon based life, because carbon and silicon have similar structures (both have four possible atomic links), although silicon is much heavier, but carbon is by far the most likely. Also, water is a fascinating molecule in liquid form, used for a variety of purposes in life, so it would be very surprising to see a life form that did not use water.
All of life exists somewhere in the density spectrum between water (liquid) and carbon (solid). Some are closer to the water side, like a jellyfish. And some life forms are closer to solids, like trees. Land based animals ("fleshlings") are in the middle, and seem to offer a good mixture between the mobility of a jellyfish and a protective shell of a tree. So it seems likely that any sentient life form will be made of some kind of flesh.
So while we can guess about the physical form of another life form, deducing the nature of an alien brain is much harder. That's primarily because we don't know enough about the human brain to guess which features only have one simple solution. We've only encountered one kind of sentient life: humans ourselves. Would aliens need to sleep? Our research into sleep implies our brains use sleep to process memories, similar to defragmenting a hard disk. Important memories are stored, unimportant ones are discarded. But is our brain's implementation of memory the only way to solve this problem?
Well, computers solve the storage of data-- thoughts and memories-- through completely different means. Human thoughts are fluid. People can easily forget things that happened five seconds ago, or even remember the details incorrectly. Even photographic memory isn't perfect, and seems to decay with age. Short of hardware errors, however, a computer's memory management is perfect. All the data can be retrieved without error. The human brain seems to sacrifice accuracy for much greater storage capacity, access speed, and perhaps processing speed. It's possible there exists an alien life form that has found a solution to the memory problem that incorporates human memory capacity with computer memory accuracy, but I doubt it.
So this line of thought makes me think two things about the field of AI research. The first is that it's crucial to identify the portions of intelligence that only have one good solution and solve them first. For video game AI, these are problems like navigation and visualization. At this point everyone knows the navigation solution is A*, but there's still the question of how the mind identifies the potential way points A* requires. For general AI, the most fundamental problem is language processing, which is devilishly difficult and could take centuries to solve. But having a library of known solutions to basic AI problems will accelerate the ability to create good AI. This is similar to how an operating system abstracts away simple solution to problems a programmer doesn't want to worry about very much, such as processor scheduling and disk space access.
The second thought I have is this nagging feeling we may be designing AI on a fundamentally flawed hardware platform. The computer is excellent when what you want is ultimate precision. Designing AI on a computer involves writing sophisticated algorithms to artificially create the "randomness" that real life seems to incorporate. Perhaps one reason artificial intelligence is so hard is that sentient life requires a system of memories that trades precision for increased data capacity and faster access time the way a human brain does, and we'll never create satisfying AI until we start programming on that kind of a hardware platform. I don't know if that hardware platform is still based on transistors or if it's something more like DNA, but deep down I feel like designing AI on a computers is pushing a square peg into a round hole.
- Very useful when obtained
- Not completely obvious
- Little to no room for implementation differences
So I often wonder what an alien life form would be like, evolved totally independent of life on Earth. What concepts are there about life that really only have one good solution? For example, the structure of the carbon atom makes it highly likely that all life would be carbon based. It's theoretically possible to have silicon based life, because carbon and silicon have similar structures (both have four possible atomic links), although silicon is much heavier, but carbon is by far the most likely. Also, water is a fascinating molecule in liquid form, used for a variety of purposes in life, so it would be very surprising to see a life form that did not use water.
All of life exists somewhere in the density spectrum between water (liquid) and carbon (solid). Some are closer to the water side, like a jellyfish. And some life forms are closer to solids, like trees. Land based animals ("fleshlings") are in the middle, and seem to offer a good mixture between the mobility of a jellyfish and a protective shell of a tree. So it seems likely that any sentient life form will be made of some kind of flesh.
So while we can guess about the physical form of another life form, deducing the nature of an alien brain is much harder. That's primarily because we don't know enough about the human brain to guess which features only have one simple solution. We've only encountered one kind of sentient life: humans ourselves. Would aliens need to sleep? Our research into sleep implies our brains use sleep to process memories, similar to defragmenting a hard disk. Important memories are stored, unimportant ones are discarded. But is our brain's implementation of memory the only way to solve this problem?
Well, computers solve the storage of data-- thoughts and memories-- through completely different means. Human thoughts are fluid. People can easily forget things that happened five seconds ago, or even remember the details incorrectly. Even photographic memory isn't perfect, and seems to decay with age. Short of hardware errors, however, a computer's memory management is perfect. All the data can be retrieved without error. The human brain seems to sacrifice accuracy for much greater storage capacity, access speed, and perhaps processing speed. It's possible there exists an alien life form that has found a solution to the memory problem that incorporates human memory capacity with computer memory accuracy, but I doubt it.
So this line of thought makes me think two things about the field of AI research. The first is that it's crucial to identify the portions of intelligence that only have one good solution and solve them first. For video game AI, these are problems like navigation and visualization. At this point everyone knows the navigation solution is A*, but there's still the question of how the mind identifies the potential way points A* requires. For general AI, the most fundamental problem is language processing, which is devilishly difficult and could take centuries to solve. But having a library of known solutions to basic AI problems will accelerate the ability to create good AI. This is similar to how an operating system abstracts away simple solution to problems a programmer doesn't want to worry about very much, such as processor scheduling and disk space access.
The second thought I have is this nagging feeling we may be designing AI on a fundamentally flawed hardware platform. The computer is excellent when what you want is ultimate precision. Designing AI on a computer involves writing sophisticated algorithms to artificially create the "randomness" that real life seems to incorporate. Perhaps one reason artificial intelligence is so hard is that sentient life requires a system of memories that trades precision for increased data capacity and faster access time the way a human brain does, and we'll never create satisfying AI until we start programming on that kind of a hardware platform. I don't know if that hardware platform is still based on transistors or if it's something more like DNA, but deep down I feel like designing AI on a computers is pushing a square peg into a round hole.
Monday, April 7, 2008
Getting it "Just Right"
There's not much difference between driving 55 and 56. Unless of course the speed limit is 55, in which case that small amount of speed could make you get a speeding ticket. Standard outside temperatures average between 0 and 100 degrees Fahrenheit, but people easily notice the difference between 68 and 72 degrees. And yet for other measurements in our lives, small changes are completely unnoticed. A car with a full gas tank drives just as well as a car with a quarter tank left-- you only notice the problem when the last drop of gas is gone.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
Monday, February 25, 2008
At the Heart of it All
As I outlined last week, the item pickup problem in First Person Shooter games is very difficult to solve, and that goes for humans as well. How do the truly advanced players approach this problem? At the heart of it all is one central question:
How will this benefit me?
If you want to know whether to pickup item A or B, you first must know how much item A benefits you, and how much it costs (in additional time to get the item). BrainWorks solves this problem using a customized resource prediction model, handled by ai_resource.c. Be warned, this code is not for the feign of heart. It's gratuitously well commented and documented, but there are so many bits and pieces it's very hard to get your head around everything at once. Think of it like opening the hood of your car, removing the engine block, and taking everything down to the nuts and bolts. Very interesting, but good luck assembling it into a working vehicle.
First, the AI's resource engine must encode the player's current state. This is handled by the resource_state_t structure (defined in ai_main.h). In brief, that information is:
Determining how many points a given resource state is worth is significantly more complicated. Why is that? What other information does the bot need to estimate the points it would gain if it had this set of items? In short, it needs information about possible encounters with enemies:
The three damage values should be independent of any changes to the resource states. The amount of damage a weapon deals depends on the bot's accuracy-- getting more ammo will let the bot deal that damage longer, but it won't ever make one weapon deal more damage per second than another. As a result, the bot sorts every possible weapon it could use in a priority list at the very start of prediction. The list might read something like, "Use the plasma gun until out of ammo, then the rocket launcher, then the shotgun, then ..." Now that might not be what the bot actually does when it gets in combat, but it uses this as a rough estimate of what might happen.
Naturally the estimated damage each weapon will deal is computed from the bot's historical data of previous weapon use. If in the past the bot had 30% machinegun accuracy and fired 90% of the time the machinegun was loaded, the machinegun's effective damage rate is 27% of it's maximum possible damage rate.
So when the bot needs to predict 20 seconds of time, it might say, "Well I'll get this many points from firing my rocket launcher for 8 seconds, until it's out of ammo. Then the next weapon is a railgun, which I shoot for the remaining 12 seconds and get this many extra points." There would be 2 distinct calculations in that situation. The code uses a similar system for powerups wearing off. In that example, if the bot had a quad damage that wore off after 15 seconds, it would break the time into three segments (0 to 8, 8 to 15, 15 to 20).
Of course this is all well and good if the bot survives, but what happens if the bot predicts its own death? Surely there must be a penalty if the bot needs health but considers options other than getting it. When the bot thinks its health will reach zero, the resource prediction engine stops giving points, and the bot takes a (1 / opponents) point penalty, since getting killed gives one opponent a point.
All that work just to figure out how many points the bot will gain, not even to select the best item for pickup! Next week I'll explain how exactly the item pickup algorithm uses this resource prediction engine to determine the best item to pickup.
How will this benefit me?
If you want to know whether to pickup item A or B, you first must know how much item A benefits you, and how much it costs (in additional time to get the item). BrainWorks solves this problem using a customized resource prediction model, handled by ai_resource.c. Be warned, this code is not for the feign of heart. It's gratuitously well commented and documented, but there are so many bits and pieces it's very hard to get your head around everything at once. Think of it like opening the hood of your car, removing the engine block, and taking everything down to the nuts and bolts. Very interesting, but good luck assembling it into a working vehicle.
First, the AI's resource engine must encode the player's current state. This is handled by the resource_state_t structure (defined in ai_main.h). In brief, that information is:
- Health
- Armor
- Weapons
- Ammo per weapon
- Powerups (eg. Haste, Quad Damage)
- Activatable items (eg. Portable Teleporter)
Determining how many points a given resource state is worth is significantly more complicated. Why is that? What other information does the bot need to estimate the points it would gain if it had this set of items? In short, it needs information about possible encounters with enemies:
- Chance of encountering an enemy near the bot
- How much damage the bot will deal with each weapon
- How much damage is required to score a kill
- How much damage an attacking enemy will deal to the bot
The three damage values should be independent of any changes to the resource states. The amount of damage a weapon deals depends on the bot's accuracy-- getting more ammo will let the bot deal that damage longer, but it won't ever make one weapon deal more damage per second than another. As a result, the bot sorts every possible weapon it could use in a priority list at the very start of prediction. The list might read something like, "Use the plasma gun until out of ammo, then the rocket launcher, then the shotgun, then ..." Now that might not be what the bot actually does when it gets in combat, but it uses this as a rough estimate of what might happen.
Naturally the estimated damage each weapon will deal is computed from the bot's historical data of previous weapon use. If in the past the bot had 30% machinegun accuracy and fired 90% of the time the machinegun was loaded, the machinegun's effective damage rate is 27% of it's maximum possible damage rate.
So when the bot needs to predict 20 seconds of time, it might say, "Well I'll get this many points from firing my rocket launcher for 8 seconds, until it's out of ammo. Then the next weapon is a railgun, which I shoot for the remaining 12 seconds and get this many extra points." There would be 2 distinct calculations in that situation. The code uses a similar system for powerups wearing off. In that example, if the bot had a quad damage that wore off after 15 seconds, it would break the time into three segments (0 to 8, 8 to 15, 15 to 20).
Of course this is all well and good if the bot survives, but what happens if the bot predicts its own death? Surely there must be a penalty if the bot needs health but considers options other than getting it. When the bot thinks its health will reach zero, the resource prediction engine stops giving points, and the bot takes a (1 / opponents) point penalty, since getting killed gives one opponent a point.
All that work just to figure out how many points the bot will gain, not even to select the best item for pickup! Next week I'll explain how exactly the item pickup algorithm uses this resource prediction engine to determine the best item to pickup.
Friday, January 18, 2008
Taking Action
"Okay," I think. "Artificial intelligence. Just have to figure out what I'd do and teach a computer to do the same. Sounds easy enough. Only one problem..."
"Where do I start?"
There are so many decisions to be made when playing any sport or action game, many of them subconscious, and all the actions need to be executed at just the right time to feel natural. For example, imagine an opponent just enters your field of view. It will takes between .1 and .3 seconds for the typical human to notice and react to this. So if the bot only scans for new opponents twice a second, it could take up to half a second to respond, much worse than even a poor human player. And there are more problems than this: With only two scans per second, sometimes the bot happen to scan right after a player stepped into view, reacting much faster than .1 seconds to them. To solve this problem, bots need to scan constantly, but have their own simulated "reaction" delay to spotting the target.
On the other end of the spectrum, algorithms like deciding which item to pickup are genuinely hard. Humans can spend a second or more of thought on the problem, and if a bot recomputed item pickup as often as it rescanned, the computer run noticeably slower. Bad things will happen if scanning ran as infrequently as item pickup, or if item pickup ran as often as scanning. Every kind of thought that a bot might do needs to be properly scheduled. It can't think about the problem too much or too little.
To solve this problem, I wrote the ai_action.c file, which administrates all the thought a bot does. That code decides when certain engines run and when they get wait until later. At the core of the design is a model analogous to human thought and action. I classified all human responses into one of three categories:
Each bot action is associated with one of these states. Anything that a human would spend a lot of time thinking about is automatically conscious. Chances are, the algorithm to do that thought will strain the computer, so it should be run as little as possible. These actions are labeled "Logical" and run whenever the logical processing should run (just a few times per second, or even less frequently).
Reflexive actions are things the mind doesn't think about unless something about the world changes. You might gasp and hold your breath if you suddenly smell something foul, for example, but otherwise you'd breath normally. So all bot actions that depends on the world state are labeled "Reflexive". These run every time the server updates anything on the level (once every 50 milliseconds, or 0.05 seconds).
Last, there are a handful of maintenance things that simply must run as often as possible so the data can be handled immediately, such as checking whether the bot died. These have no label because there's never a time you don't need to run them.
Sometimes there are dependencies between different sections of thought. For example, a bot needs to aim before it shoots, and it must select a target before before aiming. And before that, the bot must first scan for eligible targets. So if firing is a reflexive action, then everything it depends on must also be reflexive (or even faster).
This isn't a particularly novel algorithm-- operating system have used more advanced schedulers for years. But it's rare to see this level of design applied to artificial intelligence in games, and that's really a shame. There are whole categories of problems that are much easier to solve once you have a proper scheduler to organize everything the AI needs to do.
"Where do I start?"
There are so many decisions to be made when playing any sport or action game, many of them subconscious, and all the actions need to be executed at just the right time to feel natural. For example, imagine an opponent just enters your field of view. It will takes between .1 and .3 seconds for the typical human to notice and react to this. So if the bot only scans for new opponents twice a second, it could take up to half a second to respond, much worse than even a poor human player. And there are more problems than this: With only two scans per second, sometimes the bot happen to scan right after a player stepped into view, reacting much faster than .1 seconds to them. To solve this problem, bots need to scan constantly, but have their own simulated "reaction" delay to spotting the target.
On the other end of the spectrum, algorithms like deciding which item to pickup are genuinely hard. Humans can spend a second or more of thought on the problem, and if a bot recomputed item pickup as often as it rescanned, the computer run noticeably slower. Bad things will happen if scanning ran as infrequently as item pickup, or if item pickup ran as often as scanning. Every kind of thought that a bot might do needs to be properly scheduled. It can't think about the problem too much or too little.
To solve this problem, I wrote the ai_action.c file, which administrates all the thought a bot does. That code decides when certain engines run and when they get wait until later. At the core of the design is a model analogous to human thought and action. I classified all human responses into one of three categories:
- Conscious
- Reflexive
- Subconscious
Each bot action is associated with one of these states. Anything that a human would spend a lot of time thinking about is automatically conscious. Chances are, the algorithm to do that thought will strain the computer, so it should be run as little as possible. These actions are labeled "Logical" and run whenever the logical processing should run (just a few times per second, or even less frequently).
Reflexive actions are things the mind doesn't think about unless something about the world changes. You might gasp and hold your breath if you suddenly smell something foul, for example, but otherwise you'd breath normally. So all bot actions that depends on the world state are labeled "Reflexive". These run every time the server updates anything on the level (once every 50 milliseconds, or 0.05 seconds).
Last, there are a handful of maintenance things that simply must run as often as possible so the data can be handled immediately, such as checking whether the bot died. These have no label because there's never a time you don't need to run them.
Sometimes there are dependencies between different sections of thought. For example, a bot needs to aim before it shoots, and it must select a target before before aiming. And before that, the bot must first scan for eligible targets. So if firing is a reflexive action, then everything it depends on must also be reflexive (or even faster).
This isn't a particularly novel algorithm-- operating system have used more advanced schedulers for years. But it's rare to see this level of design applied to artificial intelligence in games, and that's really a shame. There are whole categories of problems that are much easier to solve once you have a proper scheduler to organize everything the AI needs to do.
Subscribe to:
Posts (Atom)