Chat:Ru/2021-02-24

From CG community
Revision as of 11:35, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/29443769474274> MadKnight: а чё с ними было? <img src=/a/23956705948685> Uljahn: коннект не устанавливался, что-то в на...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

MadKnight: а чё с ними было?

Uljahn: коннект не устанавливался, что-то в настройках сервака сломали, потом починили, как обычно

MadKnight: ну бывает

Default avatar.png samrrr: А сколько можно мегабайт на дебютную книгу потратить?

Uljahn: 100k символов в тексте кода, ОЗУ дают 768Мб, за секунду первого хода можно попробовать предрассчитать что-то вычислительно сложное, чтобы потом использовать в качестве Look-Up Table

Uljahn: но обращение к LUT может негативно сказаться на кэшах проца

Uljahn: обычно дебютные книги тут сильно ужимают - конвертируют в utf-16, так по два байта на символ выходит, итого максимум 200кБ

Uljahn: можно основные дебюты захардкодить, если противник от них отступает в какой-то момент, то значит он неоптимально играет, и обычный поиск должен его порекать, т.е. из этих 100к символов надо ещё код самого бота вычитать

Uljahn: особо не развернёшься, да и в офлайне надо дебюты просчитывать

Uljahn: ну и если обычный поиск будет сливаться, то смысл дебютной книги теряется, т.к. самое интересное начинается на глубине, до которой книгам не достать, они только дают некоторое небольшое преимущество против сильных ботов

Default avatar.png samrrr: я пока пытаюсь минмакс сделать

Default avatar.png samrrr: пока толку от этого 0, даже рандомному выбору проигрывает...

Default avatar.png samrrr: всё что он может, так это точно понять, что 100% луз теперь

Uljahn: эффект горизонта во всей красе

Default avatar.png samrrr: https://www.codingame.com/replay/530599488 уже на 21 ходу минмакс сдался вот как так то

mykeich: samrrr ну минимакс не доходит до конца игры, так что весь вопрос в том какая оценка и как понять что эти ходы ведут к выигрышу. альфа бетта отсечение добавил?

Default avatar.png samrrr: какое ещё альфа бета?

Default avatar.png samrrr: я только заставил всегда выбирать ход 100% вина и всё

mykeich: для маленькой доски?

Default avatar.png samrrr: для большой

Default avatar.png samrrr: если ход ведёт к победе, то другие перестал рассматривать

mykeich: не понятно, допустим минимакс на 4 хода игры, до конца игры езе 30 ходов, по каким критериям понять какой вариант игры на 4 ходе самый выгодный?

Default avatar.png samrrr: я рассматриваю так, какбудто дерево полностью построено

mykeich: все равно не понятно

Default avatar.png samrrr: ну всегда минимум беру на слиянии 2 нод

Default avatar.png samrrr: и инсертирую результвт прошлого уровня

Default avatar.png samrrr: и инвертирую результвт прошлого уровня

mykeich: мы про MCTS или minimax?

Default avatar.png samrrr: min max

mykeich: Тогда ничего не понятно все равно

mykeich: в Minimax нет деревьев и нод обычно, а если есть то это что то другое

Default avatar.png samrrr: какэто нет?

Default avatar.png samrrr: что за фигню тогда я напилил?

Default avatar.png samrrr: http://chat.codingame.com/pastebin/88bdbaa9-35a8-4ccb-956f-bca74752991a

mykeich: Какой то вариант поиска по дереву имитирующий minimax. Просто в минимаксе нет нужны строить дерево, оно же там не нужно для работы

Default avatar.png samrrr: а что мне тогде делать с деревом?

mykeich: Добей алгоритм MCTS, тем более он в tic tac toe скорей всего предпочтителен.

Default avatar.png samrrr: его невозможно добить до mcts

Uljahn: mykeich: minimax строит полное дерево игры до заданной глубины, это полный перебор всех вариантов, в мктс тоже перебор вариантов, но не полный, некоторые ветки исследуются намного глубже, чем другие

mykeich: я придираюсь к слову строит. по завершению алгоритма нету никакого дерева на выходе

Uljahn: с этим согласен

Default avatar.png samrrr: как так то? как без дерева то?

Uljahn: в минике нужна оценка на конечной глубине и всё, а в мктс нужна статистика по нодам в дереве

mykeich: я на днях как раз хотел принципиально решить один пазл минимаксом

mykeich: https://www.codingame.com/share-replay/530593716

mykeich: но никак не могу придумать оценучную

Uljahn: можно посмотреть в сторону n-tuples, там оценка на основе паттернов

jacek: frontiers discs, mobility and stable discs

Default avatar.png samrrr: а счего всётаки минсаксу ненужно дерево?

mykeich: http://chat.codingame.com/pastebin/586a883d-2797-446d-810c-fb507e3144c7

mykeich: samrrr минимакс обходит дерево состояний игры, для него не требуется хранить все дерево

Default avatar.png samrrr: но так он не сиожет использовать всё время....

Default avatar.png samrrr: или неуспеет...

mykeich: jacek, спасиб, я догадался, но не пришел к выводу стоит ли делать сложный алгоритм расчета стабильных фишек. глубина тогда будет 4 хода. Сейчас у мина минимакс, оценка бонус за углы и число фишек. Примерно.

YurkovAS: можете подсказать: какими алгоритмами такое решается? есть большая карта, на ней есть клад: рандомное расположение и рандомное кол-во. можно исследовать как одну ячейку, так и диапазон и получить кол-во клада на этом участке. исследование большого диапазона стоит дороже.

