Vamos lutar contra as máquinas!

Calma, calma, não estou incentivando uma guerra contra as máquinas no melhor estilo sci-fi para impedir ao dominação mundial do Ultron ou da Skynet.

Ainda não... ainda não 🤔

Convido você para desafiarmos as máquinas através da criação de um jogo bem simples utilizando ObjectScript com Python embarcado.

Tenho que dizer que fiquei super empolgado com a feature do Embedded Python no InterSystems IRIS, é incrível o leque de possibilidades que se abre para criar aplicações fantásticas.

Vamos construir um jogo da velha, as regras são bem simples e acredito que todos sabem como jogar.

Era o que me salvava do tédio na minha infância durante viagens longas de carro com a família, antes de crianças terem celulares ou tablets, nada como desafiar meus irmãos a jogar algumas partidas no vidro embaçado.

Então apertem o cinto e vamos lá!

Regras

Como comentado, as regras são muito simples:

• apenas 2 jogadores por partida
• é jogado em turnos em um grid de 3x3
• o jogador humano sempre será a letra X e o computador a letra O
• os jogadores só poderão colocar as letras nos espaços vazios
• o primeiro que completar uma sequência de 3 letras iguais na horizontal, ou na vertical ou na diagonal, é o vencedor
• quando os 9 espaços estiverem ocupados será empate e o fim da partida

Todo o mecanismo e as regras escreveremos em ObjectScript, o mecanismo do jogador do computador será escrito em Python.

Vamos colocar as mãos na massa

Controlaremos o tabuleiro em uma global, sendo que cada linha estará em um nó e cada coluna em um piece.

Nosso primeiro método é para iniciar o tabuleiro, para facilitar irei iniciar a global já com os nós (linhas A, B e C) e com os 3 pieces:

/// Iniciate a New Game
ClassMethod NewGame() As %Status
{
  Set sc = $$$OK
  Kill ^TicTacToe
  Set ^TicTacToe("A") = "^^"
  Set ^TicTacToe("B") = "^^"
  Set ^TicTacToe("C") = "^^"
  Return sc
}

neste momento iremos criar o método para adicionar as letras nos espaços vazios, para isto cada jogador irá passar a localização do espaço do tabuleiro.

Cada linha uma letra e coluna um número, para colocar o X no meio, por exemplo, passamos B2 e a letra X para o método.

ClassMethod MakeMove(move As %String, player As %String) As %Boolean
{
  Set $Piece(^TicTacToe($Extract(move,1,1)),"^",$Extract(move,2,2)) = player
}

Vamos validar se a coordenada passada é válida, a maneira mais simples que vejo é utilizando uma expressão regular:

ClassMethod CheckMoveIsValid(move As %String) As %Boolean
{
  Set regex = ##class(%Regex.Matcher).%New("(A|B|C){1}[0-9]{1}")
  Set regex.Text = $ZCONVERT(move,"U")
  Return regex.Locate()
}

precisamos garantir que o espaço selecionado esteja vazio

ClassMethod IsSpaceFree(move As %String) As %Boolean
{
  Quit ($Piece(^TicTacToe($Extract(move,1,1)),"^",$Extract(move,2,2)) = "")
}

Nooice!

Agora vamos verificar se algum jogador venceu a partida ou se o jogo já terminou, para isto vamos criar o método CheckGameResult.

Primeiro verificamos se teve algum vencedor completando pela horizontal, usaremos uma list com as linhas e um simples $Find resolve

    Set lines = $ListBuild("A","B","C")
    // Check Horizontal
    For i = 1:1:3 {
      Set line = ^TicTacToe($List(lines, i))
      If (($Find(line,"X^X^X")>0)||($Find(line,"O^O^O")>0)) {
        Return $Piece(^TicTacToe($List(lines, i)),"^", 1)_" won"
      }
    }

Com outro for verificamos a vertical

