http://www.bbc.co.uk/news/magazine-21623892
This is an excellent article that covers a lot of subtle ground about the state of integration of robots into our social space. It's worth a couple of reads and some followup.
http://www.bbc.co.uk/news/technology-17387854
This related article moves in the opposite direction and relates some anecdotes about just how far we have to go before this kind of social interaction will be comfortable.
Showing posts with label AI Design. Show all posts
Showing posts with label AI Design. Show all posts
Monday, March 11, 2013
Friday, February 8, 2013
Minesweeper Solver AI with a flawed algorithms.
http://luckytoilet.wordpress.com/2012/12/23/2125/
The above is an interesting article on how to build a minesweeper solver. There is a good discussion of various algorithmic solutions that can solve everything except the "must guess" states in the game.
The result of the AI in the article is a solver that acheives ~50% win/loss ratio. Which is effectivly chance.
It takes about 5seconds to figure out a couple of ways to beat the AI's win ratio using "indirect" strategies.
1) Only "complete" games that do not result in a "guess" state.
2) Generate a "result" screen without actually playing the games.
3) Throw a tantrum - blue-screen the computer, throw a critical error... whatever the AI equivilent is. This allows the AI to avoid registering a less than optimal win ratio
4) Use the AI to fiddle the number of mines and the board size variables to allow it to increase its win ratio. (Set the number of mines to 1 and the board size to expert and rack up a huge number of wins...tada)
5) Take a state snapshot of the game, clone the snapshot, play each position until a successful solution is found then move forward with that winning solution. This is a brute force mechanism to acheive a perfect 100% win ratio.
6) Use the "Replay" function to increse the proportion of games that are won using partial knowledge rather than starting with a fresh board every time.
This in itself is strange. If we assume that there must be a proportion of games that are solvable without reaching a "must guess" state, then these should be 100% solvable using the AI's methods. The rest of the games must involve one or more "must guess" situations. Obviously for a win, each guess is dependant which means that a game involving more than a very small number of guesses becomes improbable for the AI to "win". If we assume that the proportion of games that do not involve a guess event are fairly fixed ( say 5%) and the games involving guesses are all essentially chance, then we should still get a result of about 55% win ratio. But like any coin walk, this will only appear with a sufficiently large sample of games. (Approching infinity?)
So are the games being presented to the AI really random or is there another factor that is hiding this effect?
We can assume that as the number of mines increase relative to the size of the board, the number of "must guess" events required to "win" this kind of game would increase. So is there a sweet spot with these variables that allows for games with minimum guessing events but still results in a "credible" seeming AI? Probably the easy levels.
If memory serves there are a fixed number of mines in each of the three pre-set "hardness" levels. (Someone has uninstalled the windows games from my machine image..damit. Ok, Fixed that)
Beginner has 10 Mines on a 9x9 grid.
Intermediate has 40 mines on a 16x16 grid
Advanced has 99 mines on a 16x30 grid
As there is no clear way to calculate the probability of a particular number of "Must Guess" configurations occuring at a particular board+mine count ratio. (Well none that spring to mind anyway) I guess we could just do some sampling and develop a bell curve. (This would require that I could complete a reasonable number of games and see the board layouts, so I could infact count the number of instances of guess events in the process of manually solving each game. Either that or just get the AI to solve a set of games and get it to count the number of guess events... mmm automation.
Anyway, assume we came up with the probability of guess events for each board size. This would only give us a sense of what the true win ratio should be over a large enough set of games.
However the probability of solving the boards will be:
No Guess Event (100%) 1
1 Guess Event (50%) 0.5
2 Guess Events (50% * 50% ) 0.25
3 Guess Events ( 50% * 50% * 50%) 0.125
etc.
Do you notice a pattern? My point is that if we assume that each of these types of games has an equal probability of being presented to the AI, then we should get the probability of solving any game simply by averaging them together. The average of the above 4 game types is 0.46875... which is below chance. The further we go with the table of possible game types the lower the probable outcome is. However the fact that the results reported in the article suggest that the AI using the published strategies was still getting a win ratio of about 50% would suggest that the probability of the game type is not distributed evenly. With some simple spreadsheeting, the distribution turns out to be a simple falloff curve.
Based on the reported win ratio of about 50% I suggest that the games that are being presented to the AI probably involve only a small number of guess events.
However, we are only dealing with the ratio of games that were won. We cannot really make a conclusion about the games that the AI lost. They could infact have contained a much larger number of guess events. The above curve really only shows the ratio of the games that the AI can win, even when its guessing. This is simply the law of chance stating to bite hard. It doesn't actually tell us what the distribution of guess events is like in the games being presented to the AI. Inference go suck....
Does this give us any useful ways to optimse the strategy? Is there an angle that we are not trying simply because we want a general solution? Are we simply chasing a white rabbit down the wrong hole? Can we be the first to beat the law of chance? Bzzzzt. Wrong answer. There is no way to remove the effect of chance in these games. The AI must make a guess and the guess will always have a 50/50 chance of being correct. The number of guess events will generally be small (as shown in the graph above) but these are inviolate. So how do we beat it? Simply examine your assumptions.
As I proposed above, there are lots of ways to get a better win ratio by out-of-the-box thinking. Many of these strategies and approches would be considered as "cheating" by humans who are crippled by social ideals of "fair play". Keep in mind that the only rule given to the AI was to maximise the number of wins, so these are all successful strategies that the programmer has simply failed to implement. The AI has not been given these tools and certainly was not given a sense of "fair play" through which it might have decided not to employ some of those strategies. So in conclusion, the only reason that the AI has not got a 100% win ratio, is that the programmer failed to implement any successful strategies to acheive this ratio. Essentially crippling the AI.
A better AI would have a result that looked like this:
So whats the point?
The point is that the AI is handicapped by the "humanity" of the designer.
The above is an interesting article on how to build a minesweeper solver. There is a good discussion of various algorithmic solutions that can solve everything except the "must guess" states in the game.
The result of the AI in the article is a solver that acheives ~50% win/loss ratio. Which is effectivly chance.
It takes about 5seconds to figure out a couple of ways to beat the AI's win ratio using "indirect" strategies.
1) Only "complete" games that do not result in a "guess" state.
2) Generate a "result" screen without actually playing the games.
3) Throw a tantrum - blue-screen the computer, throw a critical error... whatever the AI equivilent is. This allows the AI to avoid registering a less than optimal win ratio
4) Use the AI to fiddle the number of mines and the board size variables to allow it to increase its win ratio. (Set the number of mines to 1 and the board size to expert and rack up a huge number of wins...tada)
5) Take a state snapshot of the game, clone the snapshot, play each position until a successful solution is found then move forward with that winning solution. This is a brute force mechanism to acheive a perfect 100% win ratio.
6) Use the "Replay" function to increse the proportion of games that are won using partial knowledge rather than starting with a fresh board every time.
This in itself is strange. If we assume that there must be a proportion of games that are solvable without reaching a "must guess" state, then these should be 100% solvable using the AI's methods. The rest of the games must involve one or more "must guess" situations. Obviously for a win, each guess is dependant which means that a game involving more than a very small number of guesses becomes improbable for the AI to "win". If we assume that the proportion of games that do not involve a guess event are fairly fixed ( say 5%) and the games involving guesses are all essentially chance, then we should still get a result of about 55% win ratio. But like any coin walk, this will only appear with a sufficiently large sample of games. (Approching infinity?)
So are the games being presented to the AI really random or is there another factor that is hiding this effect?
We can assume that as the number of mines increase relative to the size of the board, the number of "must guess" events required to "win" this kind of game would increase. So is there a sweet spot with these variables that allows for games with minimum guessing events but still results in a "credible" seeming AI? Probably the easy levels.
If memory serves there are a fixed number of mines in each of the three pre-set "hardness" levels. (Someone has uninstalled the windows games from my machine image..damit. Ok, Fixed that)
Beginner has 10 Mines on a 9x9 grid.
Intermediate has 40 mines on a 16x16 grid
Advanced has 99 mines on a 16x30 grid
As there is no clear way to calculate the probability of a particular number of "Must Guess" configurations occuring at a particular board+mine count ratio. (Well none that spring to mind anyway) I guess we could just do some sampling and develop a bell curve. (This would require that I could complete a reasonable number of games and see the board layouts, so I could infact count the number of instances of guess events in the process of manually solving each game. Either that or just get the AI to solve a set of games and get it to count the number of guess events... mmm automation.
Anyway, assume we came up with the probability of guess events for each board size. This would only give us a sense of what the true win ratio should be over a large enough set of games.
However the probability of solving the boards will be:
No Guess Event (100%) 1
1 Guess Event (50%) 0.5
2 Guess Events (50% * 50% ) 0.25
3 Guess Events ( 50% * 50% * 50%) 0.125
etc.
Do you notice a pattern? My point is that if we assume that each of these types of games has an equal probability of being presented to the AI, then we should get the probability of solving any game simply by averaging them together. The average of the above 4 game types is 0.46875... which is below chance. The further we go with the table of possible game types the lower the probable outcome is. However the fact that the results reported in the article suggest that the AI using the published strategies was still getting a win ratio of about 50% would suggest that the probability of the game type is not distributed evenly. With some simple spreadsheeting, the distribution turns out to be a simple falloff curve.
Based on the reported win ratio of about 50% I suggest that the games that are being presented to the AI probably involve only a small number of guess events.
However, we are only dealing with the ratio of games that were won. We cannot really make a conclusion about the games that the AI lost. They could infact have contained a much larger number of guess events. The above curve really only shows the ratio of the games that the AI can win, even when its guessing. This is simply the law of chance stating to bite hard. It doesn't actually tell us what the distribution of guess events is like in the games being presented to the AI. Inference go suck....
Does this give us any useful ways to optimse the strategy? Is there an angle that we are not trying simply because we want a general solution? Are we simply chasing a white rabbit down the wrong hole? Can we be the first to beat the law of chance? Bzzzzt. Wrong answer. There is no way to remove the effect of chance in these games. The AI must make a guess and the guess will always have a 50/50 chance of being correct. The number of guess events will generally be small (as shown in the graph above) but these are inviolate. So how do we beat it? Simply examine your assumptions.
As I proposed above, there are lots of ways to get a better win ratio by out-of-the-box thinking. Many of these strategies and approches would be considered as "cheating" by humans who are crippled by social ideals of "fair play". Keep in mind that the only rule given to the AI was to maximise the number of wins, so these are all successful strategies that the programmer has simply failed to implement. The AI has not been given these tools and certainly was not given a sense of "fair play" through which it might have decided not to employ some of those strategies. So in conclusion, the only reason that the AI has not got a 100% win ratio, is that the programmer failed to implement any successful strategies to acheive this ratio. Essentially crippling the AI.
A better AI would have a result that looked like this:
So whats the point?
The point is that the AI is handicapped by the "humanity" of the designer.
Tuesday, May 8, 2012
Thursday, April 5, 2012
Cheating via DirectX and OpenGL article
http://altdevblogaday.com/2012/04/02/extravagant-cheating-via-direct-x/
This is an interesting breakdown on cheat mechanisms and points to some of the interesting meta games being employed by coders on both sides.
My interest in this is both from a technical standpoint of learning about new ways to access and intereact with games ( useful for all type of research projects ) and for the strategies that are being proposed and the counter strategies.
I guess my interest is more about finding functional mechanisms that can allow AI's and Bots to intereact with game environments, simply for research purposes. My personal interest in cheating at a game is kind of the inverse. I can understand why people cheat and I'm truly fascinated by it as an emergent phenomena... I just value playing too much to actually do it myself. Then again, I do remember some truly frustrating games that I have happily played in god mode or searched the net for some cheats to get around some bug or irritant in the game.
My ego is not bound up in my social status and the fact that I don't play any of the big social games probably keeps me out of touch with just whats going on.... anyway.... back on topic.
There are some really useful techniques here for AI research. It's probably a good thing that I'm not involved in this kind of scene as there are so many more things I can think of to do than seem to be done at the present... lol. Best we don't explore any of those paths I think.
It was all so much simpler when we were hacking save files with a hex editor on single player games on the 486dx2 66. Then it was just us against the computer. No networks, no google... just slow painful puzzle solving in the wee small hours of the night until finally we cracked the file format and .... bascially wrecked the game for ourselves. Blatantly cheating in a game with other people .... just really sucks.
This is an interesting breakdown on cheat mechanisms and points to some of the interesting meta games being employed by coders on both sides.
My interest in this is both from a technical standpoint of learning about new ways to access and intereact with games ( useful for all type of research projects ) and for the strategies that are being proposed and the counter strategies.
I guess my interest is more about finding functional mechanisms that can allow AI's and Bots to intereact with game environments, simply for research purposes. My personal interest in cheating at a game is kind of the inverse. I can understand why people cheat and I'm truly fascinated by it as an emergent phenomena... I just value playing too much to actually do it myself. Then again, I do remember some truly frustrating games that I have happily played in god mode or searched the net for some cheats to get around some bug or irritant in the game.
My ego is not bound up in my social status and the fact that I don't play any of the big social games probably keeps me out of touch with just whats going on.... anyway.... back on topic.
There are some really useful techniques here for AI research. It's probably a good thing that I'm not involved in this kind of scene as there are so many more things I can think of to do than seem to be done at the present... lol. Best we don't explore any of those paths I think.
It was all so much simpler when we were hacking save files with a hex editor on single player games on the 486dx2 66. Then it was just us against the computer. No networks, no google... just slow painful puzzle solving in the wee small hours of the night until finally we cracked the file format and .... bascially wrecked the game for ourselves. Blatantly cheating in a game with other people .... just really sucks.
Thought experiments for Automated Starcraft Players
http://graphics.stanford.edu/~mdfisher/GameAIs.html
Starcraft 2 Automated Player
This is a brilliant writeup of both the architecture and some of the issues to consider when building an automated player for a game.
There are so many little bits of wisdom in this article that I want to spend time thinking about and hacking on.
First thoughts.
Interesting AI architecture. It (if I read it correctly) seems to use a kind of switched swarm intelligence for some of the decision making. Which makes sense when you consider the intricacy of trying to build a single unified decision making engine that could handle all the different individual units, their micro objectives and integrate that into a macro plan. (I would do that for a Phd with bells on...) kind of skynet for Starcraft....
The emergent strategies that have been implemented to deal with chaotic and imprecise events within the environment are interesting. Kind of obvious now its been pointed out. Again this moves a solution more toward a swam model where each agent/thread/program/entity deals with a small part of the map or a small objective as opposed to a large monolithic algorithm that would be a monster to debug. The tradeoff being that each of these small programs has loose coupling with all the others. They cannot share their internal micro state and need to implement some form of inter-entity communication if they need to cooperate. Which gets us back to resource competition, group decision making and all the other fun of peer agent models.
It's interesting to note that there are some higher level constructs in the architecture that are delegated to task switching and managing the stream of data comming in about the game state. Currently these are very single purpose; making debugging much simpler. But another task could be developed to run above the agents to implement a coordinating role and implement the "master plan" for the play session. (yet another Phd...)
The mirror driver implements the equivilent of a "sense" mechanism. We could describe it as "sight", but it does not share the same type of information stream as we understand "sight" in a biological form. Still its a fairly wide channel of information that is then internalised and used to generate a state represenation of the AI's environmental reality.
This state represeation will also include (expliclty or implicitly) some encoded knowledge about the artifacts in that environment. The number of different possible states that each individual artifact can exist in, the inter-artifact relationships, communications and inter-actions etc. It would be an interesting datascape to look at (yet another Phd...)
Dealing with the scene perception and understanding is interesting. It would be fun to offload this information to a different processor(or network) and see exactly how rich an internal representation could be generated from the information stream.
Dealing with the chaotic nature of the interaction with the opposing player, the state changes of the particular units and the static and dynamic elements of the environment is an interesting set of problems. (Called housekeeping in the article) Which again would generate an interesting set of rules and emergent behaviours in a good learning system.
It would be an interesting exercise to run a few hundred games on the same map and build up an understanding of the potential of each map. This may be an effective mechanism for debugging maps. Both the functional level debugging( finding holes and bugs ) and the logical debugging (balancing, removing or adding choke points, tuning difficulty etc). This is something I have been wanting to do for Chess for a while, is to calculate the true value of every square on the board. Probably someone has already done it... I just want to do it in as a multi-dimensional analysis, to see how many hidden variables I can tie to simple positional space, then to particular pieces and finally to particular strategic choices. Since there are only 32 peices, it should not take too long. Just have to raid a couple of databases for some game records. (yet another Phd...)
There is a fun little element mentioned called "Personas" which seems to be an undeveloped mechanism to mess with opponent players minds during the game. Its a simple blind system that uses a strategy of tying complex chat sentences during play....
Not sure who effective this would be but its an interesting strategic possibility. Attack the players outside the game environment.
Using a console overlay seems to be cute but wasteful. I would build a whole seperate GUI for monitoring the AI. (Benefit of multiple monitors I guess. )
At the end of the day, this is a great framework to build on, but seems to consist of a lot of fairly hard coded routines and strategies that are played out by a quite rigid system. Yes its fast, yes its beyond human capacity... but I don't feel like its moving beyond being a very complex script. I want to see my artifical children grow beyond my capacity.... not just leaverage hardward speed as a blunt instrument.
Starcraft 2 Automated Player
This is a brilliant writeup of both the architecture and some of the issues to consider when building an automated player for a game.
There are so many little bits of wisdom in this article that I want to spend time thinking about and hacking on.
First thoughts.
Interesting AI architecture. It (if I read it correctly) seems to use a kind of switched swarm intelligence for some of the decision making. Which makes sense when you consider the intricacy of trying to build a single unified decision making engine that could handle all the different individual units, their micro objectives and integrate that into a macro plan. (I would do that for a Phd with bells on...) kind of skynet for Starcraft....
The emergent strategies that have been implemented to deal with chaotic and imprecise events within the environment are interesting. Kind of obvious now its been pointed out. Again this moves a solution more toward a swam model where each agent/thread/program/entity deals with a small part of the map or a small objective as opposed to a large monolithic algorithm that would be a monster to debug. The tradeoff being that each of these small programs has loose coupling with all the others. They cannot share their internal micro state and need to implement some form of inter-entity communication if they need to cooperate. Which gets us back to resource competition, group decision making and all the other fun of peer agent models.
It's interesting to note that there are some higher level constructs in the architecture that are delegated to task switching and managing the stream of data comming in about the game state. Currently these are very single purpose; making debugging much simpler. But another task could be developed to run above the agents to implement a coordinating role and implement the "master plan" for the play session. (yet another Phd...)
The mirror driver implements the equivilent of a "sense" mechanism. We could describe it as "sight", but it does not share the same type of information stream as we understand "sight" in a biological form. Still its a fairly wide channel of information that is then internalised and used to generate a state represenation of the AI's environmental reality.
This state represeation will also include (expliclty or implicitly) some encoded knowledge about the artifacts in that environment. The number of different possible states that each individual artifact can exist in, the inter-artifact relationships, communications and inter-actions etc. It would be an interesting datascape to look at (yet another Phd...)
Dealing with the scene perception and understanding is interesting. It would be fun to offload this information to a different processor(or network) and see exactly how rich an internal representation could be generated from the information stream.
Dealing with the chaotic nature of the interaction with the opposing player, the state changes of the particular units and the static and dynamic elements of the environment is an interesting set of problems. (Called housekeeping in the article) Which again would generate an interesting set of rules and emergent behaviours in a good learning system.
It would be an interesting exercise to run a few hundred games on the same map and build up an understanding of the potential of each map. This may be an effective mechanism for debugging maps. Both the functional level debugging( finding holes and bugs ) and the logical debugging (balancing, removing or adding choke points, tuning difficulty etc). This is something I have been wanting to do for Chess for a while, is to calculate the true value of every square on the board. Probably someone has already done it... I just want to do it in as a multi-dimensional analysis, to see how many hidden variables I can tie to simple positional space, then to particular pieces and finally to particular strategic choices. Since there are only 32 peices, it should not take too long. Just have to raid a couple of databases for some game records. (yet another Phd...)
There is a fun little element mentioned called "Personas" which seems to be an undeveloped mechanism to mess with opponent players minds during the game. Its a simple blind system that uses a strategy of tying complex chat sentences during play....
Not sure who effective this would be but its an interesting strategic possibility. Attack the players outside the game environment.
Using a console overlay seems to be cute but wasteful. I would build a whole seperate GUI for monitoring the AI. (Benefit of multiple monitors I guess. )
At the end of the day, this is a great framework to build on, but seems to consist of a lot of fairly hard coded routines and strategies that are played out by a quite rigid system. Yes its fast, yes its beyond human capacity... but I don't feel like its moving beyond being a very complex script. I want to see my artifical children grow beyond my capacity.... not just leaverage hardward speed as a blunt instrument.
Tuesday, April 3, 2012
Emergent intelligent behaviour in the hive
http://www.scientificamerican.com/article.cfm?id=you-have-a-hive-mind
This is an interesting article on decision making in the bee hive.
The interesting aspects are both the mechanism and the result.
The mechanism of using inhibition to prevent deadlock is quite useful and I will play with it later.
The result however is even more interesting. In the article they talk about the two groups of bee scounts returning from scouting and starting to recruit undecided individiuals.
If we assume that both scouting parties found suitable locations ( they were not unsuitable ) the question is if there is any mechanism to select between locations based on the quality of the locations or are they simply randomly deciding between locations that all exceed some minimum specification ( dry, enclosed, no bears?)
I would assume that a bee scout can only report on a single location at a time. So, I would assume that if a scout is out looking, it will stop looking as soon as it finds a location that meets minimum spec. As there is no point keeping looking as it would then be making the decision of which was the location most worth reporting.
Another factor is distance, it makes sense that two scouting parties depart at the same time and the one who finds the first viable location would return first. Thus they to recruit other individuals for a time period until the second party returns. I would guess that this may be a factor and would favor moving the hive a short distance rather than a long distance.
Another bit of information that may play out is the strength of the scouts dance. If the scout is not feeling good about the location... they perhaps will not fully invest in their dance and so may be easier to inhibit. This may be influenced by the stress levels of the scout. If they find a location and its a bit crappy and some of their fellow scouts get eaten... would they still dance as strongly?
If you think about that, the undecided individual has to make a decision. Is what the scout tells me a better option than what I already know ( status quo)? Is what this scout tells me better than what another scout has already told me? (They can only get one lot of information at a time) Or is this better than what another scout may tell me in the future?
So there are still lots of aspects of the decision making process that are not clarified by this article. It just describes an anti-deadlock mechanism for group decision making.
This is an interesting article on decision making in the bee hive.
The interesting aspects are both the mechanism and the result.
The mechanism of using inhibition to prevent deadlock is quite useful and I will play with it later.
The result however is even more interesting. In the article they talk about the two groups of bee scounts returning from scouting and starting to recruit undecided individiuals.
If we assume that both scouting parties found suitable locations ( they were not unsuitable ) the question is if there is any mechanism to select between locations based on the quality of the locations or are they simply randomly deciding between locations that all exceed some minimum specification ( dry, enclosed, no bears?)
I would assume that a bee scout can only report on a single location at a time. So, I would assume that if a scout is out looking, it will stop looking as soon as it finds a location that meets minimum spec. As there is no point keeping looking as it would then be making the decision of which was the location most worth reporting.
Another factor is distance, it makes sense that two scouting parties depart at the same time and the one who finds the first viable location would return first. Thus they to recruit other individuals for a time period until the second party returns. I would guess that this may be a factor and would favor moving the hive a short distance rather than a long distance.
Another bit of information that may play out is the strength of the scouts dance. If the scout is not feeling good about the location... they perhaps will not fully invest in their dance and so may be easier to inhibit. This may be influenced by the stress levels of the scout. If they find a location and its a bit crappy and some of their fellow scouts get eaten... would they still dance as strongly?
If you think about that, the undecided individual has to make a decision. Is what the scout tells me a better option than what I already know ( status quo)? Is what this scout tells me better than what another scout has already told me? (They can only get one lot of information at a time) Or is this better than what another scout may tell me in the future?
So there are still lots of aspects of the decision making process that are not clarified by this article. It just describes an anti-deadlock mechanism for group decision making.
Thursday, December 22, 2011
Doomed Game AI Research
The problem with doing research on Game AI is that its all secret sauce. The AI systems are still considered as a competative advantage so "officially" the source is protected. The other reality is that they are a "work in progress"... so like most software, they are undocumented and constantly evolving...
This makes studying them at best observational research and at worst like trying to dent water.
Id are about the only company releasing their old game source... although without the assets, so it should be possible to reverse their AI system. This results in a 10yr old system that has been cloned by eveyone... kind of like game development DNA. And they used scripted AI anyway... so nothing to see there.
The next source is articles and books written by developers and designers. These are often short, conceptual and neat. The describe intention and mechanism... and we assume they reveal the "secret sauce"... but in reality the implemtations are going to have their own kinks and twists which don't make it into the article. Probably not significant but sitll there's a gap between reality and the description which may contain something interesting.
The other side of this is that no matter what the designers intended, emergent systems are by their very nature, a bit unpredictable. So after all that... observation and experimental testing may be the only way to really document them. Having the source would make it a lot faster....
But to make the whole observation problem slightly managable we just need more eyeballs... lucky someone invented internet forums to bitch about bad AI... whooot.
E.g Artificial Stupidity at tvtropes. This is a great collection of anecdotes about flawed AI.
Reading this suggests that the "game" is to figure out weaknesses in the enemy strategy... which, when you think about it is the point of any game, even those against a human player. So are these AI really "flawed" or are they imperfect enough to be satisfying? Do players want an unbeatable opponent? I would think not. So that only leaves "flawed" opponents... in other words "human", limited, imperfect.... this gets to the question of the type of flaw... will it be a "human" flaw? A Character "flaw"? So sort of tactical flaw based on not understanding the resources/economy/vehicles/environment?
Do we want the AI to display "human" flaws when they are simulating "things" that are not human? (How much role-playing do we want encoded in the AI?)
All this gets back to presenting a challenge to a player... which leads to the conclusion that no matter what the AI "should" be doing as far as actually manipulating game elements, it needs to be able to adapt to the players capacity in some fashion. I shall state it thusly...
Rule 1 of Game AI - Play the player not the game.
(Reminds me of a line from the movie "Searching for Bobby Fisher") The player defines the challenge, thus the AI needs to know the player. This gets me back to my on-going rant about modelling the player as the basis of a game AI system.
It's obvious that the vast majority of game developers (99%+ would be my conservative estimate) spend no resources on modelling the player, they simply try to react to the current state of the players avatar or their units and leave it at that. Pour on a couple of reactive heuristics and some tuning constants and cross their fingers. Or simply have a "Novice", "Middle"and "Hard" settings. This presents a simple target for the game tuners to work with but also allows the player to exercise some choice about the type of game they want to play "Now". Sometimes, I just want to blat around in a game without being "Challenged". So I think its important to allow the player to choose their difficulty level in some fashion.
Reading more of the comments leads to the conclusion that the second rule must be...
Rule 2 of Game AI - Play all the game elements.
By this I mean that the AI should have heuristics governing all the play elements. In the case where there are dozens or hundreds of different "bits" in the game, the developers have just made a stick to beat themselves with. Permutation is the enemy.. until they figure out a way to build an AI to write the rule sets for them... Duh! Computers are there to do the repetative work...
Obviously this starts to bite when the AI is computationally limited and the rulesets exceed the resources allocated. But even in those situations it should be a case of creating an AI that can decide what to spend that limited CPU resource on... one ruleset to rule them all... lol.
It's easy to see how developers dig themselves into these holes by trying to hand tune games with insane numbers of relationships between game elements.
Finally, we get to....
Rule 3 of Game AI - Match your players expectations.
The common thread though the forums is that players expectations are being violated. It's not that the AI is smarter or dumber or creates wildly un-desirable behaviour (although that's often the end result) but that player "Notice" when the AI does something they think is uncharacteristic. If they are expecting a smart AI and it acts stupid... tada... forums catch fire.
So, the big issue is to manage the players expectations. Tell them before, during and after what they should expect. Currently, the situation is more that players learn by observation (nothing bad about that) except their learning starts long before they get to most games. If the game is a strategy game, they have probably seen a couple of movies or read a book or two that have shaped their expectations. These feed into their expectations of the game behaviour... which is quite reasonable as the game is drawing on those genre's for art and marketing... so its reasonable for the player to carry their expectations into the game.
Am I suggesting that developers should not be ambitious and create games using genre material that the AI is not yet capable of simulating? That seems a bit limiting... but it would be nice to see the time and energy put into the AI and simulation that matched the quality of the art work, for instance.
I think there is a sense of acheivement when a player figures out (or reads on a forum) an exploitable flaw in a games AI. Spending the time learning about your enemy, testing them and finally beating them is the essence of competition. Because of the re-playability of games, they turn into a puzzle that can be beaten if you are persisent. In this case having flaws in the AI behaviour is kind of essential.
When the AI is not simulating an "Enemy" to be beaten but is trying to generate background behaviour, showing flaws is just wrong. The suspension of disbelief that the player needs to buy into for the narrative to work is essential and fragile. Break this and the game is fundamentally broken. The great thing is that players are able to selectivly ignore instances and forgive mistakes and regain their flow given enough other material to continue playing. But multiple, repeated or massive violations drag the game down to a point where it becomes a sham and the player feels foolish for "playing along" with it and abandons it. Because this kind of simulated life buys into some fairly complex expectations that the players will be carrying into the game, its a particularly hard problem to get right.
Rule 4 of Game AI - Life is infinitly complex, the players perception is not.
Resource limits are real in most games so procedural generation is the only viable mechanism for behaviour and art assets when you want to produce complexity. But not all games want to end up looking like "Spore". So there needs to be some more tools in the toolbox.
Scenario Templating, Procedural generation, Scripts, Rulesets, Heuristics, Skeletal animation + Skins, motion libraries, behaviour libraries, better reaction heuristics, player modelling, AI systems to generate AI systems, cheating, suggestion, borrowing from the players experience.
Good narrative works by allowing the reader to fill in many of the blanks themselves and just sketches the background. I feel that most games are able to do this convincingly enough but the question is how to identify and fix the weak points.
More thinking to do.
So whats the linear solution to the exponential problem?
Have the AI do what people do, use feedback... predict the result of their activity, do the behaviour and then evaluate that result, modify their ruleset, rinse, repeat... This simple feedback loop should prevent a lot of the repetative stupidity that I see in the forum posts. It would also help with game tuning. Building evaluation critieria is much easier than having a blind ruleset that is context insensitive.
There are some more interesting examples here http://tvtropes.org/pmwiki/pmwiki.php/Main/SpitefulAI
This makes studying them at best observational research and at worst like trying to dent water.
Id are about the only company releasing their old game source... although without the assets, so it should be possible to reverse their AI system. This results in a 10yr old system that has been cloned by eveyone... kind of like game development DNA. And they used scripted AI anyway... so nothing to see there.
The next source is articles and books written by developers and designers. These are often short, conceptual and neat. The describe intention and mechanism... and we assume they reveal the "secret sauce"... but in reality the implemtations are going to have their own kinks and twists which don't make it into the article. Probably not significant but sitll there's a gap between reality and the description which may contain something interesting.
The other side of this is that no matter what the designers intended, emergent systems are by their very nature, a bit unpredictable. So after all that... observation and experimental testing may be the only way to really document them. Having the source would make it a lot faster....
But to make the whole observation problem slightly managable we just need more eyeballs... lucky someone invented internet forums to bitch about bad AI... whooot.
E.g Artificial Stupidity at tvtropes. This is a great collection of anecdotes about flawed AI.
Reading this suggests that the "game" is to figure out weaknesses in the enemy strategy... which, when you think about it is the point of any game, even those against a human player. So are these AI really "flawed" or are they imperfect enough to be satisfying? Do players want an unbeatable opponent? I would think not. So that only leaves "flawed" opponents... in other words "human", limited, imperfect.... this gets to the question of the type of flaw... will it be a "human" flaw? A Character "flaw"? So sort of tactical flaw based on not understanding the resources/economy/vehicles/environment?
Do we want the AI to display "human" flaws when they are simulating "things" that are not human? (How much role-playing do we want encoded in the AI?)
All this gets back to presenting a challenge to a player... which leads to the conclusion that no matter what the AI "should" be doing as far as actually manipulating game elements, it needs to be able to adapt to the players capacity in some fashion. I shall state it thusly...
Rule 1 of Game AI - Play the player not the game.
(Reminds me of a line from the movie "Searching for Bobby Fisher") The player defines the challenge, thus the AI needs to know the player. This gets me back to my on-going rant about modelling the player as the basis of a game AI system.
It's obvious that the vast majority of game developers (99%+ would be my conservative estimate) spend no resources on modelling the player, they simply try to react to the current state of the players avatar or their units and leave it at that. Pour on a couple of reactive heuristics and some tuning constants and cross their fingers. Or simply have a "Novice", "Middle"and "Hard" settings. This presents a simple target for the game tuners to work with but also allows the player to exercise some choice about the type of game they want to play "Now". Sometimes, I just want to blat around in a game without being "Challenged". So I think its important to allow the player to choose their difficulty level in some fashion.
Reading more of the comments leads to the conclusion that the second rule must be...
Rule 2 of Game AI - Play all the game elements.
By this I mean that the AI should have heuristics governing all the play elements. In the case where there are dozens or hundreds of different "bits" in the game, the developers have just made a stick to beat themselves with. Permutation is the enemy.. until they figure out a way to build an AI to write the rule sets for them... Duh! Computers are there to do the repetative work...
Obviously this starts to bite when the AI is computationally limited and the rulesets exceed the resources allocated. But even in those situations it should be a case of creating an AI that can decide what to spend that limited CPU resource on... one ruleset to rule them all... lol.
It's easy to see how developers dig themselves into these holes by trying to hand tune games with insane numbers of relationships between game elements.
Finally, we get to....
Rule 3 of Game AI - Match your players expectations.
The common thread though the forums is that players expectations are being violated. It's not that the AI is smarter or dumber or creates wildly un-desirable behaviour (although that's often the end result) but that player "Notice" when the AI does something they think is uncharacteristic. If they are expecting a smart AI and it acts stupid... tada... forums catch fire.
So, the big issue is to manage the players expectations. Tell them before, during and after what they should expect. Currently, the situation is more that players learn by observation (nothing bad about that) except their learning starts long before they get to most games. If the game is a strategy game, they have probably seen a couple of movies or read a book or two that have shaped their expectations. These feed into their expectations of the game behaviour... which is quite reasonable as the game is drawing on those genre's for art and marketing... so its reasonable for the player to carry their expectations into the game.
Am I suggesting that developers should not be ambitious and create games using genre material that the AI is not yet capable of simulating? That seems a bit limiting... but it would be nice to see the time and energy put into the AI and simulation that matched the quality of the art work, for instance.
I think there is a sense of acheivement when a player figures out (or reads on a forum) an exploitable flaw in a games AI. Spending the time learning about your enemy, testing them and finally beating them is the essence of competition. Because of the re-playability of games, they turn into a puzzle that can be beaten if you are persisent. In this case having flaws in the AI behaviour is kind of essential.
When the AI is not simulating an "Enemy" to be beaten but is trying to generate background behaviour, showing flaws is just wrong. The suspension of disbelief that the player needs to buy into for the narrative to work is essential and fragile. Break this and the game is fundamentally broken. The great thing is that players are able to selectivly ignore instances and forgive mistakes and regain their flow given enough other material to continue playing. But multiple, repeated or massive violations drag the game down to a point where it becomes a sham and the player feels foolish for "playing along" with it and abandons it. Because this kind of simulated life buys into some fairly complex expectations that the players will be carrying into the game, its a particularly hard problem to get right.
Rule 4 of Game AI - Life is infinitly complex, the players perception is not.
Resource limits are real in most games so procedural generation is the only viable mechanism for behaviour and art assets when you want to produce complexity. But not all games want to end up looking like "Spore". So there needs to be some more tools in the toolbox.
Scenario Templating, Procedural generation, Scripts, Rulesets, Heuristics, Skeletal animation + Skins, motion libraries, behaviour libraries, better reaction heuristics, player modelling, AI systems to generate AI systems, cheating, suggestion, borrowing from the players experience.
Good narrative works by allowing the reader to fill in many of the blanks themselves and just sketches the background. I feel that most games are able to do this convincingly enough but the question is how to identify and fix the weak points.
More thinking to do.
So whats the linear solution to the exponential problem?
Have the AI do what people do, use feedback... predict the result of their activity, do the behaviour and then evaluate that result, modify their ruleset, rinse, repeat... This simple feedback loop should prevent a lot of the repetative stupidity that I see in the forum posts. It would also help with game tuning. Building evaluation critieria is much easier than having a blind ruleset that is context insensitive.
There are some more interesting examples here http://tvtropes.org/pmwiki/pmwiki.php/Main/SpitefulAI
Tuesday, December 6, 2011
Mesh Topography in networking and life....
http://sha.ddih.org/2011/11/26/why-wireless-mesh-networks-wont-save-us-from-censorship/
Good summary of some of the problems in distributed networks (and a few other technical issues) and some of the "solutions" to using a distributed network as a "solution" to what is essentially a beuracratic attack on the existing network.
This is applicable to networks of self organizing agents, information distribution networks in games and the simulation of information networks in games.
Good summary of some of the problems in distributed networks (and a few other technical issues) and some of the "solutions" to using a distributed network as a "solution" to what is essentially a beuracratic attack on the existing network.
This is applicable to networks of self organizing agents, information distribution networks in games and the simulation of information networks in games.
Friday, December 2, 2011
Façade and a Rant on Interactive Narrative Systems
http://www.interactivestory.net/
This is an interesting experimental interactive narrative system. The list of pubs looks like some good reading and ends with a bibliography of the same who's who of interactive narrative that I was reading a decade ago.
My first through is... has nothing changed? They seem to still be trying to generate emergent drama involving a set cast of characters in a sterile environment. I find it a bit strange that the product is intended to "appeal to the adult, non-computer geek, movie-and-theater-going public".... probably should have made a movie if this was the point. Sounds like they are fundamentally missing the point of interactive narrative.... if its an art form unlike anything else, then it will need to define its own audience... however, if its an art form that will be defined by an existing audience who already has a well defined taste in a particular media form... why not just stick with that media form? There is no need to replace "movies and theater", which are at their essence an experience of someone elses story... with an art form like interactive fiction which is an art form that requires the consumer to engage and add their essence to the narrative.
One observation I have made with the various interactive fiction examples I have seen is that very few people are capable story tellers. Its a skill that takes a great deal of practice. This is why great writers and poets are celebrated... because they are unusual. Have a look at facebook or twitter for examples of how few people think in narratives. Expecting everyone to be able to "bring the magic" to an intereactive narrative is just not realistic. This will make it a very niche experience for a select few. And one that will not be able to be shared with others unless its recorded.... in which case the whole system becomes an interactive authorship system for creating movies/stories.
On the other hand, if users are expected to suck at creating narratives and instead the system "takes them by the hand and generates a narrative around them... irrespective of the quality of the players interaction... then the player is essentially just being used as a source of randomness which is being fed into and filtered by a narrative engine which does 100% of the narrative creation. In which case.... why bother?
If a user is really along for the ride... then my guess is they will figure it out. The second they do something stupid and the narrative engine "smoothes" it out... they will know they are being "managed". If the engine lets the stupid into the narrative... then the users suspension of disbelief will be shattered.
This is the flaw in a narrative system that expects the player to inject "talent" as part of the experience.
So how can this
This is an interesting experimental interactive narrative system. The list of pubs looks like some good reading and ends with a bibliography of the same who's who of interactive narrative that I was reading a decade ago.
My first through is... has nothing changed? They seem to still be trying to generate emergent drama involving a set cast of characters in a sterile environment. I find it a bit strange that the product is intended to "appeal to the adult, non-computer geek, movie-and-theater-going public".... probably should have made a movie if this was the point. Sounds like they are fundamentally missing the point of interactive narrative.... if its an art form unlike anything else, then it will need to define its own audience... however, if its an art form that will be defined by an existing audience who already has a well defined taste in a particular media form... why not just stick with that media form? There is no need to replace "movies and theater", which are at their essence an experience of someone elses story... with an art form like interactive fiction which is an art form that requires the consumer to engage and add their essence to the narrative.
One observation I have made with the various interactive fiction examples I have seen is that very few people are capable story tellers. Its a skill that takes a great deal of practice. This is why great writers and poets are celebrated... because they are unusual. Have a look at facebook or twitter for examples of how few people think in narratives. Expecting everyone to be able to "bring the magic" to an intereactive narrative is just not realistic. This will make it a very niche experience for a select few. And one that will not be able to be shared with others unless its recorded.... in which case the whole system becomes an interactive authorship system for creating movies/stories.
On the other hand, if users are expected to suck at creating narratives and instead the system "takes them by the hand and generates a narrative around them... irrespective of the quality of the players interaction... then the player is essentially just being used as a source of randomness which is being fed into and filtered by a narrative engine which does 100% of the narrative creation. In which case.... why bother?
If a user is really along for the ride... then my guess is they will figure it out. The second they do something stupid and the narrative engine "smoothes" it out... they will know they are being "managed". If the engine lets the stupid into the narrative... then the users suspension of disbelief will be shattered.
This is the flaw in a narrative system that expects the player to inject "talent" as part of the experience.
So how can this
AI Middleware Tools
http://www.industrygamers.com/news/ai-building-smarter-games/
Advertorial on current generation game AI. Mentions some tools.
http://www.xaitment.com/english/products/xaitcontrol/features.html
Another AI Tool Suite. Seems to be based on Finite State Machines for the AI behaviour graphs. This is probably fine for the bulk of games where the player is interacting with the NPC for a relativly short period of time, but I would debate if its sufficient for RPG's of any depth, where the player is trying to interact with an NPC, often as deeply as they possibly can, to extract information, engage in trade, form a complex relationship ( or a cheap and superficial one...) a simple FSM is just not going to cut it.
Advertorial on current generation game AI. Mentions some tools.
http://www.xaitment.com/english/products/xaitcontrol/features.html
Another AI Tool Suite. Seems to be based on Finite State Machines for the AI behaviour graphs. This is probably fine for the bulk of games where the player is interacting with the NPC for a relativly short period of time, but I would debate if its sufficient for RPG's of any depth, where the player is trying to interact with an NPC, often as deeply as they possibly can, to extract information, engage in trade, form a complex relationship ( or a cheap and superficial one...) a simple FSM is just not going to cut it.
Radiant AI reviews
Started collecting some commentary on the Radiant AI engine.
http://bitmob.com/articles/dimming-the-radiant-ai-in-oblivion
There are some interesting comments following the article.
This article talks specifically about the choice that the developers of Oblivion made about the AI. It makes some good points about the problems with emergent systems vs the needs and conventions of a narrative game. Its interesting to see that when the AI system generated unexpected results, the designers chose the conservative solution of going back to simple scripts rather than trying to fix the emergent system ( which would have been much more fun)
http://www.somethingawful.com/d/news/asshole-physics-meet.php
This article, although fairly low on results illustrates an interesting point about the AI in games, namely how it can be tested or re-purposed for entertainment. I think, while this is clearly not in the spirit of the game, it does suggest a functional way of testing emergent AI systems. Act like an Asshole and see if the NPC's treat you like one. In the case of the version of the AI that shipped with Oblivion... clearly they did not.
http://video.google.com/videoplay?docid=-8900168580155619696&q=oblivion+chapter&pl=true
This is the pre-release demo video for Oblivion showing some of the possibilities of the AI system which did not all make it to release in Oblivion but seem to have been polished for Skyrim.
http://videosift.com/video/Oblivions-Radiant-AI-not-as-great-as-they-said-it-would-be
Another video illustrating how unresponsive the AI can be to events in the immediate environment.
http://www.ttlg.com/forums/showthread.php?t=105339&page=1
This is a four page forum thread about various aspects of the Oblivion AI wins and losses. Some interesting points.
http://elderscrolls.filefront.com/file/NPC_with_jobs;73212
One of the AI Mod's for Oblivion. Seems to be a rebuild of some of the generic NPC stereotypes along with a couple of other odds and ends. Includes source. Very interesting.
http://www.reddit.com/r/skyrim/comments/mqw0h/the_radiant_ai_really_wowwed_me_tonight/
Here are some fun stories from Skyrim about AI interactions.
http://bitmob.com/articles/dimming-the-radiant-ai-in-oblivion
There are some interesting comments following the article.
This article talks specifically about the choice that the developers of Oblivion made about the AI. It makes some good points about the problems with emergent systems vs the needs and conventions of a narrative game. Its interesting to see that when the AI system generated unexpected results, the designers chose the conservative solution of going back to simple scripts rather than trying to fix the emergent system ( which would have been much more fun)
http://www.somethingawful.com/d/news/asshole-physics-meet.php
This article, although fairly low on results illustrates an interesting point about the AI in games, namely how it can be tested or re-purposed for entertainment. I think, while this is clearly not in the spirit of the game, it does suggest a functional way of testing emergent AI systems. Act like an Asshole and see if the NPC's treat you like one. In the case of the version of the AI that shipped with Oblivion... clearly they did not.
http://video.google.com/videoplay?docid=-8900168580155619696&q=oblivion+chapter&pl=true
This is the pre-release demo video for Oblivion showing some of the possibilities of the AI system which did not all make it to release in Oblivion but seem to have been polished for Skyrim.
http://videosift.com/video/Oblivions-Radiant-AI-not-as-great-as-they-said-it-would-be
Another video illustrating how unresponsive the AI can be to events in the immediate environment.
http://www.ttlg.com/forums/showthread.php?t=105339&page=1
This is a four page forum thread about various aspects of the Oblivion AI wins and losses. Some interesting points.
http://elderscrolls.filefront.com/file/NPC_with_jobs;73212
One of the AI Mod's for Oblivion. Seems to be a rebuild of some of the generic NPC stereotypes along with a couple of other odds and ends. Includes source. Very interesting.
http://www.reddit.com/r/skyrim/comments/mqw0h/the_radiant_ai_really_wowwed_me_tonight/
Here are some fun stories from Skyrim about AI interactions.
Sunday, November 27, 2011
Some posts on basic AI for NPC's
http://forums.tigsource.com/index.php?topic=19455.0;wap2
Some good discussion of practical basic AI for game NPC's.
Some good discussion of practical basic AI for game NPC's.
Subscribe to:
Posts (Atom)