В Project Reports я, как студент Калифорнийского университета в Беркли, рассказываю о своих заметках о вещах, которые я сделал своими руками, чтобы рассказать о том, чем занимаются студенты, изучающие информатику, и как мы учимся разрабатывать программы таким образом, чтобы люди могли понять, даже если они не являются Специальность CS.
В COMPSCI 61A, обычном первом курсе компьютерных наук, который изучают студенты Беркли, сотрудники курса каждый семестр проводили в классе турниры по написанию ИИ для игры под названием Hog.
Hog — это недетерминированная гонка, в которой два игрока соревнуются, чтобы набрать определенное количество очков, бросая кости.
Но вот в чем особенность:
В зависимости от количества кубиков, которые вы бросаете, и количества очков, которыми в настоящее время обладает ваш противник, очко, которое вы получаете в этот ход, может значительно увеличиваться или уменьшаться, что внезапно приводит к тому, что ход игры оказывается в пользу другого игрока.
Я был очень рад узнать о различных стратегиях, которые студенты Беркли могут использовать в этом конкурсе, и побороться с ними, поэтому я также присоединился к турниру.
В этом журнале будет обсуждаться процесс и интересные идеи программирования, которые я узнал, участвуя в этом конкурсе в качестве начинающего программиста.
Примечание. Если вы являетесь студентом COMPSCI 61A, здесь нет проектных решений. Но интересно посмотреть, чем занимались нынешние старшеклассники во время Турнира свиней.
Организация требований пользователей: правила турнира
Прежде чем перейти к правилам конкурса, позвольте мне более подробно объяснить, что такое «Кабан».
В Калифорнийском университете в Беркли есть огромный (более 1700 студентов в моем семестре) вводный курс по компьютерным наукам под названием «CS61A».
В этом курсе у нас есть тип задания под названием «проект», который включает в себя большой сбор файлов кода, которые составляют более масштабное приложение.
«Свинья» — это первое проектное задание, включающее недетерминированную гоночную игру, упомянутую в знакомство с этим журналом.
Игра описана ниже:
- Условия победы: набрать не менее 100 очков.
- Способ получения очков: игрок может бросить до 10 шестигранных кубиков за ход и получит количество очков, равное сумме всех очков по результатам игры в кости.
Но тогда основной стратегией будет просто бросать 10 кубиков каждый раз! Чтобы внести разнообразие в игру, а также сбалансировать силу бросания слишком большого количества кубиков, следующие правила «ослабления» также представлены:
- Бросьте один: если любой из результатов кубиков равен 1, очки, заработанные за этот ход, равны 1.
- Zero Dice: Если игрок бросает 0 кубиков, пусть счет противника равен N, и игрок получает счет, эквивалентный N-й цифре после запятой для десятичного выражения одной седьмой (0,142857…).
- Двойные очки: после завершения подсчета очков текущего хода, до смены текущего игрока, если оба игрока набрали одинаковое количество очков, очки текущего игрока удваиваются.
- Дополнительный бросок: Каждый ход нумеруется, начиная с 0. Если игрок бросает K кубиков на N-м ходу, где остаток от N, деленный на 8, равен K, игрок получает дополнительный ход. Это правило не может применяться последовательно.
В турнире каждая стратегия играет против любой другой стратегии и ранжируется на основе количества стратегий, против которых они выиграли.
Для каждого матча будет проводиться огромное количество игр друг против друга с примерно равным количеством игры на первое и второе.
Затем, чтобы наказать файлы, использующие слишком много кода, к голевой статистике каждого игрока применяется новое правило:
Минимально возможный балл — 50, но для любых файлов, превышающих определенный размер, их целевые баллы будут увеличены за пределы 50 в зависимости от размера их файла.
Это побудило бы игроков уменьшить размер своего файла, содержащего стратегию игры.
Итак, как мне решить, сколько кубиков бросить?
Отличный вопрос.
Перед этим мы должны придумать метрику, которая определяет, какое количество костей нужно бросить. В частности, эта метрика должна оценивать количество бросков костей в зависимости от того, насколько она помогает. игрок должен выиграть, чтобы метрика показала нам, какое количество кубиков кажется наиболее эффективным для победы.
Для этой метрики существует много возможных вариантов: количество очков, набранных за ход, разница между очками игрока и противника, количество очков, которое противник может набрать в следующий ход… но хорошие метрики разделяют особенность.
- Они числовые, поэтому легко оценивать решения игрового ИИ с помощью баллов.
- Большой балл может означать только хорошее или плохое, а маленький балл представляет собой нечто противоположное большому баллу.
Используя показатель «количество очков, выигранных за ход» в качестве примера:
Если количество выигранных очков велико, ход ИИ хорош, так как получение большого количества очков заставит текущего игрока выигрывать быстрее. В противном случае, если количество очков, доступных за ход, невелико, текущий игрок не получит такого прогресса и сделает плохой ход.
В своей стратегии я использовал «шанс на победу, бросив это количество кубиков» в качестве метрики.
Это означает, что для каждого количества костей, которые я могу бросить, я моделирую всю возможную игру, чтобы увидеть, какова вероятность того, что бросок этого количества костей может привести к выигрышу. Моя окончательная стратегия будет всегда выбирать такое количество кубиков, которое дает наибольшую вероятность выигрыша в текущей игре.
Кратко о моем решении
Теперь мы должны задать вопрос о правилах и реализациях.
Другими словами, вопрос заключается в следующем: «Как мне рассчитать вероятность выигрыша при определенном количестве бросков?» А также «Как вы реализуете это решение?»
Шанс выиграть игру с n бросками, вообще говоря, равен сумме
probability_of_rolling_point(target_point, num_rolls) * probability_win_by_point(my_score, opp_score)
На протяжении всего возможного количества очков выкатывается из n бросков.
Теперь понятно, как мы реализуем окончательную стратегию: мы можем спросить, какова вероятность выигрыша при количестве бросков от 0 до 10(вероятность_прокручивания_точки), и, наконец, выберите такое количество бросков, которое дает максимальный шанс на победу(вероятность_выигрыша_по_очбу).
Наши текущие проблемы — это черные ящики: вероятность_по_пойнту и вероятность_выигрыша по_пойнту, их реализация и их алгоритм.
Вероятность_подвижки_точки
Мы хотели бы знать вероятность выпадения определенного количества очков при заданном количестве бросков. Что мы можем сделать, так это изучить все возможные комбинации выпавших очков и посмотреть, сколько из этих возможностей дают мне целевую сумму очков, которую я хотел бы видеть. Это требует больших вычислительных мощностей.
Вероятность_выигрыша_по_точке
Мы хотели бы знать вероятность победы, учитывая текущий счет игрока и счет противника. Сначала мы можем учесть случай, когда счет одного из игроков уже достиг цели.
Затем мы можем рассчитать вероятность победы противника (с помощью вышеупомянутой схемы в начале этого раздела), которая эквивалентна вероятности проигрыша текущего игрока.
Мы вычитаем из этой вероятности 1, чтобы увидеть шансы на победу текущего игрока при текущем счете.
Это требует больших вычислительных мощностей.
В общем, поскольку стратегия должна рассчитывать всю игру для каждого отдельного решения, которое она моделирует, это требует больших вычислительных мощностей. Много.
Решение может даже не соответствовать ограничениям времени выполнения из-за абсурдного количества данных, которые ему необходимо обработать. Код может быть недостаточно маленьким, чтобы не наказываться правилами турнира.
Поэтому в следующих разделах я расскажу, как сделать это решение «рабочей программой», которая может работать «лучше»: более эффективно и с меньшим энергопотреблением.
Написание работающей программы, которая работает «лучше»
Вот два наблюдения с нашим текущим решением, или, если хотите, алгоритмом.
- Кажется, что в нашем алгоритме много повторяющихся частей.
Например, мы вычисляем как вероятность_по_катящемуся_пойнту, так и вероятность_выигрыша по_пойнтумножество раз на протяжении всей симуляции, и эти функции также очень часто используют друг друга в своих вычислениях. - Это требует больших вычислительных мощностей, особенно потому, что компьютеру приходится пересчитывать множество вероятностей для одной и той же повторяющейся ситуации.
Делегация
Слово делегирование имеет следующее определение:
передача полномочий другому лицу (обычно от руководителя к подчиненному) для выполнения определенных действий.
В программировании у нас есть аналогичная практика: мы назначаем строки кода для конкретных вычисляемых элементов в блоки.
Таким образом, вызывая имя блока и давая ему разные входные данные, мы можем повторно использовать код в строках кода!
Это очень удобно, потому что, имея возможность называть эти имена, мы избавляемся от необходимости кодировать их вручную каждый раз, когда нам нужен код.
Это действие по делегированию ответственности каждому блоку кода и имени для ссылки на них является концепцией, называемой в программировании «делегированием».
Чтобы представить это, подумайте о разнице между ящиком для мусора и упорядоченным контейнером:
В каком из них легче найти свои вещи?
А в командах из разных людей, среди команды, где никто не знает, что делает, и команды, где у каждого есть специализированная позиция, какая из них кажется более эффективной?
Мемоизация
Представьте, что вы бухгалтер в 18-м веке и передали ряд трехзначных умножений на трехзначные. Может быть, сотни умножений. Большинство этих умножений повторяются, поэтому среди этих сотен есть те же самые вычисления, которые приходится делать вручную.
Вот два способа выполнить задание:
- Просто вручную вычислите все сотни умножений вручную.
- Или вы все равно вручную вычисляете умножения. Но подготовьте еще один лист бумаги и для каждого умножения, которое вы делаете:
- Проверьте, есть ли на другом листе бумаги запись о текущем умножении.
- Если да на шаге 1, прочтите прямо с листа бумаги результат умножения. В противном случае выполните умножение вручную, так как это новое уравнение.
- Если результат этого умножения еще не записан на другом листе бумаги, запишите результаты текущего уравнения на другой лист.
В приведенном выше методе у нас есть место для запоминания каждого умножения или повторных вычислений, которые мы сделали. Когда мы сталкиваемся с уже сделанными расчетами, нам не нужно все пересчитывать и переделывать, а просто ссылаться на таблицу и использовать нашу предыдущую работу!
Этот общий подход называется динамическим программированием.
Это метод, применяемый к компьютерным программам, когда программисты устанавливают в компьютер «дополнительный лист бумаги для записей» и позволяют ему помнить ранее завершенные вычисления, чтобы компьютер мог повторно использовать свою старую работу в случае необходимости.
В частности, техника, которую использует эта программа, называется «Запоминание», что является методом «добавить дополнительный лист» в первом примере этого раздела.
Что такое мемоизация помимо вычисления трехзначного умножения?
Хорошим примером применения запоминания является вычисление последовательности Фибоначчи, где этот ряд чисел определяется следующим образом:
Следовательно, члены последовательности Фибоначчи от нулевого элемента можно пронумеровать следующим образом:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
Итак, чтобы вычислить, например, 5-й элемент последовательности Фибоначчи:
Но при выполнении мемоизации количество необходимых вычислений становится таким, как показано ниже:
Чем выше становится число членов Фибоначчи, тем более действенной становится эта таблица памяти:
Скажем, мы вычисляем 100-й член Фибоначчи, тогда использование таблицы памяти потребует от нас всего лишь вычисления 100 терминов (вызовов функций) последовательности Фибоначчи, поскольку она сохраняет результаты каждых 100 терминов в себе; однако без таблицы памяти нам потребуется вычислить более 11 000 вызовов функций: более чем в 100 раз больше затрат, необходимых для таблицы памяти!
Турнир
Турнир начался.
Перейдем к результату:
В этом 1700-м классе в конкурсе приняли участие 102 ученика, и мне выпала честь занять 15-е место в этом турнире.
(Позже я узнал, что большинство людей, стоявших впереди, использовали машинное обучение на вводном курсе информатики для забавного турнира без оценок. 😶)
Возможные изменения в моей программе.
Есть несколько пунктов, которые моя стратегия не учитывала. Это, вероятно, также продемонстрирует, как я думаю о пересмотре своего кода.
Первый элемент — это вдохновение, которое я получил от своего друга, но не знал, как реализовать: счетчик временной рыси, черный ящик, который каким-то образом может заставить мой код максимизировать вероятность использования временной рыси, а также механизм прогнозирования, который помогает чтобы предсказать тайм-рыс соперника.
Получение дополнительного хода в этих играх с бросанием костей может дать действительно хорошее преимущество.
Фактически, это удваивает ожидаемый выигрыш очков за ход игрока, обеспечивая дополнительный ход.
Возможно, это доступный механизм для участников ML, поскольку они могут формировать сложные правила для своих компьютеров (агентов), выполняя простые симуляции и вычисления множество раз.
Второй пункт в основном мой плохой. Проверив свой код с помощью моего бедного человеческого мозга, я понял, что забыл подумать о правиле двойного очка в игре, из-за которого прогнозы моей программы сильно отличались от того, как игра должна идти на самом деле.
Простое исправление заключается в следующем. чтобы немного изменить мой алгоритм, чтобы предсказание включало это правило «удвоения» и могло позволить игроку извлечь выгоду из более точного расчета вероятности для шансов на победу.
Чтобы предотвратить эту проблему, для большинства более поздних проектов я начинаю с документом, касающимся элементов и категорий блоков кода, которые я должен спроектировать, а также того, как я ожидаю их спроектировать.
И последнее, но не менее важное: поскольку объем вычислений и блоков кодов будут увеличиваться, можно также позволить большему количеству функций получить доступ к запоминанию для экономии вычислительных ресурсов. мой алгоритм делает.
И последнее, но не менее важное: не связанные с технологиями размышления
Было, конечно, интересно участвовать в моем первом турнире, связанном с кодом, а также услышать, как каждый другой участник Беркли решил работать со своими стратегиями.
Я также очень удивлен, что занял 15-е место в конкурсе, несмотря на то, что мой значительный предыдущий опыт в области компьютерных наук был только APCSA из средней школы. Хотя этот конкурс, возможно, пробудил во мне интерес к ИИ, оказалось, что меня больше интересует его подполе и основа большинства стратегий высшего уровня: глубокое обучение.
В противном случае я также понял, что программы — это не просто инструменты для выполнения сценариев. Они делают это, но это больше касается вдохновения и удовольствия, которые приносят программы, чем просто насыщенный процесс разработки, стоящий за ними. Я научился относиться к программам на своих компьютерах больше как к произведениям искусства и кристаллизации усилий, взволнованный тем, что однажды поучаствую в такого рода усилиях всей командой.
Я могу с уверенностью 95% сказать, что конкурс свиней был самым веселым днем, который у меня был в этом курсе под названием COMPSCI 61A!
