CyberEcho: Вчера Puzzle of Week начался. Он только неделю будет идти? Или неограниченное время?
Uljahn: сам мультиплеер без ограничения, а статус PotW - только на неделю
Uljahn: этот статус - просто для привлечения внимания публики, ну и один раз можно ачивку получить, вроде бы
CyberEcho: Спасибо, тогда можно не спешить
YurkovAS: kurnevsky отличный результат в spring challenge 2021, поздравляю!
kurnevsky: Отличным он был бы, если бы вытеснил Рекурса, а так просто хороший :)
YurkovAS: ну это надо нейронку делать, да и тут точно не просто, т.к. у других опытных нейронщиков не получилось.
kurnevsky: Там просто пару побед случайных над Рекурсом было, что дало сильный буст в рейте :)
YurkovAS: какой алгоритм используешь, duct?
kurnevsky: Да.
YurkovAS: о, круто!
YurkovAS: у меня так и не получилось, ну точно неправильно значит дерево сделал.
YurkovAS: странно, что мктс тут тоже хорошо играет
kurnevsky: Ну, я с обычным минимаксом был на 10 месте :)
YurkovAS: на днях тут у Uljahn-а спрашивал про дерево, ты случайно не видел это сообщение? может у тебя так же дерево сделано?
kurnevsky: Не видел.
kurnevsky: Я, кстати, не сравнивал с обычным uct.
kurnevsky: Может, если я выпилю duct, все только лучше станет :)
YurkovAS: ну вот у меня обычный мктс, а играет тоже хорошо
YurkovAS: т.е. в дереве сначала хожу за себя, потом будут ходы противника, дальше опять мои и т.п.
как в минимаксе
Uljahn: в этом случае противник обладает инфой о твоём ходе?
YurkovAS: да, родительская нода для ходов противника - мой ход
YurkovAS: ну тут из-за wait-а кто-то может в одного играть
а так все по классике
YurkovAS: а вот как он в duct-е дерево сделал, мне очень интересно.
самому проверять лень, конечно
kurnevsky: Ровно как в вайтпейпере описано :)
YurkovAS: да там же 2 предложения
kurnevsky: Вместо списка ходов 2 списка, и квадрат детей.
kurnevsky: Ну, вернее, n*m.
YurkovAS: ох, сложно для меня, не могу представить дальше 1-го хода
YurkovAS: думаю проверить такую идею:
- 2 независимых дерева для каждого игрока, со всей статистикой, как в smitsimax-е.
- дерево для: состояний, 2 родительские ноды из верхнего дерева, и список допустимых ходов. статистику они будут обновлять каждый в своем обобщенном дереве.
kurnevsky: Так все то же самое, что в обычном mcts, только дерево становится короче и шире - вместо одного хода нода содержит сразу 2 хода.
kurnevsky: И статистика собирается уже не в нодах, а по ходам в отдельном списке.
YurkovAS: у каждого свой индивидуальный список?
YurkovAS: ну дерево
kurnevsky: Нет, дерево одно.
kurnevsky: Просто каждый узел содержит список ходов каждого игрока размерами n и m, и n*m детей.
Uljahn: а что за список со статистикой? в пейпере написано, что ходы выбираются независимо по UCB
YurkovAS: и получается, статистика противника (2-го игрока) содержит больше данных, в отличии от мктс-а
т.к. там каждый ход противника зависит от предыдущего хода нашего
Uljahn: YurkovAS: не зависит же
YurkovAS: да да, у него не зависит
YurkovAS: а в мктс-е зависит
kurnevsky: Список со статистикой per ход.
kurnevsky: Она не собирается для матрицы, а для каждого хода.
YurkovAS: в случае смитсимаксового дерева, статистика будет еще более обобщенной и полной.
т.к. у каждого только его всевозможные ходы
kurnevsky: Так и тут у каждого только его ходы.
YurkovAS: ну может я не так вас понял.
вроде делал как ты описал, а играло заметно хуже: 35% вин vs 65% вин мктс-а
kurnevsky: Я тоже вот сделал tree reuse, и получил винрейт в 30% :)
kurnevsky: Вероятно, где-то баг :)
YurkovAS: да, у меня тоже это есть
YurkovAS: и на первом ходу подольше надо посчитать, там 1сек
kurnevsky: Ну вот моя текущая версия на каждый ход новое дерево создает.
kurnevsky: На каждый запрос хода.
kurnevsky: И я пока не осознал, как между днями переиспользовать дерево - там противник может много ходов сделать, и все их найти не просто.
YurkovAS: у меня реюз дерева дает заметное улучшение, не помню точно какое
YurkovAS: ну да, когда он сделает на 2+ хода больше тебя, то уже теряется. опять же зависит от твоего прунинга
YurkovAS: я специально сделал для противника побольше допустимых ходов и это дало улучшение
kurnevsky: Ну, проблема не в прунинге, а в том, как найти правильную последовательность ходов :)
kurnevsky: Потому как есть только состояние.
YurkovAS: свой ход ты знаешь, потом проверяешь все допустимые ходы противника.
если у тебя был wait, тогда добавляешь обход в глубь и всегда сверяешь состояние
YurkovAS: тут проблемы нет, на самом деле. просто дерево сильно грубоко не успевает построиться
YurkovAS: или из-за прунинга теряется
YurkovAS: еще мне тут понравилось поускорять бота: битовые маски, определение теней по битовым маскам и сдвигам.
ну и стало только лучше.
YurkovAS: *немного лучше
оценочная, прунинги и прочее давало большее улучшение
miklla: если кто задумает серьёзно оценивать позиции в клоббере одним числом, то обязательно скачайте программу http://www.cgsuite.org/
miklla: там вводишь позицию клоббера, а она выдаёт её атомный вес, в 90% случаев это вещественное число
miklla: так что даже понимать теорию партизанских игр не обязательно
miklla: но если обучать программу в промышленных масштабах, то, конечно, самому надо писать вычисление атомного веса произвольной позиции
YurkovAS: надо достать эту формулу и проверить вместо рандома
YurkovAS: или как бонус использовать, чтобы такие ходы чаще выбирались
miklla: если что, сложность точного вычисления атомного веса примерно 4 * размер полного дерева, где под полным деревом я имею ввиду, когда в каждой позиции допустимы все ходы одного игрока и все ходы другого
miklla: это почти квадрат размера обычного игрового дерева
miklla: но зато можно ограничиться одной компонентой связности, когда 2 компоненты связности, их атомные веса просто складываются
miklla: + если определённые сложности, когда атомный вес не вещественное число
miklla: есть*
YurkovAS: :thinking:
miklla: а, забыл сказать, почему он так крут
miklla: если атомный вес >= 1, то если ход левого игрока, то он гарантированно выигрывает, а если атомный вес >= 2, то левый игрок выигрывает независимо от того, чей первый ход, для правого игрока симметрично с -1 и -2
miklla: при этом у большинства позиций атомный вес не просто вещественное число, а целое
YurkovAS: ну бомба!
YurkovAS: атомная бомба :)
vovka42rus: салам
mrcrast: привет
igoryan4ik: уазабчик
vovka42rus: копчик это кто?
igoryan4ik: серега копчик
igoryan4ik: не знаешь такого
vovka42rus: копчик кто этг?
igoryan4ik: тебе не надо знать это
igoryan4ik: парень
vovka42rus: копчик - это маленький амеиканский полицейский
Davlat_Vagapov: qq
vovka42rus: :man_tone5:
igoryan4ik: Вовка 42 Рус ты что несешь
igoryan4ik: какой полицейский
vovka42rus: копчик
vovka42rus: маленький
vovka42rus: copчик
igoryan4ik: dol***b
vovka42rus: copchik
vovka42rus: чик уменшительно ласкательное
vovka42rus: игорянчик
igoryan4ik: хуепчик
igoryan4ik: о нет маты
igoryan4ik: а
igoryan4ik: а
Davlat_Vagapov: :nose_tone4:
mrcrast: милицейский
vovka42rus: мент
vovka42rus: мусор
vovka42rus: салам
