\documentstyle[12pt,russcorr]{article}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt
\begin{document}

Напомним, что автоматной игрой с двумя игроками,  первым  и
вторым, называется  следующая  совокупность: ${\langle 
A_{1},\,A_{2},\,P,\,p_{0},\,P_{1},\,F\rangle}$.
Здесь $A_{1}$, $A_{2}$ --- конечные алфавиты, $P$ --- конечное множество  
позиций
игры, $p_{0}\in P$   ---  начальная   позиция, $P_{1}\subseteq P$   --- множество
заключительных  позиций, $F$  ---  всюду  определенная  функция  из
${(P\setminus P_{1})\times A_{1}\times A_{2}}$ в $P$. Все  заключительные  
позиции  разбиты  на  два
класса: выигрышные для  первого  игрока  или  для  второго.  Все
подмножества множества незаключительных позиций тоже разбиты  на
два такие класса. Шаг игры заключается в том, что сначала первый
игрок называет некоторую букву $a_{1}\in A_{1}$,  затем  второй  называет
некоторую букву $a_{2}\in A_{2}$, и позиция становится равной 
$F(p,a_{1},a_{2})$,
где $p$ --- позиция  перед  этим  шагом.  Если  партия  когда-нибудь
приходит в заключительную  позицию,  выигрывает  соответствующий
игрок, в противном случае партия продолжается бесконечное  время
и  выигрывает  тот  игрок,  для  которого  выигрышно   множество
позиций, встретившихся  бесконечное  число  раз  (это  множество
называется предельным). Очевидно, партия полностью  определяется
двумя последовательностями букв, названных каждым игроком.

Стратегией игрока называется функция, которая по  названной
противником к любому текущему  моменту  последовательности  букв
указывает  очередной  ход  этого  игрока.  Стратегия  называется
выигрышной  для  игрока,  если  он  выигрывает  при  любой  игре
противника. Очевидно, что не более  чем  у  одного  игрока  есть
выигрышная стратегия. Игра, в которой у одного из  игроков  есть
выигрышная  стратегия,  называется  детерминированной.  Известна
следующая теорема.

ТЕОРЕМА 1. {\it Любая     автоматная      игра      является
детерминированной, и по ней  эффективно  определяется, у какого
игрока есть выигрышная стратегия.}

ДОКАЗАТЕЛЬСТВО. Пусть  дана  автоматная  игра $G$.  Проведем
индукцию по числу $n$ незаключительных  позиций  при  произвольном
числе заключительных. Если $n=1$, то  возможны  два  случая.  1.~У
какого-либо игрока  есть  стратегия,  гарантированно  приводящая
партию в заключительную  выигрышную  для  него  позицию.  Тогда,
очевидно, он может привести партию в эту позицию за один  шаг  и можно
легко  определить  этого  игрока.  2.~У  каждого   игрока   есть
стратегия,  не  позволяющая   противнику   привести   партию   в
выигрышную заключительную  позицию.  В  этом  случае  выигрышной
стратегией обладает, очевидно, тот игрок, для которого выигрышно
предельное одноэлементное множество. Базис индукции доказан.

Докажем шаг индукции. Пусть число незаключительных  позиций
равно $n+1$. Занумеруем их и обозначим через ${p_{1},\,p_{2},\ldots,\,p_{n+1}}$,  
где
$p_{1}$ --- начальная позиция. Обозначим игрока, для которого выигрышно
предельное множество всех незаключительных позиций, через $A$,  а
его противника через $B$. Рассмотрим $n+1$ редуцированных  игр,  где
$i$-ая редуцированная игра  (обозначим  ее $G_{i}$)  получается  из $G$
объявлением  позиции $p_{i}$  в  качестве  начальной  и  добавлением
позиции $p_{i+1}$ к заключительным, выигрышным  для $A$ (если $i=n+1$,
полагаем $i+1=1$). По предположению индукции, в каждой $G_{i}$ у одного
из  игроков  есть  выигрышная  стратегия,  и  можно   эффективно
выяснить у кого именно. Возможны два случая.

1. Во  всех $G_{i}$  выигрышная  стратегия  есть  у $A$.  Опишем
выигрышную для $A$ стратегию  в  игре $G$. $A$  начинает  играть  по
выигрышной стратегии для $G_{1}$. Если $A$ выигрывает в позиции $p_{2}$,  
то
он играет по выигрышной стратегии для $G_{2}$, и так далее, по кругу.
Если число смен редуцированных игр конечно, то в последней  игре
$G_{i}$ партия не попадает в позицию $p_{i+1}$ и $A$, очевидно, выигрывает в
игре $G$. Если число смен игр бесконечно, то предельное  множество
есть множество всех незаключительных позиций игры $G$,  выигрышное
для $A$.

