Chat:Ru/2022-01-06

From CG community
Jump to navigation Jump to search

aangairbender: прикольно когда бот играет так же как топ1

aangairbender: https://www.codingame.com/replay/601026253

aangairbender: YurkovAS а с тобой не так... https://www.codingame.com/replay/601026526

aangairbender: ахах а если сделать чтоб топ1 ходил первым, то он меня за 100 ходов выносит))

Uljahn: глубина 1 - это когда все игроки походили, а ход одного игрока - это ply, т.е. для 4 игроков глубина четыре ply будет равна глубине 1

Vlad100: Какой самый оптимизированный алгоритм для проверки победителя в UTTT? Попытки придумать хороший алгоритм либо давали тот же результат либо не работали.

Vlad100: Правильнее сказать в TTT.

Uljahn: если у тебя битборды, то look-up table, наверное

Vlad100: То есть сравнивать хеши?

aangairbender: хранишь битовую маску, где i-тый бит означает что игрок победил на i-ом поле, тогда достаточно проверить эту маску на равенство одной из 8 масок

aangairbender: 0b_111_000_000, http://chat.codingame.com/pastebin/9f2eb29c-d28d-4987-acd4-ad4bae189bbe

Vlad100: Всё спасибо.

aangairbender: Vlad100 точней не на равенство, а что-то типа WIN_POSITIONS.iter().any(|&w| (p & w) == w)

aangairbender: где p - маска выигранных полей игрока

Uljahn: https://www.youtube.com/watch?v=5t5jzkO0t7w

Uljahn: ещё вот так можно

Vlad100: А и ещё по поводу bitboard. Мы по сути храним массив чисел и когда нам нужно узнать позицию

Vlad100: состояние

Vlad100: Мы просто проверяем бит

Vlad100: Так?

aangairbender: битборд - это то же самое что массив bool только оптимальней

aangairbender: по сути ты прав

aangairbender: я стараюсь не использовать битборд, если битов больше чем 64 (иногда 128)

aangairbender: то есть если оно не помещается в одно число, то это уже не так круто

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

YurkovAS: это у тебя maxN на глубину 1 так хорошо играет?

aangairbender: YurkovAS мое решение брало топ50 с ply в 7


YurkovAS: ну вот посмотри в сторону дерева

aangairbender: я сейчас пишу мощную оценочную, что-то типа tree of chambers, но еще с динамическим программированием, пока не заиграло

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

aangairbender: а ну и iterative deepening есть, доходит до 100 ply

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

aangairbender: я понимаю) но у меня maxN

YurkovAS: в максН нет отсечений и будет полный перебор всегда

YurkovAS: в параноид есть отсечения, а отличается оценочной: всегда оцениваешь только себя, без разницы чей был ход

YurkovAS: типа: scoreMy - scoreOps

aangairbender: но параноид - это считать что все против тебя играют, имхо такое редко

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

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

aangairbender: но если нет - лучше максимизировать свой скор

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

aangairbender: так мне хватает глубины

YurkovAS: или оценочную делать хорошую: через разделение на комнаты и в воронове учитывать реально возможный путь, а не бфс-ом все достижимые

aangairbender: вот это я и делаю

aangairbender: но пока не работает

YurkovAS: а ну раз хватает глубины, выше написано что глубина 4хода

YurkovAS: да это сложно сделать

YurkovAS: я даже хз как, дфс тут много не найдет

aangairbender: ну код я уже написал, где-то баг походу

YurkovAS: круто, будем ждать отличных результатов :)

aangairbender: ищу cut клетки, строю дерево и по нем динамика

YurkovAS: cut это тунели?

aangairbender: рассматриваю варианты 1) заполнить эту комнату и остановиться 2)заполнить эту комнату и пойти в следующую 3)пробежать быстро эту комнату и пойти в следующую

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

aangairbender: YurkovAS cut - у меня это входы в туннели

aangairbender: точки невозврата

amzh: Всем привет! Я помню когда то я находил ссылку на беларусский (кажется) сайт с расписанием различных контестов по программированию. Я, к сожалению, потерял эту закладку. Кто-нибудь знает о чем я говорю?

YurkovAS: https://clist.by

amzh: точно! Спасибо огромное)