Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Так это же сапёр!
Вот так задачку вы мне подкинули. Уже час мучаюсь.
А между тем — решение единственно. И, на мой взгляд, логически вычсиляемо.
Не прокатит. Кто первый походил у того фатальное преимущество если тупить не будет…
Позволю себе напомнить уважаемому хабрасообществу про азиатскую (изначально китайскую, затем корейскую, но именно японцы довели до совершенства эту игру) — игру Го
В зависимости от культуры названия: Go, iGo, Вэйци(围棋), Бадук (Падук скорее произносится — 바둑)
Цитата:
«Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 10^46 (в шашках порядок куда скромнее — 10^20), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.»
"
… число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10^171. И к ним можно прийти одним из 10^1100 путей"
Это фантастически эпически опупительно много. А ведь в Go на порядок более простые правила — их всего пять, и нет ранжирования фигур — все камни равнозначны — просто белые против черных.
«Черные» делают ход первыми, ставят первый камень на доску. Столетия игры выявили правило — это даёт «черным» преимущество. На доске 19х19, при 10^171 вариантов и 10^1100 путей, тем не менее эмпирически, столетиями опыта выснилось, что черные имеют преимущество в 5-6 камней на доске к итогу партии.
В итоге японцы ввели правило «коми» (или «гандикапа», «форы» по-нашему) именно 5,5 очков.
Тот кто играет за «черных» уже изначально проигрывает 5,5 камней при подсчете очков, и начинает игру проигрывая, давая белым фору. Заодно и ничьей не будет.
Если говорить о «морском бое» в статье и сравнивать…
«А гандикап предусмотрен?» — мой первый вопрос.
Позволю себе напомнить уважаемому хабрасообществу про азиатскую (изначально китайскую, затем корейскую, но именно японцы довели до совершенства эту игру) — игру Го
В зависимости от культуры названия: Go, iGo, Вэйци(围棋), Бадук (Падук скорее произносится — 바둑)
Цитата:
«Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 10^46 (в шашках порядок куда скромнее — 10^20), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.»
"
… число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10^171. И к ним можно прийти одним из 10^1100 путей"
Это фантастически эпически опупительно много. А ведь в Go на порядок более простые правила — их всего пять, и нет ранжирования фигур — все камни равнозначны — просто белые против черных.
«Черные» делают ход первыми, ставят первый камень на доску. Столетия игры выявили правило — это даёт «черным» преимущество. На доске 19х19, при 10^171 вариантов и 10^1100 путей, тем не менее эмпирически, столетиями опыта выснилось, что черные имеют преимущество в 5-6 камней на доске к итогу партии.
В итоге японцы ввели правило «коми» (или «гандикапа», «форы» по-нашему) именно 5,5 очков.
Тот кто играет за «черных» уже изначально проигрывает 5,5 камней при подсчете очков, и начинает игру проигрывая, давая белым фору. Заодно и ничьей не будет.
Если говорить о «морском бое» в статье и сравнивать…
«А гандикап предусмотрен?» — мой первый вопрос.
Да, как при такой сложности вывели именно 5-6 очков гандикапа для равной игры во времена за столетия до первого транзистора? Очень просто, это вершина «приближенных вычислений».
Разные мастера примерно одного уровня играли серии партий друг против друга поочередно за Б и за Ч, и сравнивали разницу очков в итоге. За несколько тысяч «калибровочных» игр истории Go значение стало ясным, оно между 5 и 6 камней.
Разные мастера примерно одного уровня играли серии партий друг против друга поочередно за Б и за Ч, и сравнивали разницу очков в итоге. За несколько тысяч «калибровочных» игр истории Go значение стало ясным, оно между 5 и 6 камней.
http://ru.wikipedia.org/wiki/Коми_(го)
Тем не менее, в 21-м веке почти повсеместно принято играть с коми 6.5, а в Китае уже и 7.5.
Тем не менее, в 21-м веке почти повсеместно принято играть с коми 6.5, а в Китае уже и 7.5.
Я и многие игроки не согласны, исторически сложилось, что коми начался когда-то с одного очка, потом рос и рос, и в настоящее время китайцы играют до 9.5 очков коми. Перебор. Баланс был на 5.5 очков, рост коми с эволюцией должен был остановиться на 5.5 — выше это уже компенсация психологической составляющей. IMHO
Не уверен, что рост коми кому-то что-то должен )
Каждый ход стоит каких-то очков, первые — много, последние — мало, игра останавливается, когда стоимость становится отрицательной.
Когда-то техника игры была не такой совершенной, как сейчас, и не позволяла реализовать полностью преимущество первого хода, тогда коми 5.5 было разумным. С ростом техники игры у черных (ходят первыми) появляется дополнительное преимущество, которое надо компенсировать ростом коми.
У меня недостаточно мастерства, чтобы оценить, какая часть этого преимущества обьективная, а какая — психологическая. Но то, что коми растет — вполне обьяснимо — эволюционирует техника игры.
Каждый ход стоит каких-то очков, первые — много, последние — мало, игра останавливается, когда стоимость становится отрицательной.
Когда-то техника игры была не такой совершенной, как сейчас, и не позволяла реализовать полностью преимущество первого хода, тогда коми 5.5 было разумным. С ростом техники игры у черных (ходят первыми) появляется дополнительное преимущество, которое надо компенсировать ростом коми.
У меня недостаточно мастерства, чтобы оценить, какая часть этого преимущества обьективная, а какая — психологическая. Но то, что коми растет — вполне обьяснимо — эволюционирует техника игры.
Вы путаете детерменированные игры с полной информацией (какими являются и шахматы и го) и случайную игру с неполной информацией.
В детерменированных играх действительно можно построить полное дерево вариантов (по крайней мере теоретически) и обнаружить его дисбаланс. Естественно, для выравнивания этого дисбаланса и необходим гандикап.
В случайных играх с неполной информацией нет (и не может быть) выигрышной стратегии. Поэтому уравнивать тут нечего.
В детерменированных играх действительно можно построить полное дерево вариантов (по крайней мере теоретически) и обнаружить его дисбаланс. Естественно, для выравнивания этого дисбаланса и необходим гандикап.
В случайных играх с неполной информацией нет (и не может быть) выигрышной стратегии. Поэтому уравнивать тут нечего.
Го — абсолютно детерменирована. Как и Шашки (которые хакнуты уже полностью при 10^20. В любой момент игры при любом раскладе игры даже в середине игры компьютер вам подскажет единственный самый выгодный ход)
Вы правила Го почитайте, я вас прошу, потом применяйте в комментарии умное слово «детерменировано», ато вы выглядите несколько девиантно по отношению к математикам.
Вы правила Го почитайте, я вас прошу, потом применяйте в комментарии умное слово «детерменировано», ато вы выглядите несколько девиантно по отношению к математикам.
Добавлю: кто не в курсе, шашки хакнуты суперкомпьютерами года 4 назад полностью, тупым перебором всех возможных вариантов.
Но, до шахмат таким образом еще далеко. У шахмат 10^46 вариантов. Но… даже 10^21 это уже в десять(!) раз больше вычислений надо, чем хакнутые 10^20 шашки.
Представьте себе масштаб, сколько энергии надо, чтобы хакнуть шахматы полным перебором.
Но, до шахмат таким образом еще далеко. У шахмат 10^46 вариантов. Но… даже 10^21 это уже в десять(!) раз больше вычислений надо, чем хакнутые 10^20 шашки.
Представьте себе масштаб, сколько энергии надо, чтобы хакнуть шахматы полным перебором.
Вы комментарий, на который отвечаете, почитайте, я ваш прошу, потом применяйте в комментарии умное словое слово «детерменировано», а то вы выглядите несколько девиантно по отношению к людям, умеющим воспринимать информацию с помощью чтения. ;)
Я читаю, честно ;) обращу внимание:
«В детерменированных играх действительно можно построить полное дерево вариантов» — в Го это есть.
«В случайных играх с неполной информацией нет (и не может быть) выигрышной стратегии.» — в «Морском бое» это нет, нет случайности.
За исключением первых ходов может быть, да и первые ходы можно построить на основе выработанной статистики, а значит они не случайны. Это не казино.
(хотя строго физически казино детерменировано окружающими условиями, температурой, влажностью, изначальным положением камней/фишек/рулетки)
«В детерменированных играх действительно можно построить полное дерево вариантов» — в Го это есть.
«В случайных играх с неполной информацией нет (и не может быть) выигрышной стратегии.» — в «Морском бое» это нет, нет случайности.
За исключением первых ходов может быть, да и первые ходы можно построить на основе выработанной статистики, а значит они не случайны. Это не казино.
(хотя строго физически казино детерменировано окружающими условиями, температурой, влажностью, изначальным положением камней/фишек/рулетки)
(хотя строго физически казино детерменировано окружающими условиями, температурой, влажностью, изначальным положением камней/фишек/рулетки)Да-да, а состояние нашей Вселенной в любой момент времени строго физически детерминированно её состоянием в первые секунды Большого Взрыва.
Да-да, а состояние нашей Вселенной в любой момент времени строго физически детерминированно её состоянием в первые секунды Большого Взрыва.
Насколько я понимаю, квантовая физика утверждает что это не так.
Квантовая физика ничерта не знает точно про первые моменты жизни Вселенной и почему она такая как есть.
Но, с большой достоверностью имеет «инфляционную теорию», которая в грубом приближении всё объясняет, а также подразумевает мультивселенную.
Правда в более близком приближении там косяки со сверхсветовой скоростью расширения, что не противоречит ТО (расширяется именно пространство, а не взаимодействие материи), но приводит в азартное уныние математиков, потому-что здравая идея есть, а посчитать ее — фиг.
И позитивная нота, что не во всех удалениях от нас наша Вселенная имеет одинаковые законы физики, а совсем далеко продолжается инфляция в другой (относительно нас) временнОй метрике.
...Homo-sapiens лучше так далеко не летать.
Но, с большой достоверностью имеет «инфляционную теорию», которая в грубом приближении всё объясняет, а также подразумевает мультивселенную.
Правда в более близком приближении там косяки со сверхсветовой скоростью расширения, что не противоречит ТО (расширяется именно пространство, а не взаимодействие материи), но приводит в азартное уныние математиков, потому-что здравая идея есть, а посчитать ее — фиг.
И позитивная нота, что не во всех удалениях от нас наша Вселенная имеет одинаковые законы физики, а совсем далеко продолжается инфляция в другой (относительно нас) временнОй метрике.
...Homo-sapiens лучше так далеко не летать.
Хм. Это вы мне отвечаете? Я как раз и пишу, что го — детерменирована, потому приводить ее в качестве примера для морского боя не стоит. Или вы построение моей фразы не поняли?
> Вы путаете детерменированные игры с полной информацией и случайную игру с неполной информацией.
Поскольку размер поля в морском бое ограничен, эта игра тоже детерминированная.
Поскольку размер поля в морском бое ограничен, эта игра тоже детерминированная.
Для такого морского боя вполне можно предусмотреть вариант, когда оба игрока ходят одновременно.
Т.е. оба игрока называют клетку, в которую совершают ход. Потом оба говорят результат хода соперника.
Повтор хода в случае успешного попадания убрать. Получаем игру именно на анализ поля противника, на умение грамотно расставлять корабли.
Т.е. оба игрока называют клетку, в которую совершают ход. Потом оба говорят результат хода соперника.
Повтор хода в случае успешного попадания убрать. Получаем игру именно на анализ поля противника, на умение грамотно расставлять корабли.
А вообще что-то в этом есть… постараюсь реализовать программно эту игру.
Согласен, такое правило добавит интригу и нивелирует недостатки.
Satellence, вы молодцом )) Действительно, достаточно убрать очередность ходов, и коми не нужно, в «морском бое» это прокатит, за исключением возможного уточнения правил, поскольку может получиться «ничья»
Satellence, вы молодцом )) Действительно, достаточно убрать очередность ходов, и коми не нужно, в «морском бое» это прокатит, за исключением возможного уточнения правил, поскольку может получиться «ничья»
Повтор модно оставить… если один из игроков попал, то в следующем ходе противник молчит… если попали оба — по прежнему одновременный ход
Еще в школе пробовали с другом играть в шахматы подобным образом — ход совершался одновременно (для надежности записывался на бумажке, что бы нельзя было смухлевать). Такой подход сильно меняет игру и вводит новые, неопределенные классическими правилами моменты, — например, одновременый шах, или попытка взять фигуру, которая от вас убегает этим же ходом, пришлось вводить дополнительные правила: разрешить ходить под потенциальный шах, но обязать совершать уклонение от него следующим же ходом. Хотя, конечно, наши изменения не были проверены многократными переигрываниями или сложным мат. аппаратом и возможно правила нужно модернизировать совершенно иначе под риалтайм.
Первая пятерка решивших задачу определилась. Это AlexKostin, tzlom, Mrrl, Leg01as, hellman. Первый из них прислал решение через 3 часа 17 минут после публикации топика, последний — через 5 часов 3 минуты. Поздравляю!
Привет, ребята. Летом прошлого года я независимо (не зная о ней ранее) придумал эту игру, и мы с коллегами ее реализовали. Играть можно в вебе, на айфоне и на андроиде.
battlesweeper.com/
Скорее всего, вам не понравится, что надо иметь логин в Фейсбуке, но нам это помогает играть с нашими друзьями :-)
battlesweeper.com/
Скорее всего, вам не понравится, что надо иметь логин в Фейсбуке, но нам это помогает играть с нашими друзьями :-)
Игру явно упростили — есть идея как компенсировать. Необходимо Добавить возможность двигать корабли, вместо выстрела сдвинуть один из кораблей на 1 квадрат, при условии что корабль не подбит и точка куда движется корабль ранее не обстреливалась.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Продвинутый морской бой