2. В некоторой $G_{i}$ выигрышная стратегия есть у $B$. Рассмотрим
еще одну игру $G'$, получаемую  из $G$  добавлением  позиции $p_{i}$  к
заключительным, выигрышным для $B$.  Если  в  игре $G'$  выигрышная
стратегия есть у $A$, то та же стратегия, очевидно, выигрышная для
$A$ и в игре $G$. Если же выигрышная стратегия в $G'$ есть у $B$,  то  в
игре $G$ выигрышная стратегия для $B$ следующая. Сначала $B$ применяет
выигрышную стратегию для игры $G'$, и если  партия  завершилась  в
позиции $p_{i}$,  применяет  выигрышную  стратегию  для   игры $G_{i}$.
Теорема~1 доказана.

Пусть дана автоматная игра $G$. Естественно  рассмотреть  так
называемую автоматную игру с  форой  размера $n$,  которую  будем
обозначать через $G(n)$.  Скажем,  что  первый  игрок  дает  фору
размера $n$ второму, если второму игроку перед каждым своим  ходом
известны кроме очередного хода первого игрока  еще $n$  следующих
его ходов. Скажем, что игрок делает $n$-ход, если он  добавляет  к
объявленной им последовательности еще $n$ букв. Таким  образом,  в
игре $G(n)$ на первом шаге первый игрок делает $(n+1)$-ход, второй ---
1-ход, а на каждом следующем шаге  каждый  игрок  делает  1-ход.
Определение выигрышной стратегии  для  такой  игры  сохраняется.
Автоматную игру $G(n)$ легко свести к  автоматной  игре  без  форы
следующим образом. Новым алфавитом $A_{1}$  будут  последовательности
длины $n+1$ из букв прежнего  алфавита $A_{1}$.  Алфавит $A_{2}$  остается
прежним.  В  позиции  запоминается  кроме  позиции  игры $G$  еще
последний ход (слово длины $n+1$) первого игрока.  Если  первые $n$
букв очередного хода первого игрока не совпадают с последними $n$
буквами  предыдущего  его  хода,  первый  игрок  проигрывает.  В
противном   случае   последняя   буква   хода   первого   игрока
соответствует его 1-ходу в игре $G(n)$. Правила изменения  позиций
очевидны. Понятно,  что  существование  выигрышной  стратегии  у
игрока в игре $G(n)$ эквивалентно существованию у него  выигрышной
стратегии в описанной игре.

Очевидно, что если второй игрок имеет выигрышную  стратегию
в игре $G(n)$, то он имеет выигрышную стратегию и  во  всех  играх
$G(m)$, где $m>n$. Естественно поставить вопрос  о  существовании  и
нахождении  минимального $n$  такого,  что  второй  игрок   имеет
выигрышную стратегию в игре $G(n)$.

ТЕОРЕМА 2. {\it Существует алгоритм, который по любой автоматной
игре $G$  решает  вопрос  о  существовании  минимального  числа $n$
такого, что в игре $G(n)$ второй игрок имеет выигрышную  стратегию
и, если оно существует, находит это число.}

ДОКАЗАТЕЛЬСТВО. Сведем  игру $G(n)$  к   следующему   более
удобному виду. На первом шаге  первый  игрок  делает  $2n$-ход,  а
второй игрок --- $n$-ход. На  каждом  следующем  шаге  каждый  игрок
делает $n$-ход.  Названные   игроками   последовательности   букв
определяют партию в соответствии с правилами игры $G$.  Описанную
игру обозначим $G_{1}(n)$.

ЛЕММА 1. {\it Если первый игрок  имеет  выигрышную  стратегию  в
игре $G_{1}(n)$, то он имеет ее и в  игре $G(n)$.  Если  первый  игрок
имеет выигрышную стратегию в игре $G(2n-1)$, то он имеет  ее  и  в
игре $G_{1}(n)$.}

ДОКАЗАТЕЛЬСТВО. Докажем   первое   утверждение.    Опишем
выигрышную стратегию первого игрока в игре $G(n)$. На первом  шаге
он называет $(n+1)$-буквенное  начало  того  $2n$-хода,  который  он
сделал бы первым в $G_{1}(n)$. На следующих $n-1$ шагах  он  по  буквам
называет остаток этого хода, после чего у первого  игрока  будет
названо $2n$ букв, а у  второго $n$. Это  положение  соответствует
первому шагу игры $G_{1}(n)$ и  дальнейшие  действия  первого  игрока
очевидны. Докажем второе утверждение леммы. Выигрышная стратегия
первого игрока в игре $G_{1}(n)$ состоит, очевидно,  в  том,  что  он
сначала делает тот же $2n$-ход, что и в  игре $G(2n-1)$,  а  дальше
строит совершаемые $n$-ходы по ответу противника в соответствии со
стратегией для игры $G(2n-1)$. Лемма~1 доказана.

