Задача:
Сможете ли вы побить мировой рекорд по решению старого доброго сапера? Несколько раз подряд :)
В задаче требовалось написать бота, который мог бы выиграть в традиционного “Сапёра” на уровне “профессионал” за 50 секунд несколько раз подряд (как выяснилось, “несколько” было равно трём).
Первая пришедшая в голову идея заключалась в том, что можно написать приложение, которое распознаёт экран и моделирует щелчки мышью. Однако Лёша Ропан заметил, что взаимодействие с сервером состоит в отправке post-запросов с координатами клетки, в которую был произведён щелчок мышью, и номером кнопки (1 – левая, 2 – правая). Сервер же умеет по соответствующему урлу отдавать картинку с текущим состоянием поля.
Реализовывать бота я решил на питоне. Для отправки запросов была использована довольно удобная библиотека requests (http://docs.python-requests.org/en/latest/), для работы с картинкой поля — PIL (http://www.pythonware.com/products/pil/).
Первое, что было необходимо сделать, это научиться преобразовывать картинку в двумерный массив, где в каждой ячейке была бы записана соответствующая информация (клетка ещё не открыта/заведомо пустая/помеченная флажком/содержит цифру). Сначала было желание воспользоваться каким-то алгоритмом машинного обучения для классификации каждой клетки, например, нейронными сетями. Но для этого пришлось бы готовить обучающую выборку, а тратить на это время не хотелось. В процессе обдумывания способа распознавания я заметил, что цифра каждый раз рисуется каким-то одним цветом, хотя этот цвет и меняется при получении каждой картинки. Также и фон каждый раз при получении картинки случайным образом зашумлялся сервером. Я попробовал посчитать количество пикселей, из которых состоит каждая цифра (это число было постоянным) и оказалось, что этого достаточно для того, чтобы однозначно восстановить цифру. Так, например, единица состоит из 40 пикселей, а шестёрка — из 72. Клетки, не содержащие цифр, выглядят всегда одинаково и распознаются довольно примитивно (есть красный цвет — флажок, только серый цвет — неоткрытая клетка, и так далее).
После того, как необходимая информация получена, надо понять, в какие клетки мы заведомо можем поставить флажки, а какие безопасны для открывания. Для начала я решил применить совсем банальные проверки вида “если возле клетки с цифрой уже стоит необходимое количество флажков, то все остальные клетки безопасны” и “если возле клетки с цифрой осталось ровно столько неоткрытых клеток, сколько не установлено флажков, то все эти клетки надо пометить флажками”. Сначала я запрашивал с сервера картинку после каждого щелчка, однако на её получение и парсинг уходило довольно много времени и за 50 секунд бот успевал открыть около 30% поля, что было явно далеко от победы.
Я понял, что можно отослать сразу все запросы, которые следуют из текущей картинки, и только затем запросить новую, открыв сразу все безопасные клетки. Дела пошли значительно лучше. Бот стал успевать проигрывать прежде, чем заканчивались 50 секунд :) А дело было в том, что в какой-то момент однозначно определённые клетки заканчивались, и бот начинал открывать случайные клетки, что в итоге не приводило ни к чему хорошему :) Понаблюдав некоторое время за поведением бота и попробовав несколько вариантов случайного выбора клеток, я осознал, что так я к успеху не приду. Были очевидные моменты, когда решение можно было принять и без случайного выбора клетки. Например, в случае на картинке ниже нетрудно понять, что в центральной закрытой клетке мины быть никак не может. Такой вывод нельзя сделать, рассматривая каждую цифру по отдельности.
Я решил написать перебор возможных вариантов, который должен был значительно улучшить поведение бота. Его суть заключалась в следующем.
- Рассмотрим некоторую уже открытую цифру.
- Переберём все возможные расположения мин вокруг неё. Таких расположений в типичной ситуации 3-5, хотя и в худшем случае их может быть C(8, 4) = 70.
- Для каждого расположения мин рассмотрим близлежащие клетки с цифрами и убедимся, что текущее расположение не противоречит ни одной из них. Если противоречие нашлось, данное расположение мин невозможно.
- Для всех полученных возможных расположений посмотрим, не существует ли такой клетки, в которой мина стоит всегда, либо, наоборот, никогда.
- Если такая клетка есть, то её можно либо открыть, либо пометить флажком.
Данный перебор весьма успешно справляется со случаем, описанным выше, а также с рядом других, более нетривиальных случаев. Бот перестал паниковать и делать случайные ходы при первой же возможности, и стал опять не успевать по времени :) Я заметил, что значительное количество времени уходит на отсылку всех запросов, и подумал, что было бы неплохо сделать их асинхронными. Асинхронная отправка запросов нашлась в библиотеке grequests и была с успехом внедрена в программу.
После этого бот без особого труда выиграл три раза подряд с пятой попытки, и флаг оказался у меня =)
Ниже я предлагаю посмотреть вам небольшую запись одной из победных игр :) На 32-34 секундах видно, как в неопределённой ситуации с помощью перебора вычисляется сначала клетка с заведомой миной, а затем — заведомо безопасная клетка, в которой открывается единичка.
Спасибо за внимание!
Исходный код бота:
import requests as R from PIL import Image from StringIO import StringIO from collections import defaultdict from random import randint, choice import grequests as GR import sys DEBUG = True if DEBUG: import pygame token = "<TOKEN>" MAIN_URL = "http://saper.quals.ructf.org/" IMAGE_URL = MAIN_URL + "games/{0}.png".format(token) W = 480 H = 256 SX = W / 16 SY = H / 16 deltas = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] COOKIES = { "PHPSESSID": "gae4jif8k15hl4lkrttami04d3" } CLOSED = 10 MINE = 11 EMPTY = 12 FLAG = 13 FREE = 14 VALUE = { 40: 1, 65: 2, 62: 3, 56: 4, 70: 5, 72: 6, 148: CLOSED, } TXT = { 14: "H", 10: ".", 11: "*", 12: "_", 13: "F", 1: "1", 2: "2", 3: "3", 4: "4", 5: "5", 6: "6", } if DEBUG: pygame.init() screen = pygame.display.set_mode([W, H + H]) font = pygame.font.SysFont("None", 18) def get_image(): r = R.get(IMAGE_URL) return Image.open(StringIO(r.content)) def text(s, x, y): if DEBUG: screen.blit(font.render(str(s), 0, (255, 255, 255)), (x, y)) async_list = [] closed_nb = [] left = [] mem_bf = {} sent = set() cells_to_check = set() for x in xrange(SX): for y in xrange(SY): cells_to_check.add((x, y)) def resp(response, **kwargs): print response.text if "gratz" in response.text: print >>sys.stderr, "Win!!! ^_^" sys.exit(0) if "time limit" in response.text: print >>sys.stderr, "Failed by TL =/" sys.exit(0) # while True: # pass def send_click(click): if click in sent: return sent.add(click) # print "I want to click", click r = R.post(MAIN_URL + "engine.php", data={"i": click[1], "j": click[0], "btn": click[2]}, cookies=COOKIES, hooks={"response": resp}) async_list.append(r) # print r # print r.text def near(x, y): for dx, dy in deltas: nx, ny = x + dx, y + dy if 0 <= nx < SX and 0 <= ny < SY: yield (nx, ny) def check(closed, nb, cur): # print "Check mask", bin(cur) for x, y in nb: unknown_closed = closed_nb[x][y] cur_left = left[x][y] # print "Look at nb (%d %d): unknown_closed = %d, cur_left = %d" % (x, y, unknown_closed, cur_left) for i, (xc, yc) in enumerate(closed): if abs(xc - x) <= 1 and abs(yc - y) <= 1: unknown_closed -= 1 if (cur & (1 << i)) > 0: cur_left -= 1 # print unknown_closed, cur_left if cur_left < 0 or cur_left > unknown_closed: return False return True def rec(i, n, closed, left, nb, possible, cur): if left > n - i: return if i == n: if check(closed, nb, cur): # print "I want to append!" possible.append(cur) else: if left > 0: rec(i + 1, n, closed, left - 1, nb, possible, cur | (1 << i)) rec(i + 1, n, closed, left, nb, possible, cur) def go_brute_force(data, unknown): for x, y in unknown: closed = [] left = data[x][y] nb = set() for nx, ny in near(x, y): if data[nx][ny] == CLOSED: closed.append((nx, ny)) for nx2, ny2 in near(nx, ny): if 1 <= data[nx2][ny2] <= 8: nb.add((nx2, ny2)) if data[nx][ny] == FLAG: left -= 1 if (x, y) in mem_bf and mem_bf[(x, y)] == len(closed): continue mem_bf[(x, y)] = len(closed) possible = [] # print "Running rec with closed={0}, left={1}, nb={2}".format(closed, left, nb) rec(0, len(closed), closed, left, nb, possible, 0) # print "Result: {0}".format(possible) _and = (1 << len(closed)) - 1 _or = 0 for mask in possible: _or |= mask _and &= mask ret = False if _or != (1 << len(closed)) - 1: for i, z in enumerate(closed): if (_or & (1 << i)) == 0: print "There is no way for mine to be in (%d %d)" % (z[0], z[1]) send_click((z[0], z[1], 1)) ret = True if _and != 0: for i, z in enumerate(closed): if (_and & (1 << i)) > 0: print "For sure there is mine in (%d %d)" % (z[0], z[1]) send_click((z[0], z[1], 2)) ret = True if ret: return print "Bruteforced", x, y, "- nothing good" def find_clicks(data): sent.clear() global async_list print "To check:", len(cells_to_check) if not cells_to_check: while True: sent.clear() to_remove = [] prev = -1 unknown = set() global closed_nb global left closed_nb = [] left = [] row = [0] * SY for _ in xrange(SX): closed_nb.append(list(row)) left.append(list(row)) while len(async_list) != prev: prev = len(async_list) for x, y in cells_to_check: if data[x][y] == EMPTY: to_remove.append((x, y)) if 1 <= data[x][y] <= 8: flags, closed = 0, 0 for dx, dy in deltas: nx, ny = x + dx, y + dy if 0 <= nx < SX and 0 <= ny < SY: if data[nx][ny] == CLOSED: closed += 1 if data[nx][ny] == FLAG: flags += 1 left[x][y] = data[x][y] - flags closed_nb[x][y] = closed if closed > 0 and flags + closed == data[x][y]: to_remove.append((x, y)) for dx, dy in deltas: nx, ny = x + dx, y + dy if 0 <= nx < SX and 0 <= ny < SY: if data[nx][ny] == CLOSED: send_click((nx, ny, 2)) to_remove.append((nx, ny)) data[nx][ny] = FLAG elif flags == data[x][y]: to_remove.append((x, y)) for dx, dy in deltas: nx, ny = x + dx, y + dy if 0 <= nx < SX and 0 <= ny < SY: if data[nx][ny] == CLOSED: send_click((nx, ny, 1)) else: unknown.add((x, y)) if data[x][y] == FREE: send_click((x, y, 1)) if not sent: go_brute_force(data, unknown) if not sent: while True: x = randint(0, SX - 1) y = randint(0, SY - 1) if data[x][y] == CLOSED: break print "Sending random click... (skype:worried)" send_click((x, y, 1)) print "Send %d clicks..." % len(async_list) # GR.map(async_list) async_list = [] for z in to_remove: if z in cells_to_check: cells_to_check.remove(z) def parse_and_view(image): if DEBUG: screen.fill((0, 0, 0)) pixels = list(image.getdata()) data = [] lost = False for xc in xrange(SX): data.append([]) for yc in xrange(SY): cell = [] for dx in xrange(16): cell.append([pixels[(xc * 16 + dx) + (yc * 16 + dy) * W] for dy in xrange(16)]) cnt = defaultdict(int) mmax = -1 mmin = 1000 for x in xrange(16): for y in xrange(16): c = (cell[x][y][0] + cell[x][y][1] + cell[x][y][2]) / 3 cell[x][y] = c # screen.set_at((xc * 16 + x, yc * 16 + y), (c, c, c)) cnt[ cell[x][y] ] += 1 if cell[x][y] > mmax: mmax = cell[x][y] if cell[x][y] < mmin: mmin = cell[x][y] s = 0 for x in xrange(6, 10): for y in xrange(6, 10): s += cell[x][y] s /= 16 # text(s, xc * 16 + 2, yc * 16 + 2) # continue if (s == 63): data[xc].append(MINE) lost = True continue if (s == 134): data[xc].append(FLAG) continue if (s == 0): data[xc].append(FREE) continue if mmax - mmin < 60: data[xc].append(EMPTY) continue mc = max(cnt.itervalues()) # text(mc, xc * 16 + 2, yc * 16 + 2) data[xc].append(VALUE[mc]) assert(len(data[xc]) == SY) for yc in xrange(SY): for xc in xrange(SX): print TXT[data[xc][yc]], print if lost: closed = 0 mines = 0 for xc in xrange(SX): for yc in xrange(SY): if data[xc][yc] == CLOSED: closed += 1 if data[xc][yc] == MINE: mines += 1 print >>sys.stderr, "Lost game with %d mines left and %d closed cells :(" % (mines, closed) sys.exit(0) if DEBUG: for xc in xrange(SX): for yc in xrange(SY): text(TXT[data[xc][yc]], xc * 16 + 2, yc * 16 + 2) for x in xrange(W): for y in xrange(H): screen.set_at((x, y + H), pixels[x + y * W]) pygame.display.update() find_clicks(data) # send_click(click) def main(): r = R.get(MAIN_URL, cookies=COOKIES) # for q in xrange(3): # x = randint(0, SX - 1) # y = randint(0, SY - 1) # send_click((x, y, 1)) while True: image = get_image() parse_and_view(image) if DEBUG: for event in pygame.event.get(): if event.type == pygame.QUIT: print will_cause_crash if __name__ == "__main__": main()
Leave a Reply