How do video games allow you to take different paths each time you play?

[billa12]

Does a chess program game knows every move that you can make? Does that mean that every possible outcome exists in the chess game and it just creates a path everytime you play by saving that path? Does this apply to more complex games with open worlds? So would it be correct to say the second you turn on the game all possible action the player can perform from beginning to end exist? If this is not explained I will try again.

I have no knowledge of programming so could you keep your answer simple.

 

[chiro]

Hey billa12 and welcome to the forums.

The programs do have rules for the moves that can be made for both the human and the AI component if one exists.

It's not a simple thing though because a lot of different things determine this. Let's give a few examples.

You have for example generic non-game code in things like 3D games. An example is collision detection. Most of the time collision detection will always block players from moving through walls and other objects, regardless of the game specific code.

Then you have game specific code. This code might restrict the user from doing certain things like going into certain areas or doing other specific things.

With the AI in games like Quake III, the AI knows all the information about your position and uses it to make decision. It's like the AI bots have a lock-on all the time and once you are visible (which is determined through computational geometry techniques), they use some instructions (code) on how to act and shoot throughout the game. There are usually parameters that correspond to difficulty.

With chess or tic-tac-toe type games, there are algorithms for the code to create good moves that vary with difficulty. Remember that a computer can calculate many many moves before it finally makes one, and often in these kinds of games that's exactly what they do.

But to answer your question, the answer is actually often more than not no. The games often do not calculate every single possible path, but they calculate enough to let them make a decision.

What the algorithms do, especially in computational geometry for 3D games, is that the algorithms eliminate enough information so that they only have to consider a good enough minimum.

This happens for example when you draw a frame on your video card: the game engine actually narrows down the amount of objects to roughly what you can see and draws those. If they didn't do this then your game would be really sluggish and you probably wouldn't be able to play it smoothly for more than 5 seconds unless you designed the engine in a different way.

The way that games also save information is different. For example if a game wanted to save a users gameplay for say a playback feature, what typically happens is that it stores all the events that happened in the game and on playback simply sends those events back to the engine as if they came from the user (it's just capturing the data). The events can be anything from key presses to AI movements and so on (usually with AI we use random number generators and provide a seed).

For save-games it depends on the game and the engine, but the idea is to get all the variables that are defined and write them to a file. Then when you load you read all these variables from a file and load them into the engine. That's the basic idea.

Your answer depends on the type of game and how it's coded, but hopefully the above answer has shed some light on an answer to your question.

 

[rcgldr]

Does a chess program game knows every move that you can make?

No. The main component is a mathematical algorithm that takes the current position of a chess game and calculates a value that represents the positional and material advantage for the two opponents. Given this, for each opponent, the computer can try every possible single move from the current position to find the best possible value for the next position, then follow that with every possible response, then the next move, and so on, perhaps 6 to 8 moves ahead or more (I'm not sure how many moves ahead that the best chess programs / computers can look ahead these days). The better programs also include large tables for the initial moves, perhaps up to 8 moves, and for all of the common end games, some involving 20 moves or more, such as a king and two knights versus king and one pawn. There may be table entries of specific positions to fix any "weaknesses" found in the core algorithm.

The main reason the best chess programs can beat the best human chess players is the shear brute force of being able to look ahead a sufficient number of moves, considering a huge tree beyond what a human could consider, combined with those large tables, made possible by the speed and capacity of modern computers. There are competions between chess programs. Wiki article:

http://en.wikipedia.org/wiki/Computer_chess

Does this apply to more complex games with open worlds?

Generally with open world type games, the video game doesn't need to deal with complex strategies as much as it just needs to render objects within the player's view, and to have those objects interact based on a combination of what the player is doing and how the game wants the objects (like opponents) to respond. For the most part, a video game can ignore objects that are "out of range" of the players current position, unless the game includes the objects interacting with each other.

 

[stonecoldgen]

I think the guys above have already answered your question pretty well, but just as a curious fact (in case you want to know) to beat a 2600 computer in a chess game, you need a specific set of mooves, else, you will not win.

 

[rorix_bw]

Does a chess program game knows every move that you can make?

No, chess has too many moves for that.

The computer performs a mathematical calculation that produces a rating or score for a position. e.g. +1 point per peice, +1 point if it has more board space, etc etc

It then tries different moves and works out the scores for the new board positions and records which gives it the most points. It then does the same for the other player and works out which give the other player the least points. By looking at the chain of moves, and the score differences, it decides what to do. This is called "min max strategy".

The ability of the computer is determined by how good it's scoring formula is, and how many moves ahead it can calculate. I haven't looked a modern chess program but 7 moves ahead (4 for one player, 3 for the other) was about where most chess software was, the last time I looked. They are certainly a lot better now.

Of course in the end game with fewer pieces and moves, it can think much further ahead. They can indeed play "perfect" endgames. In the opening like a human player it can play from a memorised list. There are "standard openings" in Chess that good players will memorise.

Checkers/draughts is simple enough that the computer can determine all possible moves. It could in theory then play from a pre-computed list of moves, but it could also work them out as it needs them, as there are not as many.

Does this apply to more complex games with open worlds

That is actually really complex and it can't be explained without going into programming. I feel kind of bad about saying that, but I can't really explain how AI of that type works in a few sentences, especially as lot of the logic is now in the game data (i.e. the level data) instead of the core code. If you give me a particular situation in a particular game I can explain how *I* would have done it, but I doubt that's going to the way they did it - there really isn't a standard model for anything more complex than Pacman.

Although I can explain how the Pacman AI works if you want :-)

 

[rorix_bw]

With the AI in games like Quake III, the AI knows all the information about your position and uses it to make decision. It's like the AI bots have a lock-on all the time and once you are visible (which is determined through computational geometry techniques), they use some instructions (code) on how to act and shoot throughout the game. There are usually parameters that correspond to difficulty.

Actually there's a big debate about that. These days it's important that bots accurately simulate a human player and it's sometime easier to do this if your bots do not possesses perfect information. "The AI cheats" is a very common cause of player frustration, especially in a strategy game.

With regard to Quake III there is a 103-page computer science white paper on the Quake III bot AI, by the guy who implemented it but it's going to be inaccessible unless you're bot a programmer and a mathematican.

http://dev.johnstevenson.co.uk/bots/20585341-The-Quake-III-Arena-Bot.pdf

If you're a programmer yourself you may also be interested in this website. He's done a quick top level analysis of the (now released) quake 3 source code. I found its architecture interesting:

http://fabiensanglard.net/quake3/a.i.php