Chat:Ru/2021-03-22

From CG community
Revision as of 11:36, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/25714480415254> tutubalin: не 3 миллиона, а меньше. и тогда может будет в питон их нормально впихнуть <i...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 ну вроде секунда на первый ход