O código-fonte tem uma IA de busca

A IA em othello-web/lib/ai.ts lê várias jogadas à frente com busca alfa-beta. Com muitas casas vazias, ela lê 4 jogadas; com 12 casas ou menos, lê 6; e com 8 casas ou menos, lê até o fim. O tabuleiro é avaliado pelo peso das casas, pelo número de lugares onde se pode jogar, pelos cantos e pelas casas na diagonal ao lado dos cantos (casas X). O aiplayer.cpp do app em Qt funciona da mesma forma.

Se essa IA for colocada para jogar a sequência do 13–0, na 6ª jogada ela joga B5 em vez de D6. Ela não segue a sequência dos registros.

A IA implantada era outra

Desempacotamos a parte da IA do código da página que othello.mariago.kr serve atualmente. Não há busca. Ela experimenta colocar uma peça uma vez em cada lugar possível e escolhe o de maior pontuação.

  • Pontuação = peso da casa×4 + número de peças no tabuleiro + (minhas peças − peças do adversário)×3 − lugares onde o adversário pode jogar×2
  • Se for um canto, somam-se 40 pontos.

Se essa IA for colocada para jogar a sequência do 13–0, as quatro jogadas das brancas coincidem todas com os registros.

O último build da web foi feito 13 minutos antes de a IA de busca ser salva. Depois disso o build não foi refeito, e a primeira IA continuou no site.

A 8ª jogada

A imagem acima mostra os seis lugares onde as brancas podem jogar na 8ª jogada. Em quatro deles, assim que as brancas jogam, as pretas viram todas as peças brancas na jogada seguinte. A IA de uma jogada avaliou F4 como a melhor, com -12 pontos, e a escolheu. Como ela não olha a próxima jogada das pretas, não tem como perceber a aniquilação. A IA de busca vê os quatro lugares como jogadas perdedoras e escolhe B6.

Colocando as IAs para se enfrentar

Colocamos três IAs para jogar entre si, 100 partidas por par. Elas alternaram pretas e brancas, e as 4 primeiras jogadas foram aleatórias para que a mesma partida não se repetisse.

  • IA de busca contra IA de uma jogada: 100 a 0
  • IA de busca contra aleatória: 99 a 1
  • IA de uma jogada contra aleatória: 86 a 10, 4 empates

As pretas têm 2 sequências que aniquilam as brancas em até 11 jogadas contra a IA de uma jogada, e 0 contra a IA de busca.

Resultados de 100 partidas entre cada par de IAs e número de sequências de aniquilação
Resultados de 100 partidas entre cada par de IAs e número de sequências de aniquilação

O código real desta etapa

Esta é a IA de uma jogada desempacotada do código da página implantada. Só os nomes de variáveis abreviados foram trocados para facilitar a leitura.

IA no build implantadots · 34 linhas
const WEIGHTS = [
  [100, -20, 10, 5, 5, 10, -20, 100],
  [-20, -50, -2, -2, -2, -2, -50, -20],
  [10, -2, 1, 1, 1, 1, -2, 10],
  [5, -2, 1, 0, 0, 1, -2, 5],
  [5, -2, 1, 0, 0, 1, -2, 5],
  [10, -2, 1, 1, 1, 1, -2, 10],
  [-20, -50, -2, -2, -2, -2, -50, -20],
  [100, -20, 10, 5, 5, 10, -20, 100],
];

function suggestMove(board, who) {
  const moves = legalMoves(board, who);
  if (moves.length === 0) return null;
  const opp = opponent(who);
  let best = moves[0];
  let bestScore = -1e9;
  for (const mv of moves) {
    const res = playAt(board, mv.r, mv.c, who, "playing");
    if (!res.ok) continue;
    const mine = who === BLACK ? res.black : res.white;
    const theirs = who === BLACK ? res.white : res.black;
    let score = 4 * WEIGHTS[mv.r][mv.c];
    score += res.black + res.white;
    score += (mine - theirs) * 3;
    score -= 2 * legalMoves(res.board, opp).length;
    if ((mv.r === 0 || mv.r === 7) && (mv.c === 0 || mv.c === 7)) score += 40;
    if (score > bestScore) {
      bestScore = score;
      best = mv;
    }
  }
  return best;
}

Esta é a IA de busca do código-fonte.

othello-web/lib/ai.tsts · 61 linhas
function searchDepth(empties: number): number {
  if (empties <= 8) return empties;
  if (empties <= 12) return 6;
  if (empties <= 20) return 5;
  return 4;
}

// ...

function negamax(
  board: Stone[],
  who: Stone,
  depth: number,
  alpha: number,
  beta: number,
): SearchResult {
  const moves = legalMoves(board, who);
  const opp = opponent(who);

  if (moves.length === 0) {
    if (legalMoves(board, opp).length === 0) {
      const { black, white } = counts(board);
      const mine = who === BLACK ? black : white;
      const theirs = who === BLACK ? white : black;
      return { score: (mine - theirs) * 100_000, move: null };
    }
    const child = negamax(board, opp, depth - 1, -beta, -alpha);
    return { score: -child.score, move: null };
  }

  if (depth <= 0) {
    return { score: evaluate(board, who), move: null };
  }

  let bestScore = -Infinity;
  let bestMove: Point | null = null;
  for (const mv of orderMoves(moves)) {
    const res = playAt(board, mv.r, mv.c, who, "playing");
    if (!res.ok) continue;
    const child = negamax(res.board, opp, depth - 1, -beta, -alpha);
    const score = -child.score;
    if (score > bestScore) {
      bestScore = score;
      bestMove = mv;
    }
    if (score > alpha) alpha = score;
    if (alpha >= beta) break;
  }
  return { score: bestScore, move: bestMove };
}

/** 알파·베타 탐색. 초반은 위치·기동력, 종반은 돌 수를 중시. */
export function suggestMove(board: Stone[], who: Stone): Point | null {
  const moves = legalMoves(board, who);
  if (moves.length === 0) return null;
  if (moves.length === 1) return moves[0]!;

  const depth = searchDepth(emptyCount(board));
  const { move } = negamax(board, who, depth, -Infinity, Infinity);
  return move ?? moves[0]!;
}

O próximo post é "3. O VLM nunca fez uma jogada: falha ao carregar o Gemma 4".