(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.28m. 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:
2.3 Constant games
A gamestructure
is a nonempty set Lr of runns,
called legal runs, satisfying the condition that a run is
in
Lr iff so are all finite initial
segments of it. The empty position 〈 〉 is thus always legal. The
runs that are not in Lr are said to be illegal.
An illegal move
in a given position 〈Φ〉 is a move λ
such that 〈Φ,λ〉 is illegal.
The player who made the first illegal move
in a given run is said to be the offender.
Intuitively, illegal moves can be thought of as moves that cannot or
should not
be made. Alternatively, they can be seen as actions that cause the
system to crash
(e.g., requesting to divide a number by 0).
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 lost
by the
environment);
and when Wn〈Γ〉 =, we say that Γ is won by the
environment (and lost by the machine).
We
extend the domain of Wn to all runs
by stipulating that an illegal run is always lost by the offender.
Since we are fans of Machine, the default meaning of just “won” (or
“lost”) is
“won (or lost) by the machine”.
Definition
2.3.2 A constant
game G
is a pair (LrG,WnG),
where LrG is
a gamestructure, and WnG
is a content on LrG.
Given a constant game G, we will be using the notation LpG ("legal positions of G") to mean the set {Φ | Φ is finite and Φ∈LrG}. In order to define the gamestructure component of G, it is sufficient to simply define LpG. The latter uniquely extends to LrG because, as implied by our definition of gamestructures, a run is in LrG iff all of its finite initial segments are in LpG.
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 free.
Free games model real-life situations more directly and naturally than
strict
games do. Hardly many tasks that humans, computers or robots perform
are
strict. Imagine you are playing chess over the Internet on two boards
against
two independent adversaries that, together, form the (one) environment
for you.
Let us say you play white on both boards. Certainly in the initial
position of
this game only you have legal moves. However, once you make your first
move ---
say, on board #1 --- the picture changes. Now both you and the
environment have
legal moves, and who will be the next to move depends on who can or
wants to
act sooner. Namely, you are free to make another opening move on board
#2,
while the environment --- adversary #1 --- can make a reply move on
board #1. A
strict-game approach would have to impose some not-very-adequate
supplemental
conditions uniquely determining the next player to move, such as not
allowing
you to move again until receiving a response to your previous move. Let
alone
that this is not how the real two-board game would proceed, such
regulations
defeat the very purpose of the idea of parallel/distributed
computations with all
the known benefits it offers.
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 d, called the depth
of G, such that the length of every
legal run of G is ≤d. And G
is perifinite-depth
iff every legal run of it is finite, even if there are arbitrarily long
legal
runs. Let us call a legal run Γ of G maximal
iff Γ is not a
proper initial segment of any other legal
run of G. Then we say that G is finite-breadth iff the
total number of maximal legal runs of G,
called the breadth
of G, is
finite. Note that, in a general case, the breadth of a game may be not
only
infinite, but even uncountable. G
is
said to be (simply) finite
iff it only has a finite number of legal runs. Of
course, G is finite only if it is
finite-breadth, and when G is
finite-breadth, it is finite iff it is finite-depth iff it is
perifinite-depth.
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
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 2n,
or finding an
integral root of x2-2n=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 2nd
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
= {var1, var2,
var3,… } 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 Constants = {0,1,2,3,…} of decimal
numerals, and call its elements constants.
With some abuse of
concepts, we shall often identify constants with the numbers they
represent.
A
universe (of
discourse) is a pair U = (Dm, Dn),
where Dm, called
the domain
of U, is a nonempty set, and Dn,
called the denotator of U,
is a (total) function of type Constants Dm.
The elements of Dm
will be
referred to as the individuals
of U. The
intuitive meaning of d=Dn(c)
is that the individual d is the denotat
of the constant c and thus c is a name (or code)
of d. So, the function Nm from Dm
to the powerset of Constants
satisfying the condition c∈Nm(d)
⇔ d=Dn(c)
can be called the naming function
of U. Of course, whenever
convenient, a
universe can be characterized in terms of its naming function rather
than
denotation function.
A universe (Dm, Dn) is said to be ideal iff Dn is a bijection. Generally, in a not-necessarily-ideal universe, some individuals may have unique names, some have many names, and some have no names at all. Real-world universes are seldom ideal: not all people living or staying in the United States have social security numbers; most stars and planets of the Galaxy have no names at all, while some have several names (Morning Star = Evening Star = Venus); etc. A natural example of an inherently non-ideal universe from the world of mathematics would be the one whose domain is the set of real numbers, only some of whose elements have names, such as 5, 1/3, √2 or π. Generally, even if the set of constants was not fixed, no universe with an uncountable domain would be “ideal” for the simple reason that there can only be countably many names. This is so because names, by their very nature and purpose, have to be finite objects. Observe also that many properties of common interest, such as computability or decidability, are usually sensitive with respect to how objects (individuals) are named, as they deal with the names of those objects rather than the objects themselves. For instance, strictly speaking, computing a function f(x) means the ability to tell, after seeing a (the) name of an arbitrary object a, a (the) name of the object b with b=f(a). Similarly, an algorithm that decides a predicate p(x) on a set S, strictly speaking, takes not elements of S --- which may be abstract objects such as numbers or graphs --- but rather names of those elements, such as decimal numerals or codes. It is not hard to come up with a nonstandard naming of the natural numbers through decimal numerals where the predicate “x is even” is undecidable. On the other hand, for any undecidable arithmetical predicate p(x), one can come up with a naming such that p(x) becomes decidable --- for instance, one that assigns even-length names to all a with p(a) and assigns odd-length names to all a with p(a). Classical logic exclusively deals with individuals of a universe without a need to also consider names for them, as it is not concerned with decidability or computability. CoL, on the other hand, with its computational semantics, inherently calls for being more careful about differentiating between individuals and their names, and hence for explicitly considering universes in the form (Dm, Dn) rather than just Dm as classical logic does.
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 e of type VrDm. Where x1,..., xn are all the variables of Vr listed according to their lexicographic order, such a valuation e can be simply written as an n-tuple (a1,..., an), meaning that e(x1)=a1,...,e(xn)=an. When Vr
and Dm are clear from the context,
we
may omit an explicit reference to them and simply say “valuation”.
References
to a universe U or its components
can
be similarly omitted when talking about individuals, denotats, names or
some
later-defined concepts such as those of a game or a 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 n
distinct variables, and G is a mapping which sends every (Vr,Dm)-valuation e to a constant game G(e).
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 universe of the game; correspondingly, the game can be simply written as the triple (Un,Vr,G)
rather than the quadruple (Dm,Dn,Vr,G).
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
(rather than to constant
games).
Definition
2.4.2 Let n
be a natural
number. An n-ary function
is a tuple (Dm,Dn,Vr,f),
where (Dm,Dn)
is a universe,
Vr
is a set of n
distinct variables, and f
is a mapping which sends every (Vr,Dm)-valuation to an element f(e) of Dm.
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 domain of
f, etc.
Given
a game (Dm,Dn,Vr,G), a set X of variables with
Vr⊆X and an (X,Dm)-valuation e, we write G(e)
to mean the constant game G(g), where g is the
restriction of e to Vr
(i.e., the (Vr,Dm)-valuation that agrees with e on all variables from Vr).
Such a
constant game G(e)
is said to be an instance
of G. Also,
for readability, we usually write LreG
and WneG
instead of LrG(e)
and WnG(e).
Similarly, given a function (Dm,Dn,Vr,f),
a set X of variables with
Vr⊆X and an (X,Dm)-valuation e, we write f(e)
to denote the individual f(g) to which f
maps g, where g is the
restriction
of e to Vr.
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 (x1,…,xn) of pairwise distinct variables for K when first mentioning it, and write K as K(x1,…,xn). When doing so, we do not necessarily mean that {x1,…,xn}=Vr. Representing K as K(x1,…,xn) sets a context in which, for whatever functions f1=(Dm,Dn,Vr1,f1), ..., fn=(Dm,Dn,Vrn,fn), we can write K(f1,…,fn) to mean the function [resp. game] (Dm,Dn,Vr',K') such that:
Further, we
allow
for any of the above “functions” fi
to be written as just an individual a, just a constant c or just a
variable x. In such a case, fi
should be
correspondingly
understood as the 0-ary function the 0-ary function aU
, the 0-ary function cU
or the unary function xU,
where U=(Dm,Dn).
So, for
instance, K(0,x)
is our lazy way to write K(0U,xU).
Consider
a
game G.
What we call a unilegal
run of G is a run which
is a legal run of all
instances of G. We say that G is unistructural iff
all legal runs of all of its instances are unilegal runs of G. The class of
unistructural
games is known to be closed under all game operations studies in
CoL.[Jap03] While
natural examples of non-unistructural games exist such as the games
mentioned
in the above paragraph, virtually all other examples of
particular games
discussed elsewhere in the present article are unistructural.
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 fe,
defined by fe (n)
= n+e(z) (“the zth
successor of
n”). Note
that we have different
functions and thus different constant games for different valuations e
here.
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.
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. red)
delay of run Γ iff the
following
two conditions are satisfied:
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) P and any runs Γ and Δ such that Δ is a P delay of Γ, in the context of G, the following two conditions are satisfied:
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.