2
\$\begingroup\$

I'm implementing alpha-beta pruning for a chess engine in TypeScript

Here's the code:

public static alphabetta(board: Board, player: Player = Player.CPU, move?: Move, depth: number = 0,
    α: number = -Infinity, β: number = +Infinity): EvaluatedMove {

    const { gameOver, winner } = board;
    if (gameOver) {
      if (winner === Player.CPU) return EvaluatedMove.from(move, MAX_SCORE - depth);
      if (winner === Player.Human) return EvaluatedMove.from(move, depth - MAX_SCORE);
    }

    if (depth >= MAX_DEPTH) {
      return EvaluatedMove.from(move, this.score(board, depth));
    }

    const opposingPlayer = opponent(player);
    const possibleMoves = board.possibleMoves(player);

    if (player === Player.CPU) {
      let result = <EvaluatedMove>{ score: α };
      for (const possibleMove of possibleMoves) {
        const newBoard = board.makeMove(possibleMove);
        result = max(result, this.alphabetta(newBoard, opposingPlayer, possibleMove, depth + 1, α, β));
        α = Math.max(α, result.score);
        if (β <= α) break;
      }
      return result;
    } else {
      let result = <EvaluatedMove>{ score: β };
      for (const possibleMove of possibleMoves) {
        const newBoard = board.makeMove(possibleMove);
        result = min(result, this.alphabetta(newBoard, opposingPlayer, possibleMove, depth + 1, α, β));
        β = Math.min(β, result.score);
        if (β <= α) break;
      }
      return result;
    }

for full context here's a pull request on Github, I used this wikipedia page and this paper for refernce, tho they have slightly different pseudocode.

In my case I want alphabetta() not only return heuristic weight of a move but also the move itself, hence the slightly different implementation and signature

However both examples suggest that the algorithm may return moves that are not immediate (but may rather happen further down in game), which confuses me.

Any suggestions as to how this can be improved? My (non pruning minimax implementation from the same repo is doing just that)

\$\endgroup\$
  • 1
    \$\begingroup\$ Sorry to sound a bit harsh, but does this code work? "[B]oth examples suggest that [the] algorithm may return moves that are not immediate". Notice that v in the Cornell algorithm is not a move, it is a score. I suspect that trying to return result as you have done will give you a move much further down the tree. This is, roughly speaking, why the scoring is decoupled from actually making the moves. \$\endgroup\$ – Dair Mar 28 '17 at 2:40
  • \$\begingroup\$ You didn't return the move, but only the score. Why? \$\endgroup\$ – SmallChess Mar 28 '17 at 6:45
  • \$\begingroup\$ The algorithm looks very similar to Wikipedia. Although the implementation look very slow, but it looks functional to me. \$\endgroup\$ – SmallChess Mar 28 '17 at 6:46
  • \$\begingroup\$ @Dair no it doesn't work, and hence this question \$\endgroup\$ – dark_ruby Mar 28 '17 at 8:01
  • \$\begingroup\$ Off you go to stackoverflow then. Checklist for how to write a good Code Review question \$\endgroup\$ – kyrill Mar 28 '17 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.