Понятно. Нет, стрельба в "Морской бой" с точки зрения поиска по множеству размещения кораблей противника, не является аналогичной методу сетки. Даже неоптимальная стрельба наобум сходится экспоненциально, ведь прикинь порядок величины количества всех возможных размещений флота - 1E20! А даже в самом худшем случае, самой неудачной стрельбе, максимально за 100 выстрелов мы находим нужный элемент в этом множестве. Иначе, как экспонентой, такое множество нельзя победить за человеческое времяСообщение от GriV
Да, надо пересчитывать, как в случае промаха, так и в случае попадания.
В общем-то, здесь можно поступить аналогично тому, как это делается в шахматных программах. Иметь базу данных нескольких первых ходов ("дебютов"). А ближе к концу игры, когда кораблей мало, перебор всех комбинаций можно будет осуществлять за приемлемое время.
Ну и еще один метод есть для составления базы данных первых ходов и для расчетов в промежуточных ситуациях, который я собираюсь описать в следующих сообщениях. Это метод Монте-Карло. Он дает приближенный, не точный результат. А полный перебор всех 1E20 комбинаций - это задача неподъемная даже для современных компьютеров. Если представить себе, что в секунду мы рассматриваем миллиард размещений кораблей (1E9) - то для полного перебора потребуется 1E11 секунд - это около 3000 лет. Даже взлом 56-битного шифра DES является более легкой задачей (там меньше комбинаций).
Ответить с цитированием
