MadKnight: а чё с ними было?
Uljahn: коннект не устанавливался, что-то в настройках сервака сломали, потом починили, как обычно
MadKnight: ну бывает
samrrr: А сколько можно мегабайт на дебютную книгу потратить?
Uljahn: 100k символов в тексте кода, ОЗУ дают 768Мб, за секунду первого хода можно попробовать предрассчитать что-то вычислительно сложное, чтобы потом использовать в качестве Look-Up Table
Uljahn: но обращение к LUT может негативно сказаться на кэшах проца
Uljahn: обычно дебютные книги тут сильно ужимают - конвертируют в utf-16, так по два байта на символ выходит, итого максимум 200кБ
Uljahn: можно основные дебюты захардкодить, если противник от них отступает в какой-то момент, то значит он неоптимально играет, и обычный поиск должен его порекать, т.е. из этих 100к символов надо ещё код самого бота вычитать
Uljahn: особо не развернёшься, да и в офлайне надо дебюты просчитывать
Uljahn: ну и если обычный поиск будет сливаться, то смысл дебютной книги теряется, т.к. самое интересное начинается на глубине, до которой книгам не достать, они только дают некоторое небольшое преимущество против сильных ботов
samrrr: я пока пытаюсь минмакс сделать
samrrr: пока толку от этого 0, даже рандомному выбору проигрывает...
samrrr: всё что он может, так это точно понять, что 100% луз теперь
Uljahn: эффект горизонта во всей красе
samrrr: https://www.codingame.com/replay/530599488 уже на 21 ходу минмакс сдался вот как так то
mykeich: samrrr ну минимакс не доходит до конца игры, так что весь вопрос в том какая оценка и как понять что эти ходы ведут к выигрышу. альфа бетта отсечение добавил?
samrrr: какое ещё альфа бета?
samrrr: я только заставил всегда выбирать ход 100% вина и всё
mykeich: для маленькой доски?
samrrr: для большой
samrrr: если ход ведёт к победе, то другие перестал рассматривать
mykeich: не понятно, допустим минимакс на 4 хода игры, до конца игры езе 30 ходов, по каким критериям понять какой вариант игры на 4 ходе самый выгодный?
samrrr: я рассматриваю так, какбудто дерево полностью построено
mykeich: все равно не понятно
samrrr: ну всегда минимум беру на слиянии 2 нод
samrrr: и инсертирую результвт прошлого уровня
samrrr: и инвертирую результвт прошлого уровня
mykeich: мы про MCTS или minimax?
samrrr: min max
mykeich: Тогда ничего не понятно все равно
mykeich: в Minimax нет деревьев и нод обычно, а если есть то это что то другое
samrrr: какэто нет?
samrrr: что за фигню тогда я напилил?
samrrr: http://chat.codingame.com/pastebin/88bdbaa9-35a8-4ccb-956f-bca74752991a
mykeich: Какой то вариант поиска по дереву имитирующий minimax. Просто в минимаксе нет нужны строить дерево, оно же там не нужно для работы
samrrr: а что мне тогде делать с деревом?
mykeich: Добей алгоритм MCTS, тем более он в tic tac toe скорей всего предпочтителен.
samrrr: его невозможно добить до mcts
Uljahn: mykeich: minimax строит полное дерево игры до заданной глубины, это полный перебор всех вариантов, в мктс тоже перебор вариантов, но не полный, некоторые ветки исследуются намного глубже, чем другие
mykeich: я придираюсь к слову строит. по завершению алгоритма нету никакого дерева на выходе
Uljahn: с этим согласен
samrrr: как так то? как без дерева то?
Uljahn: в минике нужна оценка на конечной глубине и всё, а в мктс нужна статистика по нодам в дереве
mykeich: я на днях как раз хотел принципиально решить один пазл минимаксом
mykeich: https://www.codingame.com/share-replay/530593716
mykeich: но никак не могу придумать оценучную
Uljahn: можно посмотреть в сторону n-tuples, там оценка на основе паттернов
jacek: frontiers discs, mobility and stable discs
samrrr: а счего всётаки минсаксу ненужно дерево?
mykeich: http://chat.codingame.com/pastebin/586a883d-2797-446d-810c-fb507e3144c7
mykeich: samrrr минимакс обходит дерево состояний игры, для него не требуется хранить все дерево
samrrr: но так он не сиожет использовать всё время....
samrrr: или неуспеет...
mykeich: jacek, спасиб, я догадался, но не пришел к выводу стоит ли делать сложный алгоритм расчета стабильных фишек. глубина тогда будет 4 хода. Сейчас у мина минимакс, оценка бонус за углы и число фишек. Примерно.
YurkovAS: можете подсказать: какими алгоритмами такое решается?
есть большая карта, на ней есть клад: рандомное расположение и рандомное кол-во. можно исследовать как одну ячейку, так и диапазон и получить кол-во клада на этом участке. исследование большого диапазона стоит дороже.
mykeich: samrrr, все верно. у минимакса есть неприятная особенность что время его работы очень сильно плавает особенно с альфа бета отсечением. Если видишь что бот соперника часто падает, то 90% что у него минимакс
samrrr: ну так построить дерево и норм будет...
YurkovAS: ну и цель выкопать побольше клада
mykeich: YurkovAS, ну ты спросил:) поиск А* подойдет?:)
samrrr: YurkovAS подели всё поле на ячейки в N/2/кол_спотов и чекай, потом как с тигром
YurkovAS: а, забыл, времени на полный перебор не хватает, только на 1/20
YurkovAS: с тигром?
YurkovAS: и это жадные алгоритмы нужны? типа как с рюкзаком?
или что-то нестандартное уже
mykeich: samrrr, нет смысла прикручивать дерево к минимаксу, падает число рассмотренных ходов, т.е. глубину надо уменьшать.
samrrr: падает насколько?
mykeich: Настолько что MCTS выигрывает.
mykeich: samrrr и есть неприятность что если не все ходы рассмотрены, то его точность падает. не уверен конечно, но мое кроилово по изобретению велосипедов всегда проваливалось
samrrr: а босса то завалить удастся?
mykeich: YurkovAS там чтоль надо делить карту на области постепенно уменьшая зону поиска? И надо уложиться в число ходов?
samrrr: Вот тебе про льва
samrrr: http://chat.codingame.com/pastebin/45b82ed9-4a20-4908-a193-d58d72a7c161
YurkovAS: mykeich там надо в конкретной ячейке выкапывать клад. и есть функционал, который говорит сколько клада в конкретной ячейке. или в диапазоне суммарно.
перебором по каждой ячейке не успевает все выкопать, только 1\20 часть
samrrr: Давай как тигра
YurkovAS: samrrr получается здесь надо делать примерно такое же, только тигров много
YurkovAS: спасибо!
YurkovAS: это задача из highloadcup-а
samrrr: ну так возьми стартовую область меньше
samrrr: фи куп бы
samrrr: аи куп бы...
YurkovAS: да тоже самое, только без противников и веб апи
samrrr: без противников неинтересно
YurkovAS: там призеры раика, за ними не угонишься
YurkovAS: это типа оптимизаций тут на КГ - тоже нет противника, но есть табличка
samrrr: темболее ещё и конкурентов дофига
samrrr: тут есть противники и битвы
YurkovAS: здесь на кг в прошлый раз участвовало 7к человек - вот где не угнаться...
samrrr: зато тут батлы есть, а не простое напиливание кода чтоб работал побыстрее
Uljahn: тут всякое есть, и напиливание тоже
YurkovAS: Uljahn можешь глянуть задачку, что выше писал? может знаешь про алгоритмы, которые такое решают?
Uljahn: "исследование большого диапазона стоит дороже" - вот это поясни
samrrr: есть только 1 алгоритм
samrrr: берёшь и чекаешь области пока можешь, сужая диапазон
Uljahn: т.е. у нас есть бюджет на исследования, если по одной ячейке, то хватает на 1/20 карты, так?
YurkovAS: Uljahn чем больше диапазон запросил (например 100х100 клеток), тем дольше оно тебе отвечает.
ну и в ответе будет суммарное кол-во золота в этих клектах
Uljahn: сколько будет стоит чекнуть 1/2 карты?
YurkovAS: у меня точной информации сейчас нет, но очень долго, может даже половину всего времени
samrrr: чекать пол карты 0 толку
Uljahn: нет, толку 0.5
Uljahn: это не ноль :)
samrrr: клад не один, поэтому толку 0.5^n а это 0
Uljahn: а сколько кладов? какая плотность распределения?
samrrr: если кучкой то полосками чекай)
YurkovAS: эх, у меня нет этой статистики
samrrr: тогда это не задача, а идиотизм
YurkovAS: понял, надо собрать статистику и дальше уже посчитать. и добавить исследований по зонам и потом копать в лучших
YurkovAS: думал может это какая-то стандартная задачка, типа аналог рюкзака или т.п...
да почитал бы потом про этот класс алгоритмов
YurkovAS: а то я могу долго экспериментировать
YurkovAS: ну и да, смысл им давать стандартную задачку. придется подгонять под конкретные правила.
Uljahn: чем-то похожа на задачу о двух яйцах от гугла
Uljahn: только если плотность кладов каждый раз разная, то сложно очень
samrrr: https://www.codingame.com/replay/530625688 такое впечатление что мой бот спецом сливает
samrrr: https://www.codingame.com/replay/530626477 не ну точно, когда лузнуть шанса нет, он просто закрашился
YurkovAS: Uljahn спасибо
Uljahn: :thinking:
YurkovAS: до меня не дошло "идеальное решение задачи про яйца" :)
vrabosh: Приветы! Можете покахать плз, что находится в Tree Paths во Validator 2
TheCrucial: обычно примерно то же самое что в test 2 из приложенных по смыслу
vrabosh: все не надо, нашел ошику
samrrr: https://www.codingame.com/replay/530666103 наконечто хоть разок завалил свой прошлый ход
samrrr: А сколько можно мегабайт на дебютную книгу потратить?
