In the previous step, you added a way for players to reject a game, so there is a way for stale games to be removed from storage. But is this enough to avoid state pollution?
There are some initial thoughts and code needs to keep in mind during the next sections to be able to implement forfeits in the end.
There are two ways for a game to advance through its lifecycle until resolution, win or draw: play and reject.
Game inactivity could become a factor. What if a player never shows up again? Should a game remain in limbo forever?
Eventually you want to let players wager on the outcome of games, so you do not want games remaining in limbo if they have value assigned. For this reason, you need a way for games to be forcibly resolved if one player stops responding.
The simplest mechanism to expire a game is to use a deadline. If the deadline is reached, then the game is forcibly terminated and expires. The deadline is pushed back every time a move is played.
To enforce the termination it is a good idea to use the EndBlock part of the ABCI protocol. The call EndBlock is triggered when all transactions of the block are delivered, and allows you to tidy up before the block is sealed. In your case, all games that have reached their deadline will be terminated.
How do you find all the games that have reached their deadline? You could use a pseudo-code like:
Copy
findAll(game=> game.deadline < now)
This approach is expensive in terms of computation. The EndBlock code should not have to pull up all games out of the storage just to find a few that are relevant. Doing a findAll costs O(n)(opens new window), where n is the total number of games.
You need another data structure. The simplest option is a First-In-First-Out (FIFO) that is constantly updated, so that:
When games are played, they are taken out of where they are and sent to the tail.
Games that have not been played for the longest time eventually rise to the head.
When terminating expired games in EndBlock, you deal with the expired games that are at the head of the FIFO. Do not stop until the head includes an ongoing game. The cost is:
O(1) on each game creation and gameplay.
O(k) where k is the number of expired games on each block.
k <= n where n is the number of games that exist.
k is still an unbounded number of operations. However, if you use the same expiration duration on each game, for k games to expire together in a block they would all have to have had a move in the same previous block (give or take the block before or after). In the worst case, the largest EndBlock computation will be proportional to the largest regular block in the past. This is a reasonable risk to take.
This only works if the expiration duration is the same for all games, instead of being a parameter left to a potentially malicious game creator.
How do you implement a FIFO from which you extract elements at random positions? Choose a doubly-linked list:
You must remember the game ID at the head to pick expired games, and at the tail to send back fresh games. The existing NextGame object is useful, as it is already expandable. Add to its Protobuf declaration:
Copy
messageNextGame{...string fifoHead =3;// Will contain the index of the game at the head.string fifoTail =4;// Will contain the index of the game at the tail.} proto checkers next_game.proto View source
To make extraction possible, each game must know which other game takes place before it in the FIFO, and which after. Store this double link information in StoredGame. Add them to the game's Protobuf declaration:
Copy
messageStoredGame{...string beforeId =8;// Pertains to the FIFO. Toward head.string afterId =9;// Pertains to the FIFO. Toward tail.} proto checkers stored_game.proto View source
There must be an "ID" that indicates no game. Use "-1", which you save as a constant:
Copy
const(
NoFifoIdKey ="-1") x checkers types keys.go View source
Adjust the default genesis values, so that it has proper head and tail:
Now that the new fields are created, you need to update them to keep your FIFO up-to-date. It's better to create a separate file that encapsulates this knowledge. Create x/checkers/keeper/stored_game_in_fifo.go with the following:
A function to remove from the FIFO:
Copy
func(k Keeper)RemoveFromFifo(ctx sdk.Context, game *types.StoredGame, info *types.NextGame){// Does it have a predecessor?if game.BeforeId != types.NoFifoIdKey {
beforeElement, found := k.GetStoredGame(ctx, game.BeforeId)if!found {panic("Element before in Fifo was not found")}
beforeElement.AfterId = game.AfterId
k.SetStoredGame(ctx, beforeElement)if game.AfterId == types.NoFifoIdKey {
info.FifoTail = beforeElement.Index
}// Is it at the FIFO head?}elseif info.FifoHead == game.Index {
info.FifoHead = game.AfterId
}// Does it have a successor?if game.AfterId != types.NoFifoIdKey {
afterElement, found := k.GetStoredGame(ctx, game.AfterId)if!found {panic("Element after in Fifo was not found")}
afterElement.BeforeId = game.BeforeId
k.SetStoredGame(ctx, afterElement)if game.BeforeId == types.NoFifoIdKey {
info.FifoHead = afterElement.Index
}// Is it at the FIFO tail?}elseif info.FifoTail == game.Index {
info.FifoTail = game.BeforeId
}
game.BeforeId = types.NoFifoIdKey
game.AfterId = types.NoFifoIdKey
} x checkers keeper stored_game_in_fifo.go View source
The game passed as an argument is not saved in storage here, even if it was updated. Only its fields in memory are adjusted. The before and after games are saved in storage. Do a SetStoredGame after calling this function to avoid having a mix of saves and memory states. The same applies to SetNextGame.
A function to send to the tail:
Copy
func(k Keeper)SendToFifoTail(ctx sdk.Context, game *types.StoredGame, info *types.NextGame){if info.FifoHead == types.NoFifoIdKey && info.FifoTail == types.NoFifoIdKey {
game.BeforeId = types.NoFifoIdKey
game.AfterId = types.NoFifoIdKey
info.FifoHead = game.Index
info.FifoTail = game.Index
}elseif info.FifoHead == types.NoFifoIdKey || info.FifoTail == types.NoFifoIdKey {panic("Fifo should have both head and tail or none")}elseif info.FifoTail == game.Index {// Nothing to do, already at tail}else{// Snip game out
k.RemoveFromFifo(ctx, game, info)// Now add to tail
currentTail, found := k.GetStoredGame(ctx, info.FifoTail)if!found {panic("Current Fifo tail was not found")}
currentTail.AfterId = game.Index
k.SetStoredGame(ctx, currentTail)
game.BeforeId = currentTail.Index
info.FifoTail = game.Index
}} x checkers keeper stored_game_in_fifo.go View source
Again, it is advisable to do SetStoredGame and SetNextGame after calling this function.
Copy
NextGame:
creator: ""
fifoHead: "1" # The first game you created
fifoTail: "2" # The second game you created and on which Bob just played
idValue: "4"
Having a list of games ordered by age is not enough to ascertain their staleness. You must also add an expiry date on each game to reach that decision. That is the goal of the next section.
