|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kovalev 2:5020/400 03 Apr 2002 09:06:25
To : Vladimir Veretnov
Subject : Re: Оптимизация алгоритма игры "Быки и коровы"
--------------------------------------------------------------------------------
"Vladimir Veretnov" <VovaVV@cash.eburg.uniland.ru> wrote in message
news:a8c0ju$6fd$1@ddt.demos.su...
> Hi, All !
>
> Hаписал программу, которая отгадывает любую комбинацию из 4х чисел не
более,
> чем за 7 ходов.
> Алгоритм - простой перебор возможных вариантов, который здесь неоднократно
> обсуждался.
Извиняюсь, если посоветую уже обсужденные идеи,
т.к. пропустил начало темы.
В детстве я тоже писал такую программку и хорошо помню,
что вполне приличный результат давала минимаксная стратегия.
А именно:
Компутер перебирает все числа, допустимые к данному шагу игры.
Для каждого числа компутер
а) перебирает все возможные ответы игрока при гипотетическом
предъявлении компутером этого числа и определяет,
насколько сокращается множество допустимых числ при каждом ответе.
б)находит самый неудачный ответ для данного числа, т.е. ответ,
который в минимальной степени сокращает множество допустимых чисел.
Теперь среди всех самых неудачных ответов (по множеству
допустимых к данному моменту чисел)
ищется наименее неудачный. Соответсвующее число и предъявляется игроку.
Таким образом, на каждом шаге компутер стремится максимизировать сокращение
множества оставшихся чисел в расчете на самый неудачный
для компутера ответ игрока. Если реальный ответ не самый
неудачный, то, естественно, множество допустимых чисел
сокращается еще быстрее, чем расчитывал компутер.
SK
--- ifmail v.2.15dev5
* Origin: HOME (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
