Игра на доске 10x10

[worm2]

vicvolf, правдоподобно
А какие-нибудь другие модели пробовали?
Говорят, есть какие-то прямо заточенные на математические задачи.
Хотя, кстати, и эта модель может быть небезнадёжной: возмутитесь, что её решение заставляет бедного короля скакать больше чем на одну клетку по вертикали, вдруг чего-нибудь путное выдаст.

[vicvolf]

worm2 в сообщении #1678908 писал(а):

решение заставляет бедного короля скакать больше чем на одну клетку по вертикали

Если Петя попытается двигаться вертикально, чтобы обойти высокое число в текущем столбце, Вася может расположить в соседних строках ещё более высокие числа и Петя будет вынужден их взять.

[Geen]

vicvolf в сообщении #1678907 писал(а):

Петя выбирает путь, проходящий через минимальные числа каждого столбца.

Не может - путь определяется возможностями короля.

[vicvolf]

Geen в сообщении #1678915 писал(а):

vicvolf в сообщении #1678907 писал(а):

Петя выбирает путь, проходящий через минимальные числа каждого столбца.

Не может - путь определяется возможностями короля.

Равновесие Нэша достигается только при диагональном распределении минимумов. Если Вася разместит минимумы в несмежных строках, Петя сможет найти путь с меньшей суммой, что противоречит цели Васи. Если Петя отклонится от диагонали, он заплатит больше.

[Geen]

vicvolf в сообщении #1678916 писал(а):

Если Вася разместит минимумы в несмежных строках, Петя сможет найти путь с меньшей суммой

А это откуда следует?

[Dan B-Yallay]

vicvolf в сообщении #1678907 писал(а):

Таким образом, при оптимальной стратегии обоих игроков минимальная сумма, которую Петя обязан заплатить, составляет $460$ рублей.

Пройдите королём от левого синего столбца до правого зелёного за меньше, чем 500

Вложение:

r.jpg [ 107.86 Кб | Просмотров: 0 ]

[Alex Krylov]

Возникает логичное соображение, что общая сумма должна быть поровну поделена между 10 строками:
$\frac{\sum\limits_{i=1}^{100}i}{10}=\frac{5050}{10}=505$
Чтобы сумма каждой строки давала 505. Приведенная постом выше "змейка" построчно дает 505, но за счет возможности передвижения между строками можно снизить значение этих сумм до 500.

[zgemm]

интересно, а как бы эта задача решалась, если бы вместо короля был бы конь... змейка-то будет уже не оптимальной стратегией

[vicvolf]

zgemm в сообщении #1679006 писал(а):

интересно, а как бы эта задача решалась, если бы вместо короля был бы конь... змейка-то будет уже не оптимальной стратегией

Здесь уже стратегия "змейки" не пойдет, конь ее перепрыгнет. В этом случае, наверно можно использовать, что при каждом следующем ходе конь ходит на клетку с другим цветом. Поэтому можно рекомендовать следующую стратегию. На чёрных клетках размещаются числа из верхней половины диапазона (51–100). На белых клетках — числа из нижней половины (1–50). Или наоборот.

[mihaild]

Тогда уже для произвольных графов задачу ставить. Выглядит как гроб, но отличие ходов коня от произвольных тоже не выглядит хорошим.

[Alex Krylov]

Вообще не мешало бы переформулировать изначальную задачу в виде некоей хоть сколько-нибудь обозримой оптимизационной задачи...

Для примера рассмотрим задачу 3x3.

$\begin{bmatrix}c_{11}&c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{bmatrix} \leftrightarrow \left\lbrace 1,2,3,4,5,6,7,8,9\right\rbrace$

Например можно сделать вот так:
$c_{11} = 1 X_{1,1}+2 X_{1,2}+3 X_{1,3}+4 X_{1,4}+5 X_{1,5}+6 X_{1,6}+7 X_{1,7}+8 X_{1,8}+9 X_{1,9}$
...
$c_{21} = 1 X_{4,1}+2 X_{4,2}+3 X_{4,3}+4 X_{4,4}+5 X_{4,5}+6 X_{4,6}+7 X_{4,7}+8 X_{4,8}+9 X_{4,9}$

На переменные $X_{i,j}$ накладываются ограничения, характерные для линейной задачи о назначениях

