MAXimal

добавлено: 11 Jun 2008 11:19
редактировано: 11 Jun 2008 11:20

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

Пусть игра ведётся двумя игроками на некотором графе 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");

}