Разрабатывая браузерную игру Гомоку (5 в ряд) на языке JavaScript, я столкнулся с необходимостью реализации компьютерного противника (ИИ). В данной статье кратко описаны основные компоненты ИИ, а также приведено сравнение алгоритмов поиска Negamax, NegaScout и MTD-F.

Основные компоненты ИИ: функция оценки состояния игры, генератор ходов, алгоритм поиска, алгоритм определения победы.

Предисловие

Мой переход на F# в качестве излюбленного языка был слегка усеян препятствиями. Примерно через десять лет почти постоянного использования C# у меня пробудилось любопытство, когда я услышал об этом другом #-языке. Моя первая реакция была той, которую с тех пор видел у других C#-разработчиков — отрицание, — C# является хорошим языком, и мне с ним комфортно, так зачем тратить силы на изучение другого? Но любопытство осталось — и, по крайней мере, несколько раз выделил вечер, чтобы прочитать базовый вводный пост и попытаться написать каких-нибудь ката на F#. Это не прижилось, потому что я просто чувствовал себя потерянным и не мог воплотить свой опыт использования C# в ощущение даже отдаленного комфорта с F#. Достаточно легко опустить фигурные скобки, немного замяться, чтобы не забыть let вместо var — но как сделать то, что я хотел?

Тогда я этого не осознавал, но, на мой взгляд, наблюдал потенциальный недостаток в том, как F#-разработчики говорят, описывают и представляют свой язык внешнему миру. Существует обширная база материалов обо всех возможностях и функциональности F#: Algebraic Data Types, Exhaustive Matching, Type Inference и т.д. Есть много статей, посвященных тому, как решать широкий спектр задач с помощью F#. Но, как мне кажется, не хватает чего-то вроде следующего: некоторых указаний о том, как взять то, что вам уже удобно в C#, и перевести их на F#. Так что мне интересно, можем ли мы как-то закрыть этот недостаток.

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

Однажды в студенческие годы мне попалась на глаза новость о прошедшем в Лондоне чемпионате мира по памяти. На нем люди разных возрастов запоминали тысячезначные числа, десятки колод карт и сотни номеров телефонов. Меня, как человека иногда путающего пин-код от карты, это очень заинтересовало. Я сцепил пальцы в замок и подумал, — "Такая память всегда будет хорошим доводом". И углубился в тему, а вскоре смог запоминать и воспроизводить стозначные числа и порядок карт в колоде. Так каков же он, рецепт хорошей памяти? Сейчас расскажу.

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

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

Всё уже изобретено до нас

Обобщенные асинхронные типы возвращаемых значений — это новая возможность появившаяся в C# 7, которая позволяет использовать не только Task в качестве возвращаемого типа асинхронных (async/await) методов, но также и любые другие типы (классы или структуры), удовлетворяющие определенным требованиям.

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

async Task Main()
{
  foreach (var s in new[] { "1,2", "3,7,1", null, "1" })
  {
      var res = await Sum(s).GetMaybeResult();
      Console.WriteLine(res.IsNothing ? "Nothing" : res.GetValue().ToString());
  }
  // 3, 11, Nothing, Nothing
}

async Maybe<int> Sum(string input)
{
    var args = await Split(input);//Нет проверки результата
    var result = 0;
    foreach (var arg in args)
        result += await Parse(arg);//Нет проверки результата
    return result;
}

Maybe<string[]> Split(string str)
{
  var parts = str?.Split(',').Where(s=>!string.IsNullOrWhiteSpace(s)).ToArray();
  return parts == null || parts.Length < 2 ? Maybe<string[]>.Nothing() : parts;
}

Maybe<int> Parse(string str)
    => int.TryParse(str, out var result) ? result : Maybe<int>.Nothing();

Далее я объясняю, как работает этот код ...

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

Другой вопрос, что мне субъективно не очень нравится, как объясняется его работа. Потому, предлагаю альтернативный подход, описанный в моей книге, .NET Platform Architecture.

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

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

Заглянуть «под капот» кода или посмотреть на внутреннее устройство CLR можно с помощью множества инструментов. Этот пост родился из твита, и я должен поблагодарить всех, кто помог составить список подходящих инструментов. Если я пропустил какие-то из них, напишите в комментариях.

Во-первых, я должен упомянуть, что хороший отладчик уже присутствует в Visual Studio и VSCode. Также существует множество хороших (коммерческих) профилировщиков .NET и инструментов мониторинга приложений, на которые стоит взглянуть. Например, недавно я попробовал поработать с Codetrack и был впечатлён его возможностями.

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