wh - Definition of gweiqi

Introduction

The Chinese ancient game weiqi, widely known in Japan as GO, led me to consider a great spectrum of different variants which I call gweiqi. Let me describe gweiqi systematically. This introduction gives you a general idea. Then solid definitions are provided in the subsequent sections.

Arbitrary 2-person games

2-person games are well known among mathematicians. They involve just strategies and the payment function (the outcome of the game). General 2-person games include games both with full informations, and other games where some information to one or two players is hidden. It doesn't matter to the definition (only to players). Each player chooses a strategy independently one from another. This results in an outcome (payment--a real number). The first player tries to obtain a maximal result, and the second--the minimal.

Positional games

More special are positional games with full information. They are specified by players by providing consecutive positions alternatively via moves from one position to another. All possibilities are openly presented to the both players at all time hence these are the full information games. A strategy means here means a choice of a move in any positions available to a given player. The strategies are chosen by the players based on the global view of the whole games.

Gweiqi

During a gweiqi game the two players move from one vertex of a finite ordered graph to another. At any time a player can pass for one move. Two passes in a row (one pass per player) end the game. This is the only way to finish a game--two consecutive passes. Furthermore, once a vertex was visited it is illegal to visit it again. Thus it's common that a player can be left without a (regular) move--then this player has to pass. Sice the number of all vertices is finite the whole last only a finite number of moves (according to the standard definition below, when the number of vertices is $\ n\ $ the number of moves cannot exceed $\ 2\cdot n$.

In a typical gweiqi, first of all in the classical weiqi, vertices have a complex structure of certain configurations as illustrated for instance by the weiqi board positions (consisting on white and black stones placed on some of the points of a weiqi board).

General 2-person game--definition

A game is defined by:

a set $\ F\ $ called the first player strategy set;
a set $\ S\ $ called the second player strategy set;
a function $\ \pi : F\times S\rightarrow\mathbb R\ $ called the payment.

The strategy sets are assumed to be non-empty. Each players chooses their strategy independently, without knowing in advance about the other choice--the first player chooses an element $\ f\in F$, and the second player chooses $\ s\in S$. That's a single game. The first player wins $\ \pi(f\ s)\ $ (and the second player receives $\ \sigma(t\ s) := -\pi(f\ s)\ $ -- the negative of the first player's payment. The object for each player is to maximize their winning by selecting their strategies. Since $$ \pi(f\ s) + \sigma(f\ s) = 0 $$ such games are called the $0$-sum games.

Positional 2-person games with full information--definition

There are several possible definitions. Some are theoretically equivalent meaning that each one can simulate another one. The following one, just below, is perhaps the simplest to formulate it conceptually, and is as general as others within the given domain.

A positional 2-person game $\ \Gamma\ $ consists of the following data:

a sequence of non-empty sets $\ P_0\ P_1\ P_2\ \ldots$; an element $\ p\in P_n\ $ is called an $n$-th move; the set $\ P_0\ $ is exceptional, it is a single element set $\ P_0:=\{o\}$;
a sequence of relations $\ M_n\subseteq P_{n-1}\times P_n\ $ for $\ n=1\ 2\ \ldots$ such that $\ \forall_{p\in P_{n-1}}\exists_{q\in P_n} (p\ q)\in M_n$; an element $\ m\in M_n\ $ is called an $n$-th move; furthermore, the set $\ M_1\ $ is defined as $\ M_1:= P_0\times P_1$;
the set of (actual) games $\ G\subseteq\prod_{n=0}^{\infty} P_n\ $ defined by $$ G\ :=\ \{g\, :\, \forall_{n=1\ 2\ \ldots} (g_{n-1}\ g_n)\in M_n\} $$ where $\ g := (g_0\ g_1\ \ldots)\in\prod_{n=0}^{\infty} P_n$ -- an element $\ g\in G\ $ is called a game (word game has more than one meaning; e.g. one is an actual game like $\ g$; another is a notion of the game and its rules; still another--in everyday life--is a material set like for instance a board and pieces; etc.).
the outcome function $\ \gamma : G\rightarrow\mathbb R$.

A strategy for the first player is defined as a selection, namely as an arbitrary sequence $\ f:= (f_1\ f_3\ \ldots)\ $ where each $\ f_n\ $ is a function $\ f_n : P_{n-1}\rightarrow P_n\ $ such that $\ \forall_{p\in P_{n-1}} (p\ f_n(p))\in M_n\ $ for all odd $\ n=1\ 3\ \ldots $; a strategy for the second player is defined as an arbitrary sequence $\ s:= (s_2\ s_4\ \ldots)\ $ where each $\ s_n\ $ is a function $\ s_n : P_{n-1}\rightarrow P_n\ $ such that $\ \forall_{p\in P_{n-1}} (p\ s_n(p))\in M_n\ $ for all even $\ n=2\ 4\ \ldots $. Now in the spirit of the general 2-person game definition we define $\ F\ $ to be the set of all first player strategies (as described just before); $\ S\ $ to be the set of all second player strategies (again as just before); and finally we define the payment function $\ \pi:F\times S\rightarrow\mathbb R\ $ as follows:

$$ \pi(f\ s) := \gamma(g) $$ where $$ \forall_{n=1\ 3\ \ldots}\forall_{p\in P_{n-1}} \quad g_n := f_n(p) $$ $$ \forall_{n=2\ 4\ \ldots}\forall_{p\in P_{n-1}} \quad g_n := s_n(p) $$

A positional variant

Let's extend the above game description by adding the following two rules:

There exists an element $\ \epsilon\ne o;\ $ called the ending position such that $\ \epsilon\in P_n\ $ for every positive $\ n=1\ 2\ \ldots$;

