Статьи

Преимущества функционального программирования

Январь 5, 2019

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

  1. Использование функций в качестве входа и выхода из других функций,
    функции высшего порядка
  2. Использование функций map , filter и reduce типов вместо зацикливания
  3. Неизменное состояние
  4. Рекурсия вместо зацикливания
  5. Составление функций из других функций
  6. Отличие «чистых» функций от функций с побочными эффектами

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

Создание эффективного шахматного AI с помощью Elm

Но сначала немного информации о шахматном программировании:

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

Задача оптимизации кода шахматного ИИ породила несколько замечательных алгоритмов, таких как альфа-бета-обрезка и поиск минимума-максимума. В Deep Blue , AI, победившем чемпиона мира Гарри Каспарова , были встроены специализированные «шахматные» фишки, которые делали его во много раз быстрее, чем программные решения. Кроме того, Энциклопедия шахматных дебютов содержит лучшие ходы для всех популярных дебютов, и они жестко запрограммированы в шахматные программы как данные, не требующие работы со стороны ИИ в течение первых десяти-двадцати ходов каждой игры.

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

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

Для простоты, давайте предположим, что количество законных ходов на каждом последующем ходу остается неизменным (это не так; обычно оно увеличивается с каждым ходом в первой части игры). Первый игрок, который в «Ранениях» — красный игрок, имеет около 30 легальных ходов в начале игры. ИИ попробовал бы каждый из этих ходов для слоя 1, а затем он дал бы каждому из ответов Синей команды (слой 2), который был бы 30 раз 30 или 900. Вы видите, куда это идет. Затем он рассмотрел бы 27 000 секундных ходов красных (сгиб 3) и 810 000 ответов синих на них (сгиб 4). Легко не хватает времени и памяти, когда начинаешь смотреть дальше.

Сравнивая Objective-C и вяз

Когда я написал код для этого в Objective-C, прежде чем столкнулся с функциональным программированием, я увидел, что рекурсия позволит мне написать чистый код для этого. Когда я реализовал рекурсивный код, я обнаружил, что при глубине в 5 слоев код может привести к сбою моего iPad. Для этого было две причины: во-первых, перед каждым следующим перемещением на доске необходимо сохранить копию каждой позиции доски, а во-вторых, Objective-C не был оптимизирован для рекурсии и, следовательно, потребовал дополнительных затрат. Рекурсивные вызовы (без оптимизации) поглощают пространство стека, поэтому это обычно самое слабое звено.

Будем надеяться, что это лучше работает в Elm. Взгляните на это:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
makeAIMove : Player -> Board -> Board
makeAIMove player board =
  let
    moveList = getAIMoves board player
    scoredMobility = List.map (\move -> scoreMoveMobility board player move) moveList
    scoredMoves =
    List.map (\move -> scoreMoveMaterial board player move) scoredMobility
    sortedMoves = List.sortBy .score scoredMoves |> List.reverse
    maybeMove = List.head sortedMoves
  in
    case maybeMove of
      Just maybeMove ->
        let _ = Debug.log "score " maybeMove.score
        in
          makeMove board maybeMove
      _ ->
        board

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
makeAIMove : Player -> Board -> Board
makeAIMove player board =
  let
    maybeMove =
    getAIMoves board player
    |> List.map (\move -> scoreMoveMobility board player move)
    |> List.map (\move -> scoreMoveMaterial board player move)
    |> List.sortBy .score
    |> List.reverse
    |> List.head
  in
    case maybeMove of
      Just maybeMove ->
        makeMove board maybeMove
      _ ->
        board

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

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

Частично примененные функции

Я немного соврал, когда сказал, что вывод одной функции передается следующей функции. То, что фактически передается, называется частично примененной функцией . Акт передачи это называется карри .

Карринг назван в честь Хаскелла Брукса Карри, пионера комбинаторной логики. Мало того, что глагол «карри» относится к нему и его работе, также есть три функциональных языка программирования, также названных в его честь: Хаскелл, Брукс и Карри. Из этих трех только Хаскелл имеет значительное число последователей.

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

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

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

Например, в React / Redux вы обрабатываете состояние, кодируя функции Redux, называемые «редукторами». Затем вы создаете «действия». Когда Redux получает действие, он тщательно применяет любое промежуточное программное обеспечение, а затем вызывает все редукторы. Редукторы могут действовать на действия, которые их интересуют, или просто так сказать. React / Redux не является чисто функциональным набором инструментов, но авторы говорят, что на них сильно повлияла архитектура Elm.

Элегантность неизменного состояния

Давайте снова поговорим об неизменяемом состоянии и на этот раз немного углубимся в элегантность использования его в вашем коде. «Чистые» инструменты функционального программирования обеспечивают неизменное состояние. Полуфункциональные инструменты, такие как React (с Redux), настоятельно рекомендуют, а также предполагают, что вы будете придерживаться шаблона проектирования неизменных состояний. Например, ReactJS вам разрешено звонить

1
this.state = ‘new state’;

в constructor() но последующие изменения состояния должны использовать

1
this.setState(‘new state’);

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

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

Вот мой (отредактированный для простоты) рекурсивный код Objective-C, который ищет хорошие движения ИИ:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
- (Move *) pickBestMove: (Board *) board forPlayer: (Player *) player depth: (int) depth
{
    Move *bestMove = nil;
    NSMutableArray *moves = [self generateLegalMoves:board forPlayer:player];
    if(moves.count > 0)
    {
        bestMove = moves[0];
        BOOL alphaBeta = depth % 2 == 1;
        for(Move *move in moves)
        {
            move.score = 0;
            int interimValueScore = 0;
            if(move.defending_man != nil)
            {
                interimValueScore += move.defending_man.value;
            }
            if(self.searchDepth > depth)
            {
                if(move.defending_man != nil)
                {
                    if(depth < 4)
                    {
                        Board *tempBoard = [board copy];
                        [tempBoard makeMove:move];
                        Player *nextPlayer = [self getNextPlayer:player];
                        // here's the recursive call
                        Move *nextPlyBestMove =
                [self pickBestMove:tempBoard forPlayer:nextPlayer
                    depth: depth + 1];
                        if(nextPlyBestMove != nil)
                        {
                            interimValueScore += nextPlyBestMove.score;
                        }
                        [tempBoard unMakeMove:move];
                    }
                }
            }
            if(alphaBeta)
            {
                move.score += interimValueScore;
                if(move.score > bestMove.score)
                {
                    bestMove = move;
                }
            }
            else
            {
                move.score -= interimValueScore;
                if(move.score < bestMove.score)
                {
                    bestMove = move;
                }
            }
        }
    }
    return bestMove;
}

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

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

01
02
03
04
05
06
07
08
09
10
11
makeAIMove : Player -> Int -> Board -> Board
makeAIMove player searchDepth board =
  let
    maybeMove = pickBestMove player 1 4 board
  in
    case maybeMove of
      Just maybeMove ->
        maybeMove
       |> makeMove board
      _ ->
        board

Функция pickBestMove делает рекурсивный вызов сам по себе, пока не достигнет глубины поиска, указанной параметром limit :

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
pickBestMove : Player -> Int -> Int -> Board -> Maybe Move
pickBestMove player depth limit board =
  let
    legalMoves = getAIMoves board player
    alphaBeta = (rem depth 2) /= 1
 
    setMoveScore move player depth limit board =
      if depth < limit then
        let
          nextBoard = makeMove board move
          nextPlayer = (Player.getNextPlayer player)
          -- here's the recursive call
          nextPlyBestMove =
            pickBestMove nextPlayer (depth + 1) limit nextBoard
        in
          case nextPlyBestMove of
            Just nextPlyBestMove ->
              if alphaBeta then
                {move | score = move.score + (scoreBoard nextPlayer nextBoard)}
              else
                {move | score = move.score - (scoreBoard nextPlayer nextBoard)}
            _ ->
              move
      else
        {move | score = makeMove board move |> scoreBoard player}
  in
    List.map (\move -> setMoveScore move player depth limit board) legalMoves
    |> List.sortBy .score
    |> List.reverse
    |> List.head

В разделе let вверху я определяю локальную функцию setMoveScore которая будет вызываться для каждого перемещения в списке legalMoves . setMoveScore рекурсивно вызывает внешнюю функцию pickBestMove . Интересно, что локальная / внутренняя функция рекурсивно вызывает внешнюю функцию. Это помогает думать о setMoveScore как о блоке кода, а не как о незаметной функции.

Шаблон {move | score = makeMove board move |> scoreBoard player} {move | score = makeMove board move |> scoreBoard player} показывает, как Элм реагирует на изменения состояния. Этот фрагмент возвращает новую копию move с обновленным счетом. Это хорошо согласуется с List.map функции List.map который создает новый список, применяя функцию к каждому элементу в старом списке.

Аналогично, вызов функции nextBoard = makeMove board move возвращает новую доску с измененной позицией. Player.getPlayer работает так же. Это очень полезно, так как мы хотим иметь возможность использовать исходную board и player в последней строке этой функции.

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

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

Подойдя

Следующий пост в этой серии будет посвящен React и Redux.

Опубликовано на Java Code Geeks с разрешения Эрика Форда, партнера нашей программы JCG . Смотрите оригинальную статью здесь: Преимущества функционального программирования

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

39
Share: