(CoL)

Section 2**
**

**Games**

2.1
The two players

2.3
Constant games

2.4
Not-necessarily-constant
games

2.5
Static games

2.1 The two players

The CoL
games
are
between two players, called Machine and Environment (not always
capitalized,
and may take articles). On the picture below we see a few other names
for these
players.

We will
be
using and
as
symbolic names
for Machine and
Environment, respectively. is
a deterministic
mechanical device only
capable of following algorithmic strategies.
’s strategies,
on
the other hand, are arbitrary. Throughout this article, we shall
consistently use
the green color to represent Machine, and red for Environment. As seen
from the
picture, our sympathies are with the machine. Why should we be fans of
the
machine even when it is us who act in the role of its “evil”
environment?
Because the machine is a tool, and what makes it valuable as such is
exactly
its being a good player. In fact, losing a game by the machine means
that it is
malfunctioning. Imagine
Bob using a
computer for computing the “28% of *x*”
function in the process of preparing his US federal tax return. This is
a game
where the first move is by Bob, consisting in inputting a number *m* and meaning asking his machine the
question “what is 28% of *m*?”. The
machine wins iff it answers by the move/output *n*
such that *n*=0.28*m*.
Of course, Bob does not want the
machine to tell him that 27,000 is 28% of 100,000. In other words, he
does not
want to win against the machine. For then he could lose the more
important game
against Uncle Sam.

2.2 Moves, runs and positions

Machine
and
Environment interact with each other through mutually observable *actions*. We will be using the term “move”
instead of “action”. Looking back at the ordinary Turing machine model,
it is
about games where only two moves are made: the first move, called
“input”, is
by the environment, and the second move, called “output”, is by the
machine. ** **

We agree on the following:

- A
is any finite string over the keyboard alphabet. We will be using α, β, γ as metavariables for moves.*move* - A
is a move a together with one of the two colors*colored move**green*or*red*, with the color indicating which player has made the move. We shall write such a move as α or α,*.*Often we omit the word “colored” and simply say “move”. The letter λ - A
is a (finite or infinite) sequence of colored moves. We will be using Γ,Δ,Ω,Σ as metavariables for runs.*run* - A
is a finite run. We will be using Φ, Ψ, Ξ as metavariables for positions.*position* - We will be
writing runs and positions as 〈
**α, β, γ****〉, 〈****Φ****〉, 〈****Φ, Ψ, β, Γ****〉, etc. The meanings of such expressions should be clear. For instance,****〈****Φ, Ψ, β, Γ****〉** - 〈
.*empty position*

2.3 Constant games

A ** gamestructure**
is a nonempty set

Gamestructures
can
be visualized as upside-down trees where the nodes represent positions.
Each
edge is labeled with a colored move. Such an edge stands for a legal
move in
the position represented by the upper node of it. Here is an example:

**Figure 2.3.1: **A gamrestructure

This
gamestructure
consists of the following 16 runs: 〈** **〉, 〈α〉, 〈β〉, 〈γ〉, 〈α,
β〉, 〈α, γ**〉, 〈β, α〉, 〈γ, α〉, 〈γ,β〉,**** **〈γ, γ〉, 〈α, γ,β〉, 〈α, γ,γ〉,** **〈γ, α, β〉, 〈γ, α, γ〉, 〈γ, β, α〉, 〈γ, γ, α〉. All
of the infinitely (in
fact, uncountably)
many other runs are illegal. An example of an illegal run is 〈γ, γ,
β, β, α〉. The offender
in it
is Environment, because the offending third move is red.

