Русский
Русский
English
Статистика
Реклама

Логические игры

Перевод Как я программировал шахматную партию против брата

13.06.2021 12:23:01 | Автор: admin


Это история о том, как я попытался выиграть у брата партию в шахматы. Всего лишь гребаную одну игру. Что в этом особенного? Хорош ли я в шахматах? Вовсе нет. Научился ли я чему-то в процессе игры? Тоже нет. Может, это история о путешествии ради путешествия, а не цели? Не совсем. Получил ли я хотя бы удовольствие от этого? Не уверен.

Это история о моей попытке соригинальничать в одной из самых изученных в мире игр, используя опыт разработки ПО там, где это, быть может, и не нужно.

Несмотря на свою абсолютную бестолковость в шахматах и полную бесполезность этой статьи для тех, кто стремится улучшить свою игру, я все равно считаю, что стоило поделиться оригинальным способом применения к задаче инженерных принципов. Добился ли я успеха? Об этом вы узнаете в конце.

Почему я вообще связался с шахматами


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

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

Первым моим решением было углубиться в изучение игры.

Попытка первая: изучение


Моя первая попытка улучшить качество игры состояла в очевидном: обратиться к Reddit и YouTube за рекомендациями других обучающихся. В перерывах между уроками от GM Naroditsky, чтением и решением задачек на Lichess я также сыграл несколько игр со случайными соперниками по интернету. Несмотря на все это мой рейтинг оставался низким (1300 1400 Rapid на Lichess).



После еще пары партий против брата на меня снизошло, что шансов победить у меня нет. Я продолжал следовать все тем же приемам развития (играл, изучал техники и смотрел видео), но уделял этому намного меньше времени, чем брат. На тот момент он уже играл сотни партий в месяц, я же не более 10. Такими темпами мое отставание росло все больше и больше.

Тогда-то я и осознал очень важный нюанс: меня не особо интересовала сама игра, и, по сути, совершенствоваться в ней я не хотел. Основной целью для меня было всего лишь победить одного человека моего брата.

Попытка вторая: изучение противника


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

На стадии миттельшпиля преимущество обычно достигается за счет развертывания долгосрочной стратегии и применения тактики. Стратегию можно совершенствовать чтением и изучением принципов игры (мне это нравится), а тактика вырабатывается только через решение задач (что мне особенно не нравится). Поэтому я понимал, что в тактических навыках буду однозначно отставать, учитывая, что мой брат решал на chess.com около 20 таких задач ежедневно. Для меня это был недостижимый предел. Таким образом, оставалась всего одна возможность: получать преимущество на стадии дебюта.

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

Тогда я решил просмотреть несколько случайных игр брата и попробовать понять используемые им дебюты. Я также изучил на Lichess дебюты Итальянская партия и Сицилийская защита, постаравшись запомнить их основные принципы. Помимо этого, я просмотрел кучу видео на YouTube.

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

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

Попытка третья: программирование


Теперь моя задача обрела иную форму: найти позиции на выходе из дебюта, которые мой брат (далее PlayerX) с наибольшей вероятностью достигнет, оказавшись при этом в невыгодном положении. Учтите, что никто из нас не является экспертом в игре, и что игроки нашего уровня играют не очень аккуратно.

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

У меня также был список из более, чем 500 игр, которые брат сыграл на chess.com. А так как я программист, то естественным подходом для меня стало решить эту задачу инженерным путем.

Я начал скачивать сыгранные им партии с помощью API chess.com и разделять их на игры белыми и черными. Далее я сосредоточился на партиях, где брат играл за черных, потому что чувствовал, что имею больше шансов направить игру в нужное мне русло при игре за белых.

import jsonimport requestsdef get_month_games(player, yyyy_mm):    url = 'https://api.chess.com/pub/player/{}/games/{}'    r = requests.get(url.format(player, yyyy_mm))    if not r.ok:        raise Exception('get_month_games failed')    games = json.loads(r.content)    # Format: {games: [{url, pgn}, ...]}    return games['games']# ...

import chess.pgnimport ioimport jsonwith open('games.json') as f:    data = json.load(f)games = []for game in data:    pgn = io.StringIO(game)    games.append(chess.pgn.read_game(pgn))black_games = [g for g in games if g.headers["Black"] == "playerx"]

Далее я сформулировал задачу так: Учитывая все позиции, которые видел PlayerX, какие из них по завершению дебюта скорее всего окажутся для него наименее выгодными?.

На этот раз задача была четко определена, и работа пошла уже в знакомой мне области. Я решил провести анализ в Python, а именно в блокноте Jupyter, потому что цели создавать переиспользуемый инструмент у меня не было, и нужно было лишь изучить доступные данные для нахождения одного решения.

Оказалось, что в Python уже есть отличные библиотеки для работы с шахматами: python-chess (генерация ходов, оценка и визуализация) и python stockfish (привязки для оценки шахматной позиции с помощью известного шахматного движка Stockfish).

Я преобразовал задачу в граф таким образом: узел это частная шахматная позиция (описанная в нотации FEN). Ребро связывает два узла при том, что целевая позиция оказывается достижима из исходной путем допустимого хода. Для всех игр есть один одинаковый стартовый узел: начальная позиция.

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

class GamesGraph():    def __init__(self):        self.graph = igraph.Graph(directed=True)    def add_move(self, start_fen, end_fen, uci):        vs = self._ensure_vertex(start_fen)        vt = self._ensure_vertex(end_fen)        try:            e = self.graph.es.find(_source=vs.index, _target=vt.index)            e["count"] += 1        except:            e = self.graph.add_edge(vs, vt)            e["uci"] = uci            e["count"] = 1    @property    def start_node(self):        return self.graph.vs.find(chess.STARTING_FEN)    def _ensure_vertex(self, fen):        try:            return self.graph.vs.find(fen)        except:            v = self.graph.add_vertex(name=fen)            v["fen"] = fen            v["turn"] = chess.Board(fen).turn            return v

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



Здесь начальная позиция обозначена квадратным узлом, цвет указывает, чей в этой позиции ход: белых или черных.

Я также хотел получить оценку каждой позиции в плане преимущества белых, для чего использовал Stockfish. Учитывая, что процесс оценки тысяч позиций требует времени, я решил выполнить его отдельно и создал объект JSON, сопоставляющий каждую уникальную позицию FEN с ее оценкой Stockfish.

from stockfish import Stockfishstock = Stockfish(parameters={"Threads": 8})stock.set_depth(20)stock.set_skill_level(20)def eval_pos(fen):    stock.set_fen_position(fen)    return stock.get_evaluation()# fens - это сопоставление между строкой FEN и узлом графа.for fen, node in graph.fens.items():    node.eva = eval_pos(fen)

Оценка преимущества возвращалась в сантипешках или как мат в X ходов, где положительное число означает преимущество белых, а отрицательное преимущество черных:

{"type":"cp", "value":12}    # Преимущество белых в 12 сантипешек.{"type":"mate", "value":-3}  # Черные получают мат в три хода.

100 сантипешек означают преимущество перед оппонентом в одну пешку, а 300 в одну легкую фигуру вроде слона. Однако стоит обратить внимание, что Stockfish присваивает фигурам значение в зависимости от их позиции, значит вполне возможно иметь преимущество в 1000 сантипешек даже при равнозначном количестве фигур на доске.

Мне нужно было отобразить эту оценку во что-то более удобное для обработки, например в числа между 0 и 1. Для этого я навскидку решил, что преимущество в 300+ будет отображаться в 1.0, а отставание в 300+ в 0. Помимо этого, любой мат в X ходов (даже если X равен 20) будет 1 или 0.

# Возвращает [-1;1]def rating(ev, fen):    val = ev["value"]    if ev["type"] == "cp":        # Закрепить -300, +300. Достаточно захватить фигуру.        val = max(-300, min(300, val))        return val / 300.0    # Мат в X ходов: также max рейтинг.    if val > 0: return 1.0    if val < 0: return -1.0    # Это уже мат, но для белых или черных?    b = chess.Board(fen)    return 1.0 if b.turn == chess.WHITE else -1.0# Возвращает [0;1], где 0 - это min, а 1 - это max преимущество для черных.def rating_black(ev, fen):    return -rating(ev, fen) * 0.5 + 0.5

Теперь вся информация была не месте, и мне оставалось найти узлы графа (т.е. позиции), в которых черные находились в проигрышном положении, а также наиболее подходящие для их достижения последовательности ходов. Нужно было взвесить ребра таким образом, чтобы стало возможным легко вычислять вероятность достижения конкретной позиции. Я рассуждал так:

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

Для решения задачи с помощью стандартных графовых алгоритмов нужно было преобразовать веса ребер так, чтобы:

  • Они представляли расстояние, а не вероятность (т.е. чем больше расстояние, тем ниже вероятность выбора пути).
  • Расстояние между двумя узлами являлось суммой весов пройденных ребер (в противоположность произведению вероятностей).

На деле это гораздо легче сделать, чем объяснять. Формула очень проста:

distance(e) = -log(prob(e))

В Python это будет выглядеть так:

def compute_edges_weight(vertex):    all_count = sum(map(lambda x: x["count"], vertex.out_edges()))    for edge in vertex.out_edges():        prob = edge["count"] / all_count        edge["prob"] = prob        edge["weight"] = -math.log(prob)

Логарифмирование вероятности выбора ребра даст отрицательное число, потому что вероятность находится между 0 и 1. При этом не стоит беспокоиться о случае, когда вероятность равна нулю (в результате чего логарифмирование бы дало минус бесконечность), поскольку каждое ребро графа было пройдено не менее одного раза. Чем меньше вероятность, тем более отрицательным получится логарифм, значит инвертирование его знака даст то, что нам нужно, так как:

  • Сумма логарифмов равна логарифму произведения их аргументов: log(a) + log(b) = log(a*b).
  • Чем больше результат, тем ниже определяющая его вероятность.



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

В этот момент я произвольно выбрал минимальное значение преимущества и упорядочил пути по вероятности. Первые несколько путей представляли для меня наибольший шанс выйти из дебюта с преимуществом перед PlayerX.

Доработки


Что я выяснил? Среди выданных этим алгоритмом позиций была следующая (ход белых):



Как видите, черные находятся в очень неловком положении (+8.9 согласно Stockfish), потому что g6, последний ход черных, был ошибкой. Белые продолжат, забирая пешку с e5 и слона. На этом партия для черных практически закончена, так как спасать им придется коня, пешку на h7 и слона. Еще один результат алгоритма был таким (ход белых):



Здесь мы видим мат в один ход (детский мат).

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

Еще одна проблема была связана с последовательностями ходов, которые происходили только раз, но из типичных позиций. Вероятность их заключительной позиции оказывалась такой же, что и вероятность последней типичной позиции, потому что каждое ребро имело вероятность 1.0 (учитывая, что другие возможности не разыгрывались). В примере ниже можно проследовать по ребрам 7 и 6 (наиболее распространенная позиция на втором ходу), а затем по одному из ребер с 1-ми. Далее все последующие ходы будут сыграны только раз (потому что данная позиция сложилась только в одном матче), в результате чего каждый ход будет иметь вероятность 1.0.



А вот и вероятности:



Такой схеме верить нельзя, потому что вряд ли однозначно будет сыграна одна и та же последовательность ходов. Для такого вывода у нас недостаточно игр, в которых игра бы происходила из этих позиций.

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

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

def compute_edges_weight(vertex, prob_ceiling=0.9):    all_count = sum(map(lambda x: x["count"], vertex.out_edges()))    for edge in vertex.out_edges():        # Уверенности нет... Установим потолок вероятности (default 90%).        prob = min(edge["count"] / all_count, prob_ceiling)        edge["prob"] = prob        edge["weight"] = -math.log(prob)

Для первой же проблемы я просто вручную отфильтровал плохие предположения. В итоге у меня для проработки осталась всего пара позиций.

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



Подготовка


В процессе изучения я остановил свой выбор на следующей позиции:



Согласно Lichess, это защита Алехина (атака двух пешек). В этой позиции для черных есть всего один удачный ход (Nb6), после которого они все равно остаются в менее выгодном положении (+0.6 согласно Stockfish). Однако из этой позиции PlayerX зачастую играет на Nf4, что весьма для него неудачно (+2.3). Я создал на Lichess студию и начал просматривать несколько вариаций (хороших ходов и ходов, сыгранных PlayerX).

В конечном итоге получилось дерево возможностей, которое я постарался запомнить и понять. К примеру, мне нужно было узнать, чему угрожал ход вроде d5, почему ход Nf4 был неудачным, и подготовить на все оптимальные ответы.

Занимался я этим недолго, потому что мне быстро надоело, и подготовился по факту лишь частично.

Решающая партия


Все случилось так, словно я глядел в будущее: мы с PlayerX попали в позицию защиты Алехина. Оказавшись в неудобной ситуации, он прозевал своего коня на пятом ходу. Оказывается, что даже игроки намного опытнее тебя начинают одну за другой совершать ошибки, когда попадают в проигрышные условия. Легко играть четко, когда ты побеждаешь, но удастся ли тебе сохранить хладнокровие в противоположной ситуации? На 10 ходу я уже вел с преимуществом +7.1, при котором сложно проиграть, но на этом также завершалась проработанная мной схема. Взгляните, насколько стеснены сейчас черные, и как мои фигуры нацелены напасть на короля:



С этого момента я начал тут и там совершать ошибки, но при этом мне удалось сохранять некоторое преимущество вплоть до 27 хода:



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



Вот весь матч (с грубыми ошибками и прочим):


Интерактивный просмотр партии: lichess.org/2qKKl2MI

Выводы


Чему я из всего этого научился? Нескольким вещам, большая часть из которых в ретроспективе выглядит очевидной:

  1. Подготовка под конкретного противника может дать значительное преимущество в дебюте.
  2. Начинающие игроки часто упускают возможность воспользоваться сомнительными ходами соперника. В связи с этим легко получить преимущество, доведя противника до позиции, из которой есть лишь один удачный ход.
  3. Дебют не является определяющим. Если вы не умеете действовать по времени и слабы в тактике, то вполне можете проиграть даже абсолютно выигрышные позиции. Шахматная партия порой решается одним неверным ходом.
  4. Очень важно изучать игру, и нет никакого универсального средства против оппонента, который намного опытнее вас. Однако за счет правильной подготовки разрыв в навыках можно сократить .
  5. Применение к шахматам принципов программной разработки оказалось занятной идеей, особенно учитывая, что самоцелью было победить брата.

Использованный мной код лежит в репозитории. Обратите внимание, что я не включил туда данные, и сам код весьма небрежен. Тем не менее, надеюсь, он окажется полезен, в особенности тем, кто еще размышляет на тему освоения компьютерной науки. Смотрите с ее помощью вполне можно решать задачи из реальной жизни, так что это не просто перемещение битов туда-сюда.

На этом все, друзья. Надеюсь, что однажды мне удастся одолеть брата, а пока что буду стараться достичь этогосвоими средствами.


Подробнее..

DagazServer Встречайте Garbo Chess

21.01.2021 18:22:37 | Автор: admin
Кто мне сказал, не получится?
Если мне хочется, сбудется!

Земфира

Плюнь тому в глаза, кто скажет,
что можно объять необъятное!

Козьма Прутков "Плоды раздумья"


Новогодние праздники вновь навалились внезапно. Такое обилие свободного времени было просто необходимо разбавить какой-то осмысленной деятельностью и я решил приделать к своему серверу бота для игры в Шахматы. Готовых шахматных движков существует множество. Я решил остановиться на Garbochess-JS простой и понятной реализации, на языке JavaScript, названной в честь знаменитой актрисы Греты Гарбо (вы можете видеть её на фотографии).

Прежде всего, должен сказать пару слов о своём сайте. Поскольку вся идея состоит в том, чтобы люди играли с друг другом по сети, на сайте требуется регистрация. При регистрации не требуется указывать никакой конфиденциальной информации (EMail может быть сохранён в профиле пользователя, по желанию, позже). Ссылка, указанная мной выше и отображающая список всех имеющихся игр, работает без регистрации, но если вы решите пойти дальше, потребуется логин и пароль.


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

Другая возможность реализована не для всех игр, но если на форме имеется чекбокс Play against AI, вы можете ничего не ждать вовсе. Эта опция запускает режим игры с ботом, отвечающим на сделанные ходы практически немедленно. Как правило, речь идёт об очень простых ботах, без каких-то сложных вычислений (хотя победить некоторых из них, всё равно, может быть тяжело). Для Шахмат такое решение не подходит вовсе, но возможность поиграть с ботом всё-таки имеется.

Чего хотелось


Обычный встраиваемый в игру бот не является для Dagaz чем-то новым. Технически, такая игра представляет собой html-сборку, включающую в себя модуль выбора оптимального для этой игры хода, в зависимости от текущей позиции. К имени html-файла добавляется суффикс "-ai", позволяющий серверу загрузить правильную сборку, при выборе режима игры с ботом. Думаю понятно, что разработать бота, подходящего абсолютно для всех существующих на свете игр невозможно, но можно использовать одни и те же боты для различных, но сходных между собой игр.

Например, этот бот используется очень часто
(function() {function RandomAi(params) {  this.params = params;  if (_.isUndefined(this.params.rand)) {      this.params.rand = _.random;  }}var findBot = Dagaz.AI.findBot;Dagaz.AI.findBot = function(type, params, parent) {  if ((type == "random") || (type == "solver")) {      return new RandomAi(params);  } else {      return findBot(type, params, parent);  }}RandomAi.prototype.setContext = function(ctx, board) {  ctx.board  = board;}RandomAi.prototype.getMove = function(ctx) {  var moves = Dagaz.AI.generate(ctx, ctx.board);  if (moves.length == 0) {            return { done: true, ai: "nothing" };  }  if (moves.length == 1) {      return { done: true, move: moves[0], ai: "once" };  }  var ix = this.params.rand(0, moves.length - 1);  return {      done: true,      move: moves[ix],      ai:   "random"  };}})();

Это не шутка. Дело в том, что в Dagaz боты выстроены в цепочку и бот рандомного выбора хода используется в тех случаях, когда боты, стоящие выше по иерархии, дать ответ отказались (такое возможно в тех случаях, когда любой ход ведёт к поражению). Разумеется, есть и более сложные боты, но, в целом, все они не очень сильные. Прежде всего, это связано с использованием универсальной (а значит медленной) модели, пригодной для абсолютно любых игр, реализуемых Dagaz.

Второе ограничение связано со временем расчёта хода. Для встроенного бота оно не может превышать 2-3 секунд, поскольку все вычисления производятся непосредственно в браузере пользователя и, в силу однопоточности JavaScript, все другие действия, на это время блокируются. Если задержаться слишком долго, браузер выбросит предупреждение о возможном зацикливании на странице или вообще молча остановит все выполняющиеся скрипты (такое случалось в Safari).

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

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


После старта, бот выполняет инициализацию, авторизуясь на сервере, после чего переходит к циклу опроса: ищет на сервере сессии, в которых он должен выполнить очередной ход (TURN), загружает текущую позицию (RECO), передаёт её описание в Garbo Chess, а полученный ответный ход отправляет на сервер (MOVE). Если сессий ожидающих хода нет, бот переходит к проверке наличия ожидающих сессий, созданных ботом (CHCK), если таковых нет и общее количество сессий, в которых участвует бот, меньше заданного, создаёт новую (SESS).

При возникновении ошибок (например, в случае устаревания JWT-токена), бот возвращается к фазе инициализации (INIT) для выполнения повторной авторизации, а если ошибка возникла уже там (при недоступности сервера или чём-то подобном) переходит к фазе STOP и останавливается. Вот так всё это выглядит.

Бот может играть одновременно с несколькими игроками, но в каждый момент времени имеет дело не более чем с одной игрой. Таким образом, если игра ведётся с несколькими людьми, каждому придётся ждать чуть дольше. Кроме того, это не самый эффективный способ использования Garbo Chess. Движок поддерживает режим, при котором анализ игры ведётся непрерывно (запускается в отдельном потоке Web Worker-а), но в этом случае, играть можно только с одним противником.

SAN-ы, FEN-ы, PGN-ы


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

С этим была небольшая засада
Разумеется, в Dagaz я тоже описываю позиции. Это функциональность, обойтись без которой очень трудно. Представьте себе, что доиграв до середины партии мы вышли из игры, а потом зашли в неё заново (или просто перегрузили страницу). Было бы глупо прокручивать все ходы с самого начала. DagazServer использует описание позиции, чтобы загрузить правильную расстановку фигур сразу, без утомительной перемотки.

Вернее, он действует ещё хитрее: в случае если ожидается ход противника, загружается последняя расстановка фигур, как и было написано, но если ходить должен игрок, DagazServer загружает предыдущую позицию, возникшую в игре на момент начала последнего хода противника. Следующий ход игра получает обычным образом, уже после загрузки html. Благодаря этому, игрок, загружая игру, всегда видит анимацию последнего хода (или нескольких ходов) противника. А если он не успел рассмотреть этот ход во всех подробностях, всегда можно просто перезагрузить страницу.

