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: точно! Спасибо огромное)
