Re: тетрис

From

Dmitry Azovtsev ()

To

Max Pervukhin

Date

2002-11-09T22:43:40Z

Area

RU.ALGORITHMS

From: "Dmitry Azovtsev" <nospam@azovtsev.com>

Hello, Max!

On Wed, 06 Nov 2002 22:54:55 +0300 you wrote:

 MP> Надо заставить программу играть в тетрис.

А зачем?

 MP> Думаю сделать это перебором всех возможных положений фигуры с
 MP> выборов такого хода, который бы давал максимум оценочной фунции.
 MP> Вопрос - как должна выглядеть такая фунция?

Мнэ... На самом деле если тебе нужно показать процесс игры, который приводит
к (более или менее) определенному  результату - я бы начал с этого
результата (т.е.
собранной кучи), потом разобрал бы эту кучу и прокрутил все в обратном
порядке.

А так - вот тут (http://www.arxiv.org/abs/cs.CC/0210020) есть здоровенное
исследование
тетриса. В частности, там они доказывают что оптимальное решение (в смысле
минимизации выстоы кучи при заданном входном наборе) NP-сложное. Где-то
что-то они там еще писали о неаппроксимируемости за полиномиальное время.

Если таки хочется функцию - то наверняка идей для таковой из статьи можно
наковырять массу.

Best regards,
Dmitry

--- ifmail v.2.15dev5
 * Origin: AT&T Broadband (2:5020/400)