Таким образом, модули описания позиции, вроде этого важная часть проекта. У меня их несколько и я использую тот или иной, в зависимости от особенностей игры. Почему я не использовал FEN? Просто потому, что Dagaz это не только Шахматы. Приведу простой пример: возможность рокировки, в FEN кодируется как KQkq, но такое описание слишком завязано на правила традиционных шахмат! Даже в слегка изменённых шахматных вариантах нотацию приходится расширять. В любом случае, мне понадобился FEN и я его сделал.

В ответ на полученное описание, Garbo Chess, проработав некоторое время, возвращает лучший (по его мнению) ход (просто пара позиций вроде e2e4 и тип фигуры, при наличии превращения). К сожалению, на момент разработки бота, на сервере было сыграно уже довольно много партий в Шахматы и я хранил описание хода немного в другом виде. Я не хотел, чтобы эти партии сломались и добавил дефис, разделяющий позиции (тот факт, что старые партии не использовали FEN-нотацию роли не играл, при проигрывании уже завершённых партий, описания позиций не используются).

С нотациями пришлось ещё повозиться
Одной из особенностей минимаксных алгоритмов является их детерминированность. При одинаковых условиях, будет формироваться один и тот же ход. Это может привести к однообразной игре бота, что не очень приятно. Я вижу два способа борьбы с этим:

  • Случайное ограничение времени на расчёт хода
  • Книга дебютов

С первым пунктом всё понятно вместо того чтобы жёстко ограничивать время на расчёт хода, например одной секундой, можно задать вилку из минимального и максимального значений и каждый раз брать случайное число в этих пределах. Что касается книги дебютов, то она полезна сама по себе. Шахматные движки придуманы для миттельшпиля. В дебюте и эндшпиле они не столь эффективны. Для эндшпилей существуют таблицы Налимова, а дебюты обрабатываются специальными справочниками, гораздо более компактными.

В силу своей иерархической организации, дебютные таблицы предоставляют некоторую вариативность. При наличии для позиции нескольких лучших ходов, мы можем использовать случайный выбор. Я уже использовал дебютные таблицы в Dagaz, в формате SGF, но для сервера потребовалось реорганизовать их иначе. Вместо последовательностей ходов от начала партии, мне были нужны FEN-описания позиций со списками соответствующих им лучших ходов (это, кстати, позволяет описывать дебютные ловушки, путём сохранения лучших ходов только одной стороны). Здесь очень помогла утилита pgn2fen, обнаруженная в блоге Николая Кисленко, работающая как с SAN так и с Long algebraic notation.

Далее, я создал пользователя, для того чтобы бот мог заходить на сервер и прописал его id в качестве дежурного бота шахматным играм, для того чтобы frontend автоматически включал бота в созданную игру, при выборе опции Play against AI. В целом, новая схема данных выглядела так:


Здесь есть ещё один момент, о котором стоит сказать. Я добавил табличку ai_settings, для хранения настроек бота по отношению к игроку в конкретной игре. Это, своего рода, рейтинг. Если игрок выигрывает, дополнительное время, выделяемое боту на раздумье, увеличивается. При поражениях оно уменьшается. Таким образом, бот может подстраиваться к силе игрока, с которым он играет.

Что получилось


Это одна из игр бота на сайте. И это не дебютная ловушка (можете проверить это самостоятельно)! При ограничении времени на расчёт хода в 1-2 секунды, бот вполне разумно играет против человека и умеет ставить красивые маты. Возможности бота не ограничиваются классическими шахматами. Подойдёт любая игра, в которой правила перемещения фигур не изменены, например "Шахматы Фишера" или "Шахматы Будённого".

Правда, здесь есть небольшая загвоздка
Шахматный движок должен знать, с какой позиции началась игра. Если первым ходит человек, никаких проблем нет после выполнения хода, FEN-описание позиции передаётся на сервер, но если бот ходит первым, описать позицию некому, поскольку сервер ничего не знает о конкретике игры. Мне пришлось применить небольшой трюк загружать FEN-описание начальной позиции даже в том случае, если игра после загрузки ожидает ход бота.

Может возникнуть, своего рода ситуация гонок, когда бот получает описание сессии раньше, чем интерфейс игры успел загрузиться и сохранить FEN начальной позиции. Понятно, что ни к чему хорошему это привести не может, поэтому я добавил атрибут setup_required, требующий наличия FEN на момент загрузки сессии. Если FEN ещё не сформирован, сервер возвращает ошибку, получив которую, бот просто переходит к повторной авторизации, после чего продолжает выполнение обычным образом.

Также, без каких либо изменений, можно играть в "Шахматы втёмную". Если проявить немного фантазии, можно пойти ещё дальше. Помните, как построены миссии кампании в знаменитой "Battle vs Chess"?

Здесь, в качестве бота, используется обычный шахматный движок Fritz. Если подумать, это становится понятно. Подрыв на мине просто потеря фигуры. Бот не будет ходить на мины в том случае если будет их учитывать это просто невыгодно, а суть миссии как раз в том, чтобы заманивать в ловушку его фигуры. Решение простое информация о минах просто не должна передаваться боту.


Вот что получается: я добавляю в FEN описание мин, но перед передачей в Garbo Chess, просто убираю мины из описания, а после получения ответа возвращаю в позицию те мины, которые не взорвались в результате хода бота. Теперь вы можете заманить бота в ловушку уже на DagazServer.

Что дальше


Есть много шахматных игр: Шатрандж, Макрук бот может играть в них, надо только добавить в Garbo Chess новые фигуры. Есть игры на малых досках. Наконец, можно переосмыслить Garbo Chess, создав на его основе универсальный движок, подходящий для более широкого класса игр. Возможностей для развития много, было бы желание.
Подробнее..

Перевод 10 лучших игр по программированию, которые улучшат ваши навыки

11.03.2021 20:12:02 | Автор: admin

Вы помните далёкие дни из детства, когда вы, проводили целый день, а иногда даже не ели целый день, чтобы поиграть в игры на Nintendo? (Ах, дни Mario и Contra!!!)

С того времени игры претерпели гигантские преобразования и сфера стала более обширной. Это уже не просто хобби. Сейчас в Интернете доступно множество игр, связанных с программированием, и вы можете использовать их чтобы изучить и отточить свои скилы в увлекательной форме. Более того, эти игры могут помочь вам улучшить навыки решения задач, поскольку вам нужно будет решать задачи различной сложности, а также соревноваться с другими опытными программистами по всему миру. Специально к старту новых потоков курсов Fullstack-разработчик на Python, разработка на C# и разработка на Java, в этой статье мы отобрали несколько таких игр, играя в которые можно параллельно качать и себя самого.

1. Untrusted

Приключения доктора Эвала!

Untrusted это приключенческая онлайн-игра, предназначенная для людей, которые хотят попрактиковаться и проверить свои навыки в JavaScript . В этой игре от вас требуется направлять доктора Эвала через машинный континуум и изменять его реальность, чтобы получить свободу. Игра предоставляет вам игровую среду, похожую на мошенническую, и окно консоли с JavaScript-кодом. У вас будет доступ ко всем исходным кодам, но, чтобы спастись, вам нужно внести необходимые изменения в этот код.

В игре есть несколько уровней, таких как cellBlockA, где вы будете генерировать и удалять стены, theLongWayOut, в котором вам нужно создать новый выход, и многое другое. Игра довольно увлекательное путешествие, если вы обладаете хорошими знаниями концепций и программирования JavaScript. Интерфейс игры выглядит так:

2. Robocode

Было бы здорово изучать программирование, и создавать боевых роботов-танков (звучит увлекательно, правда?).

Да, вы можете сделать это в известной игре Robocode. Robocode позволяет разработать боевого робота-танка с использованием Java или .NET, для борьбы с другими танками. Вам нужно написать ИИ для робота, чтобы он знал, что делать и как реагировать на события, происходящие на поле битвы.

Игра очень полезна для изучения и практики нескольких языков программирования, таких как Java, Scala, и C# . Она также поможет вам попасть в сферу искусственного интеллекта . Более того, Robocode предоставляет вам полноценную среду разработки: есть собственный установщик, встроенный редактор роботов и компилятор Java. Кроме того, Robocode это проект с открытым исходным кодом, и вы все можете придумывать свои собственные надстройки или режимы, чтобы продемонстрировать свои навыки разработки.

3. Elevator Saga

Elevator Saga поможет вам продемонстрировать свои навыки в JavaScript в контексте программирования движения лифтов для эффективной перевозки людей. Задачи самые разные, начиная с простых: перевезти 15 человек за 60 секунд или меньше и т. д., И они постепенно усложняются. Вам нужно придумать оптимизированный алгоритм, чтобы сократить время ожидания пассажиров. Игра действительно очень полезна для работы над вашими навыками JavaScript и подходами к оптимизации алгоритмов.

Кроме того, интерфейс Elevator Saga довольно прост, всё, что вам нужно, ввести свой код в окно ввода и нажать кнопку Применить, чтобы начать испытание. Некоторые из примеров кода для Elevator Saga приведены ниже, чтобы дать вам общее представление:

  • чтобы сообщить лифту о переходе на 1-й этаж: elevator.goToFloor(1);

  • чтобы остановить лифт, если он движется: elevator.stop();

  • чтобы получить номер этажа, на котором в настоящее время находится лифт: elevator.currentFloor();

  • и многие другие.

4. Vim Adventures

Если вы часто испытываете трудности с VIM, то Vim Adventures наверняка создан для вас!! Vim Adventures это онлайн-игра, которая позволяет вам изучать горячие клавиши VIM и другие известные концепции в увлекательной и интересной форме с помощью игровой среды, подобной Zelda. Эта игра упрощает изучение и понимание мощного текстового редактора Vim, который впоследствии поможет вам стать более эффективным программистом.

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

5. CodeCombat

CodeCombat в основном рекомендуется тем людям, которые имеют небольшой или даже нулевой опыт в программировании, поскольку игра не только помогает вам практиковать свои навыки, но и обеспечивает замечательный процесс обучения в формате игры. Вы можете изучить различные языки программирования, такие как Python, JavaScript, CoffeeScript, Lua и т. д., с помощью игры. Вам нужно будет написать код на любом из этих языков, чтобы сообщить персонажу, что ему нужно делать. Более того, игра начинается с простых головоломок и задач, а затем уровень сложности постепенно растёт. И, да, в игру также включены различные обучающие программы, позволяющие овладеть синтаксисом языка.

Кроме того, CodeCombat это проект с открытым исходным кодом, и вы можете не только учиться и играть, но и вносить вклад в исходный код, чтобы добавлять новые функции, исправлять ошибки и т. д., чтобы повысить уровень своего программирования. Что ещё нужно?

6. Flexbox Defense

Flexbox Defense действительно один из лучших способов укрепить свои знания и навыки CSS Flexbox! Это игра в жанре Tower Defense, в которой вам необходимо не дать приближающимся врагам пройти через вашу оборону, переместив башни на такое место, чтобы турели могли стрелять во вторгшихся врагов, прежде чем они пройдут через вас. Вам необходимо использовать свойство justify-content в контейнере для размещения ваших башен. Несколько наиболее распространённых значений, принимаемых свойством justify-content, следующие:

  • flex-start: группировать элементы в начале главной оси;

  • flex-end: группировать элементы в конце главной оси;

  • center: группировать элементы в центре;

  • space-around: равномерно распределить элементы по главной оси так, чтобы вокруг всех элементов было равное пространство.

Есть много других свойств CSS Flexbox, которые используются в игре, такие как align-items, flex-direction, order и некоторые другие.

7. Code Hunt

Ещё игра в списке, которая может помочь вам попрактиковаться и улучшить свои навыки программирования в игровой манере, это Code Hunt. Это игра по программированию от Microsoft Research. Игра основана на головоломках, которые вы должны изучить, используя данные подсказки и контрольные примеры. Сначала вам нужно определить шаблон, а затем написать решение. Code Hunt позволяет вам овладеть двумя известными языками Java и C #. Игра разработана таким образом, чтобы научить вас основам этих двух языков.

Поскольку Code Hunt принадлежит Microsoft, её предпочитают миллионы студентов (и даже профессионалов) во всём мире, и, если вы с нетерпением ждёте, чтобы укрепить свои навыки владения Java или C# более увлекательным способом, вы, безусловно, можете попробовать.

8. CheckIO

CheckIO это игра по программированию, которая позволяет вам улучшить свои навыки, особенно для двух языков Python и TypeScript . Игра рекомендуется как новичкам, так и опытным программистам для повышения уровня своих навыков, так как она предоставляет вам множество захватывающих задач различных уровней сложности. Каждый набор этих задач расположен на разных островах, и пользователям необходимо решить требуемую задачу или головоломку, чтобы перейти с одного острова на другой. Кроме того, обогащающее и поддерживающее сообщество CheckIO помогает вам делиться знаниями и опытом с разными блестящими умами по всему миру.

Вы не поверите, что CheckIO используют учителя и инструкторы в своих учебных программах или классах, чтобы помочь учащимся отрабатывать навыки программирования. Более того, игра очень кастомизируемая, и вы всегда можете внести свой вклад в неё.

9. Screeps

А вот и ещё одна популярная игра по программированию для всех программистов Screeps! Это онлайн-стратегия в реальном времени, которая требует от вас хотя бы некоторых базовых знаний в области программирования. В этой игре вам нужно создать свою собственную колонию в определённом мире, доступном всем игрокам. А колония сможет добывать ресурсы, создавать юнитов и завоевывать территории. Более того, необходимо запрограммировать реакцию юнитов на события, и вы можете сделать это, используя язык программирования JavaScript .

Вам также необходимо знать, что написание скрипта для Screeps ничем не отличается от написания любого другого приложения JavaScript. И вы также можете разделить свои скрипты на модули с помощью синтаксиса Node.js, чтобы сделать игру более удобной.

Кроме того, вы можете использовать другие языки, такие как C++ и т. д., А также можете компилировать их с помощью WebAssembly. А также Screeps позволяет вам вносить свой вклад в разработку игрового движка и изменять поведение игровых объектов.

10. CSS Diner

Наконец, CSS Diner игра по программированию, которая помогает вам практиковаться и совершенствовать свои навыки CSS. Игра помогает вам управлять селекторами CSS на всех 32 уровнях, включённых в игру. И уровень сложности каждого раунда повышается по мере прохождения игры. Игра состоит из различных захватывающих уровней в зависимости от нескольких важных атрибутов, таких как id, classname, empty, first-child, only-of-type и многих других. Более того, если вам нужна подсказка для решения определённого уровня, всё, что вам нужно сделать, это навести указатель мыши на элементы в таблице и просмотреть HTML-разметку.

Игра предоставит вам лучшее понимание для выбора определённых элементов в HTML и CSS и впоследствии поможет вам перемещаться по элементам DOM, когда дело касается JavaScript. И самое приятное то, что вы можете играть в CSS Diner в своем браузере без каких-либо затрат или хлопот, таких как вход в систему, создание учётной записи и т. д.

Также можно принять во внимание несколько других игр: Codewars, SQL Murder Mystery и Duskers. Излишне говорить, что почти каждый технический энтузиаст так или иначе склонен к играм. А с помощью упомянутых выше игр по программированию вы можете улучшить свои навыки более увлекательным и авантюрным способом. Тем не менее вам не рекомендуется идти на компромисс с продолжающимся процессом обучения и использовать эти игры в течение ограниченного времени, поскольку избыток чего-либо всегда неблагоприятен.

Если у вас есть на примете полезные игровые проекты подобные этим, но в список не попавшие делитесь ими в комментариях!

Играми поделились, а теперь поделимся и релевантными программами обучения. Тем кому в освоении нового не хватает "крепкого плеча" ментора, которая поможет довести начатое до конца добро пожаловать на наши программы Fullstack-разработчик на Python, разработка на C# и разработка на Java и да прибудет с вами сила.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы
Подробнее..

Как желание поиграть в шахматы превратилось в написание своего движка. История и реализация

07.04.2021 14:14:13 | Автор: admin
Всем привет! Меня зовут Борис Николаев, сегодня я хотел бы поделиться с вами своими наработками по технической реализации простого шахматного движка на Kotlin.

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



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

В шахматах обманчиво простые правила, которые со всеми особыми случаями не так-то просто сделать единообразно. Я приведу пример реализации логики игры на Kotlin, при этом сознательно не буду рассматривать графическую часть движка для этого есть множество вариантов решений, в том числе и готовых. Ну, а для самых любопытных все исходники проекта я выложил на github.

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


Обозначения для шахматных фигур


Для начала определимся с терминами и названиями. Не все, что стоит на доске, является фигурой (англ. piece). Пешку к фигурам не относят. Но это скорее профессиональный сленг. Мы для простоты все будем называть фигурами.

Познакомимся c фигурами и запомним их вид в нашем движке.
Иконка Фигура
Пешка pawn
Конь knight
Слон bishop
Ладья rook
Ферзь queen
Король king
Обзор фигур, и как они ходят
Здесь кратко напомню, как ходят фигуры.

Пешка (англ. pawn) самая слабая фигура. Фактически, пушечное мясо. Двигается только вперед. Атакует только по диагонали вперед на одну клетку.

То есть в процессе атаки пешка переходит на соседний ряд. При этом прямо атаковать не может, поэтому, встретив у себя на пути любую другую фигуру, оказывается заблокированной. Слабость пешек компенсируется их количеством. Кроме того, это единственная фигура, которая превращается в любую другую (кроме короля), если достигнет противоположного края доски. Чаще всего пешку превращают (это действие promotion) в самую сильную фигуру в ферзя. У каждого игрока по 8 пешек, они располагаются в ряд перед остальными фигурами.

Ладья (устар. тура, англ. rook) фигура основательная. Хотя бы своим видом, похожим на башню. Ходит по горизонтали и вертикали в любом направлении на любое количество клеток, пока не встретит на своем пути другую фигуру. У каждого игрока по две ладьи, которые ставятся по углам доски.

Слон (устар. офицер, англ. bishop) ходит по диагонали в любом направлении, пока не упрется в другую фигуру. У каждого игрока по два слона, которые стоят по бокам от короля и ферзя. Из этого следует, что один слон всегда ходит по белым полям (белопольный слон), а другой всегда по черным полям.

Конь (англ. knight) отличается как самым оригинальным внешним видом, так и самым причудливым ходом, который проще всего представлять буквой Г. Две (или одна) клетка по горизонтали в любом направлении и одна (или две) клетки по вертикали. Причем неважно, есть на этих клетках другие фигуры или нет. То есть конь единственная фигура, которая умеет перепрыгивать другие. У каждого игрока по два коня, которые ставятся между ладьей и слоном.

Ферзь, он же королева (англ. queen) ходит как хочет: и по горизонтали, и по вертикали, и по диагонали в любом направлении на любое количество клеток. По сути ход королевы является комбинацией ходов слона и ладьи. С точки зрения первоначальной расстановки на доске ферзь ставится рядом с королем и всегда на поле своего цвета.

Король (англ. king) ходит так же, как и королева, в любом направлении. Но монарху не к лицу суетиться, поэтому он ходит только на 1 клетку в каждую сторону. Также королю доступна рокировка (это действие castling) с ладьей, если между ними нет других фигур. Потеря короля означает проигрыш, поэтому ходы, в результате которых король окажется под ударом вражеской фигуры, запрещены.

Обозначения ходов


Для этого используем краткую запись, которая на первый взгляд похожа на набор букв и цифр, однако на деле все довольно просто.

Расскажу и покажу наглядно.

Сперва пишется первая буква, обозначающая фигуру (для пешек букву не используем). Затем поле, с которого фигура совершает ход. Координата по Х обозначается буквами от a до h, по Y цифрами, начиная с 1. Очень похоже на морской бой.

Если в ходе была уничтожена вражеская фигура, то пишем x, если никто не пострадал, то будет . Затем указываем поле, на которое перешла фигура. Ну, и в конце обозначаем особые случаи: для шаха +, для мата ++, для пата =. Для превращения пешки указываем в конце тип новой фигуры.

Техническая реализация


На шахматной доске 8 на 8 клеток, всего 64. Поскольку на каждой клетке может находиться только одна фигура, то во всех современных движках шахматные фигуры хранятся в виде битовых полей в типе Long, который как раз имеет разрядность 64 бита. То есть каждая клетка получает порядковый номер от 0 до 63 и если на данной клетке есть фигура, то соответствующий бит равен 1. Но это делается для оптимизации расходов памяти и просчета большого количества комбинаций. Поскольку в моей реализации ничего такого нет, я сделал упор на читаемость кода и решил хранить фигуры в Map, где ключом является вот такой тип Point.

