Scrabble Опции

[Reflex]

Давайте всем форумом напишем вот эту игру. Причем так, что бы в ней были режимы как одно пользовательской ( с ИИ ) так и много пользовательской игры, желательно еще и игру по локалке.
сделать все вместе согласны такой общий проект?

[Lapp]

Что касается ИИ, то мне кажется, что особых проблем нет. Если есть словарь, то нужно составить из имеющихся на руках букв всевозможные сочетания, затем приставлять их к буквам на доске и сверять со словарем, что получится. Алгоритм дубовый, и работать он будет долго, но это уже второй вопрос .

Reflex, первое и главное замечание: при совместной работе хорошо было бы иметь словесное описание как данных, так и алгоритмов. Интерфейс не является исключением. Если в лом делать отдельное описание (что я вполне понимаю), то по крайней мере все должно быть прокомментировано, и без этого никак! Хотя, я бы все же предпочел сначала обсудить..

Например, в том коде, что ты привела, в глаза бросается набор констант. Он зачем? Мне кажется, такие вещи, как ценность буквы, нужно иметь отдельно, в файлах ресурсов. Сами же буквы естественно заменить на номера, занеся их реальные значения (типа А, Б ..) в массив (который, кстати, может зависеть от выбранной кодировки). Если следовать такому плану, то игру можно сделать многоязычной: русская, английская, украинская, французская.. - смена языка производится заменой файлов. Тогда мумба-юмбафикация игры могла бы заключатся в простом добавлении файлов (словарь можно позаимствовать у Ильфа с Петровым ).

Затем, давайте договоримся о выборе стандарта языка. Я предлагаю Object Pascal, но можно и сразу на Дельфи. Суть в том, чтобы задействовать объекты - они, как известно, хороши при совместном осуществлении пректа. Чисто процедурный подход я бы не рекомендовал.. Но можно и его, если есть возражения против объектов.

[Michael_Rybak]

Если есть словарь, то нужно составить из имеющихся на руках букв всевозможные сочетания, затем приставлять их к буквам на доске и сверять со словарем, что получится. Алгоритм дубовый, и работать он будет долго, но это уже второй вопрос .

Алгоритм не дубовый, и он будет летать. Только лучше, наверное, сначала смотреть, куда будем ставить, а потом уже ставить.

На поле 15х15 всего 225 клеток. От каждой клетки пытаемся проложить слово вправо, и слово вниз.

Пусть словарь у нас отсортирован лексикографически, и пусть в нем n слов. У нас есть клетка на доске, и мы идем от нее вправо. Хотим получить список всех возможных слов (учитывая, хватит ли у нас фишек, чтоб достроить недостающие буквы).

Рекурсивный перебор такой:

Сначала считаем, что нам подходят все слова: [0; n). Смотрим на первую букву (т.е. на начальную клетку). Если там уже стоит фишка с буквой, скажем, К, то нас уже устраивает не [0; n), а [x; y), где x - первое слово на букву К, а y - первое слово на букву Л. Если же там - пусто, то пытаемся туда поставить одну из букв, имеющихся на руках (всего их 7?). И опять-таки, сужаем интервал соответственно. И теперь рекурсивно переходим ко второй букве. Опять, если там не пусто, сужаем интервал однозначно, если же пусто - перебираем и сужаем, и т.д.

Поскольку на каждом шаге, решения относительно всех предыдущих букв уже приняты, то каждый раз нам всегда нужно рассматривать только слова из текущего интервала (все остальные не подходят под уже построенное).

Используя префиксное дерево, мы будем сужать интервалы за O(1), и перебор будет работать неприлично быстро

Эту часть могу взять на себя.

Сообщение отредактировано: Michael_Rybak - 2.11.2006 16:55