2014 dxdy logo

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

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





Начать новую тему Ответить на тему
 
 Разработать выигрышную стратегию
Сообщение24.12.2016, 22:05 


10/05/13
251
Доброй ночи! Всех поздравляю с наступающим.
Сегодня хотел бы обсудить, такую задачку:
Алиса и Боб играют в игру: перед ними стоит доска 8x8, в каждой ячейке содержится целое число от -9 до 9.
Первой ходит Алиса, она может взять любое число в 1-й строке. Затем ход Боба, боб может взять любое
число из столбца, которому принадлежало число взятое Алисой. Затем снова ход Алисы, она берет любое
число из строки, из которой Боб взял число. Игра заканчивается когда ходов не осталось.
Выигывает тот кто набрал больше очков.

Пример (доска 3x3)
Код:
Алиса
0:0
3 1 -9
1 2 -3
0 -4 5

Боб
1:0
3   -9
1  2 -3
0 -4 5

Алиса
1:2
3   -9
1   -3
0 -4 5

Боб
2:2
3   -9
    -3
0 -4 5


Требуется разработать для Боба и Алисы оптимальные стратегии.

Пока, я решил данную задачу в лоб, Алгоритм за $O(8^{n^2})$
Давайте обсудим, может найдутся более быстрые решения :D

 Профиль  
                  
 
 Re: Разработать выигрышную стратегию
Сообщение25.12.2016, 12:57 
Аватара пользователя


31/10/08
788
Вначале изучите книгу:
А. Шень Игры и стратегии с точки зрения математики.

 Профиль  
                  
 
 Re: Разработать выигрышную стратегию
Сообщение26.12.2016, 12:58 
Аватара пользователя


26/09/16
36
Снегири
Если один из игроков будет специально выбирать такие поля, что игра будет идти только на двух строчках (или только на двух столбцах), то можно серьёзно упростить алгоритм.

 Профиль  
                  
 
 Re: Разработать выигрышную стратегию
Сообщение26.12.2016, 18:39 


28/03/16
48
Pavia в сообщении #1179814 писал(а):
Вначале изучите книгу:
А. Шень Игры и стратегии с точки зрения математики.

Интересная книжка, посоветуете подобное?

 Профиль  
                  
 
 Re: Разработать выигрышную стратегию
Сообщение31.12.2016, 01:34 


10/05/13
251
SVD-d в сообщении #1180193 писал(а):
Если один из игроков будет специально выбирать такие поля, что игра будет идти только на двух строчках (или только на двух столбцах), то можно серьёзно упростить алгоритм.

Но такое невозможно

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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