$ \quad\forall_{n\ge 2}\forall_{p\in P_n}\quad \left(\ \left(\epsilon\ p\right)\in M_p\ \Leftrightarrow\ p=\epsilon\ \right) $

On one hand this extension of rules narrows the domain of positional games, but on the other it doesn't. Indeed, an imposition of an element $\ \epsilon\ $ restricts the games to more special games. On the other hand an additional element $\ \epsilon\ $ can be safely ignored by moves $\ M_{n}\ $ (it doesn't have to appear in any move $\ (p\ q)$), thus leaving us with all games known to us before.

Introducing the end-position $\ \epsilon\ $ is a way to tell us that a game actually had stopped once the end-position is reached. In particular we can introduce the games of potentially finite duration, and the games of finite duration (just remember that a game $\ g:=(p_0\ p_1\ \ldots)\ $ has to satisfy the condition: $\ \forall_{n=0\ 1\ \ldots}\ (p_{n-1}\ p_n)\in M_n$):

DEFINITION A game $\ \Gamma\ $ is of a potentially finite duration $\ \Leftarrow:\Rightarrow\ $ for every game $\ g :=(p_0\ p_1\ \ldots)\in G\ $ there is a natural $\ n=1\ 2\ \ldots\ $ (the index $\ n\ $ depends on $\ g$) such that $\ p_n=\epsilon$. Furthermore, a game $\ \Gamma\ $ has a finite duration $\ \Leftarrow:\Rightarrow\ \exists_{n\ge 1}\forall_{(p\ q)\in M_n}\ q=\epsilon $.

Thus every game of finite duration has potentially finite duration, while the opposite is often false. However, a known classical theorem (or its direct equivalent formulation) states:

THEOREM If $\ \Gamma\ $ is a game of potentially finite duration, and if every $\ P_n\ $ is finite (for every $\ n=0\ 1\ \ldots$) then $\ \Gamma\ $ has finite duration.

gweiqi--Definition

While infinite gweiqi are possible I will consider here only the strictly finite version--as follows. A gweiqi game $\ Q\ $ consists of the following data:

a finite set $\ V\ $ called the set of vertices (or also configurations in some game when the structure of vertices is complex);
a fixed vertex $\ o\in V$;
an additional pseudo-vertex $\ \delta\notin V$ called pass;
a set of gweiqi moves $\ \mu\subseteq V\times V\setminus \Delta_V\ $ where $\ \Delta_V:=\{(v\ v): v\in V\}$;
a payment function $\ \omega : V\rightarrow \mathbb R\ $ -- we will see that the payment $\ \pi\ $ for a game is done simply via a final vertex of the respective game (see below);
the set of all actual games $\ W\ $ which consists of all finite sequences $\ w:= (w_0\ \ldots\ w_n)\ )\ $ called (an actual) game, such that
1. $\ n \ge 2$
2. $\ w_0=o$
3. $\ \forall_{k=0}^n\ \ w_k\in V\cup\{\delta\}$
4. $\ \forall_{k\lt n}\ \left(\ \left(w_k\ w_{k+1}\right)=\left(\delta\ \delta\right)\ \Leftrightarrow\ k=n-1\ \right)$
5. $\ \forall_{k\lt n}\ \left(\ \left(w_k\ w_{k+1}\right) \in V\times V\ \Rightarrow\ \left(w_k\ w_{k+1}\right) \in \mu\ \right)$
6. $\ \forall_{k\lt n-2}\ \left(\ w_{k+1}=\delta\ \Rightarrow\ \left(w_k\ w_{k+2}\right) \in \mu\ \right)$
7. $\ \forall_{k\ne m}\ \left(\ \left(w_k\ w_m\right)\in V\times V\ \Rightarrow\ w_k\ne w_m\ \right)$

The first player attempts to maximize value $\ \omega(w_{n-2})$, while the second players tries to minimize it.

It's not difficult to interpret gweiqi as a positional game--let me leave it at this.

REMARK 1 The length $\ n\ $ of a game $\ w:= (w_0\ \ldots\ w_n)\ )\ $ is finite, and bounded: $$ n\ \le\ 2\times |V| $$

REMARK 2 In the language of the classical weiqi or GO the rule 4. above means that the two consecutive pass calls end the game; also, rule 7. means for the classical weiqi that (the generalized) ko is illegal. The latter was formulated at a Taiwanese conference on weiqi in year 1958.

Two variations of rules

One could avoid introducing a special start vertex $\ o$. Instead, we could assume that $\ w_1\ $ is an arbitrary element $\ w_1\in V\cup\delta$, and otherwise the rules would be the same. But we could simulate this variation within the gweiqi rules above. We could introduce an element $\ o\notin V$, and then we would define:

$\ V'\ :=\ V\cup\{o\}$
$\ \mu'\ :=\ \mu\ \cup\ \{o\}\times V$.

The gweiqi game as described above but applied to $\ V'\ \mu'\ $ would be equivalent to the variant game which does not include the notion of the start vertex $\ o$.

Another variant could recognize ko, i.e. a repetition, only when the repeated vertices $\ w_k\ w_m\ $ would be a result of moves made by the same player, or in other words, when parity of $\ k\ m\ $ would be the same ($\ 2|m-k\ $). Once again we can simulate this variant simply--let

$\ V'\ :=\ V\times\{1\ 2\}$
$\ \mu'\ :=\ \{ ((v\ \alpha)\ (w\ \beta))\ \in\ V'\times V'\ :\ \ ((v\ w)\in \mu)\ \ \&\ \ (\alpha\not\equiv\beta \mod 2) \}$
$\ o'\ :=\ (o\ 2)$

The gweiqi game as described above but applied to $\ V'\ \mu'\ o'\ $ would be equivalent to the variant game which prevents repetitions (ko) only for each player separately.