Comments 43
habrastorage.org/files/1e8/9d9/ded/1e89d9ded66447ea964641a880a27be5.png
«Сапер» подстраивался под игрока, иногда убирая из-под открываемой ячейки мину. Если судить по ХР версии, то перестраивает поле когда Вы первым кликом попадаете на мину и больше никогда не меняет. Можно убедиться посмотрев заполнение поля в сапере для той же ХР, под спойлером c# код распределения цифр (для онлайне не пойдет — нужно знать расположение мин, но возможно кому-то будет интересно)
private void OpenMap()
{
this.m_processes = Process.GetProcesses();
foreach (Process process in this.m_processes)
{
if (process.ProcessName.ToLower() == "winmine")
{
this.wText = process.MainWindowTitle;
int num = 6;
int num2 = 0x31;
int num3 = 0x10;
int x = this.X;
int y = this.Y;
int[,] arr = this.Read(process);
IntPtr hWnd = FindWindow(null, "Сапер");
if (hWnd != IntPtr.Zero)
{
this.m_procHandle = process.Handle;
if (GetWindowRect(hWnd, out this.rct))
{
Graphics graphics = Graphics.FromHwnd(hWnd);
Pen pen = new Pen(Color.Black, 1f);
for (int i = 0; i < y; i++)
{
for (int j = 0; j < x; j++)
{
if (arr[i, j] == 1)
{
graphics.DrawEllipse(pen, new Rectangle(new Point((num + (num3 / 2)) + (num3 * j), (num2 + (num3 / 2)) + (num3 * i)), new Size(10, 10)));
continue;
}
int num8 = this.Count(arr, i, j);
if (num8 > 0)
{
Brush black = Brushes.Black;
switch (((num8 - 1) % 3))
{
case 0:
black = Brushes.Blue;
break;
case 1:
black = Brushes.Green;
break;
case 2:
black = Brushes.Red;
break;
}
graphics.DrawString(num8.ToString(), this.Font, black, (PointF) new Point((num + (num3 / 2)) + (num3 * j), (num2 + (num3 / 2)) + (num3 * i)));
}
}
}
}
}
break;
}
}
}
private int[,] Read(Process process)
{
this.m_scanLength = 1;
this.m_startAddress = 0x1005361;
byte[] lpBuffer = new byte[this.m_scanLength];
byte[] buffer2 = new byte[this.m_scanLength];
int[,] numArray = new int[1, 1];
if (process != null)
{
this.m_intptrProcess = OpenProcess(0x1f0fff, false, (uint) process.Id);
ReadProcessMemory(this.m_intptrProcess, (IntPtr) 0x10056ac, buffer2, 1, out this.m_bytesRead);
this.X = buffer2[0];
buffer2 = new byte[1];
ReadProcessMemory(this.m_intptrProcess, (IntPtr) 0x10056a8, buffer2, 1, out this.m_bytesRead);
this.Y = buffer2[0];
numArray = new int[this.Y + 2, this.X + 2];
StringBuilder builder = new StringBuilder();
for (int i = 0; i < this.Y; i++)
{
for (int j = 0; j < this.X; j++)
{
ReadProcessMemory(this.m_intptrProcess, (IntPtr) ((this.m_startAddress + (i * 0x20)) + j), lpBuffer, 1, out this.m_bytesRead);
if (lpBuffer[0] == 0x8f)
{
numArray[i, j] = 1;
}
builder.Append(lpBuffer[0].ToString() + "\t");
lpBuffer = new byte[this.m_scanLength];
}
}
}
return numArray;
}
private int Count(int[,] arr, int i, int j)
{
return (((((((this.Count2(arr, i - 1, j - 1) + this.Count2(arr, i - 1, j)) + this.Count2(arr, i - 1, j + 1)) + this.Count2(arr, i, j - 1)) + this.Count2(arr, i, j + 1)) + this.Count2(arr, i + 1, j - 1)) + this.Count2(arr, i + 1, j)) + this.Count2(arr, i + 1, j + 1));
}
private int Count2(int[,] arr, int i, int j)
{
if ((((i >= 0) && (j >= 0)) && (i < arr.GetLength(0))) && (j < arr.GetLength(1)))
{
return arr[i, j];
}
return 0;
}
Тестовое приложение.
Ну это так, в тему — оказывается, очень многие не в курсе. Позволяет и мышкой возить программно и цвет пикселя по координатам определять.
В вопросах вероятностных эвристик надо добавить ещё вероятность для дальних клеток (то есть клеток, у которых нет свободных соседних).
Для рассчёта этой вероятности нужно посчитать число гарантировано «крайних» мин, вычесть его из оставшегося числа, и для всех глубинных полей посчитать вероятность нахождения там мины. Это будет «максимальная вероятность».
Дальше надо посчитать максимальное число возможных «крайних» мин, и повторить тот же рассчёт — будет «минимальная вероятность» для глубинных полей.
Эти вероятности надо учитывать, когда решать — открывать крайнее поле с вероятностью мины 0.14 или глубинное поле с максимальной вероятностью в 0.13 и минимальной в 0.10.
В вверху две двойки. Можно гарантировать, что в их окрестности есть 1 и только 1 мина.
Такой метод может помочь, когда нельзя сделать точный выбор из небольших групп. Ну и по прогнозам, должно работать достаточно быстро, даже если в группу будет входить 100 ячеек, хотя казалось бы возможных вариантов — 2^100.
Ну и плюс, было бы круто сделать робота который бы не используя вероятности мог решать решаемые поля, и на основе этого робота перегенерировать поле до тех пор пока оно не станет гарантированно решаемым.
Вот тут описал их http://pikabu.ru/story/eshchyo_odin_variant_prokhozhdeniya_sapera_3027351
Вот тут моя реализация этих правил на C#
https://www.dropbox.com/s/d4fype0rjfhuc5p/MinesFounder.rar?dl=0
Неправильно работает алгоритм по обработке пересечений групп.
Вот как решил алгоритм следующую ситуацию:
Он произвел помимо прочего такие преобразования:
(1273654, 3) - (1, 1) -> (273654, 2)
(273654, 2) X (87, 1) -> (7, 1), (23654, 1), (8, 0)
что вполне соответствует алгоритму, но очевидно неправильно.
Возможно просто какой-то нюанс преобразований автор в статье забыл упомянуть, но я не могу понять как исправить.
Доработал идею с группами.
Ввёл у группы понятие "минимально возможное кол-во мин" и "максимально возможное кол-во мин". При первоначальном создании групп заполняем одинаковым значением.
Переделал логику обработки пересечения групп, обобщив ее, тем самым избавившись от отдельного кейса "группа содержит группу". Из двух пересекающихся групп A и B создаем от одной до трех новых групп (но не плодя дубликаты), при этом старые группы не удаляем (это важно, но приходится запоминать кого с кем уже пересекали, чтобы повторно в будущем не пересекать):
A = {cells: ..., min: ..., max: ...}; // Массив ячеек, минимальное кол-во мин, максимальное кол-во мин
B = {cells: ..., min: ..., max: ...};
Добавляем новую группу C = {
cells: A.cells.getOverlap(B.cells), // Пересечение массивов ячеек
min: m0,
max: M0
}, где m0 и M0 считаем так:
m0a = min(max(A.min - (A.size - C.size), 0), C.size);
M0a = min(max(A.max, 0), C.size);
m0b = min(max(B.min - (B.size - C.size), 0), C.size);
M0b = min(max(B.max, 0), C.size);
m0 = max(m0a, m0b);
M0 = min(M0a, M0b);
Если разность массивов ячеек A минус B не пуста, добавляем группу D = {
cells: A.cells.getSubtraction(B.cells),
min: m1,
max: M1
}, где m1 и M2 считаем так:
m1 = min(max(A.min - C.max, 0), D.size);
M1 = min(max(A.max - C.min, 0), D.size);
Ну и соответственно если разность массивов ячеек B минус A не пуста, по аналогии добавляем группу E.
Также важно, при совпадении массива ячеек у двух групп удаляем не рандомную группу, а ту у которой min меньше и max больше, одновременно, иначе не удаляем никакую.
Алгоритмы логики бота для игры «Сапёр»