06:58
Сапёр и односвязность
В различных модификациях Сапёра, если только поле не подобрано специальным образом, случаются ситуации, когда логически невозможно вычислить, есть мина или нет. В этих случаях приходится полагаться только на теорию вероятности.
Самые поганые случаи -- это 50 на 50. Потому что неудачный выбор клетки ведёт к немедленному проигрышу, а удачный выбор может стратегически ничего не дать. Вы можете оказаться перед следующим, точно таким же выбором. "Пойду пока другой угол порешаю". Верным ли решением является откладывание неоднозначности?
Можно рассматривать не каждое игровое поле сапёра отдельно, а полагать, что это мета-игра, то есть игра, совмещающая все игровые поля, которые вы когда-либо разгадывали. В таком случае выгодным становится не "откладывать", а принимать решение как можно быстрее. Это экономит время. Лучше проиграть и быстрее начать следующее поле, чем разложить всё остальное и проиграть всё равно.
Тем не менее, есть случаи, когда неоднозначность может разрешиться позднее. В этом случае имеет смысл отложить решение.
Итак, когда надежды на разрешение неоднозначности нет?
1. Область с неоднозначностью изолирована от остальных областей.
2. В этой области со всех сторон имеются неоднозначности, т.е. невозможно безопасно вскрыть ни одного поля.
3. Количество оставшихся мин в области либо однозначно известно, либо информация об этом ни на что не влияет.
Может показаться, что считать на ходу все три условия будет сложно. Но после практики такую оценку можно делать за долю секунды.
Вот пример.
Посмотрим на жёлтый квадрат. 3,4 снизу обозначают, что среди нижних двух клеток квадрата есть одна мина. 4 слева обозначает то же самое для левой стороны квадрата.
Если мы знаем, что в этом квадрате только одна мина, то она будет в левом нижнем углу. Если мы знаем, что там две мины, то об их расположении ничего сказать нельзя. Если удастся "добраться" до этой зоны сверху, то неоднозначность может быть разрешена. Если же такая штука сформировалась в углу, то её также имеет смысл отложить на самый конец, чтобы узнать, сколько же там мин.
Таким образом, срочно устранять такую неоднозначность смысла нет, поскольку есть надежда на её разрешение логическим образом.
А вот другой пример.
Тут ясно, что мина одна, со всех сторон всё раскрыто и ничего больше не предвидится. Вот такую неоднозначность надо раскрывать сразу.
Самые поганые случаи -- это 50 на 50. Потому что неудачный выбор клетки ведёт к немедленному проигрышу, а удачный выбор может стратегически ничего не дать. Вы можете оказаться перед следующим, точно таким же выбором. "Пойду пока другой угол порешаю". Верным ли решением является откладывание неоднозначности?
Можно рассматривать не каждое игровое поле сапёра отдельно, а полагать, что это мета-игра, то есть игра, совмещающая все игровые поля, которые вы когда-либо разгадывали. В таком случае выгодным становится не "откладывать", а принимать решение как можно быстрее. Это экономит время. Лучше проиграть и быстрее начать следующее поле, чем разложить всё остальное и проиграть всё равно.
Тем не менее, есть случаи, когда неоднозначность может разрешиться позднее. В этом случае имеет смысл отложить решение.
Итак, когда надежды на разрешение неоднозначности нет?
1. Область с неоднозначностью изолирована от остальных областей.
2. В этой области со всех сторон имеются неоднозначности, т.е. невозможно безопасно вскрыть ни одного поля.
3. Количество оставшихся мин в области либо однозначно известно, либо информация об этом ни на что не влияет.
Может показаться, что считать на ходу все три условия будет сложно. Но после практики такую оценку можно делать за долю секунды.
Вот пример.
Посмотрим на жёлтый квадрат. 3,4 снизу обозначают, что среди нижних двух клеток квадрата есть одна мина. 4 слева обозначает то же самое для левой стороны квадрата.
Если мы знаем, что в этом квадрате только одна мина, то она будет в левом нижнем углу. Если мы знаем, что там две мины, то об их расположении ничего сказать нельзя. Если удастся "добраться" до этой зоны сверху, то неоднозначность может быть разрешена. Если же такая штука сформировалась в углу, то её также имеет смысл отложить на самый конец, чтобы узнать, сколько же там мин.
Таким образом, срочно устранять такую неоднозначность смысла нет, поскольку есть надежда на её разрешение логическим образом.
А вот другой пример.
Тут ясно, что мина одна, со всех сторон всё раскрыто и ничего больше не предвидится. Вот такую неоднозначность надо раскрывать сразу.