Let **Lr** be a gamestructure. A *content** on***Lr** is a function **Wn**:
**Lr** **{**,**}**. When
**Wn**〈**Γ****〉 = , we say that ****Γ**** is **** won** by
the machine (and

**Definition
2.3.2** A *constant
game**G*
is a pair **(Lr**^{G}**,Wn**^{G}**)**,
where **Lr**^{G}** **is
a gamestructure, and **Wn*** ^{G}*
is a content on

Given a constant game G, we will be using the notation Lp^{G} ("legal positions of G") to mean the set {Φ | Φ is finite and Φ∈**Lr*** ^{G}*}. In order to define the gamestructure

Figure
2.3.3
below
shows a constant game of the structure of Figure
2.3.1:

**Figure 2.3.3:** A constant game

Here
the
winner in
each position is indicated by the color of the corresponding node. So,
for
instance, the run 〈γ, α, β〉 is won by the
machine; but if this run had stopped after its second move, then the
environment would be the winner. Of
course, such a way of indicating winners is not sufficient if there are
infinitely long branches (legal runs), for such branches do not have
“the
corresponding nodes”.

We say
that a
constant game is ** strict**
iff, in every legal position, at most one of the two
players has legal moves. Our games generally are not strict. For
instance, in
the start position of the game of Figure
2.3.3, both
players have legal moves. We call such (not-necessarily-strict) games

Because
our
games
are free, strategies for them cannot be defined as functions from
positions to
moves, because, in some positions (such as the root position in the
game of Figure 2.3.3)
both players may have legal moves and, if
both are willing to move, which of them acts sooner will determine what
will be
the next move.

The
exact
meaning of
“strategy” will be defined later, but whatever it means, we can see
that the
machine has a winning strategy in the game of Figure
2.3.3, which can be put this way:
*Regardless of what the adversary
is doing or has done, go ahead and make move *α*; make *β* as your
second move if and when you see that the
adversary has made move *γ*, no
matter
whether this happened before or after your
first move*”. This strategy obviously
guarantees that the
machine will not offend. There are 5 possible legal runs
consistent with it, i.e.,
legal runs that
could be generated (depending on how the environment acts) when it is followed by the machine: 〈α〉, ** **〈α, β〉,** **〈β, α〉,** **〈α, γ,
β〉 ** **and** **〈γ, α, β〉. All are won
by the
machine.

Let *G* be a constant game. *G*
is said to be ** finite-depth**
iff there is
a (smallest) integer

As
noted in Section 2.2, computational
problems in the traditional
sense are nothing but functions (to be computed). Such problems can be
seen as
the following types of games of depth 2:

**Figure 2.3.4:** The “successor” game

- Why is the root green here? Because it corresponds to the situation where there was no input. The machine has nothing to answer for, so it wins.
- Why are the 2
^{nd}level nodes red? Because they correspond to situations where there was an input but no output was generated by the machine. So the machine loses. - Why does each
group
of 3
^{rd}level nodes has exactly one green node? Because a function has exactly one (“correct”) value for each argument. - What
particular
function is this game about? The successor function:
*f*(*n*)=*n*+1.

Once we
agree
that
computational problems are nothing but games, the difference in the
degrees of
generality and flexibility between the traditional approach to
computational
problems and our approach becomes apparent and appreciable. What we see
in Figure 2.3.4 is
indeed a very special sort of games,
and there is no good call for confining ourselves to its limits. In
fact,
staying within those limits would seriously retard any more or less
advanced
and systematic study of computability.

First
of all,
one
would want to get rid of the “one green node per sibling group”
restriction for
the third-level nodes. Many natural problems, such as the problem of
finding a
prime integer between *n*
and 2*n*,
or finding an
integral root of *x*^{2}-2*n*=0,
may have more than one as well as less than one solution. That is,
there can be
more than one as well as less than one “right” output on a given input *n*.

And why
not
further
get rid of any remaining restrictions on the colors of whatever-level
nodes and
whatever-level arcs. One
can easily
think of natural situations where, say, some inputs do not obligate the
machine
to generate an output and thus the corresponding 2^{nd}
level nodes
should be green. An example would be the case where the machine is
computing a
partially-defined function *f*
and receives an input *n*
on which *f*
is undefined.** **

So far
we have
been
talking about generalizations within the depth-2 restriction,
corresponding to
viewing computational problems as very short dialogues between the
machine and
its environment. Permitting longer-than-2 or even infinitely long runs
would
allow us to capture problems with arbitrarily high degrees of
interactivity and
arbitrarily complex interaction protocols.
The task performed by a network server is an example of an
infinite
dialogue between the server and its environment **---**
the collection of clients, or let us just say the rest of the
network.

It also
makes
sense
to consider “dialogues” of lengths less than 2. “Dialogues” of length
0, i.e.
games of depth 0 are said to
be ** elementary**.
There are exactly two elementary
constant games, denoted by and
:

Note
that the
symbols and
** **thus have dual
meanings: they may stand for the two
elementary games as above, or for the corresponding two players. It
will
usually be clear from the context which of these two meanings we have
in mind.

Just like classical logic, CoL sees no extensional distinction between “snow is white” and , or between “snow is black” and : All true propositions, as games, are , and all false propositions are . In other words, a proposition is a game automatically won by the machine when true and lost when false. This way, CoL’s concept of a constant game is a generalization of the classical concept of a proposition.

2.4 Not-necessarily-constant games

We
fix an infinite set *Variables*
= {*var*_{1}, *var*_{2},
*var*_{3},… } of ** variables**.
As usual, lowercase letters near the end of the Latin alphabet will be
used to
stand (as metavariables) for variables. We further fix the set

A
** universe** (of
discourse) is a pair

A
universe (Dm,
Dn) is said to be *ideal*** **iff
Dn

The standard universe is
the ideal universe whose domain is the set of natural numbersm and
whose denotator is the function that sends every constant to the number
represented by that constant in decimal notation.

Where
*Vr* is
a set of variables and *Dm* is the
domain of some universe, by
a (*Vr**,Dm*)-** valuation**
we
mean a (total) function

**Definition**** 2.4.1 **Let
*n* be a natural number. An *n*-ary
** game**
is a quadruple (Dm,Dn,Vr,G),
where (Dm,Dn)
is a universe,
Vr is a set of

Given a game (Dm,Dn,Vr,G), we
refer to Dm as the domain of the game, refer to Dn as the denotator of the game, refer to the elements of Vr
as the
variables on which the game ** depends** (or simply "the variables of" the game), and refer to G as the extension of the game. We further refer to the
pair Un=(Dm,Dn)
as the

In classical logic, under an intensional (variable-sensitive) understanding, the definition of the concept of an

In
formal contexts, we choose a similar intensional
approach to functions. The definition of a function *f*
below is literally the same as our definition of a game *G*,
with the only difference that the extension component
is now a mapping of (Vr,Dm* ^{}*)-valuations to
Dm

**Definition
2.4.2 **Let *n*
be a natural
number. An *n*-ary ** function**
is a tuple (Dm,Dn

Just
like in the case of games, we customarily use the same name f for a function (Dm,Dn**,**Vr,f) as for its last component. We refer to the
elements of Vr as the variables on which the function *f*
** depends**,
refer to Dm
as the

Given
a game (Dm,Dn,Vr,G), a set X of variables with
Vr⊆*X *and an (*X***,**Dm* ^{}*)-valuation

**Convention
2.4.4** Assume K=(Dm,Dn,Vr,K)
is a function [resp. game]. Following
the standard readability-improving practice established in the
literature for
functions and predicates, we may fix a tuple (*x*_{1},…,*x*_{n}) of
pairwise distinct variables for K
when
first mentioning it, and write *K*
as K(*x*_{1},…,*x*_{n}).
When doing so, we do not necessarily mean that {*x*_{1},…,*x*_{n}}=Vr.
Representing K as K(*x*_{1},…,*x*_{n}) sets
a context in which, for whatever functions *f*_{1}=(Dm,Dn,Vr_{1},*f*_{1}), ..., f_{n}=(Dm,Dn,Vr_{1},*f*_{n}), we can
write K(f_{1},…,*f*_{n}) to mean the
function [resp. game] (*Dm,Dn,Vr',K'*)* *such that:

- Vr'=(Vr
*x*_{1},…,*x*_{n}})∪Vr_{1}∪…∪**Vr**_{1}^{};^{}