data class Point(    val x: Int,    val y: Int)

Data class это неизменяемый тип, автоматически определяющий такие методы, как equals и hashCode, а потому его можно использовать в качестве ключа мапы. Х расположение фигуры по горизонтали, а Y по вертикали.

Для самой фигуры определим два параметра: цвет и тип.

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

enum class PieceColor(val text: String) {    WHITE("white"),    BLACK("black");    fun other(): PieceColor =    when (this) {        WHITE -> BLACK        BLACK -> WHITE    }}

Тип фигуры также определим в виде enum class с параметрами: название, ценность и краткое обозначение.

enum class PieceType(val nameEn: String,val nameRu: String,val price: Int,val notation: String,val useForPromotion: Boolean) {PAWN("pawn", "пешка", 100, "", false),KNIGHT("knight", "конь", 320, "N", true),BISHOP("bishop", "слон", 330, "B", true),ROOK("rook", "ладья", 500, "R", true),QUEEN("queen", "ферзь", 900, "Q", true),KING("king", "король", 20_000, "K", false)}

Признак useForPromotion показывает, может ли пешка превращаться в данную фигуру. Как видим, пешка не может превращаться только в короля и в саму себя.

Поле notation нам потребуется для записи ходов (помним, что для пешки нет специального обозначения).

Теперь мы подошли к такому вопросу, как ценность фигур.

Ценность фигур


Ценность шахматных фигур можно считать по-разному. Она меняется в течение игры в зависимости от того, какие фигуры уже выбыли. Но в самом простом случае можно взять пешку за единицу измерения, как самую слабую фигуру.

Отсюда получается, что конь и слон примерно равны между собой и равноценны трем пешкам. Ладья более ценна и равна пяти пешкам. Ферзь чуть дороже ладьи и слона вместе взятых, и его ценность равна девяти пешкам. Король имеет самую высокую ценность, ведь без него игра прекращается, поэтому просто возьмем заведомо большое число, превышающее суммы всех остальных фигур вместе взятых.

Движок


К этому моменту мы можем полностью хранить текущее состояние игры в виде мапы. Для этого будем использовать поле pieces класса BoardImpl, который и будет по сути нашим движком. Затем, совершая каждый ход, мы будем менять нашу мапу pieces. Все совершаемые ходы будут добавляться в историю (поле history).