Теперь посмотрим, как выглядит минимум всевозможных сумм при всевозможных проходах короля... Вот так выглядет все возможные комбинации:

$c_{11}+c_{12}+c_{13}$
$c_{11}+c_{12}+c_{23}$
$c_{11}+c_{22}+c_{13}$
$c_{11}+c_{22}+c_{23}$
$c_{11}+c_{22}+c_{33}$

$c_{21}+c_{12}+c_{13}$
$c_{21}+c_{12}+c_{23}$
$c_{21}+c_{22}+c_{13}$
$c_{21}+c_{22}+c_{23}$
$c_{21}+c_{22}+c_{33}$
$c_{21}+c_{32}+c_{23}$
$c_{21}+c_{32}+c_{33}$

$c_{31}+c_{22}+c_{13}$
$c_{31}+c_{22}+c_{23}$
$c_{31}+c_{22}+c_{33}$
$c_{31}+c_{32}+c_{23}$
$c_{31}+c_{32}+c_{33}$

Надо по ним взять минимум. Задача
$\min\limits_{}\left\lbrace c_{11}+c_{12}+c_{13}, c_{11}+c_{12}+c_{23}, \dots\right\rbrace$
эквивалентна задаче:

$\max\limits_{}t$

$c_{11}+c_{12}+c_{13} \geqslant t$
$c_{11}+c_{12}+c_{23} \geqslant t$
$c_{11}+c_{22}+c_{13} \geqslant t$
$c_{11}+c_{22}+c_{23} \geqslant t$
$c_{11}+c_{22}+c_{33} \geqslant t$

$c_{21}+c_{12}+c_{13} \geqslant t$
$c_{21}+c_{12}+c_{23} \geqslant t$
$c_{21}+c_{22}+c_{13} \geqslant t$
$c_{21}+c_{22}+c_{23} \geqslant t$
$c_{21}+c_{22}+c_{33} \geqslant t$
$c_{21}+c_{32}+c_{23} \geqslant t$
$c_{21}+c_{32}+c_{33} \geqslant t$

$c_{31}+c_{22}+c_{13} \geqslant t$
$c_{31}+c_{22}+c_{23} \geqslant t$
$c_{31}+c_{22}+c_{33} \geqslant t$
$c_{31}+c_{32}+c_{23} \geqslant t$
$c_{31}+c_{32}+c_{33} \geqslant t$

Осталось выполнить подстановку и выразить все относительно переменных $X_{i,j}$, плюс добавить ограничения на эти переменные, характерные для линейной задачи о назначениях. В итоге имеем задачу максимизации (если я тут ничего не напутал нигде).

[vicvolf]

Alex Krylov в сообщении #1679138 писал(а):

Вообще не мешало бы переформулировать изначальную задачу в виде некоей хоть сколько-нибудь обозримой оптимизационной задачи...

А зачем? Чтобы сделать ее нерешабельной даже в таком простом случае? Давно известно, что любую такую игровую задачу можно свести к задаче линейного программирования.

[Alex Krylov]

To vicvolf

Цитата:

Давно известно, что любую такую игровую задачу можно свести к задаче линейного программирования.

Не могли бы вы привести пример данной линейной программы (хотя бы для случая 3x3), чтобы было понятно, что вы имеете в виду.

Да, кстати... То, что было приведено мной выше, это пока еще не линейная программа, так как содержит булевы ограничения (подобно линейной задаче о назначениях)... Но эти булевы ограничения мы, однако, можем релаксировать в линейные неравенства... и посмотреть, что выйдет.

[vicvolf]

Alex Krylov в сообщении #1679209 писал(а):

Не могли бы вы привести пример данной линейной программы, чтобы было понятно, что вы имеете в виду.

Для ответа на Ваш вопрос воспользовался ИИ. Вот его ответ.

Для формализации задачи о нахождении минимальной суммы пути короля через таблицу 10×10 в рамках линейного программирования (ЛП) выполним следующие шаги:

