This paper discusses methods of player progression and sketches out algorithms for machine implementation. It also discusses how a game master communicates with the players depending on which method of player progression is used. It does not discuss games where there is more than one player per team.
This paper is part of a larger project to design a general game master for multi-player games on multi-user, interactive computer systems. Making a general master requires formal definition of player progression, the order in which players take their turns during one part of the game. Unfortunately, games use several progression methods, so conversion to a general algorithm may not be recommended for all games.
For a given game, the players may take their turns one after the other, all at once, or some combination of the two. When play is restricted to one player at a time, the game uses sequential player progression: Players take turns in a deterministic order, and each player can halt the game by not taking a turn. When more than one player can play at one time, the game uses simultaneous player progression: Each player races to make a move before the others. The method is more chaotic and a player can't stop the game--it continues even if a player doesn't take a turn. Games often combine the two methods, for example, cribbage has a defined order of play, and then, if any points are unclaimed after a move, the players race to claim them. Other games only use one type of a progression method, for example, chess uses pre-defined player progression, which is a type of sequential player progression method.
Several types of sequential player progression exist. The simplest, pre-defined progression, orders the players at the beginning of the game, and then sticks to that order throughout the game until someone loses or quits. Each player takes one move per turn, so the number of moves per round is equal to the number of players in the game. When a player is removed from the ordering, the gap closes and the next player moves up one spot in the order. This also happens temporarily for one round if a player loses a turn.
When pre-defined player progression is modified so that player order can change, variable player progression results. These variations in order occur in games which give players power plays. A power play can add moves to a player's turn, take away moves from a player's turn, reverse player order, or skip players in the progression. In addition, other power plays directly after the first power play may be able to cancel or change the action of the original, so the player order may change zero or more times with each power play.
In a game using the last type of sequential player progression, round-order progression, the player order may change after every round (or hole in golf). One way to determine the next round's order is to let whoever did best in the previous round go first and then the pre-determined order is used for the rest of the round. Alternately, the score of the previous round or the entire game up to this point determines the player order of the next round. Finally, the score or power plays may not have any effect on the player order at all: In autocratic games, a preferably unbiased game master decides what the player order will be for the next round.
Any of the sequential player progression methods may have a time limit imposed on each player's turn to speed up the game or make the game more challenging. The player must either make the move before the time limit is up or receive some penalty, such as losing a turn or points, etc.
Simultaneous player progression exists when players take their turns in an undefined order; each player can make moves independent of other players' moves. The largest unit of play in a simultaneous progression game is a contest made up of zero or more moves by each player. The number of moves a player can make in one contest determines the simultaneous progression type.
Snatch progression allows one move per player per contest, and is used in some sequential sequencing games to allow players to claim untaken points, challenge another player's move, or combat the previous player's move. The winner of the contest (or the loser) is the first one (or last one) to make a move. Often a time limit is imposed on the snatch: It must occur before the next player takes a turn.
Some games allow more than one move, but not an unlimited number of moves per contest--the games use limited progression. Normally, each player can take as many moves as they want within a reasonable amount of time. An example of limited progression would be an auction, or betting at a casino game such as craps or roulette.
In games using continuous progression, players take as many moves as they need or want. Players may drop out of the contest, and in some instances, may join the game whenever they want to. Sometimes the contest has a definite goal, and when the player reaches that goal, the contest is over for that person. The order in which people reach the goal is the winning order, those that fail to reach the goal make up a losing order. At other times, the player's goals conflict with each other, or the goals oscillate between teams as play progresses.
A small modification to the simultaneous progression methods makes the players make at least one move, which can take the form of a pass in the snatch method or a quit in the continuous method. This gives the player some control over the game: The contest will never finish if one player doesn't make a move.
Although an important part of player progression, sequential player progression can be easily simulated with simultaneous player progression by limiting the number of players allowed in a contest. The game master can turn a deaf ear to the players who aren't allowed to take a turn. Use sequential progression only if you are sure that it would be best for the game, you want a simple algorithm to program or your computer doesn't provide you with a method of playing in parallel. Ultimately, on a sequential machine, simultaneous progression will be implemented sequentially, but this is taken care of in the operating system, so we won't discuss it here. What forces the simultaneous progression to be sequential is the game master, since we only want one player accessing the game database at a time. Here's the generic game master algorithm:
When implementing simultaneous progression, several design decisions or system constraints may modify the final solution. If the system allows signals between the game master and the players, this is the best way to go for simultaneous progression; the game master will only accept and process signals from selected players. In order to process the signals fairly, they are queued up according to when the game master received them. Steps 1 and 2 are discarded, and the order of the players becomes the signal queue.
Simultaneous progression can also be implementented using a device similar to the FreeeBSDselect(2) system call.
During one part of the game, the players who have the opportunity to move are checked to see if they have made a move. If they have, the input is read and processed, and the next group of players eligible for play are selected. Unfortunately, this may treat race conditions found in step 3 unfairly; some method of determining player order must be devised. This method really better for writing sequential games, since it allows some parallelism if auxillary functions are allowed in addition to a normal move.
When determining how player interface should be handled, the issues of adding a player to the game, player input/output, and player termination need to be dealt with.
First of all, there must be a method for players to join the game. Two methods common methods follow: One where all of the players are selected at the beginning of the game, the other where players are free to join the game any time. When players are selected at the beginning of the game, it is usually done to allow the players to talk to the game master using signals, or to prevent unwanted players from joining the game. If players can join at any time, they have to watched for in the middle of the game.
Player send messages as single characters, strings of characters. If messages are single characters, then there is no problem dealing with the messages: a flag is set when the message is read, and reset when the message is processed. Strings of characters are more difficult because the message may arrive at the master incomplete; the first part of the message must be stored, and then the rest concatenated to the first. Therefore, the flag for input from each player should have three states: one for ready for message, one for partial message, and one for complete message.
We also must consider how to handle the player's messages. Should the player be able to send several messages, and the game master store them, or should the game master only accept one message at a time?
In general, the game master can either require that a player provides a message, or not. If a message is required, the game stops until that player provides the message; if not, the game continues even if the player doesn't take a turn.
If the right kind of communication is used between game master and player, the master should be able to send all of the messages required without having to worry about buffering. If not, then the game master will have to keep a buffer for each player and have some way of testing whether or not the player can take a message. When a message can be sent, some or all of the buffer will be sent to the player.
A player can be terminated by quitting, losing, or system failure. The game master can handle a player losing or quitting easily, system failure is more difficult. It is usually discovered when I/O fails. When it does, the buffers should be flushed, and the appropriate files removed. If necessary, the game master process or job itself can terminate.