- For any (Vr',Dm)-valuation
*e*', K'(e')=K(e), where*e*is the (Vr,Dm)-valuation such that*e*(*x*_{1})=f_{1}(e), …,*e*(*x*_{n})=f_{n}(e) and e agrees with e' on all other variables from Vr.

Further, we
allow
for any of the above “functions” *f _{i}*
to be just a constant

The entities that in common language we call games are at least as often non-constant as constant. Board games such as chess and checkers are examples of constant games. On the other hand, almost all card games are more naturally specified as non-constant games: each session/instance of such a game is set by a particular permutation of the card deck, and thus the game can be understood as a game that depends on a variable

Consider
a
game *G*.
What we call a ** unilegal**
run of

Non-constant
games, as long as they are unistructural,
can be visualized as trees in the earlier
seen
style, with the difference that the nodes of the tree can now be
labeled with predicates rather than only propositions (colors) as before. For
any given
valuation *e*, each such label *L* is
telling us the color of the node.
Namely, the *L*-labeled node is green
if *L* is true at *e*,
and red if *L* is
false.

**Figure
2.3.5:**
The
“generalized successor” game

The above figure
shows a game which depends on *x*.
Specifically, for
every valuation *e*,
the game is about computing the function* f _{e}*,
defined by

Denoting
the game of Figure
2.3.5 by *G*(*x*),
the game of Figure 2.3.4
can be seen
to be the instance *G*(1) of it. The
latter results from replacing z
by
1
in Figure 2.3.5. This replacement turns every label *m*=*n*+*z*
into the proposition *m=n*+1,
i.e., into (green
filling) or (red
filling).

2.5 Static games

In the
particular
games that we have seen so far or will see in the subsequent sections,
when
talking about the existence of a winning strategy or the absence of
thereof,
the question about the (relative) speeds of the players was never
relevant.
That is because all those games share one nice property, called the *static*
property. Games with this property are (also) said to be static. Below are some intuitive characterizations of this important
class of
games.

- Static games are games where the speed of the adversary is not an issue: if a player has a winning strategy, the strategy will remain good no matter how fast its adversary is in making moves. And if a player does not have a winning strategy, it cannot succeed no matter how slow the adversary is.
- Static games are games where “it never hurts a player to postpone making moves” (Blass’ words from his AMS review of [Jap03]).
- Static games
are
contests of intellect rather than speed. In such games, what matters is
*what*to do (strategy) rather than*how fast*to do (speed).

The
games that
are
not static we call ** dynamic**. The
following games are dynamic:

In
either
game, the
player who is quick enough to make the first move becomes the winner.
And
asking whether Machine has a winning strategy is not really meaningful:
whether
Machine can win or not depends on the relative speeds of the two
players. In a
sense, *B*
is even “worse” than *A*.
Just like in *A*,
it would not be a
good idea for Machine to wait, because, unless Environment is stupid
enough to
also decide to wait, Machine will lose. Let us now say that Machine
goes ahead
and initiates the first move. What may happen in *B*
is that Environment moves before Machine actually completes its
move. This will make Machine not only the loser but also the offender.
Machine
cannot even be sure that its move will be legal!
If communication happens by exchanging
messages through a (typically) asynchronous network, that often has
some
unpredictable delays, this can also be a contest of luck: assuming that
the
arbitration is done by Environment or a third party who is recording
the order
of moves, it is possible that Machine makes a move earlier than
Environment
does, but the message carrying that move is delivered to the arbiter only after
Environment’s move
arrives, and the arbiter will be unable to see that it was Machine who
moved
first. An engineering-style attempt to neutralize this problem could be
to let
all moves carry timestamps. But this would not save the case: even
though
timestamps would correctly show the real order of moves by each
particular
player, they could not be used to compare two moves by two different
players,
for the clocks of the two players would never be perfectly synchronized.

Another
attempt to
deal with problems in the above style could be to assign to each
player, in a
strictly alternating order, a constant-length time slot during which
the player
has exclusive access to the communication medium. Let alone that this
could
introduce some unfair asymmetry in favor of the player who gets the
first slot,
the essence of the problem would still not be taken care of: some games
would
still essentially depend on the relative speeds of the two players,
even if
arguably no longer on the speed of the network.

Formally,
the
concept of static games is defined in terms of “delays”.
We say that run Δ
is a ** green**
(resp.

- The moves of either color are arranged in Γ in the same order as in Δ.
- For any
*n*,*k*≥1, if the*k*th red (resp. green) move is made earlier than the the*n*th green (resp. red) move in Γ, then so is it in Δ.

In other words, Δ is the result of shifting to the right (“delaying”) some green (resp. red) moves in Γ without violating their order.

Example: 〈**0,2,1,3,4,5,7,8,6,10,9〉**** is a green
delay of 〈****0,1,2,3,4,5,6,7,8,9,10〉****.****
** The former
is obtained from the latter by shifting
to the right some green moves. When doing so, a green move can jump
over a red
move, but one green move cannot jump over another green move.

Now, we
say
that a
constant game *G* is ** static**
(or that it has the static property) iff, for either player (color)

- If Γ is won by
*P*, then so is Δ. - If
*P*does not offend in Γ, then neither does it in Δ.

All
game
operations
studied in CoL have been shown to preserve the static property of games.^{[Jap03]
}So, as
long as the atoms of an expression represent static games, so does the
whole
expression. One natural subset of all static games is the closure of
elementary
games under the operations of CoL.

As already noted, CoL restricts
its attention to static
games only (at least, at its present stage of development). To see why
static
games are really what CoL is willing to call “pure” computational
problems,
imagine a play over the delay-prone Internet. If there is a central
arbiter
(which can be located either in one of the players' computer or
somewhere on a
third, neutral territory) recording the order of moves, then the
players have
full access to information about the official version of the run that
is being
generated, even though they could suffer from their moves being
delivered with
delays. But let us make the situation even more dramatic: assume, as
this is a
typical case in distributed systems, that there is no central arbiter.
Rather,
each players’ machine records moves in the order it receives them, so
that we
have what is called distributed arbitration. Every time a player makes
a move,
the move is appended to the player’s internal record of the run and, at
the
same time, mailed to the adversary. And every time a message from the
adversary
arrives, the move contained in it is appended to the player’s record of
the
run. The game starts. Seeing no messages from Environment, Machine
decides to
go ahead and make an opening move α**.**_{ }As it happens,
Environment also decides to make an “opening” move β. The messages
carrying α and β cross. So,
after
they are both delivered, Machine’s internal records show the
position 〈**α,β****〉, while
Environment
thinks that the current position is 〈****β,α****〉. Both of the
players decide to make two consecutive new moves: γ,δ****
**and ε,ω,
respectively, and the two pairs of messages, again,
cross.

After
making
their
second series of moves and receiving a second series of “replies” from
their
adversaries, both players decide to make no further moves. The game
thus ends.
According to Machine’s records, the run was 〈**α,β,γ,δ,ε,ω****〉, while
Environment thinks
that the run was 〈****β,α,ε,ω,γ,δ****〉. As
for the “real run”,
i.e. the real order in
which these six moves were made (if this concept makes sense at all),
it can be
yet something different, such as, say, 〈****β,α,γ,ε,δ,ω****〉. A little
thought
can convince us that in any case the real run, as well as the version
of the
run seen by Environment, will be a green delay of the version of the
run seen
by Machine. Similarly, the real run, as well as the version of the run
seen by
Machine, will be a red delay of the version of the run seen by
Environment.
Hence, provided that the game is static, either player can fully trust
its own
version of the run and only care about making good moves for this
version,
because regardless of whether it shows the true or a distorted picture
of the
real run, the latter is guaranteed to be successful as long as the
former
is. Moreover: for
similar reasons, the
player will remain equally successful if, instead of immediately
appending the
adversary's moves to its own version of the run, it simply queues those
moves
in a buffer as if they had not arrived yet, and fetches them only later
at a
more convenient time, after perhaps making and appending to its records
some of
its own moves first. The effect will amount to having full control over
the
speed of the adversary, thus allowing the player to select its own pace
for the
play and worry only about what moves to make rather than how quickly to
make
them. **

Thus,
static
games
allow players to make a full abstraction from any specific assumptions
regarding the type of arbitration (central or distributed), the speed
of the
communication network and the speed of the adversary: whatever strategy
they
follow, it is always safe to assume or pretend that the arbitration is
fair and
unique (central), the network is perfectly accurate (zero delays) and
the
adversary is “slow enough”. On
the other
hand, with some additional thought, we can see that if a game is not
static,
there will always be situations whre no particular one of the above
three sorts
of abstractions can be made. Specifically, such situations will emerge
every
time when a player *P*’s strategy
generates a *P*-won run that has some
*P*-lost *P*-delays.