Сопоставим следующим образом каждому слову $s_{1}$ в алфавите $A_{1}$
множество $T(s_{1})$ троек вида ${\langle p_{1},\,P',\,p_{2}\rangle}$, где $p_{1}$, 
$p_{2}$ --- позиции  игры
$G$, $P'$ --- подмножество множества позиций игры $G$. Тройка $\langle 
p_{1},\,P',\,p_{2}\rangle$
входит в $T(s_{1})$ тогда и только тогда, когда существует слово $s_{2}\in 
A_{2}^{*}$
длины $|s_{1}|$ такое, что фрагмент  игры $G$  из $|s_{1}|$
шагов,   начинающийся    с    позиции $p_{1}$    и    определенный
последовательностями $s_{1}$ и $s_{2}$  ходов  первого  и  второго  игрока
соответственно, заканчивается в позиции $p_{2}$, а множество позиций,
через которые прошел этот фрагмент,  есть $P'$.  Обозначим  через
$M(n)$ множество всех множеств $T(s_{1})$,  соответствующих  некоторому
слову $s_{1}$ длины $n$.

Опишем еще одну автоматную игру, которую  обозначим $G_{2}(n)$.
На первом шаге первый игрок выбирает из $M(n)$ два любых множества
троек,  первое  и  второе.  Второй  игрок  выбирает  из  первого
множества одну тройку так,  чтобы  первая  позиция  тройки  была
начальной (если она не начальная или  тройка  не  из  множества,
второй игрок проигрывает). На каждом следующем шаге первый игрок
называет любое множество троек из $M(n)$, а второй игрок  выбирает
одну  тройку  из  множества,  названного   первым   игроком   на
предыдущем шаге. В этой тройке первая позиция должна совпадать с
последней  позицией  тройки,   названной   вторым   игроком   на
предыдущем  шаге.  После  каждого  шага   позиция   игры $G_{2}(n)$
становится  равной  совокупности  второй  и  третьей   компонент
тройки, названной на этом шаге  вторым  игроком.  Заключительные
позиции и предельные множества  определяются  очевидным  образом
так, чтобы любая партия игры $G_{2}(n)$ (где второй  игрок  ходит  по
указанным правилам)  определяла  партию  игры $G_{1}(n)$  с  тем  же
победителем,  и  обратно.  Игра $G_{2}(n)$  однозначно  определяется
множеством $M(n)$, поэтому всех таких игр конечное число.

Покажем, что можно эффективно построить автомат $B$,  который
в каждый момент находится в состоянии $T(s)$, где $s$  ---  прочтенное
на входе слово. Достаточно  показать,  что  по  состоянию $T_{1}$  и
читаемой букве $a_{1}$ эффективно  определяется  следующее  состояние
$T_{2}$. Но очевидно, что тройка ${\langle p_{1},\,P',\,p_{2}\rangle}$ принадлежит 
$T_{2}$  тогда  и
только тогда, когда  существует  тройка $\langle p_{1},\,P'',\,p_{3}\rangle\in T_{1}$  
и  буква
$a_{2}\in A_{2}$ такие, что $F(p_{3},a_{1},a_{2})=p_{2}$ и $P'=P''\bigcup 
\{p_{2}\}$.

Теперь построим автомат $B'$, который читает унарный вход и в
каждый  момент  находится  в  состоянии $M(n)$,  где $n$  ---  длина
прочтенного входа. $B'$ легко строится по $B$, так как по  множеству
состояний $B$, достижимых на входах  длины $n$,  очевидным  образом
определяется множество состояний,  достижимых  на  входах  длины
$n+1$. Так как существуют $n_{1}<n_{2}$ такие, что $M(n_{1})=M(n_{2})$, то  
прочтя
вход длины $n_{2}$ автомат $B'$ начинает повторять один и тот же  цикл.
По теореме~1 определим, какой игрок имеет выигрышную стратегию в
игре $G_{2}(n_{1})$. Если ее  имеет  первый  игрок,  то,  очевидно,  для
любого $n$ первый игрок имеет ее в игре $G_{1}(n)$, а по  лемме~1  и  в
игре $G(n)$. Если выигрышную стратегию в игре $G_{2}(n)$ имеет  второй
игрок, то по лемме~1 искомое минимальное $n$ лежит на отрезке от $0$
до $2n_{1}-1$. Перебирая числа этого отрезка и сводя  игры $G(n)$  при
$0\leq n\leq 2n_{1}-1$ к автоматным играм без форы, мы  по  теореме~1  найдем
искомое число. Теорема~2 доказана.
\end{document}


