tutubalin: не 3 миллиона, а меньше. и тогда может будет в питон их нормально впихнуть
wlesavo: ну тебе все-равно нужен проход по трем миллионам
tutubalin: а, ну да...
tutubalin: хотя можно отсечение сделать
tutubalin: нашёл, как ускорить примерно на 50-100%.
теперь почти всегда меньше 320 даёт.
MadKnight: и как?)
tutubalin: да у меня раньше при каждой проверке кандидата строилось новое дерево.
убрал это, теперь только в конце строится уже для лучшего кандидата
tutubalin: появились идейки, как ещё соптимизировать чуток, но там уже вряд ли большой выхлоп будет
tutubalin: раньше на втором ходу для N=10 успевало перебрать 5 кандидатов. теперь 10.
MadKnight: что значит перебрать?
MadKnight: как именно?
tutubalin: есть список доступных комбинаций
tutubalin: если он небольшой, то можно проверить все из них
tutubalin: берёшь первую, сравниваешь со всеми остальными. считаешь, сколько инфы она даст. берёшь вторую и то же самое
tutubalin: трудоёмность O(N^2)
tutubalin: если список большой (например, миллион комбинаций), то все комбинации оценить не получится, поэтому просто выбираю несколько рандомных кандидатов и их оцениваю
tutubalin: вот раньше если список был из миллиона, успевал оценить 6 кандидатов (то есть 6 миллионов сравнений). теперь успеваю 12.
MadKnight: а как считаешь сколько инфы даст?
tutubalin: я же уже рассказывал. по формуле Шеннона
tutubalin: если лень с ней разбираться (хотя она простая и логичная), то можно использовать такой критерий: самая большая подгруппа должна быть как можно меньше
magaiti: как считается, кто выиграл в уттт, если поровну досок выиграно?
magaiti: у кого больше крестиков/ноликов на оставшихся досках, или у кого больше досок, на которых больше крестиков/ноликов?
magaiti: хотя одно и то же по идее
735487: у кого больше выигранных досок вроде
735487: а если поровну то ничья
Uljahn: если поровну, то ничья
magaiti: хз, а цг умеет ничью считать?
735487: умеет
magaiti: хмм ладно
735487: там за нолики ничья более выгодная с точки зрения рейтинга
wlesavo: tutubalin у меня на втором ходу два кандидата :smiley:
wlesavo: а считаю не по формуле а просто да чтобы самая большая подгруппа была как можно меньше
tutubalin: wlesavo я не проверял, но по идее из одного должно следовать другое, то есть равносильные критерии должны быть
miklla: вряд ли они равносильны
miklla: а у меня первые ходы я рандомом минимизирую макс группу, а ближе к концу делаю полный перебор внутренних ходов и выбираю наилучшее матожидание
miklla: у меня есть примеры, когда наилучшее матожидание != минимальная макс группа
miklla: ещё у меня есть пример, когда наилучший по матожиданию ход - внешний, но я хз как такое наперебирать
wlesavo: у внешнего хода есть недостаток в том что он не может случайно оказаться таргетом
miklla: да, я знаю, но когда вариантов много, внутренний так редко оказывается секретом, что это не важно
miklla: с тем же успехом можно говорить "а зачем вообще придумывать какой-то алгоритм, если можно случайно угадать на втором ходу"
wlesavo: ну да, но ближе к концу это релевантно
miklla: если осталось не больше трёх вариантов, то внешний ход никогда не наилучший
tutubalin: miklla а пример с внешним числом большой?
miklla: нет, маленький
miklla: http://chat.codingame.com/pastebin/bfe413a0-e0be-4671-99ee-4ba03e2322cb
miklla: тогда любой внутренний ход не даёт инфы, кроме попал/не попал, таким образом матожидание 2.5
miklla: однако ход 1243 с вероятностью 50% даёт гарантированное попадание на следующем ходу, а с вероятностью 50% оставляет 2 равнозначные опции, которые угадываются за 2.5 в среднем, итого матожидание через внешний 2.25
tutubalin: а такой набор вообще может остаться в реальной игре?
miklla: да
miklla: у меня встречался подобный
miklla: ну как кусок 9-ти значного числа, но нефиксированные места были такой структуры
tutubalin: вот же ж блин!
miklla: ух, долго не мог найти хороший фундамент теории комбинаторных игр в открытом доступе, а вот и он https://www.math.kth.se/matstat/gru/sf2972/2015/gametheory.pdf
miklla: (всё ещё готовлюсь к клобберу) :)
MadKnight: A game is an ordered pairG={GL|GR}
MadKnight: are the sets ofleftandright optionsofG
MadKnight: чё за let and right options ?
MadKnight: miklla
MadKnight: LetPbe any property that a game can have. If a game isPwheneverany option isP, then all games areP.
MadKnight: чё за game property и game option ?
MadKnight: left/right это типа речь об играх где только 2 возможных хода?
MadKnight: The simplest of all games is{|}which we callthe zero gameand denote by 0
MadKnight: тут ничего не понял, о чём вообще речь?
miklla: в игру (например шахматы) пусть играют 2 игрока, левый и правый
miklla: {G_L | G_R}, в нём G_L - множество позиций, в которые может попасть левый игрок из позиции G, если его ход
miklla: G_R - множество позиций, в которые может попасть правый игрок из позиции G, если его ход
MadKnight: ааа
MadKnight: а чё за simplest game ?
miklla: хоть и для решения игры обычно есть лишь стартовая позиция, где ход определённого гирока
miklla: тут оказывается полезно заодно рассмотреть что будет, если бы прям из стартовой позиции был ход другого игрока
miklla: это кажется бесоплезным
miklla: но
miklla: это очень полезно, когда игра разбивается на компоненты связности, как в клоббере
miklla: я бы рекомендовал сначала читать не теорию, а статью, которую скидывал ранее https://project.dke.maastrichtuniversity.nl/games/files/msc/Claessen_thesis.pdf
Uljahn: а, это null-move heuristic вроде
miklla: если ты про то, что никогда не надо делать ход в подыгре значения ноль, то это не эвристика, а оптимальная стратегия
miklla: или что ты имел ввиду?
MadKnight: miklla а что именно вообще дают эти 2 статьи?
MadKnight: для практики
miklla: по ним можно сделать бота, который будет оптимально играть в случае, когда позиция в клоббере маленькая или разбита на несколько маленьких не перебирая вообще все ходы, а сложив "значения" компонент в некотором смысле
MadKnight: чё за компоненты?
MadKnight: и чё за значения?
miklla: ну например если позиция разбилась на 2 компоненты по 10 команей
miklla: камней*
MadKnight: погоди, мне надо изучить вообще эту игру
miklla: обычно тебе бы пришлось её перебирать, как целую
MadKnight: а то я не знаю о чём она
MadKnight: есть линк?
miklla: https://www.codingame.com/ide/puzzle/clobber
MadKnight: а
MadKnight: > ну например если позиция разбилась на 2 компоненты по 10 команей
всмысле что 10 камней никак не могут повлиять на другие 10 камней?
miklla: да, такое часто случается
MadKnight: ну так это и так было бы понятно
miklla: и что ты собирался делать в таком случае?
MadKnight: а как эти твои линки помогают с этим?
MadKnight: ну так ходить из той компоненты, которой ход нужен больше всего
miklla: если окажется, что позиции вычислимы или сравнимы с нулём, то можно найти оптимальный ход, перебирая их по-отдельности, а не вместе
MadKnight: ну так это понятно
miklla: и как ты собрался определить, в какой ход нужнее всего, и что это за ход вообще?
MadKnight: а тут надо отталкиваться от условий победы
miklla: проигрывает, кто не может сделать ход
MadKnight: если каким-то образом можно победить чисто одной компонентой - то забиваем на менее потенциальные
MadKnight: если же всеми - то ходим той, где хуже всего дела
miklla: а если 2 компоненты, в каждой из которых выигрывает тот, кто делает первый ход?
MadKnight: а стоп
MadKnight: я только что это понял
MadKnight: число ходов у игроков одинаковое
MadKnight: была похожая мульти
MadKnight: там что-то похожее с ходами было
MadKnight: там типа массив вертикальных линий, и на каждой стоит твой юнит и юнит противника
MadKnight: ты двигаешь одного юнита за ход вверх
MadKnight: а противник - вниз
MadKnight: через друг друга проходить не можете
MadKnight: и проигрывает тот, у кого ходов не будет первым
MadKnight: помнишь такую?
miklla: корридор?
miklla: который тут называется по-другому
miklla: мельница на рисунке
miklla: тут он называется the great escape
MadKnight: нене
MadKnight: где у тебя на каждом Х по фишке
miklla: не знаю такой
Uljahn: miklla: показалось, что похоже на https://en.wikipedia.org/wiki/Null-move_heuristic
MadKnight: https://www.codingame.com/ide/puzzle/find-the-winning-strategy
MadKnight: нашёл
MadKnight: miklla
miklla: прикольная эвристика, не знал о ней, да, напоминает
miklla: только там эвристика, а тут точная теория
tutubalin: MadKnight это по сути игра Ним. представь что вместо солдатиков и клеток между ними - просто кучки камней. и ты выбираешь, из какой кучки сколько забрать
tutubalin: и да, слово Нимбер, используемое в статье про клоббер, происходит как раз от названия игры Ним
MadKnight: tutubalin ну так о том и речь
miklla: да, линк MadKnight как раз на задачу про суммирование игр, для её решения надо применять теория Шпрага-Гранди, которая является подтеория комбинаторных игр
MadKnight: просто там кучки ещё друг на друга влияют
tutubalin: вот и в клоббере тоже влияют.
MadKnight: нене
MadKnight: я про клоббер и говорил
tutubalin: в солдатиках у меня решение на JS 19х8 символов :)
tutubalin: не совсем правильный квадрат, но симпатично
MadKnight: пробовал перебор для поиска что даёт больше всего информации с глубиной?)
MadKnight: типа 2 подряд
MadKnight: кто тут играл в одну из этих игр?
Fireworks, Clobber, Connect4, 2048
MadKnight: ну с clobber в основном уже знаю
tutubalin: Connect4, говорят, полностью решена
Uljahn: есть классный вариант Connect4, там два цвета и две формы фишек, надо по цвету или по форме соединять
Uljahn: по этим правилам даже чемпионаты AI проводят, вроде
MadKnight: Uljahn а мульти на CG по этой версии будет?)
tutubalin: кстати, а есть какое-то ограничение на время компиляции?
MadKnight: tutubalin ну вроде секунда на первый ход