1. Определение переменных:
- Бинарные переменные посещения клеток:
$ x_{i,j} \in \{0, 1\} \), где \( x_{i,j} = 1 $, если король посещает клетку $(i,j)$, и $ 0 $в противном случае.
Всего: $ 10 \times 10 = 100 $ переменных.

- Переменные переходов:
$ y_{(i,j) \to (k,l)} \in \{0, 1\} $ где $ y_{(i,j) \to (k,l)} = 1 $, если король перемещается из клетки $(i,j)$ в $(k,l)$.
Всего: $100 \times 9 = 900 $ переменных (каждая клетка имеет до 8 соседей).

2. Целевая функция:
Минимизировать общую сумму чисел на пути:
$\text{Minimize: } \sum_{i=1}^{10} \sum_{j=1}^{10} c_{i,j} \cdot x_{i,j},$
где $ c_{i,j} $ — число в клетке $(i,j)$.

3. Ограничения:
a) Старт и финиш:
- Король начинает в первом столбце:
$ \sum_{i=1}^{10} x_{i,1} = 1. $
- Король заканчивает в десятом столбце:
$ \sum_{i=1}^{10} x_{i,10} = 1.$

b) Последовательность пути:
- Единственность посещения:
Каждую клетку можно посетить не более одного раза:
$ x_{i,j} \leq 1 \quad \forall i,j.$

- Связь переходов и посещений:
Если король переходит из $(i,j)$ в $(k,l)$, то обе клетки должны быть посещены:
$ y_{(i,j) \to (k,l)} \leq x_{i,j}, \quad y_{(i,j) \to (k,l)} \leq x_{k,l}. $

- Непрерывность пути:
Для каждой клетки $(i,j)$, кроме стартовой и конечной:
$ \sum_{(k,l) \in \text{предыдущие}} y_{(k,l) \to (i,j)} = \sum_{(m,n) \in \text{следующие}} y_{(i,j) \to (m,n)}.$

c) Допустимые переходы:
Переходы возможны только между соседними клетками (включая диагональ):
$y_{(i,j) \to (k,l)} = 0 \quad \text{если } |i-k| > 1 \text{ или } |j-l| > 1.$

4. Проблемы модели:
- Вычислительная сложность: Модель содержит $ 100 + 900 = 1000 $ переменных и $ \approx 2000 $ ограничений, что делает её решение трудоёмким даже для современных солверов.
- Целочисленность: Задача требует бинарных переменных, поэтому это целочисленное линейное программирование (ILP), которое NP-трудно.

Таким образом, задачу можно формально свести к ILP, но линейное программирование здесь используется как теоретический инструмент для формализации, а не для эффективного решения.

Другой подход сведения антагонистических игр к задаче линейного программирования, если игра приведена к матричной форме, рассмотрен у Е.С. Вентцель "Исследование операций".

[Alex Krylov]

Можно и как-то так:

$Y_{i,j}\in\left\lbrace 0,1 \right\rbrace$

$\sum\limits_{i=1}^{N} Y_{i,j}=1\quad\forall j =1,\dots,N$

$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N} Y_{i,j}=N$

Условия непрерывности траекторий (вроде такое имеет смысл):
$\\ \sum\limits_{i=1}^{N-1}(Y_{i,j+1}+Y_{i+1,j})+\sum\limits_{i=1}^{N-1}(Y_{i+1,j+1}+Y_{i,j})+\sum\limits_{i=1}^{N}(Y_{i,j}+Y_{i,j+1})=2 \\ \forall j =1,\dots,N-1 $

Далее, если ослабить невыпуклые булевы ограничения $X_{i,j}\in\left\lbrace 0,1 \right\rbrace,\; Y_{i,j}\in\left\lbrace 0,1 \right\rbrace$, заменив их на $0\leqslant X_{i,j}\leqslant 1, \quad 0\leqslant Y_{i,j}\leqslant 1 \quad \forall i,j$, то приходим к разрешимой билинейной минимаксной задаче с независимыми линейными ограничениями: $\min\limits_{Y}\max\limits_{X}\sum\limits_{i,j}^{}c_{i,j}Y_{i,j}=\max\limits_{X}\min\limits_{Y}\sum\limits_{i,j}^{}c_{i,j}Y_{i,j}$, где величины $c_{i,j}$ определены выше и зависят линейно от $X_{i,j}$.

Короче говоря, вся надежда на нулевой "integrality gap" за счет структурности.

Disclaimer: Написано на скорую руку, так что могут быть ошибки.