Есть игра — пять в ряд. Смысл у неё такой же как у крестиков ноликов, только нужно собрать линию не из 3, а 5 крестиков или ноликов.
А вообще это не пять в ряд, а японское Гомоку. В нашем варианте играется на неограниченном листе. В гомоку ограничена полем 15X15
Без особого успеха занимаюсь этой игрой уже несколько лет.
Век живи, век учись — дураком помрёшь! Пару лет назад наконец наткнулся на совершенно замечательный труд
"Go-Moku and Threat-Space Search" некого Louis Victor Allis
И ещё более фундаментальный труд "Searching for Solutions in Games and Arti cial Intelligence"
В общем человек не только нашёл совершенно замечательный способ решения, но ещё и доказал, что крестики (те кто начинают) всегда выигрывают.
Доказал он это для поля 15X15. Сделал он это в 92 году.
Тоже самое пытаюсь сейчас сделать я, только для неограниченного поля.
По идее это должно быть легче, потому как:
In the early days the game was played on a
19×19 board, since Go boards have that size.
This variant is still occasionally played. However,
the larger board size increases Black’s
advantage (Sakata and Ikawa, 1981).
Но, видимо я не такой умный, как мистер Алис. И даже с современными ресурсами у меня это не выходит.
The calculations were performed in parallel, on 10
SUN SPARCstations 2 of the Vrije Universiteit in
Amsterdam. Each of the machines was equipped
with 64 or 128 Mbytes of internal memory and a
swap space of over 200 Mbytes. Our processes
could only run overnight. As a result, some
processes not finished at 8 a.m. were killed, and had
to be restarted at 6 p.m. Still, over 1000 CPU-hours
a week were available for solving Go-Moku.
First, the non-restricted variant of Go-Moku was
examined, in which an overline is a winning pattern
Доу!
Сейчас у меня считается позиция с 7 хода. Состояние дел можно посмотреть здесь
Даже с ограниченными вариантами ответа для победителя это уже 1600000 вариантов.
Только с этого хода решения стали сворачиваться. След. уровень увеличется всего в 2.5 раза.
На Амазоне 16 процессов обошлись мне в 12$ (2 сервака по 8 ядер)
Учитывая, что просто для перехода на след. уровень потребуется мощность на 2 порядка больше, то для хобби это очень круто.
Нужно найти более дешёвый источник вычислительных ресурсов.
Поэтому вопрос. Может ли кто предоставить бесхозные вычислительные ресурсы на своих рабочих компах? Ночью к примеру?
Прежде чем сказать нет, и разразится язвенным постом, посмотрите снова в эти выразительные глаза.
У меня есть около 300 WMZ. Чтобы как-то стимулировать процесс, готов их планомерно на это дело потратить.
Это виндовая прога, которая получает задание, решает его (около минуты) и отсылает обратно.
Количество процессов можно задавать.
Сейчас, пока 7 уровень решается, пройдёт дней 10-20. Есть время подумать и определится.
Так что если вы готовы принять участие из любви к искусству — пишите. Мне нужно набрать хотя бы 60 процессов дней на 10.
Предупреждение. Есть большая вероятность вообще не получить никакого результата из-за таких причин:
— у меня может быть банальная ошибка
— у меня может быть логическая ошибка
— может быть логическая ошибка в оценке того, что противник не может повлиять на победу. Поэтому можно получить результат, который на самом
деле ничего не доказывает
— из-за ограничения "победителя" в ходах, можно вообще получить недостоверный результат.
— задача не свернётся при имеющихся ресурсах
ЗЫ. Пожалуйста, если вы только сами не угробили пару лет на похожую задачу, не надо давать советы.
Причины для этого такие:
— Вы не в теме. И потребуется много времени, чтобы вам это объяснить.
— Я вас просто не пойму. Даже имея две великолепные работы, я могу понять только 40% идей, которые изложены там.
Думаете у вас получится лучше?
— Идея может оказаться неэффективной. Ни в одном проекте по работе я не применял столько идей и не испытывал столько разочарования,
когда они оказывались абсолютно неэффективными.
— Для проверки идеи требуется время. А мне бы уже хотелось получить результат.
ЗЗЫ. Почему на этом форуме.
Кроме желания найти вычислительные ресурсы, есть ещё опасение, что результаты будут неадекватными.
Не сложно вмешаться в процесс получения задания и вернуть какую-то фигню. В результате всё дерево решений пойдёт лесом.
На тематическом форуме меньше шанс, что люди будут страдать такой фигнёй.
Кроме того как-то минимально надо процесс координировать и лучше держать связь с ограниченным количеством людей.
ЗЗЗЫ. Я думаю что "всем пофиг" что я там делаю. Но если вдруг интересно,
при положительном результате, обещаю написать статью в RSDN.
Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ>Пожалуйста внимательно прочтите это сообщение
Есть два соображения.
1. Портируй на Linux. Бесхозными Linux ресурсами поделятся гораздо охотнее, чем бесхозными Win ресурсами. По двум причинам. Во-первых, в opensource культуре принято делиться; а во-вторых, и это главное, ресурсы эти в основном казенные. Вон, к примеру, Шеридан на казенных серверах IRC сервер для RSDN замутил. У каждого пятого тут, я уверен, найдется простаивающая VPS-ка. (У меня например найдется). Тот же Амазон дает микро-инстанс (с Linux) на год бесплатно (для новых пользователей).
2. Есть пара русских клонов Кикстартера, сейчас названия не вспомню, но если надо, найду.
On 08/12/2012 01:33 AM, Шебеко Евгений wrote: > У меня есть около 300 WMZ. Чтобы как-то стимулировать процесс, готов их > планомерно на это дело потратить. > Это виндовая прога, которая получает задание, решает его (около минуты) и > отсылает обратно. > Количество процессов можно задавать.
Я бы мог предоставить ресурсы, ночью и не жалко, но вот проблема со
словом "виндовая". Ну можно конечно wine поставить. Но влом на сервере.
MZ>Я бы мог предоставить ресурсы, ночью и не жалко, но вот проблема со MZ>словом "виндовая". Ну можно конечно wine поставить. Но влом на сервере.
Не надо ничего ставить.
Я собирал под FreeBSD. Надо будет — соберу под линукс.
Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ>В общем человек не только нашёл совершенно замечательный способ решения, но ещё и доказал, что крестики (те кто начинают) всегда выигрывают. ШЕ>Доказал он это для поля 15X15. Сделал он это в 92 году.
Вообще-то, для простого гомоку это очень просто доказывается, что крестики выигрывают. Потому что у них преимущество в один ход
Чтобы скомпенсировать это, для крестиков вводятся ограничения, и такая игра уже называется рэндзю. Весьма заковыристая, в отличие от гомоку. http://www.gambler.ru/%D0%A0%D1%8D%D0%BD%D0%B4%D0%B7%D1%8E
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ>>В общем человек не только нашёл совершенно замечательный способ решения, но ещё и доказал, что крестики (те кто начинают) всегда выигрывают. ШЕ>>Доказал он это для поля 15X15. Сделал он это в 92 году.
К>Вообще-то, для простого гомоку это очень просто доказывается, что крестики выигрывают. Потому что у них преимущество в один ход
Очевидно, что не могут выиграть нолики. А так может быть еще ничья...
Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ>ЗЫ. Пожалуйста, если вы только сами не угробили пару лет на похожую задачу, не надо давать советы. ШЕ>Причины для этого такие: ШЕ>- Вы не в теме. И потребуется много времени, чтобы вам это объяснить. ШЕ>- Я вас просто не пойму. Даже имея две великолепные работы, я могу понять только 40% идей, которые изложены там. ШЕ> Думаете у вас получится лучше? ШЕ>- Идея может оказаться неэффективной. Ни в одном проекте по работе я не применял столько идей и не испытывал столько разочарования, ШЕ> когда они оказывались абсолютно неэффективными. ШЕ>- Для проверки идеи требуется время. А мне бы уже хотелось получить результат.
Ну я немного копал в сторону шахматного программирования... А так, просто интересно, какие эвристики используются? Ну типа ходов-киллеров, ...
M>Ну я немного копал в сторону шахматного программирования... А так, просто интересно, какие эвристики используются? Ну типа ходов-киллеров, ...
Treat-space search
В отличии от шахмат, здесь есть позиции, на которые надо обязательно реагировать.
Собственно этот Allis заметил, что люди ищут сначала последовательность вилок, которые приводят к победе,
практически не обращая внимания на ходы противника. Если такая последовательность найдена, то начинают её уже проверять.
Ключевая особенность в том, что для построения последовательности на угрозу отвечают сразу всеми защитными ходами одновременно. Если последовательность всё ещё можно построить, то уже потом угроза анализируется на контратаки.
У него ещё есть эвристика нулевого хода. Она у него даётся как: если игрок пропускает свой ход, то противник может построить выигрышную
последовательность вилок. Сказано, что типа эта позволяет видеть скрытые угрозы. Если честно, я не допёр как этим пользоваться, поэтому не использую.
Как бы непонятно, ну увидим мы угрозу на ход раньше. Совсем неочевидно, какими ходами её предотвратить. Это может быть ход на то место, откуда угроза разивается или к примеру боковые ходы, которые могут способствовать развитию контратаки.
Блин. Всё равно ничего не понятно получается. В общем сложно объяснить. Для того чтобы было понятно, нужно писать статью и подбирать картинки с примерами.
Здравствуйте, Шебеко Евгений, Вы писали:
M>>Ну я немного копал в сторону шахматного программирования... А так, просто интересно, какие эвристики используются? Ну типа ходов-киллеров, ... ШЕ>Treat-space search
ШЕ>В отличии от шахмат, здесь есть позиции, на которые надо обязательно реагировать.
В шахматах это техница ФВ (форсированного варианта). Начиная с некоторой глубины дальше считаются только шахи и взятия.
ШЕ>Собственно этот Allis заметил, что люди ищут сначала последовательность вилок, которые приводят к победе, ШЕ>практически не обращая внимания на ходы противника. Если такая последовательность найдена, то начинают её уже проверять. ШЕ>Ключевая особенность в том, что для построения последовательности на угрозу отвечают сразу всеми защитными ходами одновременно. Если последовательность всё ещё можно построить, то уже потом угроза анализируется на контратаки.
По сути это и есть NULL-move
ШЕ>У него ещё есть эвристика нулевого хода. Она у него даётся как: если игрок пропускает свой ход, то противник может построить выигрышную ШЕ>последовательность вилок. Сказано, что типа эта позволяет видеть скрытые угрозы. Если честно, я не допёр как этим пользоваться, поэтому не использую. ШЕ>Как бы непонятно, ну увидим мы угрозу на ход раньше. Совсем неочевидно, какими ходами её предотвратить. Это может быть ход на то место, откуда угроза разивается или к примеру боковые ходы, которые могут способствовать развитию контратаки.
Наверное пользоваться так: (1) поскольку мы ищем победу крестиков, то эвристику NULL-move имеет смысл выполнять для ноликов; (2) Нолики пропускают ход, и мы ищем атаку со стороны крестиков; (3) В случае, когда есть форсированный вариант, приводящий крестиков к победе, то можно эту последовательность рассматривать как киллер (т. е. при переборе всех возможных ходов ноликов, опровержение начинать с этого варианта). Вообще, alpha-beta очень чувствительна к порядку перебора вариантов.
ШЕ>Блин. Всё равно ничего не понятно получается. В общем сложно объяснить. Для того чтобы было понятно, нужно писать статью и подбирать картинки с примерами.
Все понятно, не переживай
Еще (A) идея Z-orbice. Многие позиции будут повторятся (+симметрии). Хотелось бы построить по позициям какой-нить хэш, чтобы это можно было быстро детектировать. Самая простая идея, построить таблицу, где каждой клетке поля соответствует некоторое число для крестиков (для ноликов соответсвенно). Потом мы делаем две суммы и mod на некоторое простое число. Что позволит быстро находить одинаковые позиции. Конечно, это не покрывает симметрии, но... Еще (B) имеет смысл расспросить данов по поводу теории дебютов, и взять ее за основу. Фактически, в свое время я читал, что в рендзю (запрещены вилки 3x3 и 4x4 черным) с выбором дебюта белыми (после третьего хода белые выбирают, хотят ли они играть черными) результативность составляла 55% в пользу белых. Соотвественно, уже сейчас теории этой игры очень сильно развита. (C) Еще для позиций, для которых не установлен результат, можно прикрутить ОФ для того, чтобы управлять alpha-beta.
Далее, очень сомнительно выглядит цифра 1 600 000 позиций. На моем компе шахматный движок без ОФ легко дает 3 000 000 позиций в секунду на одном ядре. Возможно, можно оптимизировать генерацию ходов.
H>Блин, упал до 4-го места. Ладно возобновляю работу
Ну для поддержания спортивного духа, статистика с сортировкой по количеству.
С количеством терминальных решений и последним терминальным решением.
Хотя с 50 спотами амазона, конечно, сложно соревноваться.
К>Вообще-то, для простого гомоку это очень просто доказывается, что крестики выигрывают. Потому что у них преимущество в один ход
Напомнило нашего лектора по матану.
Написал он как-то формулу на доске.
— Очевидно, что то-то и то-то — говорит.
(смотрит на доску минут сорок)
— Да, действительно очевидно. Теперь рассмотрим ...
Перекуём баги на фичи!