class BoardImpl : Board {private val pieces = mutableMapOf<Point, Piece>()private val history = mutableListOf<HistoryItem>()// ...}

Чтобы не хардкодить первоначальное расположение фигур на доске, его можно считывать из текстового файла. Например, файл может выглядеть так:

rnbqkbnrpppppppp................................PPPPPPPPRNBQKBNR

В этом файле 8 строк по 8 символов в каждой, т.е. 1 символ соответствует клетке на доске. Каждая фигура обозначается соответствующей буквой (например, пешка буквой P). Регистр буквы определяет цвет фигуры: верхний регистр это белые фигуры, нижний черные.

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

Генерация доступных ходов


В начале каждого хода движок будет генерировать список доступных ходов (множество клеток доски) для каждой фигуры. Это удобно и для человека (подсвечивать в интерфейсе доступные клетки), и для компьютера (просто выбирать оптимальный ход из полученного множества). Ходы бывают нескольких типов: обычный, ход с превращение пешки и рокировка. Определим интерфейс Turn:

interface Turn {val sourcePiece: Pieceval from: Pointval to: Pointval enemyPiece: Piece?fun execute(pieces: MutableMap<Point, Piece>)fun revert(pieces: MutableMap<Point, Piece>)}

Каждый ход содержит информацию о фигуре sourcePiece, которая этот ход совершает, ее исходную позицию from, пункт назначения to и вражескую фигуру enemyPiece (опционально, если она находится в пункте назначения). Также имеется два метода, принимающие текущее состояние доски: execute() для выполнения хода и revert() для его отмены. По сути это паттерн Команда.

Обычный ход


Этот интерфейс реализует класс NormalTurn. Его метод для выполнения хода execute() выглядит так:

override fun execute(pieces: MutableMap<Point, Piece>) {    pieces.remove(from)    pieces[to] = sourcePiece}

Просто извлекаем текущую фигуру по ключу from и помещаем на новую клетку доски по ключу to. При этом, если там была вражеская фигура, она просто перезатрется, т.е. удалится с доски.

Для отмены хода в методе revert() нам нужно знать, была ли в пункте назначения вражеская фигура и какой у нее был тип. Поэтому выполняем действия в обратном порядке и восстанавливаем вражескую фигуру.

override fun revert(pieces: MutableMap<Point, Piece>) {    pieces.remove(to)    pieces[from] = sourcePiece    enemyPiece?.let { pieces[to] = it }}

Ход с превращением


Также сделаем другую реализацию интерфейса Turn. Это будет специальный ход пешки, в результате которого она превращается в другую фигуру. Назовем его PromotionTurn и добавим в него одно дополнительное поле, а именно: в какую фигуру пешка должна превратиться. То есть перед этим ходом у нас имеется пешка, а после уже другая фигура. Поэтому создаем копию исходной фигуры, поменяв ее тип с помощью метода copy().

override fun execute(pieces: MutableMap<Point, Piece>) {    pieces.remove(from)    pieces[to] = sourcePiece.copy(type = toType)}

Для отмены хода нужно также учесть этот факт и восстановить исходную пешку, которая хранится в sourcePiece. Аналогично обычному ходу, восстанавливаем вражескую фигуру, если она была уничтожена.

override fun revert(pieces: MutableMap<Point, Piece>) {    pieces.remove(to)    pieces[from] = sourcePiece    enemyPiece?.let { pieces[to] = it }}

Генератор ходов


Теперь создадим следующий интерфейс, который будут реализовать генераторы ходов для каждого типа фигуры:

interface TurnGenerator {    fun getTurns(        position: Point,         pieces: Map<Point, Piece>    ): Set<Turn>}

Он состоит из одного метода getTurns(), который принимает текущее состояние доски и выбранную фигуру, для которой ищем доступные ходы (в виде ее координаты position). Метод возвращает множество доступных для данной фигуры ходов с учетом расположения других фигур на доске.

Также нам потребуется несколько утилитарных методов, которые мы будем использовать в наших генераторах.

Метод addPointIfPossible() принимает текущую позицию, относительно которой ищем ходы, состояние доски, а также смещение deltaX и deltaY относительно текущей позиции. В методе мы проверяем, не выходит ли новая точка за пределы доски, а также смотрим, нет ли в полученной точке фигуры. Если фигуры нет ход доступен. Если фигура вражеская тоже ход доступен. Дополнительно сохраняем информацию о вражеской фигуре. Ну, и если в полученной точке есть другая наша фигура, то ход недоступен.

fun MutableSet<Turn>.addPointIfPossible(position: Point,pieces: Map<Point, Piece>,deltaX: Int,deltaY: Int): Boolean {val current = pieces.getValue(position)val from = positionval to = Point(from.x + deltaX, from.y + deltaY)val otherPiece = pieces[to]return to.takeIf { it.x in 0..7 && it.y in 0..7 }    ?.let {        when {                otherPiece == null -> { // нет фигуры                this += NormalTurn(sourcePiece = current, from = from, to = to)                true                }                otherPiece.color != current.color -> { // вражеская фигура                this += NormalTurn(sourcePiece = current, from = from, to = to, enemyPiece = otherPiece)                false                }                else -> { // своя фигура                false                }        }    } ?: false}

Метод generateRectangularTurns() проверяет доступные ходы, распространяясь из исходной точки в четырех направлениях под прямым углом. То есть слева, справа, сверху и снизу. Как только где-то встретили препятствие, то дальше по этому направлению ходы не ищем. Также ограничиваем диапазон поиска с помощью параметра maxRange.

fun generateRectangularTurns(position: Point, pieces: Map<Point, Piece>, maxRange: Int): Set<Turn> {val spaces = mutableSetOf<Turn>()var left = truevar right = truevar top = truevar bottom = truefor (i in 1..maxRange) {        if (left) {        left = spaces.addPointIfPossible(position, pieces, -i, 0)        }        if (right) {        right = spaces.addPointIfPossible(position, pieces, i, 0)        }        if (top) {        top = spaces.addPointIfPossible(position, pieces, 0, i)        }        if (bottom) {        bottom = spaces.addPointIfPossible(position, pieces, 0, -i)        }}return spaces}

Эта логика поиска доступных ходов характерна для ладьи.

Далее идет еще один подобный метод generateDiagonalTurns() для поиска ходов по диагоналям также в четырех направлениях с центром в указанной точке. И тут же ограничиваем поиск по maxRange.

fun generateDiagonalTurns(position: Point, pieces: Map<Point, Piece>, maxRange: Int): Set<Turn> {val spaces = mutableSetOf<Turn>()var leftTop = truevar rightTop = truevar leftBottom = truevar rightBottom = truefor (i in 1..maxRange) {        if (leftTop) {        leftTop = spaces.addPointIfPossible(position, pieces, -i, i)        }        if (rightTop) {        rightTop = spaces.addPointIfPossible(position, pieces, i, i)        }        if (leftBottom) {        leftBottom = spaces.addPointIfPossible(position, pieces, -i, -i)        }        if (rightBottom) {        rightBottom = spaces.addPointIfPossible(position, pieces, i, -i)        }}return spaces}

Эта логика поиска подходит для слона.

Генераторы ходов для каждой фигуры


Начнем реализовывать интерфейс TurnGenerator. Самая простая реализация будет у ладьи и слона, так как мы будем вызывать один из двух утилитарных методов, рассмотренных выше.

Для ладьи вызовем generateRectangularTurns() и укажем максимальный диапазон, в котором следует сгенерить ходы (8 клеток в каждом направлении):

class RookTurnGenerator : TurnGenerator {override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =    generateRectangularTurns(position, pieces, MAX_RANGE)private companion object {        const val MAX_RANGE = 8}}

Для ладьи также будем генерить ходы в диапазоне 8 клеток, но с помощью метода generateDiagonalTurns().

class BishopTurnGenerator : TurnGenerator {override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =    generateDiagonalTurns(position, pieces, MAX_RANGE)private companion object {        const val MAX_RANGE = 8}}

Для ферзя используем аналогичный подход, но будем вызывать оба утилитарных метода, объединив их в одно результирующее множество:

class QueenTurnGenerator : TurnGenerator {override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =    listOf(    generateRectangularTurns(position, pieces, MAX_RANGE),    generateDiagonalTurns(position, pieces, MAX_RANGE)    )    .flatten()    .toSet()    private companion object {         const val MAX_RANGE = 8    }}

Для короля будет все так же, за исключением того, что MAX_RANGE будет равен 1 клетке.

class KingTurnGenerator : TurnGenerator {override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =     listOf(    generateRectangularTurns(position, pieces, MAX_RANGE),    generateDiagonalTurns(position, pieces, MAX_RANGE)    )    .flatten()    .toSet()    private companion object {        const val MAX_RANGE = 1    }}

Для коня нам нужно проверить только те точки, до которых можно добраться ходом, напоминающим русскую букву Г (или английскую L, кому как больше нравится). Если в точке нет фигуры или есть вражеская фигура, то данная точка доступна для хода.

class KnightTurnGenerator : TurnGenerator {    override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> {    val spaces = mutableSetOf<Turn>()    spaces.addPointsIfCan(position, pieces, 1, 2)    spaces.addPointsIfCan(position, pieces, 2, 1)    return spaces    }    private fun MutableSet<Turn>.addPointsIfCan(position: Point, pieces: Map<Point, Piece>, absX: Int, absY: Int) {    this.addPointIfPossible(position, pieces, absX, absY)    this.addPointIfPossible(position, pieces, absX, -absY)    this.addPointIfPossible(position, pieces, -absX, absY)    this.addPointIfPossible(position, pieces, -absX, -absY)    }

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

Для краткости приведу только основной метод.

class PawnTurnGenerator : TurnGenerator {    override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> {    val turns = mutableSetOf<Turn>()    val current = pieces.getValue(position)

Метод getStartY()по цвету пешки определяет ее стартовую позицию по вертикали. Поэтому если текущая позиция равна стартовой, то добавляем к возможным ходам на 1 клетку больше.

val range = if (position.y == getStartY(current.color)) 2 else 1val from = position

Метод getDirectionY() в зависимости от цвета определяет направление хода пешки (приращение по вертикали), так как она может двигаться только вперед.

val directionY = getDirectionY(current.color)for (i in 1..range) {    val to = Point(from.x, from.y + directionY * i)

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

if (to in pieces) {    break} else {    turns.addTurnWithPromotionCheck(position, current, to, null)}

Наконец, проверяем клетки атаки впереди слева и впереди справа от пешки.

   addAttackPoint(position, current, 1, directionY, pieces, turns)    addAttackPoint(position, current, -1, directionY, pieces, turns)    return turns        .filter { it.to.x in 0..7 && it.to.y in 0..7 }        .toSet()}//  другие вспомогательные методы}

Объединяем все вместе


Теперь пришла пора объединить все эти классы внутри нашего движка.

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

Метод getSpacesUnderAttack() строит мапу, где ключом является игрок, а значением множество клеток, которые могут быть атакованы фигурами этого игрока. По сути просто проходимся по всем фигурам игрока, для каждой из них получаем допустимые ходы и затем объединяем их в одно общее множество ходов.

fun getSpacesUnderAttack(pieces: Map<Point, Piece>): Map<PieceColor, Set<Point>> {    val spacesUnderAttack = mutableMapOf<PieceColor, MutableSet<Point>>()    pieces.entries.forEach { (position, piece) ->        spacesUnderAttack.putIfAbsent(piece.color, mutableSetOf())        spacesUnderAttack.getValue(piece.color).addAll(getTurnsForPiece(position, pieces).map { turn -> turn.to })    }    return spacesUnderAttack} 

Метод isKingUnderAttack() получает множество всех фигур на доске и цвет короля, для которого производим проверку. Внутри метода мы просто берем множество всех клеток, которые атакует другой игрок (kingColor.other() противоположный цвет), и смотрим, есть ли среди этих клеток та, на которой находится наш король.

fun isKingUnderAttack(pieces: Map<Point, Piece>, kingColor: PieceColor): Boolean {    val spacesUnderAttack = getSpacesUnderAttack(pieces).getValue(kingColor.other())    val king = pieces.entries        .first { it.value.type == PieceType.KING && it.value.color == kingColor }    return king.key in spacesUnderAttack}

Теперь мы можем определить метод getTurnsForPiece(), который будет отсекать все ходы, в результате которых наш король попадает под мат.

override fun getTurnsForPiece(position: Point): Set<Turn> {    val turns = UTILS.getTurnsForPiece(position, pieces)    val result = mutableSetOf<Turn>()    val kingColor = pieces.getValue(position).color    // нужно исключить каждый ход фигуры, который ставит её короля под удар    turns.forEach { turn ->            turn.execute(pieces)            if (!UTILS.isKingUnderAttack(pieces, kingColor)) {            result += turn            }            turn.revert(pieces)    }    return result}

Здесь мы получаем все множество допустимых ходов для данной фигуры. Выполняем каждый ход по очереди с помощью execute(), проверяем, не попадает ли король под мат в результате выполнения этого хода, и затем отменяем ход с помощью revert(). И так для каждого из возможных ходов, которые возвращает генератор.

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

Выполнение хода и проверка статуса игры


Когда ход выбран пользователем или компьютером, движок получает выбранный объект Turn и просто выполняет его в методе executeTurn(), попутно проверяя состояние игры (шах, мат или пат) и фиксируя историю ходов.

override fun executeTurn(turn: Turn): GameState {    val selectedPiece = pieces.getValue(turn.from)    turn.execute(pieces)    val state = getGameState(pieces, selectedPiece.color.other())    saveTurnHistory(selectedPiece, turn, state)    return state}

Проверка состояния в методе getGameState() производится по следующей логике:
Игрок может сделать хотя бы один ход? Его король под ударом? Статус игры
Шах
Обычное состояние, игра продолжается
Мат
Пат
Небольшое лирическое рассуждение про пат
Раньше у меня было какое-то упрощенное понятие пата. Я думал, что это когда ни один игрок не может совершить ход. В обоих случаях вражеский король загнан в угол, и по факту битва уже проиграна. Но если он никем не атакован и при этом не может совершить ни один ход (так как под мат ходить нельзя), то это уже ничья. Согласитесь, что это неочевидно?

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

Дальше дело за ИИ


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

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

Создаем свой шахматный движок алгоритм игры компьютера

21.04.2021 16:08:09 | Автор: admin
Продолжаю рассказывать, как докручиваю свой шахматный движок, и это вторая часть статьи. Она небольшая, здесь я подсвечу настройку ИИ в игре. Сыграем с соперником в лице собственного компьютера.



В первой статье я начал с истории и поделился реализацией ходов. Было много по делу в комментариях, поэтому в планах движок продолжать улучшать. Не претендую на звание гроссмейстера, just for fun. Но, как и для любого программиста, нет предела совершенству :)

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

Безусловно, алгоритм игры можно сделать сколько угодно сложным, а также просчитывать миллионы комбинаций на десятки шагов вперед, однако, я хочу предложить довольно простой алгоритм, который играет на уровне новичка и при этом не совершает откровенно глупых ходов.

Все исходники проекта выложил на Github.

Задаем алгоритм игры компьютера


Создадим класс с очень амбициозным именем Ai и свойством color, который будет содержать цвет игрока-компьютера (чёрный или белый). Класс содержит единственный публичный метод nextTurn(). Этот метод принимает текущее состояние доски в виде фигур и возвращает объект Turn, который он считает наиболее оптимальным.

class Ai(private val color: PieceColor) {    fun nextTurn(board: Board): Turn { ... }

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

val pieces = HashMap(board.getPieces())val currentSpacesUnderEnemyAttack = utils.getSpacesUnderAttack(pieces)    .getValue(color.other())

Теперь запросим у движка все доступные ходы для каждой фигуры текущего игрока-компьютера и для каждого из них вычислим профит числовую оценку успешности хода. Всю необходимую информацию сохраняем во вспомогательный data-класс TurnProfitInfo.

val profits = board.getTurnsForColor(color)    .entries.map { (from, turns) ->        turns.map { turn ->                TurnProfitInfo(                        from = from,                        turn = turn,                profit = turn.getProfit(pieces, currentSpacesUnderEnemyAttack)                )        }    }    .flatten()

Сама логика вычисления профита содержится в методе расширения Turn.getProfit(). После вычисления всех профитов найдем максимальный.

val maxOwnProfit = profits.maxOf { it.profit }

Затем внесем немного хаоса. Из всех ходов, имеющих максимальный профит, выберем случайный, ведь они все равно равнозначны с точки зрения алгоритма. Именно этот ход и вернем как наиболее оптимальный.

val turnPriceInfo = profits.filter { it.profit == maxOwnProfit }    .shuffled()    .first()return turnPriceInfo.turn}

Оценка хода, или какая фигура будет уничтожена


Теперь вернемся к методу getProfit(), который выполнен как расширение класса Turn. На вход он принимает текущее состояние доски и клетки, которые могут быть атакованы противником на следующем ходу.

private fun Turn.getProfit(pieces: HashMap<Point, Piece>,currentSpacesUnderEnemyAttack: Set<Point>): Int {var profit = 0

Если в результате хода уничтожаем вражескую фигуру, то прибавляем ее стоимость к профиту. Затем делаем пробный ход.

this.enemyPiece?.let { profit += it.getPrice() }this.execute(pieces)

После выполнения хода определяем клетки, которые могут быть атакованы соперником:

val newSpacesUnderEnemyAttack = utils.getSpacesUnderAttack(pieces)    .getValue(color.other())

Если в результате выполнения хода мы уводим нашу фигуру из под атаки, то прибавляем ее стоимость к профиту. А если фигура, наоборот, попадает под атаку, то вычитаем ее стоимость.

if (this.from in currentSpacesUnderEnemyAttack && this.to !in newSpacesUnderEnemyAttack) {    profit += this.sourcePiece.getPrice()} else if (this.from !in currentSpacesUnderEnemyAttack && this.to in newSpacesUnderEnemyAttack) {    profit -= this.sourcePiece.getPrice()}

В конце отменяем пробный ход.

this.revert(pieces)return profit}

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

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

Вместо заключения


Можно не один месяц совершенствовать алгоритм игры. Можно строить дерево принятия решений с большим уровнем вложенности. Можно значительно уменьшить расход памяти, используя битовые поля для хранения состояния доски. Однако такой цели передо мной не стояло.

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

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

5 игрушек, чтобы ребёнок почувствовал программирование

31.12.2020 00:22:22 | Автор: admin

Власть над материальными объектами пожалуй, лучший способ оценить мощь программирования.

Привет, Хабр! Я пришла разбавить карантинный онлайн подборкой игрушек, которые можно подержать в руках. Надоело же сидеть за экраном! Да и будущее за интернетом вещей, объем этого рынка растёт почти на 25% каждый год.

Гусеница Code-a-Pillar Twist (вторая версия игрушки)

Возраст: от 3 до 6 лет

Цена: 35 долларов на Amazon

Code-a-Pillar посвящение в программисты. Гусеница состоит из 5 модулей на каждом можно выбрать команду, которую она будет выполнять, например, поворот или проигрывание мелодии. Таким образом ребёнок может программировать игрушку на выполнение разных последовательностей действий то есть пощупать алгоритмы.

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

А ещё она прикольно мигает и издает смешные звуки многие ребята тащатся от такого. Музыкальные сегменты отдельная тема для радости. Вот цитата из отзыва на Amazon: My grandkids call music segments dance time segments. Но где плюсы для детей, там могут быть минусы для взрослых, поэтому имейте в виду, если не любите шумиху:)

Важно! Гусеница очень не любит ковры колесики цепляются за ворс, её любимая стихия просторные комнаты с чистым гладким полом. И не забудьте купить для неё 4 AA батарейки.

Настольная игра Прогеры

Возраст: от 6 лет до

Цена: 1192 рублей на Ozon

Настолка помогает на практике понять, что такое алгоритмы, развить стратегическое мышление, память, воображение, логику. И просто весело провести время, ведь для игры нужно от 2-х до 4-х человек. Здесь 2 уровня сложности, поэтому родителям и ребятам постарше тоже будет интересно.

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

LEGO BOOST

Возраст: от 7 лет до

Цена: 8469 рублей в Детском мире

Из этого набора из 847 деталей собирается минимум 5 моделей: робот, котик, гитара, вездеход, автомастерская. Всё это можно программировать в специальном приложении с простым визуальным интерфейсом, которое устанавливается на iOS от версии 10.2 и на Андроид от 5.0 версии.

Игрушка может очень многое. Например, робот способен двигаться по запрограммированному маршруту, определять расстояние, различать цвета, менять скорость, выражать эмоции, жестикулировать. На гитаре можно создавать свои мелодии. А киберкотик так прикольно реагирует на заботу, что в очередь за тем, чтобы его погладить и покормить, станут и все взрослые члены семьи.

Робот Otto на Arduino

Возраст: от 8 лет до

Цена: от 30 евро на ottodiy.com (доставляют по всему миру) за самый простой набор, где детали нужно печатать на 3D-принтере

Оtto напечатанный на 3D-принтереОtto напечатанный на 3D-принтере

Otto возможность почувствовать себя не только программистом, но и настоящим робототехником. Ведь детали роботапечатаются на 3D-принтерепо специальным файлам, которые идут в наборе. На печать нужно не более 5 часов, а собирается он всего за час. Можно, конечно, купить и набор с готовыми элементами, но это дороже (минимум на целых 25 евро) и не так интересно, ведь самое клёвое пройти весь путь создания Otto от начала и до конца.

Программируется робот с помощью перетаскивания блоков кода в простой и понятной программе Blockly на основе Скретч. Такой легкий старт может стать базой для перехода к C/C++. Кстати,можнокодить и в Arduino IDE так что это игрушка на вырост или, как минимум, подарочек и себе:)

Программирование робота даёт развернуться фантазии, ведь он может кучу всего: танцевать, реагировать на касания, исполнять мелодии и даже поднимать предметы.

Arduino с гарниром

Возраст: от 10 лет до

Цена: от 1500 рублей за добротный набор на Aliexpress, от 2000 рублей за наборы отечественного производителя

Ардуино уверенный шаг в мир электроники и робототехники. Это микроконтроллер, к которому можно подключать кнопки, диоды, датчики (движения, звука, температуры, дыма и т. д.), модули связи, двигатели и многое-многое для создания умных устройств. А также Ардуино одноименная бесплатная IDE для написания программ (использует диалект С++).

Предельно упрощая, Ардуино умная розетка, которая включает и выключает присоединённые элементы, в зависимости от того, как её запрограммировали, позволяя создавать всё, на что хватает фантазии и смекалки. Программировать можно в специально созданной для Arduino программе скетч или в интуитивно-понятном визуальном редакторе кода, например, Scratch для Arduino (сокращённо S4A).

Есть несколько видов Arduino, для начала подойдёт классика модель Uno. Также можно взять Nano, которая меньше, дешевле и мало чем отличается от Uno (даже сердце у них одинаковое, всё тот же микроконтроллер ATMEGA328P). За что некоторые небезосновательно считают Nano даже круче.

Вот большая сравнительная таблица ардуинок для тех, кто в темеВот большая сравнительная таблица ардуинок для тех, кто в теме

С нулевыми знаниями по Arduino лучше купить набор, в котором есть всё необходимое для начала творчества и мануал, который поможет разобраться.

Вот несколько наборов c хорошими отзывами:

  1. Arduino Keyestudio Super c 32 проектами (3149 рублей на Aliexpress)

  2. Набор UNO R3 Starter Kit с RFID модулем, контроллером, совместимым со средой Arduino, и 12 уроками (2399 рублей на Суперайс)

  3. Умный робот-автомобиль на Ардуино (1600 рублей на Aliexpress)

Неплохие наборы на Амперке, дороже, чем в Китае, зато свои.

Конечно, можно купить Ардуино отдельно (например, 399 рублей на Ampero) и потом добрать нужные элементы (модули и рассыпуху) под проект. Будет дешевле и кастомнее, но сложнее разобраться с нуля.

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

Видео для вдохновения (устройство работает на Ардуино Nano):

P.S.: Буду благодарна каждому, кто дополнит подборку.

Все игрушки отобраны из советов родительского чатика CODDY и зарубежных обзоров. Цены указаны состоянием на 30.12.2020.

Подробнее..

Взламываем Ball Sort Puzzle

08.01.2021 12:15:36 | Автор: admin
Определение кружочков при помощи OpenCVОпределение кружочков при помощи OpenCV

Ball Sort Puzzle это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.

Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался насколько бы глубоко я не пытался продумать свою стратегию. В итоге с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.

Во-первых, игра бесконечна почти бесконечна. По крайней мере уже сейчас на YouTube есть прохождения всех уровней в плоть до 5350, а в телеграмме гуляют скриншоты 10к+ уровней. Вторая особенность, и вот это уже некрасиво, не у всех уровней есть решение.

Ну это ни в какие ворота против нас играет коварный ИИ. Нужно действовать соответственно!

Под катом мы:

  • Придумаем алгоритм, решающий эту головоломку (Python)

  • Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)

  • Напишем телеграм бота, который будет принимать скриншоты и возвращать решения

  • Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции

Погнали!


Алгоритмическое решение задачи

Решать такую задачу было весьма занимательно. Поэтому предлагаю заинтересованному читателю попробовать решить её самостоятельно.

Я же в первую очередь решил побить проблему на сущности. Это сделает алгоритм чуть более элегантным, а так же поможет в будущем парсить скриншоты игры:

class Color
class Color:    def __init__(self, symbol, verbose_name, emoji):        self.symbol = symbol        self.verbose_name = verbose_name        self.emoji = emoji    def __repr__(self) -> str:        return f'Color({self})'    def __str__(self) -> str:        return self.emoji
Beta-редактор хабра ломается на рендеринге emoji :poop:Beta-редактор хабра ломается на рендеринге emoji :poop:
class Ball
class Ball:    def __init__(self, color: Color):        self.color = color    def __eq__(self, other: 'Ball'):        return self.color is other.color    def __repr__(self):        return f'Ball({self.color.verbose_name})'    def __str__(self) -> str:        return str(self.color)
class Flask
class Flask:    def __init__(self, column: List[Color], num: int, max_size: int):        self.num = num        self.balls = [Ball(color) for color in column]        self.max_size = max_size    @property    def is_full(self):        return len(self.balls) == self.max_size    @property    def is_empty(self) -> bool:        return not self.balls    def pop(self) -> Ball:        return self.balls.pop(-1)    def push(self, ball: Ball):        self.balls.append(ball)    def __iter__(self):        return iter(self.balls)    def __getitem__(self, item: int) -> Ball:        return self.balls[item]    def __len__(self) -> int:        return len(self.balls)    def __str__(self) -> str:        return str(self.balls)
class Move
class Move:    def __init__(self, i, j, i_color: Color):        self.i = i        self.j = j        self.emoji = i_color.emoji    def __eq__(self, other: 'Move') -> bool:        return (self.i, self.j) == (other.i, other.j)    def __repr__(self) -> str:        return f'Ball({self})'    def __str__(self) -> str:        return f'{self.i} -> {self.j}'

Для решения будем использовать метод поиска с возвратом (Backtracking).

Решение задачи методом поиска с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют.

В случае с нашей игрой это метод применяется так: мы рекурсивно обходим все возможные перестановки шариков (move) до тех пор, пока

  • Либо нас не выкинет наш критерий остановки решённый пазл

  • Либо в нашем хранилище состояний (states) не будет всех возможных перестановок в таком случае решения нет

    def solve(self) -> bool:        if self.is_solved:            return True        for move in self.get_possible_moves():            new_state = self.commit_move(move)            if new_state in self.states:  # Cycle!                self.rollback_move(move)                continue            self.states.add(new_state)            if self.solve():                return True            self.rollback_move(move)        return False

Алгоритм достаточно прямолинейный и далеко не всегда выдаёт оптимальное решение. Тем не менее он справляется с решением большинства задачек из игры за 1 сек.

Проверим алгоритм на чём-нибудь попроще:

def test_3x3():    data_in = [        [color.RED, color.GREEN, color.RED],        [color.GREEN, color.RED, color.GREEN],        [],    ]    puzzle = BallSortPuzzle(data_in)    result = puzzle.solve()    assert result is True    play_moves(data_in, puzzle.moves)
Алгоритм в действииАлгоритм в действии

Полная версия программы доступна на github.

Распознавание скриншотов игры

Мы будем работать с .jpg картинками двух видов

Скриншоты уровней игры Скриншоты уровней игры

Каждый чётный раунд игры состоит из 11 колб и 36 шариков, а нечётный 14 колб и 48 шариков. Чётные и нечётные раунды отличаются расположением колб, но на счастье всё остальное у них одинаковое по 4 шарика в колбе, 2 колбы пустые, цвета используются одни и те же.

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

class ImageParser:    def __init__(self, file_bytes: np.ndarray, debug=False):        self.image_orig = cv2.imdecode(file_bytes, cv2.IMREAD_COLOR)        self.image_cropped = self.get_cropped_image(self.image_orig)    @staticmethod    def get_cropped_image(image):        height, width, _ = image.shape        quarter = int(height / 4)        cropped_img = image[quarter : height - quarter]        return cropped_img
Рабочая областьРабочая область

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

    @staticmethod    def normalize_circles(circles):        last_y = 0        for circle in circles:            if math.isclose(circle[1], last_y, abs_tol=3):                circle[1] = last_y            else:                last_y = circle[1]        return circles    def get_normalized_circles(self) -> List[Any]:        image_cropped_gray = cv2.cvtColor(self.image_cropped, cv2.COLOR_BGR2GRAY)        circles = cv2.HoughCircles(image_cropped_gray, cv2.HOUGH_GRADIENT, 2, 20, maxRadius=27)        if circles is None:            raise ImageParserError("No circles :shrug:")        circles = np.round(circles[0, :]).astype("int16")        ind = np.lexsort((circles[:, 0], circles[:, 1]))        circles = circles[ind]        circles = self.normalize_circles(circles)        ind = np.lexsort((circles[:, 0], circles[:, 1]))        circles = circles[ind]        return circles
Отсортированные шарики слева-направо, сверху-внизОтсортированные шарики слева-направо, сверху-вниз

Дальше будем определять цвет шарика.

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

    @staticmethod    def get_dominant_color(circle) -> Color:        colors, count = np.unique(circle.reshape(-1, circle.shape[-1]), axis=0, return_counts=True)        dominant = colors[count.argmax()]        return dominant
Найденные кружочки Найденные кружочки

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

d = \sqrt{(r2-r1)^2 + (b2-b1)^2 + (g2-g1)^2}

Посчитаем такое расстояние до каждого из изначально заданных цветов и найдём минимальное

RBG_TO_COLOR = {    (147, 42, 115): VIOLET,    (8, 74, 125): BROWN,    (229, 163, 85): L_BLUE,    (68, 140, 234): ORANGE,    (196, 46, 59): BLUE,    (51, 100, 18): GREEN,    (35, 43, 197): RED,    (87, 216, 241): YELLOW,    (125, 214, 97): L_GREEN,    (123, 94, 234): PINK,    (16, 150, 120): LIME,    (102, 100, 99): GRAY,}COLORS = np.array(list(RBG_TO_COLOR.keys()))def get_closest_color(color: np.ndarray) -> Color:    distances = np.sqrt(np.sum((COLORS - color) ** 2, axis=1))    index_of_smallest = np.where(distances == np.amin(distances))    smallest_distance = COLORS[index_of_smallest].flat    return RBG_TO_COLOR[tuple(smallest_distance)]  # type: ignore

Далее нам остаётся только распределить шарики по колбам. Итоговый class ImageParser доступен на github.

Преобразуем программу в Telegram Bot

Узнать про то, как сделать телеграм бота на Python можно сразу из нескольких статей на хабре. Я лишь опишу пару нюансов, с которыми столкнулся.

Так как наш бот хоститься на Яндекс.Функции триггером к его запуску будет запрос на заданный нами webhook.

Whenever there is an update for the bot, we will send an HTTPS POST request to the specified url, containing a JSON-serializedUpdate.

Если в сообщении есть массив photo, то можно увеличить вероятность распознавания шариков выбрав фотографию с максимальным весом:

if photos := message.get('photo'):    # here photos is an array with same photo of different sizes    # get one with the highest resolution    hd_photo = max(photos, key=lambda x: x['file_size'])

Чтобы скачать картинку, придётся сделать 2 запроса к Telegram API

# Получение данных о файле, нас интересует ключ ответа file_pathGET https://api.telegram.org/bot{BOT_TOKEN}/getFile?file_id={file_id}# Получение самого файлаGET https://api.telegram.org/file/bot{BOT_TOKEN}/{file_path}

В остальном же всё просто получаем картинку, скармливаем её парсеру и затем алгоритму-решателю.

main.py
def handler(event: Optional[dict], context: Optional[dict]):    body = json.loads(event['body'])  # type: ignore    print(body)    message = body['message']    chat_id = message['chat']['id']    if photos := message.get('photo'):        # here photos is an array with same photo of different sizes        hd_photo = max(photos, key=lambda x: x['file_size'])  # get one with the highest resolution        try:            file = telegram_client.download_file(hd_photo['file_id'])        except TelegramClientError:            text = "Cant download the image from TG :("        else:            file_bytes = np.asarray(bytearray(file.read()), dtype=np.uint8)            try:                image_parser = ImageParser(file_bytes)                colors = image_parser.to_colors()            except ImageParserError as exp:                text = f"Cant parse image: {exp}"            else:                puzzle = BallSortPuzzle(colors)  # type: ignore                solved = puzzle.solve()                if solved:                    text = get_telegram_repr(puzzle)                else:                    text = "This lvl don't have a solution"    else:        return {            'statusCode': 200,            'headers': {'Content-Type': 'application/json'},            'body': '',            'isBase64Encoded': False,        }    msg = {        'method': 'sendMessage',        'chat_id': chat_id,        'text': text,        'parse_mode': 'Markdown',        'reply_to_message_id': message['message_id'],    }    return {        'statusCode': 200,        'headers': {'Content-Type': 'application/json'},        'body': json.dumps(msg, ensure_ascii=False),        'isBase64Encoded': False,    }

Отмечу ещё один нюанс: телеграм очень строго следует политике экранирования спецсимволов. Для Markdown это:

To escape characters '_', '*', '`', '[' outside of an entity, prepend the characters '\' before them.

Любой такой неэкранированный символ и вы не увидите ответа в телеграм-чате. И останется только гадать является ли это ошибка интеграции или вот такой коварный баг. Будьте осторожны.

Деплой бота в Яндекс.Функцию

Про создание Я.Функции также есть отличная статья от @mzaharov. Там подробно описан процесс заведения функции, а также установки вебхука для телеграмм бота.

Я расскажу как сделал Continuous Delivery при помощи GitHub Actions. Каждая сборка мастера увенчивается деплоем новой версии функции. Такой подход заставляет придерживаться модели разработки GithubFlow с его главным манифестом

Anything in themasterbranch is always deployable.

Каждая сборка мастера состоит из 3ёх этапов

  • lint (black, flake8, isort, mypy) проверка кода на соответствие всем стандартам Python 2020

  • test тестируем программу с помощью pytest, поддерживая качество и покрытие кода

  • deploy непосредственно заливаем новую версию приложения в облако

Деплоить будем с помощью Yandex-Serveless-Action уже готового Action для использования в своих пайплайнах

  deploy:    name: deploy    needs: pytest    runs-on: ubuntu-latest    if: github.ref == 'refs/heads/master'    steps:      - uses: actions/checkout@master      - uses: goodsmileduck/yandex-serverless-action@v1        with:          token: ${{ secrets.YC_TOKEN }}          function_id: ${{ secrets.YC_FUNCTION_ID }}          runtime: 'python38'          memory: '256'          execution_timeout: "120"          entrypoint: 'main.handler'          environment: "\            TELEGRAM_BOT_TOKEN=${{ secrets.TELEGRAM_BOT_TOKEN }}"          source: 'app'

Переменные окружения программы и сборки спрячем в GitHub Secrets на уровне репозитория.

Результат

Пример работы @ballsortpuzzlebotПример работы @ballsortpuzzlebot

Бота можно найти в telegram по позывному @ballsortpuzzlebot.

Все исходники на Github.

Присоединяйтесь к маленькому community любителей этой игры в telegram. Бот был добавлен в группу и внимательно следит за всеми отправленными картинками.

Бонус! Уровни, у которых нет решения
Lvl 4091Lvl 4091Lvl 6071Lvl 6071

Мой алгоритм умывает руки говорит что перебрал все возможные комбинации и решения нет. Возможно это баг алгоритма.. или QA-отдел мобильной игры просто забил на эти уровни, так как не предполагал, что кто-то так далеко зайдёт)

Заключение

Для меня это был интересный опыт скрещивания технологий (Telegram API + Python + OpenCV + Lambda). Надеюсь он окажется полезен кому-нибудь ещё.

Найденные баги, предложения по оптимизации алгоритма, или даже PR в репозиторий крайне приветствуются

С новым годом!

Подробнее..

Перевод Совместная игра в Factorio лучшее техническое собеседование, что мы проводили

09.04.2021 14:13:02 | Автор: admin
В последнее время много копий сломано вокруг технических собеседований. Очевидно, что инвертирование двоичного дерева на доске практически никак не связано с практическими навыками реального программиста. Примитивный Fizzbuzz по-прежнему остаётся самым эффективным тестом. Как следствие, выросло внимание к опенсорсным проектам, но оказалось, что это тоже не очень хороший показатель, потому что у большинства профессионалов нет на них времени.

У нас в компании самое эффективное собеседование по программированию на сегодняшний день это обычно какое-то домашнее задание на несколько дней, в котором кандидата просят исправить баг или реализовать небольшую функцию. Это не очень хорошо, потому что занимает много времени, и человек может получить внешнюю помощь (или погуглить, если функция достаточно распространённая). С другой стороны, некоторые крупные компании вместо этого удвоили количество собеседований с доской (и алгоритмами), подвергая будущих инженеров многочасовым сессиям онлайн-программирования с различным уровнем инвазивного наблюдения.

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

Factorio?


Factorio это игра об автоматизации. Вероятно, лучшим введением будет этот трейлер, но, по сути, ваша задача построить автоматизированный завод, способный запустить ракету в космос.

Начинаете с нуля. Добываете вручную железную руду и камень, строите плавильную печь, чтобы плавить руду в железные пластины, из которых можно скрафтить автоматический твёрдотопливный бур. Можно самостоятельно забирать железную руду из бура и закладывать её в плавильню, но более эффективно использовать автоматический конвейер. Потом можно использовать полученное железо, чтобы сделать другой бур, который автоматизирует добычу угля. Затем строится конвейер для забора угля и конвейер для его передачи в бур. Эта крошечная фабрика производит железные пластины, из которых можно сделать третий бур и начать добычу медной руды, которая позволяет крафтить медные плиты, а из них можно сделать медный провод, необходимый для работы погружного насоса. В сочетании с паровым котлом и паровым двигателем это даёт нам первую электроэнергию. Её можно использовать для исследовательского центра и изобретения новых технологий, таких как сборочный автомат. Как только разблокируете сборочные автоматы, можете использовать сделанный вручную провод для создания сборочной машины, которая будет автоматически изготавливать эти провода.

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

Выбор направления


Игра начинается без установленной цели и почти без направления. Ведущий программист должен быть способен изучить UI и определить цель, а затем разработать план для её достижения. От джуниора ожидают правильного выполнения задач, поставленных ведущим разработчиком. Предполагается, что стажёр работает с наставником, но джуниор должен быть в состоянии самостоятельно устранить основные проблемы со своим кодом, прежде чем просить помощи от старшего. Миддл должен уметь работать независимо, как только ему дают задание, но от него не ожидают архитектурного проектирования.

Конкретные ожидания можно сформулировать так:

  • Стажёр, как правило, должен быть в состоянии разместить чертёж и соединить его с чем-то ещё, например, с месторождением руды.
  • От джуниоров ожидают самостоятельного строительства производственной линии, пусть и не оптимальной. Им может понадобиться помощь старшего разработчика в том, как правильно направить конвейеры ко всем промежуточным сборочным автоматам.
  • Как только получено задание, миддл должен спроектировать почти оптимальную производственную линию (без маяков) с минимальным контролем.
  • Ведущий программист не нуждается в руководстве, способен сам определить цели и разработать план действий, а затем делегировать эти задачи другим программистам.

Командная работа


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

Если игрок уйдёт в себя, начнёт делать всё сам или молча исправлять проблемы, это быстро навлечёт на него гнев команды по тем же самым причинам, по которым коллеги злятся на программистов-ковбоев. К счастью, в Factorio есть встроенный эквивалент git blame: он показывает последнего игрока, который изменил любую сущность. Таким образом, если кто-то поставил костыль и не сообщил команде о проблеме, то когда этот костыль наконец сломается все узнают, кто виноват. Если хотите выиграть, придётся плотно сотрудничать с товарищами по команде.

Отладка


Одним из главных навыков для программиста является отладка. Это, пожалуй, самая очевидная параллель между Factorio и реальной разработкой ПО. Что-то может сломаться очень далеко от фактического источника проблемы. Способность быстро выяснить реальную проблему это критический навык, и процесс мышления почти идентичен отслеживанию причины сбоя в реальной программе. Если перестал работать сборочный автомат, сначала нужно проверить выходящие потоки. Потом проверить, какого ингредиента не хватает на входе. Затем проследить ингредиент по фабрике, чтобы узнать, где он производится. И повторять процесс снова и снова, до тошноты.

Отладка в Factorio быстро усложняется. Как только вы построите нефтеперерабатывающий завод, то займётесь крекингом, где на выходе три разных трубы (мазут, дизельное топливо и попутный нефтяной газ), и если какая-то из них по какой-то причине стопорится, то весь завод прекращает работу.

Бывали случаи, когда весь завод останавливался, потому что вы начали исследовать что-то, не требующее жёлтой науки. В результате вы перестали использовать каркасы дронов, которым перестали поставляться электрические двигатели, где использовалась смазочная жидкость, для производства которой забирался мазут. В итоге стопорилась выходящая труба на нефтеперерабатывающем заводе, из-за чего у вас заканчивался попутный нефтяной газ (petrolium), что останавливало производство пластмассы. Как результат, прекращался выпуск сигнального красного провода и вся фабрика выходила из строя. Опытные игроки предвидят подобные сценарии и внедряют самобалансирующийся крекинг нефти, чтобы всегда гарантировать баланс системы. Такой завод остановится только при закупорке выходящей трубы с попутным газом. Если хорошему программисту дадут сломавшийся нефтеперерабатывающий завод, он обычно сможет проследить проблему до источника, понять, что произошло, и быстро попытаться найти решение. С другой стороны, если человек просто плюхает на землю пару новых резервуаров без веской причины (он абсолютно уверен, что смазочная жидкость будет нужна всегда), то это большой красный флаг на методы решения проблем в его программах.

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

Код-ревью


Часто первоначальный дизайн нужно исправить для повышения производительности или пропускной способности. Хорошие программисты не только примут критику своих чертежей, но и учтут её в будущей работе. Если они не согласны с изменением, то предоставят конкретное объяснение, чтобы команда могла более точно обдумать плюсы и минусы предлагаемого изменения.

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

Стиль написания кода и фреймворки


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

Конструкция магистрального ленточного конвейера включает 4-8 конвейеров, разделённых на две секции (для подземных конвейеров). Он помещается в центре фабрики, и всё производство происходит перпендикулярно ленте. Эта конструкция опирается на несколько правил, нарушение которых может привести к полному хаосу. Во-первых, всегда следует использовать разделитель на выходе с конвейера. Никогда нельзя перенаправлять всю ленту: пустое пространство для другой ленты означает, что вы теряете целый конвейер ресурсов, даже после апгрейда. Во-вторых, все заводы должны масштабироваться перпендикулярно основному конвейеру. Невозможность быстрого масштабирования приведёт либо к огромной потере пространства, либо к невозможности масштабирования производственной линии, потому что она окружена другими производственными линиями.


Логистическая сеть

Есть разные способы построения логистических сетей. Самый простой с сундуками пассивного снабжения. Но есть другой метод сундуки хранения с фильтром, который решает проблему с мусором. Оба метода требуют правильной установки ограничителей в нужных местах. Сундуки пассивного снабжения обычно ограничены пространством сундука. К сундукам хранения нужно поставить манипулятор для подключения сундука к логистической сети. И обеспечить не менее N предметов перед установкой манипулятора. Если забыть про эти шаги, то будут впустую потрачены огромные ресурсы. Если программист постоянно забывает про ограничители на выходах это красный флаг, что человек небрежно относится к производительности в реальных приложениях.

В других случаях команда может применять заранее разработанные чертежи, такие как проект ядерного реактора или роботизированного завода на дронах (bot factory). Они могут быть крайне сложными, но если сделать над собой усилие и разобраться, то они чрезвычайно экономят время. Остерегайтесь кандидатов, которые не хотят настраивать на заводе новый элемент просто потому, что не могут отследить сложную управляющую логику. Или кто бросает попытки разобраться в алгоритме функционирования такого завода, несмотря на очевидные преимущества дронов перед конвейерами.


Неоптимальный дизайн завода на дронах, источник

Многопоточность


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

Количество путей в железнодорожной сети соответствует количеству ядер CPU. Один железнодорожный путь трудно масштабировать больше, чем на несколько полос, потому что пропускная способность всей системы очень быстро ограничивается, даже с зонами ожидания. Наиболее распространённой конструкцией является двухполосная конструкция, по одной полосе в каждую сторону. Здесь появятся проблемы с пропускной способностью, когда возникнет необходимость постоянно разгружать поезда. Поэтому в больших железнодорожных сетях минимум по четыре полосы, причём две внешние действуют как объездные пути, чтобы избежать пересечений, когда это возможно.

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

Масштабирование


Как и в программном обеспечении, масштабирование производства в Factorio вводит новые проблемы в оригинальный дизайн чертежей и часто требует полной перестройки для максимального повышения производительности, с установкой модулей продуктивности и модулей скорости с маяками. Конвейеры становятся узким местом производительности даже на максимальной скорости ленты, заставляя искать способы разделить конструкции так, чтобы позже можно было вставить больше лент, или разделить заводы на модули.

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

В конце игре для управления поездами требует перехода с push-архитектуры на pull-архитектуру, поскольку push-архитектура не справляется с высокой пропускной способностью. Это неизбежно приводит к использованию функции Train Limit и изучению, как использовать логические сети для кодирования базовой логики, чтобы станция запрашивала поезд только тогда, когда действительно готова полностью заполнить его ресурсами, вместо обычной игровой тактики в начале игры, когда куче поездов просто даётся команда ехать за железом. Новая схема сводит к минимуму количество поездов и при этом гарантирует, что в сети обслуживаются все станции.

Часто бывает, что ограничения входных линий в сборочный автомат и лимиты скорости манипулятора требуют перепроектирования заводов вокруг, точно так же, как высокоскоростные вычисления требуют знания узких мест в работе CPU. Эти узкие места почти никогда не являются проблемой, пока вы не достигнете определённого масштаба, но после этого начинают ограничивать производительность.

Микросервисы и модули


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

Мегабазу на основе поездов иногда называют дизайном городских кварталов (city-block), где поезда вокруг кварталов завода контролируют все входы и выходы. Таким образом, каждый отдельный квартал изолирован от всех остальных, поскольку все входные данные чисты в том смысле, что они поступают из железнодорожной сети. Это почти идентично архитектуре микросервисов (по HTTP) или межпроцессному взаимодействию (IPC), с аналогичными потенциальными проблемами из-за задержек I/O, поскольку результаты не могут поступать постоянно, они должны передаваться в пакетах или поездах по железнодорожной сети.

Модульная архитектура пытается сохранить некое подобие основного конвейера, но вместо этого разделяет ленты на заводе и использует модульные блоки, которые принимают стандартные входы и стандартные выходы. Иногда этого можно достичь полностью с помощью дронов, но обычно материалы приходится доставлять по конвейеру на большие расстояния. Это очень похоже на систему модулей для монолитного приложения с теми же компромиссами.

Такие мегабазы представляют верхний уровень дефолтного сервера Factorio. Конечно, существует много модов, которые гораздо усложняют игру.

Распределённые системы


Space Exploration полностью переделанная версия Factorio для колонизации космоса. Здесь планеты становятся ограниченными ресурсами, требуя от игроков колонизировать другие миры и использовать ракеты для передачи ресурсов между планетами. Из-за огромной задержки с доставкой материалов между планетами, координация этих баз приводит к возникновению проблем, сходных с глобально распределённой системой баз данных. Даже в логической сети приходится бороться с задержкой, потому что автоматическая система теряет из виду элементы, которые запущены, но ещё не достигли целевой планеты. Если это не учитывать, возникают дубликаты запросов для всех нужных элементов. С точно такой же проблемой сталкиваются распределённые системы при попытке обеспечить согласованность между узлами.

Вывод


В целом софтверная индустрия не имеет ни малейшего представления, как находить и нанимать лучших разработчиков. Наверное, совместная игра в Factorio стала лучшим техническим собеседованием, которые мы когда-либо проводили. И это нас сильно смущает. Такое собеседование дико непрактично, занимает более 20 часов в мультиплеере с первого раза или 8 часов для команды опытных игроков. Что из этого можно извлечь? Не знаю. Мы, конечно, не можем перейти на Factorio в качестве метода собеседований с таким же успехом можно просто дать кандидату домашнее задание.

Но это уже лучше, чем собеседование на доске.
Подробнее..

Перевод Используем глубокое обучение, чтобы отгадывать страны по фотографиям в GeoGuessr

18.04.2021 14:12:21 | Автор: admin
Во время последнего локдауна в Великобритании мы с женой играли в GeoGuessr. Эта игра более размеренна, чем те, в которые мы обычно играем, но хорошо подходит для нашей семьи с 11-недельным младенцем, который становится активнее с каждым днём.

GeoGuessr это игра о географических исследованиях. Вас бросают на случайную точку в Google Street View, после чего ваша задача указать своё местоположение на карте. Можно осматривать окрестности, увеличивать изображение и двигаться по пути автомобиля на местных улицах.

image

Нас серьёзно заинтересовали ежедневные соревнования (Daily Challenge) на GeoGuessr. Мы начали заходить на сайт каждый день и пытаться поставить новый рекорд. В формате Daily Challenge на каждый раунд выделяется по три минуты, которые мы тратили или на бешеное кликанье по австралийскому бушу (при этом иногда путая его с Южной Африкой), или на обсуждение того, есть ли в шведском языке буква .

Теперь у меня накопился большой объём знаний типа увижу узнаю. Я могу опознать Гренландию с первого взгляда. Вернулись мои утерянные знания флагов стран, а также появились новые знания о флагах штатов США, о тех странах, где ездят по левой и правой полосам, где используют километры или мили. Я знаю почти все доменные имена стран (их часто можно встретить на рекламных билбордах вдоль дорог) мне ещё долго не забыть .yu.

Вы знали, что чёрно-белые дорожные ограждения распространены в России и Украине? Или что можно разобрать синюю полосу EU на автомобильных номерах, несмотря на размытие Google Street View? Подробнее об этом можно прочитать в этом руководстве из 80 тысяч слов Geoguessr the Top Tips, Tricks and Techniques.

Указывающая вниз полосатая красно-белая стрелка даёт понять, что вы находитесь в Японии, с большой вероятностью, на острове Хоккайдо или, возможно, на острове Хонсю рядом с горами.


image

Немного глубокого обучения


Однажды я прочитал, что машинное обучение уже умеет делать всё, что и человек, но меньше чем за одну секунду. Распознать лицо, выбрать текст из изображения, повернуть, чтобы не врезаться в другую машину. Это заставило меня задуматься, а размышления привели к статье под названием Geolocation Estimation of Photos using a Hierarchical Model and Scene Classification, написанной Эриком Мюллером-Будаком, Кадером Пусту-Иреном и Ральфом Эвертом. В этой статье геолокализация рассматривается как задача классификации, в которой Земля подразделена на географические ячейки.

Она прогнозирует GPS-координаты фотографий.

image

Даже по фотографиям, которые сделаны в помещении! (Daily Challenge игры GeoGuessr часто засовывает игрока внутрь музеев).

Недавно авторы статьи выпустили реализацию на PyTorch и указали веса для обученной модели base(M, f*) с внутренней архитектурой ResNet50.

Я предположил, что обученная модель не очень хорошо будет соответствовать тем частям фотосфер, которые я смогу получить от GeoGuessr. В качестве данных обучения авторы использовали подмножество набора данных из 100 миллионов фотографий Yahoo Flickr Creative Commons (YFCC100M). В него вошли примерно пять миллионов изображений Flickr с геометками и неопределённых фотографий, например, снимков внутри помещений, еды и людей, местоположение которых сложно спрогнозировать.

Любопытно было то, что в наборе данных Im2GPS люди определяли местоположение изображения с точностью на уровне страны (в пределах 750 км) в 13,9% случаев, а Individual Scene Networks справлялись с этой задачей в 66,7% случаев!

image

Итак, возник вопрос: кто лучше в GeoGuessr, моя жена (потрясающий игрок) или машина?

Автоматизируем GeoGuessr с помощью Selenium


Для скрейпинга скриншотов из текущего внутриигрового местоположения я создал программу на Selenium, четыре раза выполняющую следующие действия:

  • Сохраняем скриншот canvas
  • Делаем шаг вперёд
  • Поворачиваем обзор примерно на 90 градусов


Количество повторов этих действий можно настроить через NUMBER_OF_SCREENSHOTS в показанном ниже коде.

'''Given a GeoGuessr map URL (e.g. https://www.geoguessr.com/game/5sXkq4e32OvHU4rf)take a number of screenshots each one step further down the road and rotated ~90 degrees.Usage: "python file_name.py https://www.geoguessr.com/game/5sXkq4e32OvHU4rf"'''from selenium import webdriverimport timeimport sysNUMBER_OF_SCREENSHOTS = 4geo_guessr_map = sys.argv[1]driver = webdriver.Chrome()driver.get(geo_guessr_map)# let JS etc. loadtime.sleep(2)def screenshot_canvas():    '''    Take a screenshot of the streetview canvas.    '''    with open(f'canvas_{int(time.time())}.png', 'xb') as f:        canvas = driver.find_element_by_tag_name('canvas')        f.write(canvas.screenshot_as_png)def rotate_canvas():    '''    Drag and click the <main> elem a few times to rotate us ~90 degrees.    '''    main = driver.find_element_by_tag_name('main')    for _ in range(0, 5):        action = webdriver.common.action_chains.ActionChains(driver)        action.move_to_element(main) \            .click_and_hold(main) \            .move_by_offset(118, 0) \            .release(main) \            .perform()def move_to_next_point():    '''    Click one of the next point arrows, doesn't matter which one    as long as it's the same one for a session of Selenium.    '''    next_point = driver.find_element_by_css_selector('[fill="black"]')    action = webdriver.common.action_chains.ActionChains(driver)    action.click(next_point).perform()for _ in range(0, NUMBER_OF_SCREENSHOTS):    screenshot_canvas()    move_to_next_point()    rotate_canvas()driver.close()

Скриншоты содержат и интерфейс GeoGuessr, но я не стал заниматься его удалением.

Приблизительное определение геолокации


Я перешёл к ветке PyTorch branch, скачал обученную модель и установил зависимости с помощью conda. Мне понравился README репозитория. Раздел requirements был достаточно понятным и на новом Ubuntu 20.04 у меня не возникло никаких проблем.

Для выяснения отношений между человеком и машиной я выбрал в GeoGuessr карту World. Отправив URL своей программе Selenium, я прогнал её для четырёх скриншотов, сделанных в GeoGuessr.

Ниже представлены сокращённые результаты работы машины.

python -m classification.inference --image_dir ../images/                                lat        lngcanvas_1616446493 hierarchy     44.002556  -72.988518canvas_1616446507 hierarchy     46.259434  -119.307884canvas_1616446485 hierarchy     40.592514  -111.940224canvas_1616446500 hierarchy     40.981506  -72.332581

Я показал те же четыре скриншота своей жене. Она предположила, что точка находится в Техасе. На самом деле место находилось в Пенсильвании. Машина сделала для каждого из четырёх скриншотов четыре различные догадки. Все догадки машины находились в США. Две достаточно близко друг к другу и две подальше.

image

Если взять усреднённое местоположение, то машина в этом раунде побеждает!

Мы сыграли ещё два последующих раунда, и окончательный счёт оказался 2-1 в пользу машины. Машина довольно близко подобралась к улице в Сингапуре, но не смогла опознать заснеженную улицу в Канаде (Мэделин назвала город за считанные секунды).

После написания этого поста я узнал о потрясающей предыдущей работе со сравнением результатов человека и машины на поле боя GeoGuessr. В статье PlaNet Photo Geolocation with Convolutional Neural Networks Тобиас Вейанд, Илья Костиков и Джеймс Филбин пытались определить местоположение фотографии всего по нескольким пикселям.

Чтобы выяснить, насколько PlaNet сравнима с интуицией человека, мы позволили ей соревноваться с десятью много путешествовавшими людьми в игре Geoguessr (www.geoguessr.com).

В сумме люди и PlaNet сыграли в 50 раундов. PlaNet выиграла 28 из 50 раундов с медианной погрешностью локализации в 1131,7 км, в то время как медианная погрешность людей составляла 2320,75 км.

Веб-демо


Авторы статьи Geolocation Estimation of Photos using a Hierarchical Model and Scene Classification создали довольно милый веб-инструмент. Я проверил его на одном из скриншотов Selenium.

Графическая демонстрация, в которой вы сможете посоревноваться против описанной в статье системы с глубоким обучением находится здесь: https://tibhannover.github.io/GeoEstimation/. Также мы создали многофункциональный веб-инструмент, поддерживающий загрузку и анализ пользовательских изображений: https://labs.tib.eu/geoestimation

image

Обучаемость GeoGuessr


Существует много причин, по которым попытки победить GeoGuessr (под этим мы подразумеваем частая демонстрация более высоких результатов, чем у человека) при помощи машинного обучения могут быть проще, чем определение местоположения фотографии, сделанной человеком.

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

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

Если в street view посмотреть вниз то можно увидеть часть машины, снимавшей текущую фотосферу. Например, в Кении спереди у машины есть чёрная труба. Основная часть Вьетнама была снята с мотоцикла, и часто можно увидеть шлем водителя. Страны часто снимаются одной машиной с уникальным цветом или антенной.

image

В других местах в небе есть место, где сшитая фотосфера выглядит разорванной (в основном в Сенегале, Черногории и Албании). В Африке за автомобилем Street View иногда едут машины сопровождения. Есть разные поколения камер, с разным разрешением, типами гало, цветопередачей и размытием в нижней части сферы. В нижнем углу фотосферы есть сообщение об авторстве, обычно это Google и указание года, но иногда бывает и имя фотографа.

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



На правах рекламы


Закажите сервер и сразу начинайте работать! Создание VDS любой конфигурации в течение минуты. Эпичненько :)

Подробнее..

Так какими же должны быть идеальные шахматы?

24.12.2020 00:21:35 | Автор: admin

Так какими же всё таки должны быть идеальные шахматы?

Как уже принято на хабре, увидел статью Какими могут быть идеальные шахматы, хотел написать комментарий, но понял, что многовато получается и решил написать статью.

Чтобы понять какими могут быть идеальные шахматы, нужно сначала понять что не так с шахматами нынешними (классическими). Давайте попробуем сформулировать недостатки не только геймплея как такового, но и недостатки связанные с психологическим восприятием того, что происходит во время игры.

Проблемы объективные

1. Проблема инвентаря при изменении правил.

2. Бесконечные ничьи достигаемые тем или иным способом.

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

Проблемы субъективные (связанные с психологией восприятия)

1. Пат. (как проблема связанная с психологией восприятия)

2. Недостаточно материала для мата.

3. Проблемы связанные с слишком сильными изменениями в правилах.

Любые проблемы желательно решать так, чтобы не плодить новые проблемы. Исходя из этой предпосылки и давайте попробуем решить нынешние проблемы шахмат.

1. Как говорится, начнём по порядку!

Я не знаю сколько в мире насчитывается шахматных досок и фигур к ним. Полагаю, что можно говорить о десятках, а может и сотнях миллионов комплектов и никто их не будет менять, даже если предложить идеальную игру на доске 10х10 с добавлением новых фигур.

Так что, шахматы Капабланки это замечательно, и может быть во времена Капабланки количество инвентаря было сильно меньше, и такую революцию можно было хотя бы пробовать осуществлять, но сейчас, если и имеет смысл изменять правила игры, то только с сохранением существующего шахматного инвентаря.

Значит определились. Доски остаются 8х8. Фигуры те же.

2. Ничьи

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

а. Пат.

б. Вечный шах.

в. Троекратное повторение позиции.

г. Правило 50 ходов.

д. Недостаточно материала для мата.

е. Ничья по соглашению сторон.

а. Одна из проблем, это пат и патовые идеи.

Новичкам не понятно, почему король попавший в пат, это ничья? Мы же проецируем это на наши представления о мире. Если вражеского полководца не убили, а обездвижили, то в этот момент мы не теряем опцию его прирезать. Это можно сделать в любой момент, если понадобится. То есть задача выполнена. В реальности, взять живым, даже зачастую ценится больше, чем доставить мёртвым.

Конечно, те люди, которые постоянно играют в шахматы свыкаются с данной им реальностью и уже не считают это чем-то неправильным, но если эта проблема приносит нам головную боль сразу двумя способами ничьи и психология, почему бы её не устранить?

Устраняем. Приравняем пат к мату. Пат победа. Тут всё просто. Едем дальше.

б, в, г. Эти проблемы так просто не решить.

Потребуется очень много правил сложных для запоминания и самое главное очень сложных для отслеживания и исполнения.

Но что если в данном случае мы поставим чёрных афроамериканцев и белых в разные условия? Если у нас на старте игры, белые имеют небольшой бонус в виде лишнего темпа (хода для непосвящённых), то почему мы не можем слегка подравнять эту несправедливость, а попутно ещё и решить проблемы с ничейными результатами?

Решаем. Любой из встреченных вариантов (б, в, г), приравнивается к победе чёрных.

Решение простое, элегантное, как говорится, дёшево и со вкусом. Мы заранее говорим белым: Да, вы первые ходите, но не бесплатно. Не допускайте вот этого.

д. Недостаточно материала для мата.

Тут мы снова сталкиваемся с двумя проблемами одновременно. Ничейные результаты от которых мы хотим максимально избавить шахматы и психология восприятия. Представим ситуацию. У начинающего игрока остался слон (конь) и король, а у его противника только король. Современные правила шахмат трактуют эту ситуацию как ничью ввиду недостаточности материала для мата, но на взгляд неофита это абсурд. Как? У него только король, а у меня ещё целый слон (или конь)! Фигура приравниваемая по силе к трём пешкам! А мне достаточно и одной, чтобы провести ферзя и победить. А тут три пешки. Как это ничья?

Выглядит и правда не очень. И если вам не понравилось как выглядит вышеописанное, то представьте теперь ситуацию, где у вас остался король и целых два коня! А у противника только король. И это тоже ничья.

Как решать проблему?

Как ни странно, тоже довольно не сложно. Достаём старое правило оголения короля, сдуваем с него пыль и имеем элегантное решение.

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

Но есть нюанс (даже три), но и их не сложно предусмотреть. Итак, нам нужно предусмотреть 3 возможных варианта.

*. Пешечный эндшпиль, где у одной из сторон остался только король, но он в ближайшее время съест пешку (пешки) противника.

Решением служит - не учитывать правило оголения короля, пока на доске есть пешки. Они либо пройдут и станут фигурами, либо их съедят.

*. Ситуация при которой слон или конь одной стороны, съел что-то последнее у другой. Тут нужно удостовериться, что король слабейшей стороны может или не может гарантированно съесть оставшуюся фигуру.

Самый сложный вариант в данном случае конь в углу. Королю может понадобится 3 хода, чтобы съесть этого коня, при этом конь спастись не может. Значит мы можем предусмотреть правило, при котором если нет пешек на доске, оголённый король имеет в своём распоряжении 3 хода, после которых засчитывается поражение. За эти 3 хода король гарантированно съест любую одинокую фигуру противника, если такая возможность теоретически существует.

*. Голые короли. Тут всё просто. Мы уже определили, что любая ничья, в пользу чёрных. Так что мы просто используем то же самое правило, что используется для решения проблем б, в, г.

е. Ничья по соглашению сторон.

Скажите мне, в каком-нибудь другом виде спорта вы видели ничью по соглашению сторон?

Может быть футболисты на пятой минуте пожимают друг другу руки и расходятся по домам, потому что обе команды устраивает ничья?

Или может быть боксёры на ринге решили, что на сегодня хватит получать по лицу, обнимаются и идут по домам без синяков и рассечений?

Решение тут простое. Никаких ничьих по соглашению быть не должно. Ни до тридцатого хода, ни до сорокового, ни до тысяча сорокового. Просто нет и всё.

3. Осталось самое сложное, /розы/ дебют

Проблема встала на повестке дня не сегодня и не вчера. Много десятилетий назад эту проблему пытался решить один из самых выдающихся шахматистов в истории шахмат Бобби Фишер. Он предложил перемешать шахматные фигуры, расставив их в случайном порядке. Правил не так много. Позиция должна быть симметрична и король должен располагаться между ладьями, чтобы можно было сделать рокировку в любую сторону. Но решение это столь радикальное, что только очень небольшой процент шахматистов относится к шахматам Фишера (chess 960) благодушно. Подавляющее большинство относится к шахматам Фишера негативно. Слишком уж сюрреалистична как начальная позиция, так и начало партии.

Однако, есть очень интересное предложение Марка Дворецкого, которым он поделился на страницах журнала 64 шахматное обозрение в первом номере от 2008 года. Статья называется Компоненты успеха и в общем-то посвящена не только проблемам современных шахмат, но часть статьи именно так и называется проблемы современных шахмат.

Марк Израилевич никак не называет свою вариацию шахмат, а лишь рассказывает о сути предложения, поэтому я долгие годы называю эти шахматы шахматы Дворецкого, за не имением официального названия.

Кто захочет, может изучить статью в подробностях, найдя нужный номер журнала. Здесь же я изложу его предложение вкратце.

Перемешивать фигуры на первом ряду слишком радикально и является своего рода холодным душем для привыкшего к нормальным шахматам человека. Но к счастью можно решить проблему не прибегая к таким радикальным мерам. Нам нужно случайным образом выдвинуть по две пешки для каждой из сторон, на одно поле вперёд (позиция не обязана быть симметричной). Исключением является пешка f, выдвижение которой сильно ослабляет позицию короля и она в генерации стартовой позиции не участвует.

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

Заключение. Проблемы, связанные с слишком сильными изменениями в правилах

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

Если бы такой задачи не стояло, можно было бы внести более радикальные изменения. Например, отменить мат и вместо него ввести правило съедания короля противника. Кто съел короля противника, тот победил.

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

Это позволило бы в целом кардинально упростить правила шахмат. Например, не нужно правило, при котором короли не могут приближаться друг к другу. Пусть подходит вражеский король, мы его съедим нашим королём. И много, много других правил становятся не нужными.

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

Так что, как я уже написал выше, приходится учитывать проблемы связанные со слишком сильными изменениями в правилах и от каких-то изменений, пусть и очень здравых отказываться.

И напоследок,

Добро пожаловать в новый мир шахмат!

Подробнее..

Шахматные алгоритмы, которые думают почти так же, как человек, только лучше

26.02.2021 16:11:32 | Автор: admin

Когда создавались первые вычислительные машины, их воспринимали только как дополнение к человеческому разуму. И до недавнего времени так и было. Программисты учили компьютеры играть в шахматы с 1960-х годов. И тогда победа у игрока-новичка уже считалась большим прогрессом. О серьёзных матчах даже не задумывались.

В 1980-х программа Belle достигла рейтинга Эло в 2250 пунктов, что примерно соответствует рейтингу мастера спорта. И с того времени развитие компьютерных шахмат вышло на совершенно новый уровень.

Сначала честь человечества не смог защитить Гарри Каспаров в 1996 году, а сегодня уже создана нейросеть с рейтингом около 5000 Эло, что в разы превосходит даже сильнейших игроков.

Сегодня разберёмся, как работают шахматные алгоритмы и почему нейросеть Alpha Zero думает практически так же, как человек, только лучше.


Как работает шахматный движок: от механического перебора вариантов до умного выбора

У шахмат довольно простые правила. Две противоборствующие стороны, шесть разновидностей фигур и одна цель дать мат сопернику.

Но при этом вариативность шахмат просто огромна. Существует 400 уникальных комбинаций первого хода 20 вариантов первого полухода белых и 20 вариантов ответа чёрных. С каждым последующим ходом количество уникальных позиций увеличивается на степень.

Общее количество уникальных партий в шахматы составляет примерно 10120, что на 1040 превышает количество атомов во Вселенной.

Шахматам не грозит быть посчитанными полностью. Поэтому в бой вступают алгоритмы оценки позиции и дерево возможных ходов.

В шахматной теории у каждой фигуры есть своя ценность, которая измеряется в пешках:

  • Конь 3 пешки;

  • Слон 3 пешки;

  • Ладья 5 пешек;

  • Ферзь 9 пешек;

  • Пешка 1 пешка.

Король бесценен, потому что его потеря означает проигрыш партии.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 912 пешек, ладью в 56, коня и слона в 35. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 912 пешек, ладью в 56, коня и слона в 35. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Чтобы было более понятно, преимущество в 0,5 пешки это уже неплохо для шахматиста. В целую пешку серьёзный перевес. В 3 пешки подавляющее преимущество, которое можно практически без проблем довести до победы.

Но счётные возможности машины ограниченны. Иногда она показывает оценку в +51 или что-то вроде. Это означает, что алгоритм видит колоссальное преимущество белых в позиции и материале, но не может найти конкретный путь к мату.

Минимакс, или прямой перебор вариантов, в таком случае не работает. Даже КМС без проблем найдёт на доске мат в 3 хода в миттельшпиле, когда на доске ещё много фигур. А программе для этого нужно будет перебрать свыше 750 млн. полуходов.

Даже если программа перебирает 1 млн вариантов в секунду, чтобы найти мат в 3 хода, ей понадобится до 750 секунд, или 12,5 минут.

И это глубина в 3 хода. В стратегических позициях, где развитие игры идёт с учетом на пять или десять ходов вперёд, такие программы и вовсе будут бесполезными.

Поэтому для анализа позиции используется алгоритм под названием альфа-бета-отсечение.

Система анализирует начальные варианты ходов и сразу отсекает те из них, которые ведут к мгновенному ухудшению оценки.

Программа отметает те варианты, в которых она сразу проигрывает материал или которые включают комбинации со стороны соперника, в ходе которых она выигрывает материал или партию.

Это позволяет сократить количество рабочих линий на порядки, сосредотачивая вычислительные ресурсы только на тех ветвях дерева, которые в перспективе ведут к улучшению позиции.

В варианте кода это может быть реализовано примерно следующим образом:

function alphabeta(node, depth, , , maximizingPlayer) is    if depth = 0 or node is a terminal node then        return the heuristic value of node    if maximizingPlayer then        value :=         for each child of node do            value := max(value, alphabeta(child, depth  1, , , FALSE))             := max(, value)            if    then                break (*  cutoff *)        return value    else        value := +        for each child of node do            value := min(value, alphabeta(child, depth  1, , , TRUE))             := min(, value)            if    then                break (*  cutoff *)        return value

За код особо не ругайте.

Рассмотрим на примере. Движок Stockfish считается сегодня одной из самых сильных компьютерных шахматных программ. Обратите внимание на первые пять линий.

Из всего множества вариантов развития событий программа выбирает ряд линий, которые в перспективе ведут к улучшению позиции. Их она анализирует более глубоко на 1520 ходов вперёд, чтобы отсечь возможные проигрышные варианты. В результате она выбирает лучшую из возможных линий и делает ход.

После ответа соперника ситуация снова анализируется по тому же алгоритму. Сначала отсекаются заведомо проигрышные линии (таких порядка 95 %), а затем путём более глубокого анализа перспективных вариантов выбирается лучший из них.

Новая эра в шахматных движках: нейросеть Alpha Zero

В 2017 году компания Deep Mind объявила о создании нейросети Alpha Zero. Тестировать её решили на трёх самых популярных стратегических настольных играх: шахматы, го и сёги.

Обучение и подготовка нейросети отличаются от классических компьютерных движков.

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

Alpha Zero не использует ничего, кроме правил. Ей просто дали стартовую позицию, объяснили, как ходят фигуры, и цель игры поставить мат сопернику. И всё.

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

В декабре 2018 года Alpha Zero во второй раз сразилась с самой последней версией движка Stockfish.

Исследователи провели 1000 партий с контролем 3 часа на партию плюс 15 секунд на ход.Alpha Zero одержала уверенную победу, выиграв в 155 партиях, сыграв вничью 839 партий и проиграв только 6.

Более того, Alpha Zero одерживала победу даже в партиях с форой по времени на обдумывание. Имея в 10 раз меньше времени, чем у противника, нейросеть всё равно победила в суммарном итоге. Только 30-кратная фора во времени смогла уравнять шансы и дать Stockfish примерно равную игру 3 часа у движка и всего лишь 6 минут у нейросети.

Alpha Zero анализирует лишь 60 000 позиций в секунду, а тестируемая версия Stockfish 60 млн. позиций. Для достижения аналогичных результатов анализа нейросети нужно в 1000 раз меньше ресурсов, чем движку.

Секрет успеха в качественно другом уровне анализа. Нейросеть использует метод Монте-Карло, который высчитывает математическое ожидание комплекса ходов.

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

И, что гораздо более важно, при оценке ситуации Alpha Zero учитывает стратегическую позицию.

Давайте рассмотрим на примере одной из партий.

После 20-го хода на доске творится невообразимая стратегическая борьба. Но если нейросеть шаг за шагом минимально укрепляет свою позицию, избавляясь даже от призрачных слабостей, то движок с 24-го по 29-й ход просто топчется на месте ладьёй.

Интересно, что Stockfish в упор не видит стратегических решений Alpha Zero, оценивая позицию как абсолютно ничейную. Но в результате минимальных укреплений позиции к 39-му ходу оказывается, что все фигуры белых активны, а чёрный конь и слон занимают пассивную оборонительную позицию. А после размена ферзей и ладей даже Stockfish оценивает преимущество нейросети в +2,2. Ещё несколько ходов и король черных зажат в углу доски, а конь в одиночку не способен справиться с проходной пешкой. Поэтому программа сдалась.

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

Тем не менее нейросеть умеет играть позиционно не хуже человека и при этом идеально играет тактические позиции, где преимущество достигается в течение 5 или меньше ходов.

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

Многие теоретики считают, что благодаря шахматным компьютерам повысился и средний рейтинг топовых шахматистов. Ведь современные тренировки включают глубокую проработку компьютерных вариантов и разбора партий движками. Средний рейтинг ведущих топ-100 шахматистов в 2000 году составлял 2644 пункта Эло, а в январе 2021 года 2715. За 20 лет среднее значение увеличилось на 71 пункт.

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

Она умеет мыслить позиционно и при этом не допускает зевков и ошибок. И самое интересное в этом ситуации шахматы для Alpha Zero являются только тестировочным полигоном, где система оттачивает навыки работы. Реальные же её цели Google не раскрывает. Поэтому здесь может быть всё что угодно: от анализа изменений климатической ситуации до создания системы идеально персонифицированной рекламы. А как вы считаете, для чего создают настолько мощную нейросеть?

Создать своего гениального цифрового шахматиста или получить Level Up по навыкам и зарплате можно пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение. Узнайте подробности.

Другие профессии и курсы
Подробнее..

Как с помощью циркуля и линейки находить корни, квадраты и обратные величины чисел

07.05.2021 20:05:41 | Автор: admin

Представьте, что у вас нет под рукой калькулятора (но есть циркуль и линейка или угольник) и вам нужно посчитать результат в виде отрезка. Задача решается за менее чем 5 простых шагов.

Базовая формула вычисления

Для начала докажем одну формулу, которая нам будет помогать с дальнейшим решением.

В прямоугольном треугольнике ABC проведем высоту h на сторону C. По теореме Пифагора выводим:

C^2 = A^2 + B^2A^2 = h^2 + a^2B^2 = h^2 + b^2C = a + b

Подставляем всё в первую формулу:

(a + b)^2 = h^2 + a^2 + h^2 + b^2

И если раскрыть скобки:

a^2 + 2ab + b^2 = 2h^2 + a^2 + b^2

После сокращения получаем:

ab = h^2

Вот с помощью этой формулы и будем выводить наши решения.

Единичная мера длины

Так как мы вычисления проводим на плоскости с отрезками, нам необходимо определиться с мерой единичной длины равной 1. Если мы отложим отрезок 1 дециметр, то он так же будет равен 10 сантиметрам, 100 миллиметрам или 4 дюймам. Один отрезок и 4 разных чисел разной меры длины его определяют. Что бы выбрать одну систему счисления длин отрезков, примем за единицу длины какой-то отрезок. Какой - определим по ходу расчетов, и он зафиксирует нужную меру длины.

Циркуль как универсальный инструмент

Циркуль удобно использовать как средство:

  • отмерить отрезок определенной длины, при этом знать величину этой длины совершенно нет надобности.

  • прочертить дугу на одинаковом расстоянии от определённой точки.

  • отложить перпендикуляр к линии через определённую точку. Для этой цели удобнее использовать угольник с прямым углом, чем циркулем чертить 4 дуги.

Вычисление квадрата длины

Для вычисления квадрата величины X используем нашу формулу в виде:

a = 1, h = X, b = X^2

Чертим прямую линию достаточной длины.

Откладываем на ней отрезок единичной длины.

От правого конца единичного отрезка 1 откладываем вверх перпендикуляр длиной X.

Проводим линию от левого конца единичного отрезка 1 до верхнего конца отрезка X.

От этого отрезка откладываем перпендикуляр на линию продолжения единичного отрезка 1. Их пересечение и есть правый край квадрата длины. Левый край начинается от точки, где отложена высота.

Пример. У вас есть какой-то квадрат, со стороной X, начерченный на плоскости или на земле. Нужно узнать его площадь в попугаях. Одна сторона квадрата длиной X у нас уже есть. На соседней стороне откладываем длину одного попугая (там где 1 находится). Соединяем концы линией, откладываем перпендикуляр, продлеваем отрезок с попугаями до перпендикуляра и получаем решение в квадратных попугаях.

Вычисление квадратного корня длины

Для вычисления квадратного корня величины используем нашу формулу в виде:

a = 1, b = X, h = sqrt(X)

Чертим прямую линию достаточной длины.

Откладываем на ней единичный отрезок длины 1.

На продолжении единичного отрезка откладываем отрезок длины X.

Полученный отрезок 1+X делим пополам с помощью циркуля и получаем точку O. Как это сделать, приводить здесь не буду, это задачка из школьного курса. Обозначим длину найденной половины как R.

Вокруг центра O, циркулем нарисуем дугу радиусом R.

От правого конца отрезка 1 отложим вверх перпендикуляр до пересечения с дугой окружности. Длина этого перпендикуляра и будет равна корню квадратному из длины X.

Вычисление обратной величины длины

Для вычисления обратной величины длины используем нашу формулу в виде:

h = 1, a = X, b = 1 / X

Решение очень похоже на нахождение квадрата величины, только a и h меняются местами.

Чертим прямую линию достаточной длины.

Откладываем на ней отрезок длины X.

От правого края отрезка X откладываем вверх перпендикуляр единичной длины 1.

Соединяем концы отрезков линией.

От верхнего конца отрезка X откладываем перпендикуляр к линии продолжения отрезка 1. Полученный отрезок и есть решение.

Выводы

Приведенные выкладки удобны, когда не хочется возиться с цифрами и их арифметическими вычислениями, которые всё равно будут обратно приложены к длинам отрезков.

Если величина X сильно отличается от единичного отрезка 1, ошибка вычисления может быть значительной. Но если применить масштабирование, то ошибку можно значительно уменьшить. Например, при захождении корня длины 20, его можно поделить на 16 (4 раза поделить пополам), а потом ответ умножить на 4 (4 раза отложить полученный отрезок).

Подробнее..

Построение при помощи циркуля и линейки, только без циркуля

08.05.2021 12:05:15 | Автор: admin
Все мы знакомы из школьной программы с построениями при помощи циркуля и линейки. А что будет, если вдруг циркуль затеряется? Можно ли при помощи одной линейки строить ещё что-то нетривиальное? Предлагаю вашему вниманию задачу, решение которой принесло мне немало приятных часов. Задача со звёздочкой, поэтому не расстраивайтесь, если сходу решение не найдёте. Хотя один мой знакомый справился за пять минут, думаю, что это скорее исключение из правил.

Итак, на плоскости есть отрезок, который мы бы хотели продолжить. Казалось бы, выбрать две точки на отрезке, приложить линейку и прочертить прямую. Но вот незадача: как раз на пути этой прямой посажено жирное пятно кетчупа, а мы линейку пачкать не хотим. Нужно продолжить изначальную прямую за пятном, не прикасаясь к нему линейкой.



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



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

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

Немного о нашей безымянной студии и о том, что мы делаем

31.01.2021 22:19:51 | Автор: admin

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

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

Начало

Дело было в институте, конец магистратуры. Мы с моим товарищем из параллельной группы решаем создать свою супер-пупер 3D-головоломку от первого лица. Такую что просто ну просто бомба и огонь. Надеюсь вы поняли меня. Почему решили делать игру? У меня есть опыт в рисовании, закончил школу с ИЗО уклоном, у напарника есть опыт в создании 3D-моделей. Ну и оба мы программисты как-никак, поработали в фирмах в т.ч. игры делали. Почему головоломку? Потому, что нам нравятся головоломки.

Работу мы разделили примерно пополам ну или делали кто что может. С одной стороны, если в команде 2 человека, то делить работу можно пополам! Удобно же :) И на контроль за результатами работы всех разработчиков не так много времени уходит как, скажем, ушло бы если бы в нашей команде было 30 человек.

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

В самом начале мы придумали идею, игровые законы, механики, протестировали все в голове, на бумаге, и в Unity, запланировали сетевой режим.

Не поверите, но у меня набралось 2 папки со скетчами по проекту и иногда мне все еще приходится набрасывать картинки/перебирать идеи/сопоставлять обьекты. Скетчи, которые я набрасывал выглядят примерно так:

На данный момент мы опубликовали большую часть скетчей в твиттере / инстаграме.

Были еще знакомые, мы попытались подключить их к проекту. Кроме нас в команде было две девушки (дизайнеры-художники), гейм-дизайнер и программист. Через 2-3 недели программист пошел работать в крупную фирму, после попыток прописать структуру проекта и сборки одного игрового обьекта - условный обьект с "глазом" (который следит за игроком). Потом нас покинули дизайнеры. Гейм-дизайнер оказался крепким. Он был с нами до последнего, а вот результатов его работы у нас не было :)

Кстати, игра на тот момент выглядела так:

Текущие модели на картинках - это одни из первых версии наших моделей. Я приложил эти картинки не для того чтобы показать графику или механику, а чтобы продемонстрировать, как все выглядело на этапе работы над механикой и проведением тестов.

Еще несколько скетчей:

Коротко о некоротком, о сети

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

Мы много чего сделали по сетевой части, в том числе и организовали сетевой чат (иконка конверта) и систему общения голосом (иконка микрофона).

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

Лучше синица в руках, чем журавль в небе

Попытки расширить команду

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

