#theoretical artificial intelligence

[askagamedev]

How is Game AI developed? Does AI start acting optimally and then they make it fun? With Dota 2 showing off an AI that can beat the best players 1v1, I wondered why I should be impressed? I thought designing AI that always plays perfectly was relatively easy and the hard part was designing mistakes to make it useful (or fun). How wrong am I?

There’s a pretty big difference between the AI you’re used to and the AI that they demonstrated at The International 7. Here’s the thing - if the rules of the game are simple enough such that there is an optimal strategy, then yes - you can start with that optimal strategy and always win or tie. If such a thing exists, the game is considered “solved”. These games are generally deterministic - you don’t even need to play in order to tell who will win. Tic-tac-toe is the textbook example of such a game - if played properly, the second player can never win. 

However, most competitive games aren’t solvable - there isn’t always one perfect way to win, because the game has play and counterplay. For example, consider the game Rock-Paper-Scissors. Is it possible to come up with a winning strategy for this game? In general, the answer is “not really” - it entirely depends on what the opponent does. If you have a good read on your opponent you can defeat her, but there is no perfect solution. An AI can be trained to play rock-paper-scissors but it can’t always play perfectly because there is no such thing as true perfect play in Rock Paper Scissors.

Another means of gumming up the work is simply to have too many confounding factors for the AI to account for everything, especially in real time. For example, on Wall Street, several firms have set up banks of computers that trade stocks at super high speeds. Super high-end machines running complicated algorithms place buy orders here, sell orders there, often microseconds apart, trying to take advantage of their inhuman reaction times to snap up favorable transactions. However, even these machines aren’t perfect. If they were, they would obsolete every other form of stock trading on the market. However, they are not infallible - they are susceptible to errors in the algorithm, incomplete or incorrect information, taking too long to crunch the numbers and make a decision, and more. The cost of these computers and the internet connections that connect them run in the millions of dollars all to shave milliseconds off of the calculation response time, and even then they are not money-printing machines. They often get it right, but they will also often get it wrong, losing millions of dollars for their owners.

The AI at TI7 was playing a very simplified version of Dota - 1v1, mid lane only, and both players were restricted to Shadow Fiend. With such a setup, there were few enough factors that the AI could process them all and come up with a winning strategy. And even then, it wasn’t a perfect strategy that was made by a human, but it was a set of strategies the AI itself built from playing millions of games against itself and finding points for improvement. Even though it managed to defeat Dendi, there were many human players who managed to outsmart the AI by doing things it had never encountered before, such as dropping items on the floor. Now consider expanding that challenge to a team of 5 heroes selected from a potential pool of 105, each with different builds and item loadouts. The complexity grows by many orders of magnitude. Then consider the actual details of the game itself - items, build, team role, scouting, creeping, and so on - and the complexity grows by many more orders of magnitude. Coming up with the correct strategy here is very difficult - the AI would need to play millions of games against good players in order to construct a viable set of strategies and counter-stratgies that would make it even remotely competitive.

Is there an optimal strategy for Dota 2? Possibly, with enough computing power and data, machines could figure it out. More likely, there will be a metagame that evolves from the available choices - a variety of viable (counter) strategies with reasonably close win percentages. But as it stands, there is no perfect script that we can just tell an AI to follow that will guarantee victory, because there’s so many different strategies and counter-strategies at play that there’s no way for humans to account for all of them.

Got a burning question you want answered?

Short questions: Ask a Game Dev on Twitter

Long questions: Ask a Game Dev on Tumblr

Frequent questions: The FAQ

[askagamedev]

if you could live one day where artificial intelligence was real what would it be like? could you describe what your day would be like if technology had a human personality like an angry atm machine or a bowel mouth toilet?

This question does seem to delve more into the philosophical than the practical, but I’ve done a bit of work in the field of artificial intelligence, so I’ll bite.

