Я скорее про игрушки типа реверси, шашки, клоподавки и т.п. На самом деле может составить. У голых MCTS есть проблема с оценкой действий. Это дорого. Я пытался прикрутить их к войнам вирусов, и скажем так, они с большим трудом чуть-чуть отличались от рандома, при этом жрали секунды процессорного времени.
Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.
RTS — другой пласт игр. Конечно, реакция у компьютера будет на порядки лучше. Вопрос скорее, насколько будет легко человеку найти стиль игры, с которым компьютер не будет справляться.
По моим наблюдениям возраст такого молодого поколения колеблется от 15 до 60. Что на форумах, что в реальной жизни получить внятный ответ вместо мутных рассуждений получается далеко не всегда.
На самом деле, если тебе говорят, что ты мудак — это не страшно. Ты просто поймешь, что здесь ловить нечего, и пойдешь в другое место. Благо, есть еще англоязычный интернет. На тостере я временами наблюдаю более печальную картину. Отвечающие не различают или не хотят различать понятия "я не знаю, как это сделать" и "это невозможно". Вреда от таких ответов гораздо больше.
Я правильно понимаю, что идея — использовать подсчет числа различных элементов, чтобы проверить лежит ли элемент в множестве. Если это так, нам потребуется константная абсолютная погрешность. По информационным оценкам на такое потребуется как минимум линейная память, а по оценкам HyperLogLog-а она будет квадратичной от числа различных элементов.
По поводу 1-разреженных векторов и проверок. Да, мы хотим уместить память алгоритма в . Если не дать алгоритму ошибаться, нижняя оценка по памяти взлетит до . Это на самом деле несложно показать.
Представьте, что у вас есть алгоритм, который умеет детерминированно определять, осталась в векторе ровно одна ненулевая позиция или нет. Возьмем множество размера и кинем обновления для всех . После обработки всех обновлений алгоритм сформирует слепок памяти. Вот я утверждаю, что из этого слепка можно восстановить все множество . Поскольку всего таких множеств , то размер слепка будет порядка .
Восстанавливать просто: перебираем все подмножества размером и кидаем обновления . Если угадали подмножество , то результат будет 1-разреженным вектором и алгоритм вернет True, иначе – False. Берем объединение по всем хорошим и получаем .
Интересно, что Канн-Гринвальд детерминированный и всегда дает ответ с нужной погрешностью. Но он мне в свое время показался очень сложным, особенно в смысле понимания, почему работает.
У задачи поиска медианы и произвольного -квантиля есть очень простое вероятностное решение через сэмплирование. Берем из всего набора случайно элементов, сортируем. Теперь, если хотим посчитать -квантиль, нужно просто вернуть -ый элемент. С константной вероятностью ответ будет на расстоянии не более от правильного. Если нужна вероятность ошибки , берем соответсвенно элементов.
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
Было бы здорово, если бы еще и habrastorage кушал svg. Как вообще у вас с этим? Хабраэффект от постов не создает проблемы? Просто я так понимаю, что число запросов пропорционально числу формул умножить на число просмотров страницы. У меня некоторое время назад возникли небольшие проблемы с одним сервисом из-за этого.
Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.
На самом деле, если тебе говорят, что ты мудак — это не страшно. Ты просто поймешь, что здесь ловить нечего, и пойдешь в другое место. Благо, есть еще англоязычный интернет. На тостере я временами наблюдаю более печальную картину. Отвечающие не различают или не хотят различать понятия "я не знаю, как это сделать" и "это невозможно". Вреда от таких ответов гораздо больше.
Если хочется максимально ужать множество, посмотрите коды Голомба: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
По поводу 1-разреженных векторов и проверок. Да, мы хотим уместить память алгоритма в
Представьте, что у вас есть алгоритм, который умеет детерминированно определять, осталась в векторе ровно одна ненулевая позиция или нет. Возьмем множество
Восстанавливать просто: перебираем все подмножества
Зависит от начального уровня. Здесь нужно за спиной иметь базовые алгоритмы, графы и теорию вероятностей.
У задачи поиска медианы и произвольного
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
Да, спасибо за ответ.
Было бы здорово, если бы еще и habrastorage кушал svg. Как вообще у вас с этим? Хабраэффект от постов не создает проблемы? Просто я так понимаю, что число запросов пропорционально числу формул умножить на число просмотров страницы. У меня некоторое время назад возникли небольшие проблемы с одним сервисом из-за этого.