  • профессиональные художники хотят получать денюжки, а у нас есть только энтузиазм

  • по большей части непрофессилнальные художники (из моего личного опыта) любят покреативить и вместо того чтобы сделать все максимально по ТЗ, их заносит и они по-полной берут на себя роль главного ГД и начинают работать уже в этом направлении

  • мотивировать команду - это работа на которую затрачивается много времени

Для себя мы поняли еще одну вещь: у нас нет времени на выдачу ТЗ ребятам, которые работают на энтузиазме потому, что высока вероятность их ухода. Так что мы решили делать все сами и никого не искать, не расширять команду. У этого решения есть плюс, который я описал бы так:

Надеемся только на крепость рук, На руки друга и вбитый крюк - И молимся, чтобы страховка не подвела.

На данный момент мы все так же усердно работаем над проектом. Сделали кучу основной работы, работаем над оптимизацией, полировкой графона, анимациями и историей.

Так же в последнее время к нам присоединился переводчик, который взялся прорабатывать сценарий :) Уже вот год работает с нами как и мы на энтузиазме.

А вот и ссылки на нас:

https://twitter.com/CGAleksey

https://www.instagram.com/cgaleksey

https://vk.com/treload

Подробнее..

Шахматы на Delphi. Как я изобретал велосипед

11.04.2021 00:10:54 | Автор: admin

