2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 19:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 20:09 


23/02/12
3451
worm2 в сообщении #1678908 писал(а):
решение заставляет бедного короля скакать больше чем на одну клетку по вертикали
Если Петя попытается двигаться вертикально, чтобы обойти высокое число в текущем столбце, Вася может расположить в соседних строках ещё более высокие числа и Петя будет вынужден их взять.

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 20:32 
Заслуженный участник
Аватара пользователя


01/09/13
4807
vicvolf в сообщении #1678907 писал(а):
Петя выбирает путь, проходящий через минимальные числа каждого столбца.

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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 20:43 


23/02/12
3451
Geen в сообщении #1678915 писал(а):
vicvolf в сообщении #1678907 писал(а):
Петя выбирает путь, проходящий через минимальные числа каждого столбца.

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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 20:46 
Заслуженный участник
Аватара пользователя


01/09/13
4807
vicvolf в сообщении #1678916 писал(а):
Если Вася разместит минимумы в несмежных строках, Петя сможет найти путь с меньшей суммой

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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение17.03.2025, 21:00 
Заслуженный участник
Аватара пользователя


11/12/05
10388
vicvolf в сообщении #1678907 писал(а):
Таким образом, при оптимальной стратегии обоих игроков минимальная сумма, которую Петя обязан заплатить, составляет $460$ рублей.

Пройдите королём от левого синего столбца до правого зелёного за меньше, чем 500
Вложение:
r.jpg
r.jpg [ 107.86 Кб | Просмотров: 0 ]

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение18.03.2025, 04:42 


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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение18.03.2025, 21:04 


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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение19.03.2025, 15:49 


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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение19.03.2025, 16:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение19.03.2025, 17:19 


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

Для примера рассмотрим задачу 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}$, плюс добавить ограничения на эти переменные, характерные для линейной задачи о назначениях. В итоге имеем задачу максимизации (если я тут ничего не напутал нигде).

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение19.03.2025, 21:11 


23/02/12
3451
Alex Krylov в сообщении #1679138 писал(а):
Вообще не мешало бы переформулировать изначальную задачу в виде некоей хоть сколько-нибудь обозримой оптимизационной задачи...
А зачем? Чтобы сделать ее нерешабельной даже в таком простом случае? Давно известно, что любую такую игровую задачу можно свести к задаче линейного программирования.

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение19.03.2025, 23:43 


14/11/21
209
To vicvolf
Цитата:
Давно известно, что любую такую игровую задачу можно свести к задаче линейного программирования.

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

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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение20.03.2025, 12:25 


23/02/12
3451
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, но линейное программирование здесь используется как теоретический инструмент для формализации, а не для эффективного решения.

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

 Профиль  
                  
 
 Re: Игра на доске 10x10
Сообщение20.03.2025, 18:53 


14/11/21
209
Можно и как-то так:

$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: Написано на скорую руку, так что могут быть ошибки.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 64 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group