← Static tasks

E139. Игры на произвольных графах

emaxx algorithm

#algorithm#emaxx#game-theory#graph

Task

Источник: e-maxx.ru/algo, страница PDF 455.

Пусть игра ведётся двумя игроками на некотором графе G. Т.е. текущее состояние игры - это некоторая вершина графа, и из каждой вершины рёбра идут в те вершины, в которые можно пойти следующим ходом. Мы рассматриваем самый общий случай - случай произвольного ориентированного графа с циклами. Требуется для заданной начальной позиции определить, кто выиграет при оптимальной игре обоих игроков (или определить, что результатом будет ничья). Мы решим эту задачу очень эффективно - найдём ответы для всех вершин графа за линейное относительно количества рёбер время - O (M).

Описание алгоритма

Про некоторые вершины графа заранее известно, что они являются выигрышными или проигрышными; очевидно, такие вершины не имеют исходящих рёбер. Имеем следующие факты:

● если из некоторой вершины есть ребро в проигрышную вершину, то эта вершина выигрышная;

● если из некоторой вершины все рёбра исходят в выигрышные вершины, то эта вершина проигрышная;

● если в какой-то момент ещё остались неопределённые вершины, но ни одна из них не подходят ни под первое, ни

под второе правило, то все эти вершины - ничейные. Таким образом, уже ясен алгоритм, работающий за асимптотику O (N M) - мы перебираем все вершины, пытаемся к каждой применить первое либо второе правило, и если мы произвели какие-то изменения, то повторяем всё заново. Однако этот процесс поиска и обновления можно значительно ускорить, доведя асимптотику до линейной. Переберём все вершины, про которые изначально известно, что они выигрышные или проигрышные. Из каждой из них пустим следующий поиск в глубину. Этот поиск в глубину будет двигаться по обратным рёбрам. Прежде всего, он не будет заходить в вершины, которые уже определены как выигрышные или проигрышные. Далее, если поиск в глубину пытается пойти из проигрышной вершины в некоторую вершину, то её он помечает как выигрышную, и идёт в неё. Если же поиск в глубину пытается пойти из выигрышной вершины в некоторую вершину, то он должен проверить, все ли рёбра ведут из этой вершины в выигрышные. Эту проверку легко осуществить за O (1), если в каждой вершине будем хранить счётчик рёбер, которые ведут в выигрышные вершины. Итак, если поиск в глубину пытается пойти из выигрышной вершины в некоторую вершину, то он увеличивает в ней счётчик, и если счётчик сравнялся с количеством рёбер, исходящих из этой вершины, то эта вершина помечается как проигрышная, и поиск в глубину идёт в эту вершину. Иначе же, если целевая вершина так и не определена как выигрышная или проигрышная, то поиск в глубину в неё не заходит. Итого, мы получаем, что каждая выигрышная и каждая проигрышная вершина посещается нашим алгоритмом ровно один раз, а ничейные вершины и вовсе не посещаются. Следовательно, асимптотика действительно O (M).

Реализация

Рассмотрим реализацию поиска в глубину, в предположении, что граф игры построен в памяти, степени исхода посчитаны и записаны в degree (это будет как раз счётчиком, он будет уменьшаться, если есть ребро в выигрышную вершину), а также изначально выигрышные или проигрышные вершины уже помечены.

vector<int> g [100];

bool win [100];

bool loose [100];

bool used[100];

int degree[100];