Писать игровой AI очень интересно и увлекательно - не раз убеждался в этом на личном опыте. Недавно, случайно наткнувшись на код своего старого проекта шахматной программы, решил его немного доработать и выложить на GitHub. А заодно рассказать о том, как он создавался и какие уроки преподал мне в процессе работы.

Начало

Это случилось в 2009 году: я решил написать простую шахматную программу, чтобы попрактиковаться в разработке игрового AI. Сам я не шахматист и даже не сказать что любитель шахмат. Но задача для тренировки вполне подходящая и интересная. Кроме того, играя в шахматы на доске или в программе, мне всегда было любопытно, почему тот или иной ход сильнее другого. Хотелось возможности наглядно видеть всё дерево развития шахматной позиций. Такой фичи в других программах я не встречал - так почему бы не написать самому? Ну а раз уж это тренировка - то придумывать и писать нужно с нуля, а не изучать другие алгоритмы и писать их собственную реализацию. В общем, думаю, дня за три можно управиться и сделать какой-то рабочий вариант :-)

Первая версия

Обычно шахматные движки используют поиск в глубину с алгоритмом "ветвей и границ" для сужения поиска. Но это не очень-то наглядно, поэтому решено: мы пойдём своим путём - пусть это будет поиск в ширину на фиксированную глубину. Тогда в памяти будет полное дерево поиска, которое можно как-то визуализировать. А также выяснить: а) на какую глубину можно просчитать шахматную игру в рамках имеющихся ресурсов CPU и памяти, б) насколько хорошо или плохо будет играть такой алгоритм?