When you’re looking at designing artificial intelligence, you’ve got two major camps. The first is to create something that will pass the Turing test. That is, to create something whose responses are indistinguishable from a human being’s. This is pretty much just purely theoretical. The AI here would have to be able to parse inputs from people and respond accordingly. Once the AI could adequately make decisions like a person, it would then be able to go on and add priorities, self-improvement, and increase its knowledge base in a more traditional way. This would be the sort of AI that would get angry, sad, happy, or frustrated, because emulation of human behavior is the goal. This sort of AI is generally developed at research universities and R&D programs simply in a theoretical exercise of seeing whether it can be done. Much like building a computer to play chess, it doesn’t really serve much of a purpose other than “Can it be done?” Research scientists are hard at work trying to prove the answer is “yes”.

The other camp of AI is that designed for a practical purpose, like the sort that exists in games. This sort of AI is built with a specific goal in mind, and any iteration on it would serve to further that particular goal. For other goals (such as an ATM machine) the focus of the AI is to emulate a bank teller to provide a user whatever services are needed at the bank without needing a living, breathing human to parse the necessary information. In that regard, anyone funding the development of such an AI would want to spend his or her money on the data parsing, and less on the human emulation. Much like a sarcastic or foul-mouthed cashier at a restaurant or coffee shop doesn’t add particularly much to the experience, adding such things to a directed AI would not be useful unless it is solely to put the user at ease. That effort in research and development would be much better spent working on recognizing and understanding all of the possible tasks that a user could possibly attempt to engage in with a teller, and then being able to recognize the various ways those tasks can be asked for.

As an example, let’s say that you want to apply for an auto loan in order to buy a car. This sort of task is currently outside the scope of an ATM, but with a sufficiently developed AI, it could handle the majority of the work necessary. It would need to understand what information is necessary to begin a loan application process, and how to calculate things like an applicant’s factors such as credit rating, job status, whether there is a co-signer, any mitigating circumstances, and things like that. It would need to be able to understand what sort of common issues might come up, adjust its internal metric for grading whether an applicant is an acceptable credit risk. The benefits to this, of course, would be that customers seeking loans could then get them nearly instantly, 24 hours a day, 7 days a week, without needing to keep staff working around the clock. The benefits here would be to the automation of the processes and increasing efficiency by being able to ask for, parse, and process the necessary information that a customer provides.

In game development, that goal would be to provide a challenge to the player and to be enjoyably beaten. There have been experiments in this arena, in games like Left 4 Dead with its AI Director where there is a perpetually running algorithm that will purposely attempt to vary the amount of tension in a Left 4 Dead run to provide a more varied experience. It does so by choosing which sections of the map have zombies, and which don’t. It also chooses when to spawn the special enemy zombies, and attempts to build tension through audio and visual cues. By periodically building up tension and then releasing it at key moments, it is intended to provide a fun and repeatable experience that doesn’t get as repetitive. It isn’t perfect, but it is an example of using procedural game design to create content. Instead of creating the content him or herself, the designer sets the rules and the game creates itself.

There is a tradeoff, of course... you lose out on the specific authored touches. Things like a specific camera angle, or a specially constructed scene won't necessarily work with primitive procedurally generated content, much like how the levels in Diablo 3 feel rather generic and haphazardly put together. However, as procedural algorithms become more advanced and more capable, designers will add more such things to their own repertoires, and they will become better at crafting more interesting and engaging content.

I think that the future of AI will actually end up taking over content creation. Our ultimate goal is to let the machinery do the work and the effort while we can do things like the creative parts. We already have tools like Maya, Max, Motion Builder, etc. to create the content we use. The next evolution would be to abstract the need for this and to get the computers to write the majority of the code for us and generate the assets we want after we define an art style and are able to establish rules and systems via plain language rather than complicated proprietary scripting languages. In such a situation, far in the future, we won't need specialists to create content anymore because they won't be needed. The AI would be able to generate the content itself, and all we'd need to do is give it the direction.