Для чего создана программка "Минер" - вы как думаете? Есть версия: для убийства времени - раз, для развития смекалки - два. Я согласен с этой точкой зрения, да только понимаю ее по-своему - и, вместо того чтобы миллионы раз кликать по клавишам, решил написать программищу, чтобы играла она в "Минера" за меня. Тут и убитие времени налицо, и развитие смекалки (в те времена она меня еще интересовала).

 

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

 

Оговорки: поскольку все это писалось давно, еще на Windows 95, то полученный код работает только на тех еще платформах. Связано это с... ну, короче, с чем-то там связано - я и забыл уже. То же самое касается и компилятора - компилировал я на Visual Studio 4. Вот недавно пересобирал на NET - проблем вроде не обнаружилось, но размер исполнительного файла уже не тот. Прилагаю его в том виде, как этот файлик был раньше, потому что он, что называется known good - а что там нет троянов, можете посмотреть в IDA :-).

 

Итак, проблема такая - поиграть в "Минера" с помощью искусственного интеллекта. Задачка как бы из двух частей: сначала подключиться к этому "Минеру" - так сказать, присобачить к нему искусственные глаза и руки. Задача номер два - по увиденному на игровом поле принять decision и сделать полезные ходы. Чтобы не путать агонию с оргазмом, вся программка так и заточена - как два отдельных файлика, а именно: Intro.cpp и ontimer.cpp. Второе название чисто историческое, поскольку изначально наш ИИ получал управление по таймеру, который (таймер) сам минер и регистрирует для отсчета секунд. Но поскольку секунда в наше время - это примерно 5 млрд. операций процессора, то в дальнейшем, как вы увидите, управление получается по нажатию секретной клавиши AnyKey.

 

Сначала посмотрим, как нам удалось "поймать" нашего неуловимого "Минера" - а потом решим, что с ним делать. Вот вам intro.cpp размером 1,5 Кб. Комментарии - как были, на английском, потому что на тот момент у меня и русской-то раскладки не было, не то что Винды.

 

#include
#include
#include "colors.h"

HWND hWND=NULL;
DWORD tID=0;

void OnTimer (HWND hwnd);
BOOL CALLBACK EnumThreadWndProc (HWND hwnd, LPARAM lParam) {
BOOL bRet=TRUE;
LONG gwlStyle=GetWindowLong (hwnd,GWL_STYLE);
LONG gwlExstyle=GetWindowLong (hwnd,GWL_EXSTYLE);
if ((gwlExstyle==0x00000100)&&((gwlStyle==0x14CA0000)||(gwlStyle==0x34CA0000))) {
hWND=hwnd; bRet=FALSE;// bug: gwlStyle may be 14ca0000 OR 34ca0000
}
return bRet;
}

BOOL MazaFakaFound (VOID) {
EnumWindows ((WNDENUMPROC)&EnumThreadWndProc,0);
if (hWND!=NULL) tID=GetWindowThreadProcessId (hWND,NULL);
return (hWND!=NULL);
}

_declspec (dllexport) LRESULT CALLBACK GetMsgProc
(int code,WPARAM wParam,PMSG lParam) {
static BOOL inside=FALSE;
MSG msg = (*lParam);
if (inside) {return 0;}; inside=TRUE;
if (msg.message==WM_KEYDOWN) {// было WM_TIMER
hWND=msg.hwnd;
if ((hWND==GetForegroundWindow ())&&(!IsIconic (hWND))) {
OnTimer (hWND);
}
}
inside=FALSE; return 0;
}

int WINAPI WinMain (HINSTANCE hIns, HINSTANCE hPrevIns, LPSTR lpCmd,int nShow) {
WinExec ("WINMINE.EXE", SW_RESTORE); Sleep (500);
if (MazaFakaFound ()) {
HMODULE hSelf=GetModuleHandle (NULL);
HOOKPROC pExp = (HOOKPROC) GetProcAddress (hSelf, (LPCSTR)1);
HHOOK hHook=SetWindowsHookEx (WH_GETMESSAGE,pExp,hSelf,tID);
} return 0;
}
 