Надо сказать, что на тот момент у меня был 2-ядерный процессор с 2 или 4 Гб памяти (точно уже не помню), 32-битная винда и 32-битный компилятор Turbo Delphi Explorer. Так что если временем работы ещё можно было как-то пожертвовать, то доступная процессу память была ограничена 2Gb. Про PE flag, расширяющий user memory до 3Gb я тогда не знал. Впрочем, поскольку память кушают и система, и Delphi и другие программы - для шахмат, чтобы не уходить в своп, доступно менее гигабайта.

В результате получилась первая версия игры, состоящая из таких модулей:

  • UI - основное окно, отрисовка доски с фигурами.

  • Игровая логика - составление списка возможных ходов, выполнение хода, детекция завершения игры.

  • AI:оценка - оценочная функция позиции.

  • AI:перебор - поиск в ширину через очередь.

  • UI:браузер - окно визуализации дерева поиска, в котором можно наглядно изучать как всё работает.

Выяснилось что:

  • Поиск на глубину 3 полухода работает быстро - меньше секунды, и расходует немного памяти - 5-15 Мб. А вот поиск на глубину 4 полухода работает уже довольно долго и расходует большую часть доступной памяти. В отдельных ситуациях памяти и вовсе не хватает.

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

  • При любой глубине поиска, компьютер совершенно не умеет играть в эндшпиле и не понимает что делать, если у противника остался один король.

Таким образом, вырисовались направления дальнейшей работы: углубить поиск, научить позиционной игре а также научить играть в эндшпиле. И многие проблемы можно решить за счёт оценочной функции.

Оценочная функция

Функция оценки позиции - важнейший компонент любого шахматного движка. Где-то она предельно простая и быстрая - учитывает лишь количество фигур и их стоимость, а где-то - сложная и учитывает множество факторов. Поскольку в моём случае количество оцениваемых позиций ограничено объемом памяти, имеет смысл использовать сложную оценочную функцию и заложить в неё как можно больше факторов.

В итоге пришел к примерно такому алгоритму:

  • Для каждого игрока:

    • Подсчитать стоимость фигур: конь - 3, ладья - 5 и т.д. Начальная стоимость пешки - 1, но она растёт по мере её продвижения.

    • Бонус за сделанную рокировку, штраф за потерю возможности рокировки, штраф в миттельшпиле за невыведенные фигуры (коней и ладьи в углах). Штраф за сдвоенные пешки и бонус за захваченные открытые линии.

    • Определение какие поля находятся под боем и кем. Это медленная операция - основная часть времени выполнения оценочной функции тратится именно здесь. Зато польза от неё колоссальная! Незащищённая фигура под боем на ходу противника - минус фигура. Защищённая - минус разность стоимости фигур. Это позволяет получить эффект углубления поиска на 1-2 уровня.

    • Если остался один король: штраф за расстояние от центра доски и штраф за расстояние до короля противника. Такая формула в эндшпиле заставляет AI стремиться прижать короля противника к краю доски, т.е. получить позицию, из которой можно найти возможность поставить мат.

  • Итоговая оценка = (white_rate - black_rate) * (1 + 10 / (white_rate + black_rate)). Эта формула делает разницу более значимой в эндшпиле, заставляя отстающего игрока избегать размена фигур, а ведущего - наоборот, стремиться к размену.

Углубление поиска

Прежде всего, несмотря на доработку оценочной функции, углубление поиска необходимо для ходов со взятием а также шахов. Для этого добавлен новый атрибут узла - вес, который используется вместо глубины. Если дочерний узел порождается обычным ходом - его вес уменьшается на 1, если ходом со взятием - на 0.4, если ходом с шахом - не уменьшается вовсе. Узлы с положительным весом возвращаются в очередь поиска и получают продолжение.

Кроме того, нужно развивать наиболее перспективные направления - ветки с наибольшей оценкой.

В итоге алгоритм получился такой:

  1. На первой стадии строится дерево с базовой глубиной 3 (при этом ветки со взятиями и шахами могут достигать заметно большей глубины).

  2. Оценка дерева алгоритмом минимакс.

  3. Если выполнены критерии принятия решения - выбирается ветка с наилучшей оценкой и алгоритм завершается.

  4. Обрезка дерева: последовательно удаляются ветки с наихудшей оценкой пока не будет свободно достаточно памяти для продолжения поиска.

  5. Переход к следующей стадии: добавляем вес всем листьям дерева и продолжаем поиск. После завершения переходим к п 2.

Критерии принятия решения:

  • Осталась единственная ветка - выбора нет.

  • Одна из веток имеет оценку существенно более высокую чем у остальных - выбираем её.

  • Истекло время на ход - выбираем ветку с наилучшей оценкой.

Кэширование

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

Всё просто: нужно вычислить хэш от позиции и если в кэше уже есть оценка с таким хэшем - использовать её вместо вычисления. А если нет - вычислить и сохранить в кэше оценок. Основная проблема - нужна достаточно качественная и быстрая хэш-функция. После множества экспериментов получилось написать приемлемую функцию, вычисляющую 64-битный хэш. Общее количество возможных шахматных позиций значительно больше 264, но количество позиций, оцениваемых в ходе партии значительно меньше 232, поэтому более-менее качественная хэш-функция должна свести вероятность хэш-коллизий к минимуму.

Процент "попаданий" в кэш в ходе игры получился в районе 30-45%, но в эндшпиле достигает 80-90%, что даёт ускорение почти в 5-10 раз, а следовательно позволяет увеличить глубину поиска. Неплохой выигрыш!

Что получилось?

Я добавил библиотеку дебютов, и в таком состоянии программа играла уже довольно неплохо - примерно на уровне 2-го разряда, а может и чуть сильнее. Результат, в принципе, достойный - можно остановиться. Хотя были вполне очевидны недостатки и направления развития:

  • AI работает в один поток - ресурс CPU задействован не полностью.

  • А что если предоставить больше памяти?

  • AI думает только во время своего хода. Почему бы не использовать время соперника для просчёта наиболее вероятных продолжений?

  • Главная слабость: детерминированность. Каждый ход рассматривается как отдельная задача, каждая позиция приводит к детерминированному решению. Достаточно выиграть один раз, чтобы запомнить последовательность ходов, которая всегда приведёт к победе. А играть с таким соперником неинтересно.

Однако, к этому времени код проекта уже достаточно "замусорился" и требовал рефакторинга. Поскольку на него и так уже было потрачено много времени, я решил его забросить.

Дальнейшее развитие

Недавно наткнувшись на этот заброшенный проект, решил всё-таки привести его код в порядок и доработать. Доработки сделал такие:

  • Многопоточность: сейчас у меня уже 8-поточный, а не 2-поточный CPU, поэтому многопоточный вариант даёт серьёзную прибавку в скорости.

  • 64-битный режим: кроме возможности использовать больше памяти, было любопытно, будет ли алгоритм работать быстрее на архитектуре x64. Как ни странно, оказалось что нет! Хотя отдельные функции на x64 работают быстрее, в целом версия x86 оказалась на 5-10% быстрее. Возможно 64-битный компилятор Delphi не очень хорош, не знаю.

  • Больше памяти: даже в 32-битном режиме за счёт PE-флага расширения адресного пространства доступной памяти стало больше. Однако практика показала, что больше 1 Гб памяти все-равно не нужно - разве что для хранения "обрезанных" ветвей дерева. К усилению игры увеличение памяти не приводит.

  • Непрерывность поиска: теперь дерево поиска не создаётся с нуля каждый ход, а создаётся лишь в начале партии. Когда делается ход - неактуальные ветви дерева обрезаются а поиск продолжается с того состояния, которое было. В том числе и во время хода соперника - идёт проработка перспективных продолжений, поэтому когда соперник сделает ход, поиск продолжится не с нуля. Быть может и вовсе получится сразу же сделать ход. Момент времени, когда игрок сделает ход - это фактор случайности, который делает игру недетерминированной. Теперь уже нельзя запомнить выигрышную последовательность ходов.

  • Оценка дерева. Ввёл новый атрибут узла - качество оценки. Качество равно сумме качества всех прямых потомков, умноженное на коэффициент затухания. Т.е. качество оценки показывает проработанность ветки.

  • Углубление поиска. Качество оценки вместе с самой оценкой учитывается при выборе веток для углубления поиска. Чем выше оценка и чем ниже её качество - тем выше приоритет такой ветки для её развития. Потому что мало смысла до посинения развивать и так хорошо проработанную ветку с максимальной оценкой, которая уже вряд ли существенно изменится, когда она сравнивается со слабо проработанными ветками, чья оценка может значительно измениться.

  • База оценок и самообучение. В процессе игры какие-то позиции детально прорабатываются и получают оценку с высоким качеством. Почему бы не сохранять такие оценки для использования в других партиях? Это ещё одна фича, которая делает игру недетерминированной.

В результате этих доработок AI стал сильнее, и вполне уверенно обыгрывает старую версию игры. Я провел несколько партий против AI на chess.com и выяснил, что уровень моей программы примерно соответствует рейтингу 1800-1900. Прогресс есть, и это хорошо!

Программирование игрового AI - занятие чертовски затягивающее: всегда хочется добиться большего. И хотя у меня по прежнему есть масса идей для дальнейшего развития, наступает момент, когда надо остановиться. Думаю, он наступил. Однако если кто-либо желает - может взять мой код, побаловаться, поэкспериментировать, что-нибудь реализовать. Благо, сейчас Delphi доступен каждому благодаря бесплатной Community Edition, не говоря уже про бесплатный Free Pascal и Lazarus. Код проекта (а также скомпилированный exe-шник) можно взять тут: https://github.com/Cooler2/chess (для компиляции понадобится также кое что из https://github.com/Cooler2/ApusGameEngine). Спасибо всем, кто дочитал :-)

Подробнее..

Перевод Головоломка от будущих создателей GTA. История Lemmings

30.12.2020 20:10:58 | Автор: admin

Верные высказыванию, что у успеха много отцов, а неудача всегда сирота (фраза президента США Джона Кеннеди), Дэйв Джонс, Скотт Джонстон, Майк Дэйли и Гэри Тиммонс рассказывают о своём влиянии на классику.


image


Вот вам задача: как пройти уровень Стальные рудники Кессела (Steel Mines of Kessel), не потеряв никого из леммингов? Даже сейчас такой вопрос можно встретить на профильных форумах. Но чем объяснить такую популярность игры, изданной 14 февраля 1991 года?


Lemmings обладает ключевой чертой Тетриса способностью привлекать как хардкорных, так и казуальных игроков. Головоломка ломает утверждение, что видеоигры нравятся только гикам. Простые механику и дизайн смогут понять даже технически неумелые родители. А увлечение электронными головоломками многие начали именно с этой игры. Мы хотели создать весёлое развлечение, рассказывает дизайнер Дэйв Джонс. С первого взгляда всё кажется просто, но сев за игру придётся поломать голову. Сразу вникаешь в процесс. И не важно какого ты возраста или пола. Но главной причиной успеха считаю оригинальную идею проекта.


Популярность как среди казуалов, так и хардкорщиков объясняется простой механикой. Избежать гибели беспомощного народца стало понятной концепцией со множеством сценариев развития событий. В индустрии, которая стимулирует первобытные инстинкты, Lemmings выделяется тем, что игрок здесь сохраняет жизни.


image


image


Такая механика появилась благодаря экспериментам с кодом. Программисты DMA Design Скотт Джонстон и Майк Дэйли поспорили о том, насколько маленьким может быть спрайт, чтобы сохранять при этом индивидуальность. Джонстон считал, что это значение должно быть не меньше 16 пикселей, а Дэйли что можно снизить до восьми. Всё произошло за один день, объясняет Скотт. Lemmings стала третьей игрой, в разработке которой принимал участие. Идея возникла, когда один из сотрудников DMA создал в программе Deluxe Paint анимацию группы маленьких человечков, поднимающихся по крутому склону. На вершине поджидала пушка и расстреливала их. Демка отображала хаос, раскидывая народец по экрану. И тут я подумал: из этого выйдет забавная игра.


Майк выиграл пари, но ведущему аниматору Гэри Тиммонсу предстояло проработать индивидуальность каждого из леммингов. Как он объясняет: Я хотел сделать такую анимацию, чтобы игрок поверил в то, что действительно видит леммингов из арта на коробке с игрой, а не просто множество пикселей. Поэтому ушёл в детали: ноги и волосы у персонажей подвижные, и над этим было интересно работать. Обычно спрайты создают на основе дизайна персонажей. В Lemmings они были завершены до того, как мы переключились на создание концепт-артов и дизайна. Я хотел, чтобы лемминги казались милыми и беспомощными. Выражение сонных глаз помогло этого добиться.


image


Джонс рассказывает, что у них не было продуманной концепции: Плана не было просто воплощали свои задумки. Проект стал уникальным, поэтому сравнивать его было не с чем. Как комбинезон у Марио, так и зелёные волосы одна из отличительных черт леммингов. Причиной такого дизайна стала экономия времени. Я уменьшил количество цветов до трёх, чтобы появилась возможность использовать множество спрайтов одновременно, говорит Тиммонс. У персонажей такой характерный цвет волос, потому что так я переместил ползунки настройки RGB в приложении DPaint, чтобы не тратить время на проработку палитры.


Lemmings иллюстрирует ключевой принцип дизайна: простые элементы объединяются для создания сложных. Этому способствует выбор профессии леммингам, чтобы преодолевать многочисленные опасности, встречающиеся на пути. Дизайн развивался постепенно, рассказывает Тиммонс. Мы выделили основные навыки леммингов, затем я оживил их, чтобы увидеть, какие работают лучше всего. Старался вложить в анимацию больше жизни и юмора. Например, шахтёр выглядит так, будто прилагает колоссальные усилия, а разрушитель похож на Папая (популярный герой комиксов).


В итоге появилось восемь профессий: альпинист, парашютист, подрывник, блокировщик, строитель, разрушитель, копатель и шахтёр. Каменные столбы можно преодолеть, если разрушитель пробьёт тоннель сквозь них. Возведя строителем мост, можно пересечь лаву и водные преграды. Такой подход стал новаторским. Игроку предлагают выбрать один из четырёх уровней сложности и пройти 120 карт. Позже вышли дополнения, например, Oh No! More Lemmings, а с помощью редактора можно создавать бесчисленное количество карт.


image


image


Уровни, отсылающие к Menace и Shadow Of The Beast


В Lemmings программисты направили все свои усилия на создание множества дьявольских головоломок. Мы реализовали почти все задумки, вспоминает Джонс. Дизайн уровней имел решающее значение, но у нас был хороший редактор, встроенный в игру, и несколько талантливых дизайнеров уровней. Внимательные игроки могут попасть на скрытые уровни, смоделированные на основе предыдущих проектов от DMA: Menace и Shadow Of The Beast.