void dfs (int v) {

used[v] = true;

for (vector<int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
if (!used[*i]) {
if (loose[v])

win[*i] = true;

else if (--degree[*i] == 0)

loose[*i] = true;

else

continue;

dfs (*i);

} }

Пример задачи. "Полицейский и вор"

Чтобы алгоритм стал более ясным, рассмотрим его на конкретном примере. Условие задачи. Имеется поле размером MxN клеток, в некоторые клетки заходить нельзя. Известны начальные координаты полицейского и вора. Также на карте может присутствовать выход. Если полицейский окажется в одной клетке с вором, то выиграл полицейский. Если же вор окажется в клетке с выходом (и в этой клетке не стоит полицейский), то выиграет вор. Полицейский может ходить в 8 направлениях, вор - только в 4 (вдоль осей координат). И полицейский, и вор могут пропустить свой ход. Первым ход делает полицейский. Построение графа. Построим граф игры. Мы должны формализовать правила игры. Текущее состояние игры определяется координатами полицейского P, вора T, а также булева переменная Pstep, которая определяет, кто будет делать следующий ход. Следовательно, вершина графа определена тройкой (P,T,Pstep). Граф построить легко, просто соответствуя условию. Далее нужно определить, какие вершины являются выигрышными или проигрышными изначально. Здесь есть тонкий момент. Выигрышность/проигрышность вершины помимо координат зависит и от Pstep - чей сейчас ход. Если сейчас ход полицейского, то вершина выигрышная, если координаты полицейского и вора совпадают; вершина проигрышная, если она не выигрышная и вор находится на выходе. Если же сейчас ход вора, то вершина выигрышная, если вор находится на выходе, и проигрышная, если она не выигрышная и координаты полицейского и вора совпадают. Единственный момент, которой нужно решить - строить граф явно или делать это "на ходу", прямо в поиске в глубину. С одной стороны, если строить граф предварительно, то будет меньше вероятность ошибиться. С другой стороны, это увеличит объём кода, да и время работы будет в несколько раз медленнее, чем если строить граф "на ходу". Реализация всей программы:

struct state {

char p, t;

bool pstep;

};

vector<state> g [100][100][2];

// 1 = policeman coords; 2 = thief coords; 3 = 1 if policeman's step or 0

if thief's.

bool win [100][100][2];

bool loose [100][100][2];

bool used[100][100][2];

int degree[100][100][2];

void dfs (char p, char t, bool pstep) {

used[p][t][pstep] = true;

for (vector<state>::iterator i = g[p][t][pstep].begin(); i != g[p]

[t][pstep].end(); ++i)

if (!used[i->p][i->t][i->pstep]) {
if (loose[p][t][pstep])

win[i->p][i->t][i->pstep] = true;

else if (--degree[i->p][i->t][i->pstep] == 0)

loose[i->p][i->t][i->pstep] = true;

else

continue;

dfs (i->p, i->t, i->pstep);

} }

int main() {
int n, m;

cin >> n >> m;

vector<string> a (n);

for (int i=0; i<n; ++i)

cin >> a[i];

for (int p=0; p<n*m; ++p)
for (int t=0; t<n*m; ++t)
for (char pstep=0; pstep<=1; ++pstep) {
int px = p/m, py = p%m, tx=t/m, ty=t%m;
if (a[px][py]=='*' || a[tx][ty]=='*')  continue;

bool & wwin = win[p][t][pstep];

bool & lloose = loose[p][t][pstep];

if (pstep)

wwin = px==tx && py==ty, lloose

= !wwin && a[tx][ty] == 'E';

else

wwin = a[tx][ty] == 'E', lloose

= !wwin && px==tx && py==ty;

if (wwin || lloose)  continue;

state st = { p, t, !pstep };

g[p][t][pstep].push_back (st);

st.pstep = pstep != 0;

degree[p][t][pstep] = 1;

const int dx[] = { -1, 0, 1, 0, -1, -1,

1, 1 };

const int dy[] = { 0, 1, 0, -1, -1, 1, -

1, 1 };

for (int d=0; d<(pstep?8:4); ++d) {
int ppx=px, ppy=py, ttx=tx, tty=ty;
if (pstep)

ppx += dx[d], ppy += dy[d];

else

ttx += dx[d], tty += dy[d];

if (ppx>=0 && ppx<n && ppy>=0 &&

ppy<m && a[ppx][ppy]!='*' &&

ttx>=0 && ttx<n && tty>=0

&& tty<m && a[ttx][tty]!='*')

{

g[ppx*m+ppy][ttx*m+tty][!

pstep].push_back (st);

++degree[p][t][pstep];

} } }

for (int p=0; p<n*m; ++p)
for (int t=0; t<n*m; ++t)
for (char pstep=0; pstep<=1; ++pstep)
if ((win[p][t][pstep] || loose[p][t]

[pstep]) && !used[p][t][pstep])

dfs (p, t, pstep!=0);

int p_st, t_st;
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (a[i][j] == 'C')

p_st = i*m+j;

else if (a[i][j] == 'T')

t_st = i*m+j;

cout << (win[p_st][t_st][true] ? "WIN" : loose[p_st][t_st]

[true] ? "LOSS" : "DRAW");

}

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    List<int> g [100];
    bool win [100];
    bool loose [100];
    bool[] used = new bool[100];
    int degree[100];
    void dfs (int v) {
            used[v] = true;
            for (List<int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
                    if (!used[*i]) {
                            if (loose[v])
                                    win[*i] = true;
                            else if (--degree[*i] == 0)
                                    loose[*i] = true;
                            else
                                    continue;
                            dfs (*i);
                    }
    }
    struct state {
            char p, t;
            bool pstep;
    };
    vector<state> g [100][100][2];
    // 1 = policeman coords; 2 = thief coords; 3 = 1 if policeman's step or 0
    if thief's.
    bool win [100][100][2];
    bool loose [100][100][2];
    bool[] used = new bool[100][100][2];
    int degree[100][100][2];
    void dfs (char p, char t, bool pstep) {
            used[p][t][pstep] = true;
            for (vector<state>::iterator i = g[p][t][pstep].begin(); i != g[p]
    [t][pstep].end(); ++i)
                    if (!used[i->p][i->t][i->pstep]) {
                            if (loose[p][t][pstep])
                                    win[i->p][i->t][i->pstep] = true;
                            else if (--degree[i->p][i->t][i->pstep] == 0)
                                    loose[i->p][i->t][i->pstep] = true;
                            else
                                    continue;
                            dfs (i->p, i->t, i->pstep);
                    }
    }
    int main() {
            int n, m;
            cin >> n >> m;
            List<string> a (n);
            for (int i=0; i<n; ++i)
                    cin >> a[i];
            for (int p=0; p<n*m; ++p)
                    for (int t=0; t<n*m; ++t)
                            for (char pstep=0; pstep<=1; ++pstep) {
                                    int px = p/m, py = p%m, tx=t/m, ty=t%m;
                                    if (a[px][py]=='*' || a[tx][ty]=='*')  continue;
                                    bool & wwin = win[p][t][pstep];
                                    bool & lloose = loose[p][t][pstep];
                                    if (pstep)
                                            wwin = px==tx && py==ty,   lloose
    = !wwin && a[tx][ty] == 'E';
                                    else
                                            wwin = a[tx][ty] == 'E',   lloose
    = !wwin && px==tx && py==ty;
                                    if (wwin || lloose)  continue;
                                    state st = { p, t, !pstep };
                                    g[p][t][pstep].push_back (st);
                                    st.pstep = pstep != 0;
                                    degree[p][t][pstep] = 1;
                                    const int dx[] = { -1, 0, 1, 0,   -1, -1,
    1, 1 };
                                    const int dy[] = { 0, 1, 0, -1,   -1, 1, -
    1, 1 };
                                    for (int d=0; d<(pstep?8:4); ++d) {
                                            int ppx=px, ppy=py, ttx=tx, tty=ty;
                                            if (pstep)
                                                    ppx += dx[d],  ppy += dy[d];
                                            else
                                                    ttx += dx[d],  tty += dy[d];
                                            if (ppx>=0 && ppx<n && ppy>=0 &&
    ppy<m && a[ppx][ppy]!='*' &&
                                                    ttx>=0 && ttx<n && tty>=0
    && tty<m && a[ttx][tty]!='*')
                                            {
                                                    g[ppx*m+ppy][ttx*m+tty][!
    pstep].push_back (st);
                                                    ++degree[p][t][pstep];
                                            }
                                    }
                            }
            for (int p=0; p<n*m; ++p)
                    for (int t=0; t<n*m; ++t)
                            for (char pstep=0; pstep<=1; ++pstep)
                                    if ((win[p][t][pstep] || loose[p][t]
    [pstep]) && !used[p][t][pstep])
                                            dfs (p, t, pstep!=0);
            int p_st, t_st;
            for (int i=0; i<n; ++i)
                    for (int j=0; j<m; ++j)
                            if (a[i][j] == 'C')
                                    p_st = i*m+j;
                            else if (a[i][j] == 'T')
                                    t_st = i*m+j;
            Console.WriteLine( (win[p_st][t_st][true] ? "WIN" : loose[p_st][t_st]
    [true] ? "LOSS" : "DRAW");
    }
}

C++ solution

matched/original
vector<int> g [100];
bool win [100];
bool loose [100];
bool used[100];
int degree[100];
void dfs (int v) {
        used[v] = true;
        for (vector<int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
                if (!used[*i]) {
                        if (loose[v])
                                win[*i] = true;
                        else if (--degree[*i] == 0)
                                loose[*i] = true;
                        else
                                continue;
                        dfs (*i);
                }
}
struct state {
        char p, t;
        bool pstep;
};
vector<state> g [100][100][2];
// 1 = policeman coords; 2 = thief coords; 3 = 1 if policeman's step or 0
if thief's.
bool win [100][100][2];
bool loose [100][100][2];
bool used[100][100][2];
int degree[100][100][2];
void dfs (char p, char t, bool pstep) {
        used[p][t][pstep] = true;
        for (vector<state>::iterator i = g[p][t][pstep].begin(); i != g[p]
[t][pstep].end(); ++i)
                if (!used[i->p][i->t][i->pstep]) {
                        if (loose[p][t][pstep])
                                win[i->p][i->t][i->pstep] = true;
                        else if (--degree[i->p][i->t][i->pstep] == 0)
                                loose[i->p][i->t][i->pstep] = true;
                        else
                                continue;
                        dfs (i->p, i->t, i->pstep);
                }
}
int main() {
        int n, m;
        cin >> n >> m;
        vector<string> a (n);
        for (int i=0; i<n; ++i)
                cin >> a[i];
        for (int p=0; p<n*m; ++p)
                for (int t=0; t<n*m; ++t)
                        for (char pstep=0; pstep<=1; ++pstep) {
                                int px = p/m, py = p%m, tx=t/m, ty=t%m;
                                if (a[px][py]=='*' || a[tx][ty]=='*')  continue;
                                bool & wwin = win[p][t][pstep];
                                bool & lloose = loose[p][t][pstep];
                                if (pstep)
                                        wwin = px==tx && py==ty,   lloose
= !wwin && a[tx][ty] == 'E';
                                else
                                        wwin = a[tx][ty] == 'E',   lloose
= !wwin && px==tx && py==ty;
                                if (wwin || lloose)  continue;
                                state st = { p, t, !pstep };
                                g[p][t][pstep].push_back (st);
                                st.pstep = pstep != 0;
                                degree[p][t][pstep] = 1;
                                const int dx[] = { -1, 0, 1, 0,   -1, -1,
1, 1 };
                                const int dy[] = { 0, 1, 0, -1,   -1, 1, -
1, 1 };
                                for (int d=0; d<(pstep?8:4); ++d) {
                                        int ppx=px, ppy=py, ttx=tx, tty=ty;
                                        if (pstep)
                                                ppx += dx[d],  ppy += dy[d];
                                        else
                                                ttx += dx[d],  tty += dy[d];
                                        if (ppx>=0 && ppx<n && ppy>=0 &&
ppy<m && a[ppx][ppy]!='*' &&
                                                ttx>=0 && ttx<n && tty>=0
&& tty<m && a[ttx][tty]!='*')
                                        {
                                                g[ppx*m+ppy][ttx*m+tty][!
pstep].push_back (st);
                                                ++degree[p][t][pstep];
                                        }
                                }
                        }
        for (int p=0; p<n*m; ++p)
                for (int t=0; t<n*m; ++t)
                        for (char pstep=0; pstep<=1; ++pstep)
                                if ((win[p][t][pstep] || loose[p][t]
[pstep]) && !used[p][t][pstep])
                                        dfs (p, t, pstep!=0);
        int p_st, t_st;
        for (int i=0; i<n; ++i)
                for (int j=0; j<m; ++j)
                        if (a[i][j] == 'C')
                                p_st = i*m+j;
                        else if (a[i][j] == 'T')
                                t_st = i*m+j;
        cout << (win[p_st][t_st][true] ? "WIN" : loose[p_st][t_st]
[true] ? "LOSS" : "DRAW");
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    ArrayList<Integer> g [100];
    boolean win [100];
    boolean loose [100];
    boolean used[100];
    int degree[100];
    void dfs (int v) {
            used[v] = true;
            for (ArrayList<Integer>::iterator i = g[v].begin(); i != g[v].end(); ++i)
                    if (!used[*i]) {
                            if (loose[v])
                                    win[*i] = true;
                            else if (--degree[*i] == 0)
                                    loose[*i] = true;
                            else
                                    continue;
                            dfs (*i);
                    }
    }
    struct state {
            char p, t;
            boolean pstep;
    };
    vector<state> g [100][100][2];
    // 1 = policeman coords; 2 = thief coords; 3 = 1 if policeman's step or 0
    if thief's.
    boolean win [100][100][2];
    boolean loose [100][100][2];
    boolean used[100][100][2];
    int degree[100][100][2];
    void dfs (char p, char t, boolean pstep) {
            used[p][t][pstep] = true;
            for (vector<state>::iterator i = g[p][t][pstep].begin(); i != g[p]
    [t][pstep].end(); ++i)
                    if (!used[i->p][i->t][i->pstep]) {
                            if (loose[p][t][pstep])
                                    win[i->p][i->t][i->pstep] = true;
                            else if (--degree[i->p][i->t][i->pstep] == 0)
                                    loose[i->p][i->t][i->pstep] = true;
                            else
                                    continue;
                            dfs (i->p, i->t, i->pstep);
                    }
    }
    int main() {
            int n, m;
            cin >> n >> m;
            ArrayList<String> a (n);
            for (int i=0; i<n; ++i)
                    cin >> a[i];
            for (int p=0; p<n*m; ++p)
                    for (int t=0; t<n*m; ++t)
                            for (char pstep=0; pstep<=1; ++pstep) {
                                    int px = p/m, py = p%m, tx=t/m, ty=t%m;
                                    if (a[px][py]=='*' || a[tx][ty]=='*')  continue;
                                    boolean & wwin = win[p][t][pstep];
                                    boolean & lloose = loose[p][t][pstep];
                                    if (pstep)
                                            wwin = px==tx && py==ty,   lloose
    = !wwin && a[tx][ty] == 'E';
                                    else
                                            wwin = a[tx][ty] == 'E',   lloose
    = !wwin && px==tx && py==ty;
                                    if (wwin || lloose)  continue;
                                    state st = { p, t, !pstep };
                                    g[p][t][pstep].push_back (st);
                                    st.pstep = pstep != 0;
                                    degree[p][t][pstep] = 1;
                                    const int dx[] = { -1, 0, 1, 0,   -1, -1,
    1, 1 };
                                    const int dy[] = { 0, 1, 0, -1,   -1, 1, -
    1, 1 };
                                    for (int d=0; d<(pstep?8:4); ++d) {
                                            int ppx=px, ppy=py, ttx=tx, tty=ty;
                                            if (pstep)
                                                    ppx += dx[d],  ppy += dy[d];
                                            else
                                                    ttx += dx[d],  tty += dy[d];
                                            if (ppx>=0 && ppx<n && ppy>=0 &&
    ppy<m && a[ppx][ppy]!='*' &&
                                                    ttx>=0 && ttx<n && tty>=0
    && tty<m && a[ttx][tty]!='*')
                                            {
                                                    g[ppx*m+ppy][ttx*m+tty][!
    pstep].push_back (st);
                                                    ++degree[p][t][pstep];
                                            }
                                    }
                            }
            for (int p=0; p<n*m; ++p)
                    for (int t=0; t<n*m; ++t)
                            for (char pstep=0; pstep<=1; ++pstep)
                                    if ((win[p][t][pstep] || loose[p][t]
    [pstep]) && !used[p][t][pstep])
                                            dfs (p, t, pstep!=0);
            int p_st, t_st;
            for (int i=0; i<n; ++i)
                    for (int j=0; j<m; ++j)
                            if (a[i][j] == 'C')
                                    p_st = i*m+j;
                            else if (a[i][j] == 'T')
                                    t_st = i*m+j;
            System.out.println( (win[p_st][t_st][true] ? "WIN" : loose[p_st][t_st]
    [true] ? "LOSS" : "DRAW");
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.