Как всегда в С, все начинается с конца. Нормальное наше оконное приложение Windows никакого окна не создает, а сразу порывается запустить "Минера" и полсекунды ждет, пока он запустится. Это, конечно, моветон - скажете вы - нужно запускать процесс в спящем состоянии, устанавливать на него хуки и потом растормаживать его. Угу-угу, но мой метод лучше по двум причинам: во-первых, если "Минер" уже запущен, то второй экземпляр не стартует. В вашем случае вы плохо кончите, но в моем это неважно; потом - все равно какого "Минера" ловить, первого или второго. Ну а во-вторых, мой код просто короче. Разве что приходится ждать полсекунды, пока диски раскрутятся,- но поскольку это работает, то оправдываться не стану.

 

Обратите внимание на то, куда ведет нас установленный хук: на наш же экзешник, хендлер на который мы тут же и получаем. Единственное, что хочется при этом сделать, это тут записать, а там прочитать. А вот этого (совсем как у Подервянского), как раз и нельзя - потому что для Винды наш модуль, с одной стороны, экзешник, а с другой - библиотека, так что working set будет проинициализирован по-новой. И, записав "при этой жизни", в той мы ничего не получим. Это в данном случае нам так повезло, что мы хотим знать хэндлер нашего потерпевшего окна, а когда наш хук получает управление, то в качестве одного из параметров мы получаем наше окно.

 

Не совсем ясный момент: во время перебора окон первого уровня - как нам найти наше? Первая и вторая идея - по имени класса и по заголовку. Можно - но вот только в разных локалях эти дела будут различаться (даже класс!), так что я отлавливаю по стилям окна. Это, конечно, очень стремное допущение - например, по тем же стилям, хоть они и довольно необычные, ищется также и Personal Web Server. Так что это может стать той причиной, по какой эта программа не станет у вас работать.

 

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

 

По этой части, кажется, все - остальное в доках по Windows API.

 

Часть 2. Именно интеллект, в натуре

 

#include
#include
#include "colors.h"

void OnTimer (HWND hWND) {
RECT r;
GetClientRect (hWND,&r); int dx=(r.right-24)/16; int dy=(r.bottom-67)>>4;
// bug: width of x-borders may be 12 OR 13 (case if 8x8 set on startup)
int x,y;
int cells [30][24];
for (x=0;x<29;x++) for (y=0;y<23;y++) cells [x][y]=CV_UNKNOWN;
int xBase=0, yBase=0; HDC hdc=GetDC (hWND);
for (x=0;xfor (y=0;yxBase=12+(x<<4); yBase=55+(y<<4); // 12 and 56 - offsets from left and top
if (Is (0,0,clWHITE)) {
if (Is (5,4,clRED3)) cells [x][y]=CV_FLAG;
else cells [x][y]=CV_UNDEFINED;
} else {
switch (GetPixel (hdc,xBase+9,yBase+11)) {//examine base point 9,11
case clBLUE1: cells [x][y]=1; break;
case clGREEN2: cells [x][y]=2; break;
case clRED3:
if (Is (8,9,clBLACK)) cells [x][y]=CV_BOOM;
else cells [x][y]=3; break;
case clBLUE4: cells [x][y]=4; break;
case clRED5: cells [x][y]=5; break;
case clBLUE6: cells [x][y]=6; break;
case clGREY:
switch (GetPixel (hdc,xBase+8,yBase+8)) {// another good point
case clGREY: cells [x][y]=0; break;
case clRED3: cells [x][y]=CV_MIST; break;
case clBLACK: cells [x][y]=CV_BOMB; break;
}
}
}
}
}
ReleaseDC (hWND,hdc); // recognizing finished

int cntUndef,cntFlags,cntInside; POINT Undefs [8];
for (x=0;xfor (y=0;ycntUndef=0; cntFlags=0; cntInside=cells [x][y];
if (cntInside>0) {// column 1
if (x!=0) {
if (y!=0) Care (x-1,y-1); Care (x-1,y); if (y!=(dy-1)) Care (x-1,y+1);
}
if (y!=0) Care (x,y-1); if (y!=(dy-1)) Care (x,y+1); // column 2
if (x!=(dx-1)) {// column 3
if (y!=0) Care (x+1,y-1); Care (x+1,y); if (y!=(dy-1)) Care (x+1,y+1);
}
}
if ((cntUndef>0)&&(cntInside==cntFlags+cntUndef))
for (int i=0;i}
}
for (x=0;xfor (y=0;y<23;y++) {// avoiding neutralisation thru double marking
if (cells [x][y]==CV_NEWFLAG) {
xBase=12+(x<<4); yBase=55+(y<<4);
PostMessage (hWND,WM_RBUTTONDOWN,0,(yBase<<16)+xBase+2);
PostMessage (hWND,WM_RBUTTONUP,0,(yBase<<16)+xBase+2);
}
}
}
for (x=0;xfor (y=0;ycntUndef=0; cntFlags=0; cntInside=cells [x][y];
if (cntInside>0) {// column 1
if (x!=0) {
if (y!=0) Care (x-1,y-1); Care (x-1,y); if (y!=(dy-1)) Care (x-1,y+1);
}
if (y!=0) Care (x,y-1); if (y!=(dy-1)) Care (x,y+1); // column 2
if (x!=(dx-1)) { // column 3
if (y!=0) Care (x+1,y-1); Care (x+1,y); if (y!=(dy-1)) Care (x+1,y+1);
}
}
if ((cntUndef>0)&&(cntInside==cntFlags)) {// all nearest flags marked
xBase=12+(x<<4); yBase=55+(y<<4); // stripe
PostMessage (hWND,WM_MBUTTONDOWN,0,(yBase<<16)+xBase+2);
PostMessage (hWND,WM_MBUTTONUP,0,(yBase<<16)+xBase+2);
}
}
}
}
 

Тут как раз все начинается с начала. А в начале первая наша задача такая - разобрать игровое поле. Хакать "Минера" и вытрушивать из него это поле - задача несложная, но это 100% против правил. Поэтому мы читаем экран "Минера", разбираемся какого не какого размер в клеточках и сканируем все клеточки на предмет чего там стоит. Сканируем мы без состояния, то есть между получениями управления мы ничего не храним. Это имеет простое оправдание: мы не мешаем пользователю делать свои ходы - а раз так, то между нашими вмешательствами пользователь может не только походить, но и начать новую игру с другими настройками. В принципе, можно было бы перехватывать все это, но на самом деле это все не нужно - можно просто не делать никаких предположений, а каждый раз определять все заново, тогда точно не будет рассинхронизации оригинала и кэша.

В процессе распознавания образов мы инспектируем последовательно три точки нашей клеточки и на основании этого определяем, какой в ней стоит значок. Может возникнуть вопрос - а откуда мы знаем, какие клеточки проверять? Ответ прост: ниоткуда. Просто я достал все пиктограммки (благо, размер у них постоянный 16 (16) из "Минера", натравил на них вспомогательную программку (здесь не приводится, да она и не сохранилась), которая нашла три полезные точки (таких триплетов было много, а вот двух точек недостаточно), однозначно определяющие распознаваемый образ.

 

Сами образы закодированы специальными константами. Специальное в них следующее: если на клеточке стоит цифра, то значение константы как раз и равно этой цифре, а для всех "спецсимволов" значения отрицательны - в дальнейшем это многое упрощает. Определения заданы в файле colors.h размером 800 байт.

 

// definition de colores / BLUE1 means blue as 1
#define clWHITE  0xffffff
#define clGREY  0xc0c0c0
#define clBLACK  0
#define clBLUE1  0xff0000
#define clGREEN2  0x008000
#define clRED3  0x0000ff
#define clBLUE4  0x800000
#define clRED5  0x000080
#define clBLUE6  0x008080
// checks for some pixel of cell has expected color

#define Is (x,y,cl) GetPixel (hdc,xBase+x,yBase+y)==cl

#define CV_UNKNOWN  -1
#define CV_UNDEFINED  -2
#define CV_FLAG   -3
#define CV_BOMB   -4
#define CV_BOOM   -5
#define CV_MIST   -6
#define CV_NEWFLAG  -7

// counts Undefs and Flags around current cell
#define Care (ix,iy) if (cells [ix][iy]==CV_UNDEFINED)
{Undefs [cntUndef].x=ix; Undefs [cntUndef].y=iy;;cntUndef++;}
else if ((cells [ix][iy]==CV_FLAG)||(cells [ix][iy]==CV_NEWFLAG)) cntFlags++
 

Как видите, в этом файлике, кроме констант, определены два макроса. Первый просто анализирует, является ли точка с координатами x, y точкой цвета cl и используется ли этот макрос только на этапе распознавания образов. Второй макрос посложнее, но смысл его таков: если клеточка с такими-то координатами типа "чистое молоко" (то есть пустая, ничего на ней не стоит) - то к переменной cntUndefined прибавляется 1. Если там стоит флажок (осторожно, мина!), или если мы уже определили в ходе наших рассуждений, что там нужно поставить такой значок - то добавляется переменная cntFlags. Все это оттого, что для каждой клеточки мы будем перебирать соседей и считать, сколько там непонятного и сколько там флагов.

 

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

 

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

 

Тут был один пробой, который пришлось выкупить. Некоторые "новомины" подпадали под маркировку с двух сторон. То есть, если на них кликнуть разик по одной и потом по другой, то мина снова снимется в ноль. Поэтому все новомаркированные сначала помечаются, а потом одноразово "компостируются" кликом правой мышки.

 

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

 

Немного о наших кликах. Поскольку, пока работает наша программа, оригинальный минерский код не получает управления, то все наши клики накапливаются в очереди сообщений и потом, когда нам надоест "играться", все клики произойдут в одно мгновение на ваших изумленных глазах.

 

Поскольку мы привязали хук на KEYDOWN, вы можете играть в игру сколько угодно, пока не надоест,- наша прога вмешиваться не будет. Но когда вы попросите помощи, то есть нажмете AnyKey, программа начнет вам помогать с периодичностью 0,1 сек - то есть со скоростью повтора генерации KEYDOWN (typematic). Хотя программа и будет анализировать игру с такой скоростью, но не каждый раз она будет находить полезные ходы. Тут уж такое дело - можно предложить программе повычислять вероятностные ходы, но тогда она будет проигрывать с такой скоростью, что вы не сможете насладиться игрой (сама игра построена по вероятностному принципу, есть ситуации "или-или").

 

В заключение скажу, что все это было давно,- но, если мне не изменяет память, рекорд с этой программой на большом поле был около четырех секунд, а без нее - около 160-ти (или 60-ти?).

 

По улучшению: пиво тому, кто доделает этот код для XP. Кроме того, наблюдались ситуации, когда ход был, а прога его не нашла - значит, нужна еще какая-то эвристика. Если же вы хотите насладиться не только результатами, но и самим процессом - то замените WM_KEYDOWN на WM_TIMER. Теперь игра превратится в медленную динамическую скульптуру - Памятник Пользователю XX-го века.

2004.05.07
19.03.2009
В IV квартале 2008 г. украинский рынок серверов по сравнению с аналогичным периодом прошлого года сократился в денежном выражении на 34% – до $30 млн (в ценах для конечных пользователей), а за весь календарный год – более чем на 5%, до 132 млн долл.


12.03.2009
4 марта в Киеве компания Telco провела конференцию "Инновационные телекоммуникации", посвященную новым эффективным телекоммуникационным технологиям для решения задач современного бизнеса.


05.03.2009
25 февраля в Киеве компания IBM, при информационной поддержке "1С" и Canonical, провела конференцию "Как сохранить деньги в условиях кризиса?"


26.02.2009
18-19 февраля в Киеве прошел юбилейный съезд ИТ-директоров Украины. Участниками данного мероприятия стали ИТ-директора, ИТ-менеджеры, поставщики ИТ-решений из Киева, Николаева, Днепропетровска, Чернигова и других городов Украины...


19.02.2009
10 февраля в Киеве состоялась пресс-конференция, посвященная итогам деятельности компании "DiaWest – Комп’ютерний світ" в 2008 году.


12.02.2009
С 5 февраля 2009 г. в Киеве начали работу учебные курсы по использованию услуг "электронного предприятия/ учреждения" на базе сети информационно-маркетинговых центров (ИМЦ).


04.02.2009
29 января 2009 года в редакции еженедельника "Computer World/Украина" состоялось награждение победителей акции "Оформи подписку – получи приз!".


29.01.2009
22 января в Киеве компания "МУК" и представительство компании Cisco в Украине провели семинар для партнеров "Обзор продуктов и решений Cisco Small Business"

 

 
 
Copyright © 1997-2008 ИД "Комиздат".