Single-Player Games

Games are most fun when other people join in, but other players are not always available. That limitation led to the invention of single-player games. One of the best known is the classic "Solitaire", which has probably wasted more office hours than any other game.

The goal of a single-player game is usually to make moves until you reach a final state that is a win, a loss, or that carries some score. Most players try to optimize their result with a good strategy. Here we instead study what happens when you play randomly — a fine way to waste time, just like any other strategy.

A game is represented compactly as a (possibly infinite) tree. Every node is a game state; the root is the starting position. For an internal node, its children are the states reachable in one move. Every leaf is a final state and carries an integer score, which is the score you receive when the game ends there.

Trees are described with the following grammar.

Definition ::= Identifier "=" RealTree
  RealTree ::= "(" Tree+ ")"
      Tree ::= Identifier | Integer | "(" Tree+ ")"
Identifier ::= a | b | ... | z
   Integer  ∈  {..., -3, -2, -1, 0, 1, 2, 3, ...}

A Definition assigns the RealTree on the right-hand side to the Identifier on the left. A RealTree is a root node together with one or more children, written as a bracketed sequence. A Tree is one of:

• the tree named by an Identifier,
• a leaf node given by a single Integer, or
• an internal node given by a bracketed sequence of one or more Trees (its children).

Your task is to compute the expected score of random play: at every internal node you choose one child uniformly at random. This expected score is well defined even for the infinite trees expressible here, provided the game ends with probability 1.

The input contains several game-tree descriptions. Each description starts with a line containing the number n of identifiers it uses; the identifiers are the first n lowercase letters of the alphabet. The next n lines give the definitions of these identifiers in the order a, b, .... A definition may contain arbitrary whitespace (but never inside a single integer), and its right-hand side only uses identifiers among the first n lowercase letters.

The input ends with a description whose n is 0; do not process that description.

For each game-tree description, first print Game k, where k is the description's number (starting at 1). Then, for each of the n identifiers in the order a, b, ..., print one line:

• If the identifier’s tree ends with probability 1, print Expected score for <id> = <value>, where <value> is the expected score of random play, rounded to exactly three digits after the decimal point.
• Otherwise print Expected score for <id> undefined.

Print a blank line between consecutive games.