Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.1 (1)     Поиск:
Автор	Тема: Игра в шахматы - это MDP, PoMDP или ?
tac Сообщений: 2601	Игра в шахматы - это MDP, PoMDP или ? Добавлено: 01 июн 10 14:40 Собственно именно этот вопрос и интересует .. В частности, связан с нашей дискуссией с Данером, когда он утверждает, что MDP это не идеализация, и может работать на практике. Так вот простейшая игра - является ли такой ? Если нет - то какие имеет характеристики с точки зрения марковости. [Ответ][Цитата]
daner Сообщений: 4602	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 01 июн 10 23:32 я думаю, что это MDP. Во-первых, состояния игры отлично видно в любой момент времени. Во-вторых, все состояния в принципе (теоретически) известны, конечны и нет ничего скрытого. Действия, тоже все в каждом из состояний известны. То что любое наше действие ведет за собой попадание в несколько возможных разных состояний (после нашего хода, идет ход противника, который мы не знаем) -- тоже в рамках МДП. [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 3:20 интересно ... но "наше действие ведет за собой попадание в несколько возможных разных состояний" не может оцениваться вероятностно, точнее если это будет оцениваться вероятностно (как в МДП), то для агента ходы противника будут казаться случайными, а это явно не так. Т.е. ему преидется иметь модель поведения противника - логическую, а не статистическую, как в Q-обучении. Значит в таких условиях даже если это МДП - Q-обучение далеко не оптимальное. [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 3:25 С другой стороны, "состояния игры отлично видно в любой момент времени" - так то оно так - но технически не перебираемы, т.е. на самом деле практически видны на определенную глубину, на сколько глубоко или широко - свобода выбора, но ограничено временем хода. Поэтому теоритически может и МДП, но как только выходим в реальность - МДП тут же улетучивается .. [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 3:33 Ну, и главное. действия то известны, но их эффективность зависит от взаимного расположения 16 агентов игрока и 16 агентов противника. Поэтому достоверно оценить эффективность каждого последующего действия невозможно. Можно придумать какую нибудь экспертную оценку - но нужно ожидать, что эта оценка будет не верна, и ее нужно будет корректировать, а не стремится к ней. К классическом МДП - это не предусмотрено, т.к. такая оценка будет зависеть от предистории ходов - задача теряет черты марковости. Так как локальные одни и те же действия одной из фигур могут приводить к совершенно разным результатам. А глобальная оценка далеко не всегда доступна. [Ответ][Цитата]
daner Сообщений: 4602	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 13:53 Цитата: Автор: tac интересно ... но "наше действие ведет за собой попадание в несколько возможных разных состояний" не может оцениваться вероятностно, точнее если это будет оцениваться вероятностно (как в МДП), то для агента ходы противника будут казаться случайными, а это явно не так. Т.е. ему преидется иметь модель поведения противника - логическую, а не статистическую, как в Q-обучении. Значит в таких условиях даже если это МДП - Q-обучение далеко не оптимальное. Все, как вы пишите. Но, иметь логическую модель противника, не мешает оценивать вероятность его ходов. Не так ли? Относительно "оптимальности": в Теории Игр с этим термином вообще проблемка. Однозначной оптимальности нет, так что... Приходится выбирать какую-то конкретную, и которая совсем не обязательно вообще существует для конкретной игры. Думаю, q-learning (просто гипотеза) в конце концов придет к стратегии minmax, если противник рационален, если нет, то к какой-то другой стратегии... [Ответ][Цитата]
daner Сообщений: 4602	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 13:59 Цитата: Автор: tac С другой стороны, "состояния игры отлично видно в любой момент времени" - так то оно так - но технически не перебираемы, т.е. на самом деле практически видны на определенную глубину, на сколько глубоко или широко - свобода выбора, но ограничено временем хода. Поэтому теоритически может и МДП, но как только выходим в реальность - МДП тут же улетучивается .. Не... не совсем. Достаточно теоретического, ведь это теоретическое описание среды. Для q-learning (конкретного алгоритма обучения с подкреплением) ели уж мы его обсуждаем, нет необходимости заглядывать вперед. Это алгоритм проб и ошибок, соответственно по определению, ЕМУ НЕОБХОДИМО проверить на собственном опыте чего-же там дальше будет. У него нет заранее точно определенной модели внешнего мира (есть только класс моделей: MDP). Поэтому, в отличии от того же minmax, он вначале должен сам эту модель определить/создать. [Ответ][Цитата]
daner Сообщений: 4602	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 14:19 Цитата: Автор: tac Ну, и главное. действия то известны, но их эффективность зависит от взаимного расположения 16 агентов игрока и 16 агентов противника. Поэтому достоверно оценить эффективность каждого последующего действия невозможно. Можно придумать какую нибудь экспертную оценку - но нужно ожидать, что эта оценка будет не верна, и ее нужно будет корректировать, а не стремится к ней. К классическом МДП - это не предусмотрено, т.к. такая оценка будет зависеть от предистории ходов - задача теряет черты марковости. Так как локальные одни и те же действия одной из фигур могут приводить к совершенно разным результатам. А глобальная оценка далеко не всегда доступна. Здесь два момента. 1. Агентов не 16+16, а только два. Все остальное -- действия этих двух агентов. MDP вообще модель которая рассматривает одного агента и его среду (которая может включать других агентов, но не различать их и не отличать от всей остальной среды), во всяком случае в классическом варианте. 2. Второй момент... есть проблемка с функцией награды (тут вы правы). Она (очень часто) не известна. Этому приходится, как-то ее эту проблему разрешать. И тут начинаются всякие разные теории относительно того, какая модель награды в той или иной задачи (повод вспомнить мой дисер). Поэтому в реале, это две разные гипотезы/модели относительно внешней среды: 1. определиться с функцией награды. 2. на основе первой гипотезы, предположить, что среда соответствует модели MDP. Но зато, мы можем анализировать свои решения в этих рамках и (для примера) утверждать, что если наши предположения верны, то мы точно сможем научиться лучшей стратегии. Тоже самое, что и в физике: если модель балистического движения тел верна, то мы можем точно рассчитать движение брошенного камня. [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 17:33 Замечательно. В кои веки - у нас с вами - консенсус Посмотрите вот на что Реконструкция_прошлого Что скажите в свете этой дискуссии ? [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 02 июн 10 17:43 Цитата: Автор: daner Думаю, q-learning (просто гипотеза) в конце концов придет к стратегии minmax, если противник рационален, если нет, то к какой-то другой стратегии... Заметьте, это сказали Вы (я даже не упоминал minmax) ... за что я готов вас расцеловать [Ответ][Цитата]
daner Сообщений: 4602	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 03 июн 10 0:25 Цитата: Автор: tac Что скажите в свете этой дискуссии ? не знаю, как эта дискуссия относится к тому на что вы ссылку дали. кстати, статья не очень-то написана. Вы можете лучше. одна из важных составляющих планирования -- это цель и эфективность плана, а при восстановлении истории нет ни цели, ни эффективности. Важна реальность найденной последовательности. Конечно, задачи близкие, и наверняка можно применять методы планирования при решении вос.ист. но явно не без дополнительных гипотез. Например.. Если известно начальное состояние, то задача сводится к построению плана от него до текущего (оно и будет целевым), причем желательно как можно эффективнее. Но найденный результат, будет решением задачи, только если начальное состояние и правда было известно, и второе: если действия делались рационально в детерминированной, не динамической среде. [Ответ][Цитата]
tac Сообщений: 2601	На: Игра в шахматы - это MDP, PoMDP или ? Добавлено: 03 июн 10 0:43 Цитата: Автор: daner 1. не знаю, как эта дискуссия относится к тому на что вы ссылку дали. 2. кстати, статья не очень-то написана. Вы можете лучше. 1. Ну, во-первый, там тоже речь о шахматах. Во-вторых, сравнение с минимаксом. В-третьих, вы сами связали минимакс с Q-learning ... вообще тяжело объяснить связь, но она явно есть ... 2. Спасибо, что верите в меня, это просто черновик (попытка из подсознания вынести связи с традиционно разными вещами ). Но может посоветуете - на что обратить внимание чтобы улучшить При восстановлении истории, так же есть цель и эффективность. Цель собственно так установить состояния неизвестных элементов (событий, фактов), чтобы они соответствовали так сказать настоящему. Как видно из статьи грани тут стираются, и скажем цель в шахматах - это поставить мат. А эффективность - это приближение к этому. В том то дело, что начальное состояние тут не так важно, исходим из конечного состояния. [Ответ][Цитата]
Стр.1 (1)