For j = 1:1:3 {
      If (($Piece(^TicTacToe($List(lines, 1)),"^",j)'="") &&
        ($Piece(^TicTacToe($List(lines, 1)),"^",j)=$Piece(^TicTacToe($List(lines, 2)),"^",j)) &&
        ($Piece(^TicTacToe($List(lines, 2)),"^",j)=$Piece(^TicTacToe($List(lines, 3)),"^",j))) {
        Return $Piece(^TicTacToe($List(lines, 1)),"^",j)_" won"
      }
    }

para verificar a diagonal:

    If (($Piece(^TicTacToe($List(lines, 2)),"^",2)'="") &&
      (
        (($Piece(^TicTacToe($List(lines, 1)),"^",1)=$Piece(^TicTacToe($List(lines, 2)),"^",2)) &&
          ($Piece(^TicTacToe($List(lines, 2)),"^",2)=$Piece(^TicTacToe($List(lines, 3)),"^",3)))||
        (($Piece(^TicTacToe($List(lines, 1)),"^",3)=$Piece(^TicTacToe($List(lines, 2)),"^",2)) &&
        ($Piece(^TicTacToe($List(lines, 2)),"^",2)=$Piece(^TicTacToe($List(lines, 3)),"^",1)))
      )) {
      Return ..WhoWon($Piece(^TicTacToe($List(lines, 2)),"^",2))
    }

por último, verificamos se teve um empate

    Set gameStatus = ""
    For i = 1:1:3 {
      For j = 1:1:3 {
        Set:($Piece(^TicTacToe($List(lines, i)),"^",j)="") gameStatus = "Not Done"
      }
    }
    Set:(gameStatus = "") gameStatus = "Draw"

Great!

É hora de criarmos a máquina!

Vamos criar o nosso adversário, precisamos criar um algoritmo capaz de calcular todos os movimentos disponíveis e usar uma métrica para saber qual é o melhor movimento.

O ideal é utilizar um algoritmo de decisão chamado de MiniMax (Wikipedia: MiniMax)

O algoritmo MiniMax é uma regra de decisão utilizado em teoria dos jogos, teoria de decisão e inteligência artificial.

Basicamente, precisamos saber como jogar assumindo quais serão os possíveis movimentos do oponente e pegar o melhor cenário possível.

Em detalhes, pegamos o cenário atual e recursivamente verificamos o resultado do movimento de cada jogador, caso o computador ganhar a partida pontuamos com +1, caso perder então pontuamos como -1 e 0 como um empate.

Caso não for o final do jogo, abrimos outra árvore a partir do estado atual. Feito isto encontramos a jogada com o valor máximo para o computador e a mínima para o adversário.

Veja o diagrama abaixo, existem 3 movimentos disponíveis: B2, C1 e C3.

Escolhendo C1 ou C3, o oponente tem uma chance de ganhar no próximo turno, já escolhendo B2 independente do movimento do adversário ganhamos a partida.

É como ter a joia do tempo em suas mãos para encontrar a melhor linha do tempo.

Convertendo para python

ClassMethod ComputerMove() As %String [ Language = python ]
{
  import iris
  from math import inf as infinity
  computerLetter = "O"
  playerLetter = "X"

  def isBoardFull(board):
    for i in range(0, 8):
      if isSpaceFree(board, i):
        return False
    return True

  def makeMove(board, letter, move):
    board[move] = letter

  def isWinner(brd, let):
    # check horizontals
    if ((brd[0] == brd[1] == brd[2] == let) or \
      (brd[3] == brd[4] == brd[5] == let) or \
      (brd[6] == brd[7] == brd[8] == let)):
        return True
    # check verticals
    if ((brd[0] == brd[3] == brd[6] == let) or \
        (brd[1] == brd[4] == brd[7] == let) or \
        (brd[2] == brd[5] == brd[8] == let)):
        return True
    # check diagonals
    if ((brd[0] == brd[4] == brd[8] == let) or \
        (brd[2] == brd[4] == brd[6] == let)):
        return True
    return False

  def isSpaceFree(board, move):
    #Retorna true se o espaco solicitado esta livre no quadro
    if(board[move] == ''):
      return True
    else:
      return False

  def copyGameState(board):
    dupeBoard = []
    for i in board:
      dupeBoard.append(i)
    return dupeBoard

  def getBestMove(state, player):
    done = "Done" if isBoardFull(state) else ""
    if done == "Done" and isWinner(state, computerLetter): # If Computer won
      return 1
    elif done == "Done" and isWinner(state, playerLetter): # If Human won
      return -1
    elif done == "Done":    # Draw condition
      return 0

    # Minimax Algorithm
    moves = []
    empty_cells = []
    for i in range(0,9):
      if state[i] == '':
        empty_cells.append(i)

    for empty_cell in empty_cells:
      move = {}
      move['index'] = empty_cell
      new_state = copyGameState(state)
      makeMove(new_state, player, empty_cell)

      if player == computerLetter:
          result = getBestMove(new_state, playerLetter)
          move['score'] = result
      else:
          result = getBestMove(new_state, computerLetter)
          move['score'] = result

      moves.append(move)

    # Find best move
    best_move = None
    if player == computerLetter:
        best = -infinity
        for move in moves:
            if move['score'] > best:
                best = move['score']
                best_move = move['index']
    else:
        best = infinity
        for move in moves:
            if move['score'] < best:
                best = move['score']
                best_move = move['index']

    return best_move

  lines = ['A', 'B', 'C']
  game = []
  current_game_state = iris.gref("^TicTacToe")

  for line in lines:
    for cell in current_game_state[line].split("^"):
      game.append(cell)

  cellNumber = getBestMove(game, computerLetter)
  next_move = lines[int(cellNumber/3)]+ str(int(cellNumber%3)+1)
  return next_move
}

Primeiro converto a global em um array simples, ignorando colunas e linhas deixando flat para facilitar.

A cada movimento analisado chamamos o método copyGameState, que como o nome diz, copia o estado do jogo naquele momento, onde aplicamos o MinMax.

O método getBestMove que será chamado recursivamente até finalizar o jogo encontrando um vencedor ou o empate.

Primeiro os espaços vazios são mapeados e verificamos o resultado de cada movimento alternando entre os jogadores.

Os resultados são armazenados em move['score'] para depois de verificar todas as possibilidades encontrar o melhor movimento.

Espero que você tenha se divertido, é possível melhorar a inteligência utilizando algoritmos como Alpha-Beta Pruning (Wikipedia: AlphaBeta Pruning) ou redes neurais, só cuidado para não dar vida a Skynet.

Fique livre para deixar comentários ou perguntas

That's all folks

Código completo:
InterSystems Iris versão 2021.1.0PYTHON