Варианты заданий

Московский государственный университет имени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиА. В. СтоляровПрактикум на ЭВММногопользовательский игровой серверМосква2005Автор будет признателен за конструктивную критику, в том числе за сообщения об обнаруженных в тексте пособия опечатках.Адрес для связи: avst@cs.msu.su.cАвторские права АндрейВикторович Столяров, 2004-2005Черновая версия от 24 февраля 2005 г.ВведениеЗадание практикума “многопользовательский игровой сервер” разработанодля занятий практикума на ЭВМ, проводимых на втором курсе на факультете ВМиК МГУ в рамках основного учебного плана.Задание предназначено для выполнения в операционной системе семейства Unix (например, FreeBSD или Linux) с использованием языков программирования C и C++.Задание состоит из двух основных частей, каждая их которых выполняется в несколько этапов.

В первой части задания предлагается реализоватьпрограмму-сервер, выполняющую роль ведущего в игре “Менеджер” [1] ипозволяющую принимать участие в игре игрокам, находящимся на разныхмашинах, используя локальную сеть. Первая часть задания может выполняться на языке C, что позволяет её выполнить в осеннем семестре.Вторая часть, предназначенная для выполнения на языке C++, состоит в создании программируемых роботов, способных принимать участиев игре “Менеджер”, имитируя действия игроков-людей. Такой робот представляет собой интерпретатор некоторого достаточно простого языка программирования, с помощью которого и задаётся его поведение в игре.Задание практикума “многопользовательский игровой сервер” нацеленона выработку и закрепление следующих навыков:• Первая часть (игровой сервер)— использование системы программирования (редакторов текстов,компилятора, отладчика, системы автоматической сборки) в ОСUNIX— программирование на языке C— создание сетевых приложений, использующих протокол TCPпри помощи berkley sockets— использование мультиплексирования ввода-вывода для созданиясобытийно-управляемых приложений• Вторая часть (программируемые роботы)— объектно-ориентированное проектирование и программирование— программирование на языке C++— использование элементов теории формальных грамматик дляразбора текстов на формальных языках (лексический анализ порегулярным грамматикам с помощью конечных автоматов, синтаксический анализ методом рекурсивного спуска, использование польской инверсной записи в качестве представления программы для осуществления интерпретации).3В настоящем пособии автор постарался ответить на наиболее типичныевопросы, возникающие у студентов по ходу работы над заданием.1Игра “Менеджмент”Игра “Менеджмент” была предложена фирмой Avalon Hill Company дляобучения основам управления предприятием.

Ч. Уэзерелл отметил чрезвычайную привлекательность этой игры в качестве упражнения (этюда)для программистов.В этом разделе излагаются сокращенные (упрощенные) правила игры“Менеджмент”. Полные правила игры желающие могут найти в книге [1].1.1Общие сведенияВ игре участвуют N игроков. Каждый игрок имеет номер 1 ≤ k ≤ N . Каждый игрок с номером k располагает некоторым количеством денег (условных долларов), Sk единицами сырья, Pk единицами продукции и Fk фабриками. В начале игры каждому игроку выдается 2 фабрики, 4 единицысырья, 2 единицы готовой продукции и 10000 долларов.Моделирование ведется пошагово, игровыми циклами. Цикл представляет собой условный игровой месяц.1.2Порядок игрыВ каждом “месяце” игроки производят на своих фабриках продукцию изсырья. Одна фабрика может произвести одну единицу продукции, израсходовав при этом одну единицу сырья и $2000.В случае, если у игрока недостаточно сырья или денег, чтобы обеспечить работу всех фабрик, либо если в связи с неблагоприятной обстановкойна рынке у игрока скопилось слишком много готовой продукции, фабрикаможет ничего не производить (что не исключает ежемесячных издержек).Каждый “месяц” банк проводит аукционы по продаже сырья и скупкепродукции.

Аукционы проводятся в соответствии с “обстановкой на рынке”,описываемой ниже. Заявки на аукционы подаются игроками “в темную”, т.е.игроки ничего не знают о заявках, подаваемых другими игроками. Однакопо окончании аукциона банк сообщает всем игрокам полную информациюо результатах торгов (а именно, кому, сколько и по какой цене проданосырья, а также у кого, сколько и по какой цене куплено продукции).4В каждом “месяце” игрок может сделать заявку на строительство новыхфабрик.

Фабрика стоит $5000 и начинает давать продукцию на 5й “месяц”после начала строительства. Половина стоимости строительства или реконструкции списывается с игрока при подаче заявки, вторая половина –за месяц до окончания строительства или реконструкции.Закончив подачу заявок на данный месяц, игрок заявляет об окончаниихода. Когда все игроки заявили об окончании хода, игровой месяц завершается.По итогам месяца с каждого игрока списываются ежемесячные издержки, а именно: $300 за оставшуюся на складе единицу сырья, $500 - за оставшуюся на складе единицу продукции, $1000 за фабрику (независимо оттого, производила она в этом месяце продукцию или нет).Игрок, которому не хватило денег на покрытие издержек, объявляетсябанкротом и выбывает из игры.Каждый игрок в любой момент может узнать о количестве денег, фабрик, единиц сырья и продукции у остальных игроков.1.3Обстановка на рынкеОбстановка на рынке может находиться на одном из пяти уровней.

В зависимости от уровня определяются предложение сырья (т.е. сколько единицсырья банк продаст в этом “месяце”), спрос на продукцию (т.е. сколько единиц продукции банк купит в этом “месяце”), минимальную цену единицысырья и максимальную цену единицы продукции. Значения этих величинопределяются по таблице уровней состояния рынка (табл. 1).УровеньСырьеПродукциякол-во min. цена кол-во max.цена11.0*P$8003.0*P$650021.5*P6502.5*P600032.0*P5002.0*P550042.5*P4001.5*P500053.0*P3001.0*P4500P - общее количество необанкротившихся игроков.Таблица 1: Уровни состояния рынкаОкругление производится в сторону уменьшения, т.е., например, если вигре участвуют 3 “живых” игрока, а уровень рынка определен как 2й, то5количество продаваемого сырья будет 4 единицы, а покупаемой продукции- 7 единиц.В начале игры уровень равен 3. Уровень для каждого следующего месяца определяется из предыдущего случайным образом в соответствии стаблицей вероятностей перехода (табл.

2).СтарыйНовый уровеньуровень1234511/3 1/3 1/6 1/12 1/1221/4 1/3 1/4 1/12 1/1231/12 1/4 1/3 1/4 1/1241/12 1/12 1/4 1/3 1/451/12 1/12 1/6 1/3 1/3Таблица 2: Вероятности смены уровня состояния рынка1.4Проведение аукционовНа каждом цикле игрок может в произвольном порядке дать заявку научастие в аукционе сырья, в аукционе продукции, заявку на производство,заявку на строительство новой фабрики и заявить об окончании своих действий на этот месяц.

Все заявки подаются “в темную”, то есть они не видныдругим игрокам. В заявке на участие в аукционе указывается число единиц для покупки или продажи и цена. Цена покупки сырья не должнабыть ниже минимальной установленной для текущего месяца, цена продажи продукции - не выше максимальной. Заявка на производство не должнапревышать количество имеющегося у игрока сырья, т.е. сырье, купленноена данном цикле, не может быть использовано при производстве продукциина этом же цикле.Если сумма заявок превышает доступное количество единиц, выставленных на аукцион, банк в первую очередь удовлетворяет наиболее выгодные для него заявки, т.е.

продает сырье игрокам, заявившим наибольшиецены, и покупает продукцию у игроков, установивших наименьшие цены.При прочих равных предпочтение отдается случайным образом (по жребию). Если размер очередной выбранной заявки превышает оставшееся количество доступных единиц, банк удовлетворяет заявку частично.Например, если банк должен купить всего 6 единиц продукции, приэтом игрок №1 выставил на продажу 3 единицы по цене 4500, игроки №2и №3 выставили каждый по две единицы продукции по цене 5000, то банк6купит все 3 единицы у игрока №1, после чего жребий определит, какая изоставшихся заявок будет удовлетворена полностью. Соответственно, игрок,на которого падет жребий, продаст обе единицы продукции по цене 5000,а второй игрок продаст только одну из двух единиц.Проведение аукциона можно начать в тот момент, когда получены заявки на данный аукцион от всех активных (необанкротившихся) игроков.Также можно проводить оба аукциона (продажи сырья и скупки продукции) в конце хода, т.е.

непосредственно после того, как последний из игроков заявит об окончании действий а данном месяце. Практика показывает, чтовторой вариант проще реализовывать.Если игрок заявил об окончании действий на данном цикле, не подавзаявки на аукцион, его заявка считается нулевой.Результаты аукционов (т.е. кому, сколько и по какой цене продано сырья, у кого, сколько и по какой цене куплено продукции) банк объявляетпублично, то есть информация об этом доступна всем игрокам.722.1Реализация серверно-сетевой частиПостановка задачиПрограмма-сервер выполняет функции ведущего игры. Игроки подключаются к серверу по сети с использованием протокола TCP/IP.Возможны два подхода к организации протокола обмена прикладногоуровня:— Сервер ожидает от клиента команды в текстовом виде, предназначенном непосредственно для обработки человеком. В этом случае вкачестве клиентской программы используется стандартная утилитаtelnet, входящая в базовую комплектацию практически любой Unixсистемы.— Сервер обрабатывает команды в определенном двоичном формате,удобном для обработки в программе.

В этом случае необходимо реализовать клиентскую программу, ведущую диалог с пользователеми формирующую соответствующие данные для сервера, а также преобразующую получаемые от сервера ответы в приемлемую для пользователя форму.Стартовыми параметрами сервера являются число игроков и номерTCP-порта, на котором программа должна ожидать запросы на соединениеот клиентов. Стартовые параметры задаются в командной строке сервера.По согласованию с преподавателем возможны другие варианты получениястартовых параметров, например, из конфигурационного файла или из переменных окружения.

Задавать стартовые параметры в тексте программы(т.е. так, что их изменение потребует перекомпиляции программы) запрещается.После запуска программы-сервера она должна открыть сокет в режимеожидания запросов на соединение (см. §2.2) на заданном порту, дождатьсяподключения заданного количества игроков, после чего перейти в режимигры, в котором и оставаться до момента, когда все игроки, кроме одного,по тем или иным причинам не выйдут из игры.До тех пор, пока сервер не перешел в режим игры, на любую командуигрока он должен реагировать сообщением о том, что игра не началась;желательно также выдавать при этом информацию о том, сколько игроковв настоящее время уже вошли на сервер и сколько еще ожидается до началаигры.После перехода в режим игры при попытке нового игрока подключитьсяк серверу он должен получить сообщение о том, что игра уже идет, послечего сервер должен разорвать соединение.8Требования к серверу:— Сервер должен предоставлять игроку все возможности, предусмотренные правилами игры (см.