mykeich: samrrr, все верно. у минимакса есть неприятная особенность что время его работы очень сильно плавает особенно с альфа бета отсечением. Если видишь что бот соперника часто падает, то 90% что у него минимакс

Default avatar.png samrrr: ну так построить дерево и норм будет...

YurkovAS: ну и цель выкопать побольше клада

mykeich: YurkovAS, ну ты спросил:) поиск А* подойдет?:)

Default avatar.png samrrr: YurkovAS подели всё поле на ячейки в N/2/кол_спотов и чекай, потом как с тигром

YurkovAS: а, забыл, времени на полный перебор не хватает, только на 1/20

YurkovAS: с тигром?

YurkovAS: и это жадные алгоритмы нужны? типа как с рюкзаком? или что-то нестандартное уже

mykeich: samrrr, нет смысла прикручивать дерево к минимаксу, падает число рассмотренных ходов, т.е. глубину надо уменьшать.

Default avatar.png samrrr: падает насколько?

mykeich: Настолько что MCTS выигрывает.

mykeich: samrrr и есть неприятность что если не все ходы рассмотрены, то его точность падает. не уверен конечно, но мое кроилово по изобретению велосипедов всегда проваливалось

Default avatar.png samrrr: а босса то завалить удастся?

mykeich: YurkovAS там чтоль надо делить карту на области постепенно уменьшая зону поиска? И надо уложиться в число ходов?

Default avatar.png samrrr: Вот тебе про льва

Default avatar.png samrrr: http://chat.codingame.com/pastebin/45b82ed9-4a20-4908-a193-d58d72a7c161

YurkovAS: mykeich там надо в конкретной ячейке выкапывать клад. и есть функционал, который говорит сколько клада в конкретной ячейке. или в диапазоне суммарно. перебором по каждой ячейке не успевает все выкопать, только 1\20 часть

Default avatar.png samrrr: Давай как тигра

YurkovAS: samrrr получается здесь надо делать примерно такое же, только тигров много

YurkovAS: спасибо!

YurkovAS: это задача из highloadcup-а

Default avatar.png samrrr: ну так возьми стартовую область меньше

Default avatar.png samrrr: фи куп бы

Default avatar.png samrrr: аи куп бы...

YurkovAS: да тоже самое, только без противников и веб апи

Default avatar.png samrrr: без противников неинтересно

YurkovAS: там призеры раика, за ними не угонишься

YurkovAS: это типа оптимизаций тут на КГ - тоже нет противника, но есть табличка

Default avatar.png samrrr: темболее ещё и конкурентов дофига

Default avatar.png samrrr: тут есть противники и битвы

YurkovAS: здесь на кг в прошлый раз участвовало 7к человек - вот где не угнаться...

Default avatar.png samrrr: зато тут батлы есть, а не простое напиливание кода чтоб работал побыстрее

Uljahn: тут всякое есть, и напиливание тоже

YurkovAS: Uljahn можешь глянуть задачку, что выше писал? может знаешь про алгоритмы, которые такое решают?

Uljahn: "исследование большого диапазона стоит дороже" - вот это поясни

Default avatar.png samrrr: есть только 1 алгоритм

Default avatar.png samrrr: берёшь и чекаешь области пока можешь, сужая диапазон

Uljahn: т.е. у нас есть бюджет на исследования, если по одной ячейке, то хватает на 1/20 карты, так?

YurkovAS: Uljahn чем больше диапазон запросил (например 100х100 клеток), тем дольше оно тебе отвечает. ну и в ответе будет суммарное кол-во золота в этих клектах

Uljahn: сколько будет стоит чекнуть 1/2 карты?

YurkovAS: у меня точной информации сейчас нет, но очень долго, может даже половину всего времени

Default avatar.png samrrr: чекать пол карты 0 толку

Uljahn: нет, толку 0.5

Uljahn: это не ноль :)

Default avatar.png samrrr: клад не один, поэтому толку 0.5^n а это 0

Uljahn: а сколько кладов? какая плотность распределения?

Default avatar.png samrrr: если кучкой то полосками чекай)

YurkovAS: эх, у меня нет этой статистики

Default avatar.png samrrr: тогда это не задача, а идиотизм

YurkovAS: понял, надо собрать статистику и дальше уже посчитать. и добавить исследований по зонам и потом копать в лучших

YurkovAS: думал может это какая-то стандартная задачка, типа аналог рюкзака или т.п... да почитал бы потом про этот класс алгоритмов

YurkovAS: а то я могу долго экспериментировать

YurkovAS: ну и да, смысл им давать стандартную задачку. придется подгонять под конкретные правила.

Uljahn: чем-то похожа на задачу о двух яйцах от гугла

Uljahn: только если плотность кладов каждый раз разная, то сложно очень

Default avatar.png samrrr: https://www.codingame.com/replay/530625688 такое впечатление что мой бот спецом сливает

Default avatar.png samrrr: https://www.codingame.com/replay/530626477 не ну точно, когда лузнуть шанса нет, он просто закрашился

YurkovAS: Uljahn спасибо

Uljahn: :thinking:

YurkovAS: до меня не дошло "идеальное решение задачи про яйца" :)

vrabosh: Приветы! Можете покахать плз, что находится в Tree Paths во Validator 2

TheCrucial: обычно примерно то же самое что в test 2 из приложенных по смыслу

vrabosh: все не надо, нашел ошику

Default avatar.png samrrr: https://www.codingame.com/replay/530666103 наконечто хоть разок завалил свой прошлый ход