С технической точки зрения Lemmings довольно простая, продолжает Джонс. Мы выбрали верное направление, представив игру с большим количеством персонажей, а не с одним. Код был отредактирован идеально, особенно когда дело касалось столкновение персонажей и изменения местности. Тем не менее, при разработке возникали проблемы. Игра требовала много оперативной памяти, сетует Джонс. Что ограничивало масштаб локации и вызывало проблемы при портировании на консоли. Было сложно добиться стабильной частоты кадров при отображении 120 леммингов на экране, поэтому игра максимально использовала ресурсы Amiga. Это усложнило перенос на другие машины хорошо, что не мы занимались портированием.


Lemmings стремительно набрала популярность. Есть что-то притягательное в спасении маленьких человечков, хотя никто не отнимает возможность уничтожить всех леммингов, если уровень чересчур головоломный. Это было прекрасное время, отмечает Джонс. Одна за другой выходили похвальные рецензии от критиков. Игра держалась в топ-20 на протяжении двух лет, но все лавры достались Psygnosis, поскольку они были издателем. Это одна из тех вещей в мире видеоигр, которые надо просто принять.


Тиммонс соглашается с Дэйвом: Оригинальная концепция с привлекательным дизайном пришлась всем по вкусу. Здесь очень весело отдать приказ одному леммингу, а затем наблюдать как это повлияет на всех остальных. Дизайн персонажей и музыка две вещи, которые запомнятся надолго. Мы потратили много времени на проработку уровней и довольны результатом.


Но для тех, кто помнит Lemmings как светлый и безобидный игровой опыт, примите во внимание следующее: развлечение задело чувства верующих на юге США. Там посчитали, что игра оказывает плохое влияние и разжигает поклонение дьяволу. Некоторые были недовольны стилистикой уровней с лавой, смеётся Джонс. Лемминги прыгали в пасть огнедышащего демона, чтобы закончить уровень, поэтому верующие пытались запретить игру. Хорошо, что у них ничего не вышло.


image



Подробнее..

11 игр, на которые стоит обратить внимание после анонсов на E3 2021

14.06.2021 18:13:31 | Автор: admin

В ночь с воскресенья на понедельник в ходе пары сессий на E3 2021 разработчики представили более 80 игр. Анонсы, как обычно, сопровождались демонстрацией трейлеров. Издатели и разработчики давали интервью во время Future Games Show и PC Gaming Show, подробно рассказывая о новых возможностях разных игр.

Все эти игры вспоминать не будем мы выбрали 11, на наш взгляд, самых интересных тайтлов. Список, естественно, очень субъективный. Если есть игры, которые мы пропустили, а вам они понравились давайте обсудим в комментариях. Итак, приступим.

Next Space Rebels



Многообещающая игра, в которой есть элементы Kerbal space program, Theme Park и некоторых других игр. Задача игры начать с малого, разработки прототипа ракеты из мусора валяющегося под ногами в собственном гараже, но закончить пуском полноценной ракеты, прямо как у Илона Маска. В ходе игры нужно будет побыть изобретателем, менеджером, пиарщиком и все это в одном лице.

Ixion



А это космическая опера, созданная стараниями студии Bulwark (в ее активе Warhammer 40,000: Mechanicus). Разработчики рассказали о том, что это стратегическая космическая опера на выживание.

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

Icarus



Шикарная игра для любителей жанра survival c добавлением элементов sim. Играть в нее можно в одиночку или целой компанией до 8 человек. Один из основателей проекта разработчик Дин Холл, который создал DayZ.

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

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

Happy Game



Весьма необычная приключенческая хоррор-игра, разрабатывает которую Amanita Design. Чем-то она напоминает Limbo, но гораздо более красочная и, наверное, страшная. Все начинается с того, что маленький мальчик, наигравшись, засывает в своей комнате.

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

Arboria



Игра достаточно мрачный приключенческий экшн с элементами RPG, в котором главный герой, представитель небольшого племени, должен спасти сородичей от вымирания. Вся проблема в том, что племя зависит от Древа-отца, которое заболело. Вредят ему злобные личности, сразиться с которыми нужно, как водится, в подземельях. Разработана игра Dreamplant, издатель All in!

Ранний доступ к Arboria был предложен игрокам еще в мае прошлого года. Но полная версия появится лишь в 2021 году.

Severed Steel



А это игра для любителей шутеров. Главный герой здесь девушка, которая способна в одиночку справиться с целой кучей врагов. Ей приходится осваивать огнестрел разных видов для того, чтобы сражаться эффективнее. По словам разработчиков, в игре есть элементы ИИ, что позволяет адаптировать игру на протяжении прохождения, чтобы мир и сражения оставались динамичными и приносили свежие эмоции.

Мир и объекты в нем можно разрушать, что делает Severed Steel еще интереснее. Ну и да, есть элементы паркура, что тоже может понравиться.

Dodgeball Academia



Dodgeball Academia, кажется, совмещает привычный геймплей и перспективу NES gem Super Dodgeball с элементами RPG и сюжетной линией школьного аниме. Этот продукт Humble Games выйдет на PS4, Xbox One, Switch и Windows в августе.

Rawmen



Rawmen берет элементы соревнования с Splatoon, добавляет часть опыта Journey и все это заворачивает в тему еды но не простой. В деле с гигантские катящиеся фрикадельки и прыгающие пончики. Игра через какое-то время появится на Xbox One, Series X / S, PS4 / 5 и Windows.

GigaBash



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

Lemnis Gate



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

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

Esports Boxing Club



Ну и напоследок бокс. В разное время разные издатели предлагали собственные версии виртуального бокса, но популярными стали очень немногие игры. Возможно, успеха удастся достичь Esports Boxing Club. Интересна игра, прежде всего, тем, что в ней можно свести вместе боксеров разных эпох всего в базе около 200 спортсменов. Поставить на ринг Мухамеда Али и Майка Тайсона? Не проблема.
Подробнее..

Продолжаем вдохновляться при написании ночных игр на ориентирование

12.01.2021 04:18:24 | Автор: admin

Почти 6 лет назад я написал свою первую и единственную статью на хабре про то, как вдохновлялся статьями и использовал их в заданиях для игр на ориентирование "Encounter". С тех пор я провёл ещё немного игр и, как мне кажется, настало время поделиться некоторыми игровыми заданиями. Возможно, кто-то из вас почерпнёт себе идеи, которое можно использовать на корпоративе, или просто для развлечения коллег.

Куда едем?

Каждую игру я стараюсь сделать максимально индивидуальной и пытаюсь использовать только те идеи, которые в моих играх ещё не использовались. Неизменным остаётся "подача" местонахождения игрового объекта (локации). Для того, что бы узнать, куда команде ехать, в игровом движке им нужно решить некую головоломку, которая после решения отдаст им координаты либо самого объекта, либо направления движения. Вот лишь некоторые из них

1337

|=!\/3||!||3|=()|||2$!}{23|2()7]-[|2337\/\/()|=()|||23!9]-[7|=()|_||2|=!\/3|=!\/3

Это - Leet. Не обязательно даже знать что это. Зная, что вы должны получить координаты в двоичной системе, можно проявить фантазию и получить из символов цифры five ( |=!\/3 ) nine ( ||!||3 ) four ( |=()|||2 ).. что приведёт в итоге к 594603248455

Brainfuck

-[----->+<  ]>++    .++ +.-         -----   --- -.+         +++.++  +++ .-.-.--     [--->++ <]> --.         [-- >+++<]> ++.         +++  +.---- ---         -.+   ++++. ---.++.+++  +++    +.++

Про нестандартные языки программирования, в том числе и про brainfuck есть уже достаточно на хабре. Если скормить этот код компилятору, то он выдаст 58.2765 26.3029

О, великий архив

В задании даётся ссылка на страницу, с комментарием о том, что история возвращает их в 3 декабря 2015 года. Если открыть эту же страницу через archive.org от 3го декабря 2015 года, то картина будет уже немного другой. Естественно, с координатами.

PNG или не GIF

Командам в задании видят картинку в PNG, со словом "animation". Немногие сразу вспомнят про APNG, который, возможно, заменит GIF. Если подождать какое-то время (не вспомню сколько, но больше 10 секунд точно), то слово заменится на координаты. Или можно воспользоваться первой попавшейся "раздербаниволкой" гифок и просмотреть все кадры.

Мне бы emoji, да по больше

Тут, кто на что горазд был. Но www.elephantpenguinsnail.ws, конечно же не работало. А вот на тот момент открывал страницу с координатами.

Thumbs.db

Командам предоставляется ссылка на архив с изображениями. Так же в архиве присутствует знакомый пользователям Windows файл "Thumbs.db". Картинки из архива не открываются, что должно навести на мысль о просмотре файла Thumbs.db. Можно воспользоваться онлайн просмотрщиком, который выдаст всего один файл, содержащийся в thumbs.db, на котором будут красоваться координаты.

Цветоимя

Первые 4 ячейки слева сверху имеют следующий hex код фона: #ff004f, #4b0082, #40826d, #614051. Если прогуглить каждый из этих кодов, то в первых же результатах будет наименование данного цвета. Так мы получим Folly, Indigo, Viridian, Eggplant - что по первым буквам даст нам "five".

Я вижу пиксели

К сожалению, не помню про что была статья на хабре, соответственно, не могу её найти (если в комментариях, или мне лично напомнят ссылку, обязательно её добавлю). Но мне хватило лишь одного её вида, что бы задание родилось само собой.

Тут можно либо присмотреться, либо воспользоваться камерой телефона. Если выбрать второй вариант, то нужно сфокусироваться на логотипе игры и начать зуумить. Что-то вроде макросъёмки получится.

Spoiler

Артефакты

Артефактами в игре называются осязаемые предметы, которые команды либо находят в течении игры, либо получают от организаторов. Артефакты призваны помочь командам для получения кода.

Кручу-верчу

Данный артефакт состоит из двух дисков, на каждом их которых в разброс расположены буквы английского языка. Это что-то вроде шифра замещения. Где буквы с большого диска приравниваются к букве с маленького диска, при условии, что диски установлены правильно.
На объекте команды находят коды состоящие из рандомно-расположенных букв.
Представим, что нашли они "TODR". Игра, напомню, называется Encounter, или сокращённо "EN". Если повернуть диски таким образом, что бы E была равна N, то TODR превращается в HABR.

The maze

На 3д принтере были распечатаны такие вот "шкатулки", состоящие из двух частей. Внутренняя- это вдавленный лабиринт, внешняя (колпачок) это выпуклость, которая должна пройти лабиринт до выхода, что бы эта колпачок открылся и команда достала из внутренней части бумажку с кодом. Для предотвращения использования физической силы, лабиринт дублировался с одной и с другой стороны внутренней части. На колпачке было, соответственно, две выпуклости. А так же, команды были предупреждены, если артефакт будет сломан, то за это они получат штраф.

Интерактивы и нестандарты

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

Diceware

Одним из таких вот нестандартов был diceware.

Это "easy" Это "easy"

Check-point

В качестве одного интерактивного задания использовались NFC метки и програмка на андроиде.
Пронумерованные метки были развешаны на разных этажах 3х-этажного здания с двумя подъездами. Командам нужно было пробежаться по всем меткам подряд и "тэгнуть" их телефоном на котором программа отсчитывала время в обратном направлении. Каждая метка добавляла n секунд. Если время дойдёт до нуля, то командам придётся начинать сначала с первой метки. Проблема состояла в том, что метки находились далеко не по порядку и нужно было проявить чудеса логистики, что бы быстро собрать все метки подряд, пока не уйдёт время.
Вот в таком порядке находились метки

Примерно так надо было проходить этот уровень

Devices

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

Team work

На данном девайсе команде нужно было пройти простую игру перепрыгивая препятствия. Что-то наподобие Дино их хрома, но более колхозно. Нюанс заключался в том, что экран находился метрах в 5 от кнопок управления прыжками интерактивного игрока.

O

Помните артефакт с дисками и буквами английского алфавита? Этот артефакт сыграл дважды. В одном из диском находилась NFC метка. Артефакт нужно было приложить к девайсу, который, прочитав метку, выдавал команде код.

Password

Идея этого девайса позаимствована из игры Keep talking and nobody explodes.
На объекте были написаны всевозможные слова, а на барабанах девайса - буквы. Только одно слово с объекта можно было выстроить на девайсе крутя барабаны. Как только правильное слово было собрано, на экране отображался код.

Sound transfer

Фотографий данного девайса, к сожалению, не сохранилось. Но не упомянуть о нём я просто не могу.
На самом деле, девайс состоял из двух частей - передатчик и приёмник. Передатчик лазером моргал саундтрэк из "супер марио". А приёмник, соответственно, при получении проигрывал то, что моргает ему лазер. Но, как всегда, нюансы - передатчик и приёмник находятся в разных помещениях. Что бы "передать" лазер нужно было воспользоваться зеркалом, что бы направить луч на приёмник.

Мы так же развлекаем игроков экстремальными заданиями
Это тоже некий Team Work, где команда поднимает своего игрока на верхЭто тоже некий Team Work, где команда поднимает своего игрока на верх

Современные ночные игры в Эстонии сильно отличаются от тех, что были лет 15 назад, когда всё это зарождалось. На смену баллонам пришли маркеры и микро-маркеры, а электроника стала неотъемлемой частью при проведении игр. Не изменилось лишь одно - желание развлекать игроков, и привносить новые и интересные идеи организаторами ночных городских игр.

Подробнее..

Шахматный телепорт

11.05.2021 14:17:08 | Автор: admin

Если зайти на какой-нибудь шахматный сайт типа личес, то там можно обнаружить помимо обычных шахмат шахматы с альтернативными правилами. Например, давно известна игра Шахматы Фишера. Так же очень популярны CrazyHouse, King of the hill, Horde и другие. Сегодня, хочу представить вашему вниманию новую шахматную игру Teleport. Кому интересно добро пожаловать под кат)

Проектируем Teleport

Предпосылка На данный момент шахматы с классическими правилами очень хорошо исследованы. Созданы огромные базы известных типовых позиций. Какие-то позиции хорошие, какие-то плохие. Профессиональных игроки заучивают такие позиции, чтобы усилить игру. В итоге может возникнуть ситуация, что побеждает такой игрок, кто лучше запомнил, как ходить в первоначальных позициях. Но хотелось бы, чтобы победил игрок, который быстрее и лучше мыслит за доской, чтобы изученные варианты меньше влияли на победу.Как же это сделать?Да просто нужно усложнить шахматы. В классических шахматах, чтобы сделать ход, у вас есть два варианта. Вы можете пойти либо на пустую клетку, либо срубить фигуру противника.Для игры Teleport предлагаю третий вариант. Можно пойти на клетку где стоит ваша фигура, в этом случае происходит так называемый Телепорт, и фигуры меняются местами. Вот пример, как это делается: Ходим Конь f3-g5

Конь и слон меняются местами. В данной ситуации первым в руку мы должны взять коня, потому что конь f3 может пойти на поле g5, а слон не может встать на f3. Значит инициатором телепорта будет конь.

Чего же мы добиваемся этим правилом? Количество возможных ходов возрастает, а значит возрастает сложность игры. Позиции становятся сложнее, анализировать их трудней. Игра становится зрелищней и интересней.Но продолжим проектировать игру. Например, возникает вопрос, должны ли телепортироваться пешки?

Вот ситуация: Ход белых. Ладья h8-h2 и пешка стремительно проходит в ферзи. Хорош ли такой маневр в целом для игры?

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

Если пешка может телепортироваться, значит может произойти такая ситуация: Ладья первым же ходом делает телепорт h1-h2, и пешка становится на первую линию горизонтали. В том что пешка очутилась на первой линии, нет ничего страшного. Затем пешка сможет двигаться дальше. И она пойдет так: с поля h1-h2 пешка сдвинется на одну клетку, и снова очутится на второй линии. А со второй линии, как известно пешка может идти на третью линию или перепрыгнуть третью и сразу встать на четвертую. Здесь ничего не меняется.

Еще момент. Можно ли в этой позиции сделать телепорт?

Пешка ходит только в перед, по диагонали она только рубит. Рубить свою фигуру нельзя, значит пешкой по диагонали телепорт не возможен. Ладья ходит по вертикали и горизонтали, и значит в данной ситуации телепорт ладьей не возможен. В общем то это очевидно, но это надо проговорить.А как на счет короля, должен ли король делать телепорт?Рассмотрим позицию. Ход белых. Здесь численное преимущество белых. Если белый король находился бы в безопасности, исход был бы очевиден белые бы победили. Если мы разрешим королю телепортироваться (Слон a8-h1), то король убежит, а вместе с ним убежит зрелищность и накал страстей).

Было бы здорово, если бы в этой ситуации победили бы черные? Поэтому принимаем решение король телепортироваться не может!Просто с большим количеством фигур, легче организовать телепорт для короля, а значит мат в начале и середине игры будет поставить сложно. И это идет в разрез с тем, что мы хотим сделать игру зрелищной.Вот еще пример. Белые ставят детский мат.

Но если бы, король мог телепортироваться (Ферзь d8-e8), тогда бы король улизнул, и детского мата не произошло. В этом случае, зрелищность теряется.

ИТАК

Окончательные правила

Играем по правилам классических шахмат. Кроме того, если вы можете пойти на какое-либо поле и там стоит ваша фигура, то вы можете сделать Телепорт. В этом случае фигуры меняются местами. Телепорт может делать любая фигура или пешка. Король телепорт делать не может. Белая пешка в результате телепорта может очутиться на первой линии, а черная соответственно на восьмой. С первой и восьмой линии пешка может сдвинуться вперед на одну клетку.

Немного задачХод черных. Мат в 1 ход. Ну правда же красиво?

Белые начинают и выигрывают. Мат в 1 ход.

Белые начинают и выигрывают в 2 хода.

Подробнее..

Как у меня увели домен на reg.ru

09.03.2021 16:05:49 | Автор: admin

Хочу поделиться радостной новостью, если у вас есть домен на reg.ru или его партнерах 2domains.ru или других, то возможно это не надолго, в смысле есть он у вас не надолго.

Как-то раз сижу я за работой и тут мне на почту пишет юзер моего сайта, говорит что-то твой сайт (http://personeltest.ru/away/lines-98.ru) давно не открывается.

Действительно, захожу я туда пишу хостеру, тот говорит ошибка в DNS. Захожу в DNS записи, а они пустые и не редактируются. Смотрю информацию по домену - домен уже у другого регистратора, был reg.ru стал webnames.ru.

После разбирательства оказалось мой теперь уже любимый регистратор, без единого письма передал домен другому лицу, а потом отправил его другому регистратору. Как так получилось? Кто-то подделав мою электронную подпись просто написал им письмо, и они с радостью это сделали.

Зайдя в госуслуги я действительно там обнаружил электронную подпись которую даже физически не мог оформить будучи не то что в другом городе, а даже в другой стране.

Reg.ru:

Здравсвуйте!

Новостей, к сожалению, нет. Так как смена регистратора была произведена после смены администратора- уведомление было выслано, но на уже новую почту, которая была указана на домене. В данной ситуации мы также, на данный момент, ничем помочь не можем, так как домен больше не у нас.

Webnames.ru:

Здравствуйте!

Информацию о событиях, которые происходили с доменом, имеет только тот регистратор, который его поддерживал на момент этих событий. Т.е. если что-то происходило, когда домен находился в Reg.ru, знать об этом может только компания Reg.ru.

Мы располагаем информацией о домене только с момента его переноса к нам - с 23 февраля 2021г. О смене регистратора мы уведомили текущего администратора (лицо, чьи данные на тот момент были внесены в реестр), проверили копии его документов и получили его согласие с переносом. С момента переноса нарушений Правил регистрации мы не выявили, поэтому у нас нет оснований что-либо делать с этим доменом.

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

Так как я нахожу в другой стране, то вариантов у меня не так много. Могу только всем посоветовать, не регистрировать домен у регистратора, который может отдать ваш домен даже не уведомив вас по почте.

Убыток где-то составляет 30к в месяц, сайт перенес пока на http://color-lines-98.ru но раскручивать его теперь придется по новой, было написано даже андройд приложение которое все это время не работало пока сайт переносился.

К слову это не первый раз когда у меня хотели увести домен, купить его, скопировать игру, на просторах интернета можно увидеть несколько копий моего сайта, сделаю им рекламу:

http://color-lines.ru/

http://game-shariki.ru/shariki-linii

http://lines98.org.ua/color-lines.html

ну и теперь к нему можно добавить http://lines-98.ru.

Не скажу что мой дизайн чем-то уникален, он копирует старую DOS игру, возможно с некоторыми моими фотошоп улучшениями, но видимо всем так понравилась моя версия, что скопировать и своровать хотят только ее.

Спасибо reg.ru, спасибо за внимание.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru