Программа для игры в покер

Intro
Начну с того, что любое GUI-приложение можно разработать на чистом си, без плюсов. Да какой там си. Ассемблер тоже годится! Достаточно скачать FASM (http://flatassembler.net/), и заглянуть в примеры, чтобы убедиться, что вполне себе рабочий GUI можно писать даже на нем.
// Сразу скажу, что с иксами непосредственно я не работал, и на низком уровне писал только на WinAPI. Поэтому отталкиваюсь от него. В иксах же, как известно, добавляется еще и клиент/серверное взаимодействие, и, наверное, еще что-то, так что модель WinAPI, пожалуй, самый простой вариант.
Пробуем написать приложение, выводящее форму на экран и делает что-то при нажатии на левую кнопку мыши.
Начало стандартное:

Ну и что же теперь? Известно, что при нажатии мышки возникает некоторое прерывание, обработчик которого, разумеется, находится в ОС. ОС также занимается обработкой прерываний при перемещении мышки, поэтому она точно может знать, в какой позиции экрана находится курсор. То есть при нажатии клавиши мышки, ОС сама по себе запросто определяет, какая клавиша была нажата (берется с аппаратуры), и позиция курсора.
Чтобы понять, на каком элементе, и в каком окне произошло нажатие, нужно, чтобы ОС знала, где располагаются эти элементы. Для этой цели ОС должна предоставлять функции регистрации некоторых прямоугольников, которые будут чем-то вроде "областей нажатия": при нажатии мышки на этом прямоугольнике, система должна запоминать, что в этом прямоугольнике клавиша была нажата.
Поэтому, определим структуру:
В ОС определим массив указателей на эти Rect-ы. Чтобы приложение и ОС оперировали одними и теми же Rect-ами, введем функцию регистрации Rect-а в ОС. Вызывать эту функцию должно приложение. Пусть оно изначально задает размер окна, мы же не хотим, чтобы наша псевдо-ОС всегда создавала прямоугольники одинаковых размеров?
Наглядное применение нашего "свежесозданного" апи, с применением for( ; ; ):
И такой код даже будет работать! Но приложение будет занимать 100% ресурсов хотябы одного ядра (хотя, при гипертрединге, даже не знаю как правильно назвать, потока чтоли). Это очевидно. отбросим все до и после цикла: в цикле банальная проверка переменной на истинность. Причем, от того, что rect -- структура, код более волшебным не становится. На уровне ассемблера, в лучшем случае, это будет:
Как же избавиться от этой загрузки процессора?
В книге Таненбаума "Операционные системы. Разработка и реализация" упоминалось, что у каждого процесса есть некий флаг загруженности. То есть если программа была прервана операционной системой (кстати, делается это по таймеру, или IRQ0, при вытесняющей многозадачности), то ей нетрудно догадаться, что программа то еще работает! С другой стороны, если программа сама передала управление в ОС, сказав: "щас мне нечего делать. я жду ввода", ОС не зачем вхолостую тратить драгоценные такты на десятки, да или сотни даже таких процессов.
Значит, после создания Rect-а, программа должна передать управление в ОС специальным образом, и тогда флаг занятости будет установлен в 1, а планировщик не будет передавать управление нашей программе. При этом, из самой очереди планировщика ее можно не исключать, ведь ОС в любой момент может сбросить флаг занятости, и тогда ему нужно будет вновь передавать управление в нашу программу.

Как жеж такое сделать?
На самом деле все просто до безумия. Если подумать, когда жеж должно передаваться управление в программу, если та ожидает, что пользователь нажмет на мышку в окошке? Правильно: тогда, когда пользователь нажмет на мышку в этом окошке! А от мышки управление, как уже говорилось, поступает непосредственно к ОС: возникает некое прерывание. точно также от клавиатуры (для PS/2 это IRQ1), точно также при любом движении мышки/сенсорника, или любого другого устройства ввода (и не только). при этом, ОС отдает управление некоторому системному процессу.
Системный процесс реализует алгоритм поиска точки внутри заданного массива прямоугольников (все они зарегистрированы в системе, и этот системный процесс имеет доступ по крайней мере, на чтение этого массива). Определяет нужный прямоугольник, и .... Что? Правильно! Нужен некоторый идентификатор процесса, к которому привязываются все создаваемые в нем прямоугольники! А еще лучше, если у каждого прямоугольника будет указатель на процесс, ну или хотябы его идентификатор.
Так. Теперь уж точно хватит прямоугольников. Прямоугольник, имеющий какой то непонятный идентификатор на что-то вообще левое -- разве это прямоугольник? Назовем эту нашу штуку, имеющую размер, позицию, и ID процесса, окном (Window).
После того, как системный процесс определил нужное окно, он считывает из его структуры id процесса и сбрасывает его флаг занятости. Планировщик через какое-то время передает управление этому процессу. Процесс обрабатывает нажатие мышки и снова должен вызвать функцию ожидания клика, или завершиться. Получаем код типа:
Все, приложение больше не виснет, и обрабатывает клики как положено. Несмотря на бесконечный for( ; ; ).
Остаются "сущие пустяки": разобраться, как можно одновременно обрабатывать и клики мышки, и нажатия клавиш на клавиатуре, и какие-нибудь таймеры, "прокрутку" "колесиком" ну и прочее и прочее...
Я как-то уже упоминал слово "событие". Так вот. Всем этим нажатиям, движениям, прокруткам, таймерам, можно дать одно название: все это является событием (Event). Все эти события берутся от операционной системы. А откуда они берутся в операционной системе, было описано выше, на примере с кликом. События бывают разные, и описать его, например, так:
не получится, ибо при нажатии на кнопочку несколько непонятно, зачем передавать координаты мыши. Зато связать с этим событием нажатую клавишу, пожалуй, более чем желательно. Что делать? Конечно, есть замечательный способ: все запихать в одну кучу, и клавишу, и координаты мыши, и, скажем, смещение колесика мыши, и контекст рисования (да-да, события могут поступать не только от аппаратуры, но еще и от самой ОС. Например, как раз когда нам нужно наше окошко "отрисовать", ОС передает управление окну, ибо только оно знает, как оно должно выглядеть) и еще кучу всего. Но память при этом будет использоваться неэффективно. Можно попытаться сделать какие-нибудь union-ы, но в итоге мы все равно наверняка придем к достаточно сложным структурам

Поэтому тут логично применить наследование (да-да, то самое, из ООП). Варианты возможной реализации я нашел тут: http://stackoverflow.com/quest... tance-in-c. Но здесь я намеренно не буду их употреблять, ибо и так уже многа букав:
Конечно, я забыл рассказать о том, как передавать все эти события в приложение. Хотя, я думаю, если уж дочитали до сюда, то скорее всего, уже у вас есть какие-то мысли по этому поводу. Вот один из простейших вариантов, на основе очереди сообщений (инспайред бай винапи). События -- это частный случай сообщения. Например, так можно реализовать возможность посылки сообщений не только от системы, но и от окна другому окну, или даже самому себе.

• Для начала убедимся, что у нас есть id текущего активного окна системы, activeWindowId, которое является глобальным. Также как в любой оконной среде вы можете выбрать только одно окно, и оно будет "основным", то есть, по умолчанию, события клавиатуры поступают к нему. Аналогично можно реализовать поведение "посылать события в окно под курсом": нам просто понадобится найти и сделать текущим окно под курсором в случае, когда пришло любое событие от клавиатуры или от мыши.
• добавляем в структуру Window еще три поля:
  

  C
  1 2 3 4 5 6 struct Window {     int x, y, width, height;     int pid;     list *messages;     int window_id; }

  новые поля last_evt, last_evt_type, window_id должны заполняться ОС. Причем последний является уникальным глобальным идентификатором внутри всей системы. Это поле заполняется при регистрации окна.
• В ядре системы добавим следующие структуры и функции:
  

  C

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 list *messagesQueue; // глобальный список событий   struct Message {     int wnd; // id окна, которому предназначается сообщение     int type; // тип сообщения. служит только для того, чтобы правильно прочитать структуру message     void *message; // тело сообщения, например, это может быть экземпляр структуры KeyboardEvent или MouseEvent }   void sendMessage(int window_id, int message_type, void *message) { // message -- указатель на одну из структур, MouseEvent или KeyboardEvent и т.д.     struct Message msg;     msg.wnd = window_id;     msg.type = message_type;     msg.message = message;     list_append(messagesQueue, msg); }   void process_events() { // код, исполняющийся в системном процессе, о котором я говорил раньше     struct Message buf;     while (list_unshift(messagesQueue, &buf)) { // извлечение из списка событий первого события.         // Эта операция должна быть атомарной, либо нужно ставить синхронизацию.         // Критическая секция возникает при возникновении прерывания во время удаления элемента из списка.         // Или, может, не возникает?? (добавление в конец, извлечение из начала. причем, при пустом списке сюда не войдет)         // В любом случае, это всего лишь опытный образец, слава богу:)         struct Window *wnd = getWindowById(buf.wnd);         ... // вот тут как раз может идти обработка события: добавление и обработка различных флагов, модификаторов и прочей дребедени             // также, сообщение можно не посылать, а запоминать где-то, напимер, для определения двойного щелчка мыши или тех же модификаторов         list_append(wnd.messages, buf); // добавляем обработанное событие в очередь окна.             // Эта операция не должна выполняться для некоторых сообщений: например, как винда, Ctrl+Alt+Del обрабатывает сама, а окну сообщение с такой комбинацией не приходит.         setProcessActive(wnd.pid, 1); // важно также установить флаг активности процесса, которое получило сообщение. Получило, значит, ему есть что обрабатывать. Пусть сделает это     } }   void waitForMessages(struct Window *wnd) { // ожидание сообщений     setProcessActive(wnd->pid, 0); // сбрасываем флаг активности процесса. собствнно, все, пожалуй }

• обработчики irq (аппаратные прерывания) пусть выглядят примерно таким образом:
  

  C

  1 2 3 4 5 6 __declspec(naked) void irq1_handler(int ch) { // событие от клавиатуры, на входе -- считанный с портов клавиатуры и преобразованный в "нормальный" вид скан-код нажатой клавиши     struct KeyboardEvent *evt = malloc(sizeof(KeyboardEvent));     evt->scanCode = ch;     sendMessage(activeWindowId, EVT_KEYBOARD, evt);     asm("iretd"); // хотя, там еще надо APIC сбросить, ага, я помню, пару операций записи в порты. только не помню, в какие, да и сейчас на smp и x64 могло все поменяться, поэтому врать не буду }

Затем, с этими событиями и обработкой сообщений все становится крайне просто:
Примерно такой же подход, только с утроенным количеством кода, можно найти в любом хеллоуворлде на си для винапи. Конечно, где-то наверняка можно найти документацию по каждой из функций, которая там применяется, и имея относительно небольшой опыт и желание понять, как все это устроено, до всего вышеописанного можно дойти самому. Но, надеюсь, я своим постом хоть кому-то смог донести, как работают волшебные "Application.ProcessMessages; Application.DispatchMessage; Application.TranslateMessage" в делфях, что находится внутри qt-шной app.exec(), а также его механизм сигналов и слотов (они вставляются в этот основной цикл обработки сообщений), ну и что, на самом низком уровне, скрыто за main() в MFC, да и, впрочем, любой гуи-шной либы.

Вот. ну а по поводу библиотек разработки, помоему у qt самый низкий порог вхождения, плюс собственная неплохая гуи, плюс кроссплатформенность. На нем же, пожалуй, хорошо учиться основным паттернам проектирования. Впрочем, теми же качествами обладает и wxWidgets, но он немного посложнее сам по себе, и его, говорят, сложнее портировать на некоторые платформы. Из плюсов wx: огромное количество поддерживаемых языков (в т.ч. луа, хаскель и эрланг, к примеру). Visual Studio тяжелый, работает только под винду, из достоинств разве что отладка поприятнее в чем-то. Если вдруг понадобится распространять приложение, то у qt LGPL лицензия (нельзя изменять саму библиотеку и при этом не открывать код. при динамической компоновке код своего приложения можно никогда никому не показывать и продавать до тех пор, пока налоговая не возмет за одно место), у wx -- BSD подобная (делай вообще все что хочешь, желательно только лишь положить текст самой лицензии в папку с приложением, хотя и это не очень-то и обязательно). Ну а VS работает со своими runtime библиотеками, устанавливающимися на целевой машине, отдельно. там разумеется лицензий 0, так как попросту лицензировать нечего, тем более что компилятор бесплатный.

По поводу расширяемости программы. Нужно так прикинуть, насколько оно должно быть расширяемо (ну например, если это только для того, чтобы играть с другими игроками, по сети, на одном столе, и расширять нужно только всякие там карты, анимации движения, -- это одно. или все же может захотеться когда-нибудь сделать возможность игры МТТ, -- это другое). Нужно это для того, чтобы определить API (Application Programming Interface: тот функционал (интерфейс), который будет доступен плагинам) программы. Есть технологии плагинов с разделяемыми библиотеками и скриптовые. В первом случае на тех же плюсах создается длл-ка, которой при инициализации передается некий объект, содержащий реализацию функций API. Она этот указатель на этот объект сохраняет, во внутренней переменной, а потом им пользуется, когда нужно что-то сделать в контексте основной программы. Для полного щастья для разделения интерфейса/реализации API используется паттерн "мост", либо банально массив(или сложная структура) указателей на функции (неужели после первой части звучит ужасающе? вот пример, как это делается). Во втором случае, программа содержит в себе реализацию небольшой виртуальной машины для скриптового языка. При этом она (программа) также передает ей (виртуальной машине) некий объект, содержащий реализацию того, что можно сделать с основной программой. машина регистрирует у себя этот объект под некоторым именем (в самих виртуальных машинах чуть менее чем всегда используются строки, для именования переменных, это все сильно резко упрощает). Далее, когда основная программа решила, что пора бы уже поработать плагину, она дает ВМ (виртуальной машине) соответсвующее указание: мол запусти-ка скриптик из такого-то файла. и та запускает, и этому скрипту разумеется, передается то самое API в том самом глобальном объекте, которым всегда ему можно будет воспользоваться, чтобы совершить действия с основной программой (пример).
По первому варианту все ясно с деталями реализации (плюсы, компиляция, dll/so). По второму: реализаций ВМ полно. По большому счету, кроме синтаксиса языка, они различаются только производительностью. Так вот, в этом плане наиболее удачные, на данный момент, реализации -- это Google V8 и LuaJIT. Есть и еще несколько, если синтаксис этих ну совсем не катит

Для сведения, Google V8 наоптимизировали по самое небалуйся, и результат сопоставим по скорости даже с тем же си, в вычислительных задачах (!!!), по крайней мере на одном ядре. Хотя никто не мешает все трудоемкие операции перенести в плюсы, тем более, что раз уж на нем пишется приложение, это будет сделать очень и очень просто. Так что, я бы в первую очередь при выборе скриптового языка обратил бы внимание на то, насколько мне понравился его синтаксис, и насколько интересно мне его будет изучать (если придется).

По поводу алгоритма подсчета вероятности на вскрытии. Когда-то сам думал, что эта задача решается только моделированием. Но вот только пока сочинял эту хрень, я придумал следующий алгоритм.
Весь алгоритм делится на две возможности:

• после флопа. 3 карты уже открыты, а значит, осталось перебрать всего лишь (54 - 3 - 2*2) * ( (54 - 3 - 2*2) - 1 ) варианта всех возможных раскладов (для количеечтва игроков = 2 останется наибольшее количество возможных карт) в худшем случае. Это всего лишь 2162 итерации. На каждой итерации прибавляем по 1 очку игроку(ам), которые выйграли, а после всего делим количество этих очков обратно на 2162 (точнее, на 54 - 3 - N*2, где N -- количество игроков. Ну я думаю, это элементарно, если вдуматься), получая количество положительных исходов на общее их число (я не силен в теории вероятностей, но все-таки умножив на 100, вроде получим количество процентов, верно?).
• на префлопе. Таблицы. Заранее просчитанные. Еще раз напоминаю, что я не силен в тервере, однако я думаю, можно практически точно определить вероятность победы игрока A против игроков B и C, когда известны вероятности победы A против B, A против C и B против C. Я попробую как нибудь решить систему уравнений, но сейчас мозг плохо соображает, что там еще можно добавить... <аттеншен>я реально не сильно хорошо разбираюсь в тервере. если это невозможно, пожалуйста, придумайте алгоритм для решения этой, на мой взгляд, уже сильно упрощенной задачи</аттеншен>
• рекомендации по представлениям. Каждую комбинацию из 5ти карт можно представить в виде 54*53*52*51*50 карт, что составляет 379 501 200 комбинаций. То есть вполне можно уложить в обычный int. Также, учтем, что условная сила руки (это с учетом "прикупа", ну то есть как его там.. кикера. во) будет не больше, чем это число. ну никак, верно? то есть тоже int. Тогда, если делать сервер для такой игры,где все должно просчитываться со сложностью O(1), можно составить табличку на каждую комбинацию (ну, в виде массива, конечно), где A=B. A -- смещение, B -- сила. и оба -- инты.

  Не по теме:

  Даже не думайте воспроизводить это на 64 битных системах!!! используте short int, все равно все уложится в него

  
  тогда табличка будет занимать в памяти 379501200 * 4 + 379501200 * 4 = 1518004800 * 2 = 3036009600. т.е. примерно 3 гига памяти. щас по 16-32 устанавливают, даже на не очень больших серверах, так что вполне можно справиться.
  Ну а если не нужна константая сложность, то пожалуйста, просчет, на каждый вариант. Правда, по-моему, это очень много тактов. Не уверен, что уложится в десятилетие секунду, хотя, возможно, я и неправ.
• еще рах подумать над задачей о префлопе. Остальное перебором спокойно решается, я это уже показал. А вот с префлопом... хз. ну, придумать можно, что нибудь, я уверен! (даже не почти, я реально уверен... интуиция!!!)

Conslusion
Вообще, лично я бы на вашем месте подумал о реализации всего этого дела на html5+javascript(canvas). Недавно как раз познакомился с Google Closure Library, крутая штука. Производительность у canvas очень неплохая (ибо аппаратное ускорение, в большинстве современных браузеров), и есть несколько неплохих библиотек для него (пока что мне больше всех понравился fabric.js, хотя в той же GCL есть Canvas, пока еще с ним не разобрался). Хотя, скорее всего, можно обойтись для начала и без canvas-а, там и так можно сделать прикольную анимацию, и кучу красивостей. А сервер бы реализовал на эрланге. Но это конечно, только лишь мое личное предпочтение, ибо я, по большей части, web-программист, хоть и не фронтэндер (пхп-шник, разумеется). Просто прельщает возможность, скажем, зайти на сайт, и ничего не устанавливая, поиграть в онлайне с кем угодно.