Journal vidarh's Journal: The structure of randomness 4
Pseudo-random numbers are numbers that are being generated with some algorithm that makes it possible to repeat the sequence if you seed the generation algorithm with the same value as you used initially, but that still seem to be random in that it is incredibly hard to predict the sequence without knowing the algorithm, and that have statistical properties that closely mirror random numbers.
Perhaps the most notable example of use of pseudo random numbers is Elite. (If you've never played Elite, shame on you, and you have no excuse, since there's an open source remake).
Elite is almost entirely based around pseudo random numbers: The universes are generated by seeding a random number generator with a fixed value. The planet names, political and economical data are generated by seeding the random number generator with a seed extracted from the random number generator with the universe seed.
Change the universe seed, and the game changes, completely.
Thats what allowed the original Elite to run on machines like the C64, the BBC, and a ton of others - contrary to many modern games, they didn't have to store ANY data about the planets, only a few bytes for the universe seed and a small set of functions to generate the code.
More modern examples of pseudo random numbers in computer games is Civilization and all it's descendants, Sim City and it's descendants and many other map based games.
However randomness could be used so much further. Games like civilization only create a basis for the further game, then AIs take over. Elite conceptually went much further, by basing the entire structure of the universe, including it's civilizations, on randomness, allthough it manifested itself in the game rather crudely (it didn't really affect you that the planet you visited was inhabited by green felines)
The main appeal of pseudo random numbers, or for that matter any formula or algorithm that can reasonably quickly generate unpredictable but repeatable sequences is that it allows you to represent a much larger world than you could ever hope to design or store on the users system. It also allow you represent a world with much larger amount of detail than would otherwise be practical.
It's worth noting that pseudo random numbers is usually only used to seed specialized generation algorithms for generating various part of the world.
For a world that is so large and complex, it makes sense that you don't need to model all events via AI's either. Most complex games, including Civilization for instance, hide a lot of what is going on from you. In most Civilization style games, you can only see what's going on around your own units, and even then there might be further restrictions on what you see.
In Elite, you only see whats going on immediately around your ship.
These restrictions play right into your hand if you want to use a randomly generated world.
Many of the benefits of randomness go straight out the window if you need to keep track of changes to account for developments in the world. However, in many types of games you don't need to most of the time.
Take an Elite style game, for instance, and add detail: Government types changes, military control and dominance fluctuates, etc. For almost any kind of change, you can put together an equation that give fluctuations over time that are reasonable. Add a few elements to the equation where you can affect it by random variables, and you have a model for generating a world where you can generate not only every position in space, but also in time.
Depending on the level of detail you want, you can go in at an arbitrary time and an arbitrary point in space, and see roughly what went on (in a newspaper headline type of way - details of events, such as how a ship navigates, will likely seem weird to a human player).
Now you have a static world that can be regenerated from a small string of numbers. But what about the player and non player AIs? Instead of recording everything that happens, you can calculate most of it, and whenever a player does something, you store information about deviations from the randomly generated world.
Imagine that you as a player in a space strategy game, destroy a ship. The ship was part of a military fleet trying to conquer a world. As a result of your action, the fleet loses its advantage, and the game doesn't manage to compensate by weakening the opposition quickly enough (without making it too obvious for the player), so the invasion fails, and the timeline doesn't work out anymore.
What should the game do? Record a deviation, and determine a target time for returning to the timeline. The world is under government X instead of Y, but some time over time T, the game will create events that will bring things back to where it should be.
As long as it's done smoothly enough, the players won't notice. This model also has the advantage that if the player stays close, then the player keeps affecting the timeline and will see little of the effects of the game slowly compensating to bring things back in sync, and if the players move around a lot, the player won't see whats going on, and any logical flaws in the compensation that is being done will be hidden.
This idea is essentially based on one of many theories trying to resolve the problems of time travel: What if any changes you make to the past will be compensated for so that you can only cause disruption for a limited period of time, before at least most of the rough differences between the two timelines have been resolved. So the further back in time you go, the less effect you can have on the present.
Structuring a world via pseudo random numbers in both time and space indeed make the game itself time travel in a way: The entire timeline of the game was set before the game started, and you as the player travel back in time and are allowed to affect limited pockets of space time, but as soon as you turn your back, the game engine compensates away all your changes, making you just a ripple in the ocean...
Wish I had time to do game programming
Pseudo-randomness and AI (Score:2)
I have been thinking about the same, pseudo-randomness, and maybe genetic algorithms in game NPC AI. If you think about Ultima Online and other MMORPGs one of the most crippling and limiting things is the fact that once the weaknesses of let's day a dragon - or other quite mighty opponent have been discovered, everyone can basicly slice them into pieces without any risk.
It would be much more interesting, if mutations were utilized. Assume, that every 10th troll that spawns, would have it's characteristics tweaked into certain direction using a pseudo-randomly generated mutation seed. If this troll survives in the world long enough without being killed, it's "genetics" would be utilized as basis for the next mutation in the pseudo-random series.
In addition to only mutating the basic characteristics of the NPC, you could mutate also it's AI patterns. And don't stop there, you could also mutate the NPCs co-operational capabilities with other NPCs. When these - evolving NPCs - have to face and survive against human players, the result might be very interesting. If this mutation is controlled in a sophisticated way, it could eventually lead to very talented and interesting NPC opponents.
Re:Pseudo-randomness and AI (Score:2)
I've seen articles hinting that the NPCs in Terminus (space strategy/action game) actually either use genetic algorithms or were evolved using genetic algorithms.
Genetic algorithms for games, particularly long running strategy games, is a very interesting field. Especially since it's so "easy" to do:
Just write your AI as usual, separate out variables that can be used as basis for mutation into a set of "genes".
Then when the game is running, the advantage you have in a game is that you most of the time will want a relatively stable population of opponents - you don't want the player to be able to eradicate someone. So whenever some NPC "dies", one way that might work fine is more or less randomly choosing one set, two sets or no set of genes from the population of living NPCs.
If you choose two sets, you use crossover - you selet a piece of genes from one of them and a piece from the other and combine them, and use that for the new NPC.
If you choose one set, you randomly apply mutation.
If you choose no sets, you randomly generate new genes.
By randomly choosing from the set of living NPCs whenever someone dies, you are implicitly favoring the better NPCs, as since they live longer they will have a higher chance of being chosen. At the same time, you introduce randomness, since deaths of NPCs aren't evenly spaced - some long living NPCs will never be chosen because noone is killed for a long time, possibly because the player is battling the very NPC in question. And some short living NPCs will be chosen tons of times because the player(s) are wasting a huge number of NPCs over a short time period.
I think that the combination of a randomly generated "universe", whether it is really a universe, a planet, a city or whatever, with AIs is very promising.
A random universe with "elastic" timelines, like I described in the journal entry allow you to get the size and detail, but AIs can provide dynamic behaviour that deviates from the generated timeline in the same way human players do, which would probably be important in order to be able to get more complex behaviour on detail level.
One example would be the example of a planetary conquest. A formula based approach based on pseudo random numbers could easily generate a believable timeline for the conquest on the detail level of which battles were fought where, who won, and even perhaps which ships gets destroyed where by weighting strengths of the opponents etc. What the pseudo random number approach won't get you is a believable battle from the point of view of a player that is actually present, watching and participating in the action.
What I envision there, is AIs under overall subtle control of a game engine that try to nudge the results towards the generated timeline: Let's say fleet A is supposed to win over fleet B, the game engine would choose AIs for fleet A's ships among higher ranking AIs than for fleet B, would give fleet A a numerical advantage, and better ships. But the battle itself would have to be fought by AIs programmed to fly and fight reasonably realistically, or it wouldn't be believable to the player.
Vidar
Re:Pseudo-randomness and AI (Score:2)
We could start by discussing on the genre, potential plots and other major characteristics of the game and continue to specify it in further detail for some time. Once it would be ready and if it is interesting enough, I am sure that atleast one of the journal readers represent a game company and could propose the manuscript to be really utilized. Or alternatively, it might spawn an open source project to implement it.
I tend to forget the constraints of reality, so maybe this is nonsense. But I truly believe it could be worth a try :)
Re:Pseudo-randomness and AI (Score:2)
Your idea is interesting, but my interest is more in open ended games, where a manuscript/story lines are less important than the general setting. I'd be very interested in seeing a space exploration game, for instance, based around some of these ideas. I've already mentioned Terminus and Elite. A cross between the two, with additions of concepts from Frontier etc. would be extremely cool.
It might be more fruitful to try to explore the ideas of interaction between a player and a pseudo-random mostly static time space continuum, as a start though, as my ideas there are very rough and I'm sure there are lots of problems. I'll post some more ideas soon.