Scribd Logo
Upload

Welcome to Scribd!

  • 378 views

    Pente: David Kron, Matt Renzelmann, Eric Richmond, and Todd Ritland

    Uploaded by

    Muthu Vijay Deepak
    The document discusses different game tree search algorithms that can be used for the board game Pente, including NegaScout, SSS-2, MTD(f), and Alpha Beta with Transposition Table. It provides brief descriptions of each algorithm and notes that Alpha Beta with Transposition Table performed the best in tests, followed by NegaScout and SSS-2, with MTD(f) and basic Alpha Beta performing worse. Faster search is not enough for solving Pente due to its large branching factor, and other techniques like stronger static board evaluation and move ordering are needed.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Pente: David Kron, Matt Renzelmann, Eric Richmond, and Todd Ritland

    Uploaded by

    Muthu Vijay Deepak
    378 views16 pages
    The document discusses different game tree search algorithms that can be used for the board game Pente, including NegaScout, SSS-2, MTD(f), and Alpha Beta with Transposition Table. It provides brief descriptions of each algorithm and notes that Alpha Beta with Transposition Table performed the best in tests, followed by NegaScout and SSS-2, with MTD(f) and basic Alpha Beta performing worse. Faster search is not enough for solving Pente due to its large branching factor, and other techniques like stronger static board evaluation and move ordering are needed.

    Original Title

    Pente

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses different game tree search algorithms that can be used for the board game Pente, including NegaScout, SSS-2, MTD(f), and Alpha Beta with Transposition Table. It provides brief descriptions of each algorithm and notes that Alpha Beta with Transposition Table performed the best in tests, followed by NegaScout and SSS-2, with MTD(f) and basic Alpha Beta performing worse. Faster search is not enough for solving Pente due to its large branching factor, and other techniques like stronger static board evaluation and move ordering are needed.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    378 views16 pages

    Pente: David Kron, Matt Renzelmann, Eric Richmond, and Todd Ritland

    Uploaded by

    Muthu Vijay Deepak
    The document discusses different game tree search algorithms that can be used for the board game Pente, including NegaScout, SSS-2, MTD(f), and Alpha Beta with Transposition Table. It provides brief descriptions of each algorithm and notes that Alpha Beta with Transposition Table performed the best in tests, followed by NegaScout and SSS-2, with MTD(f) and basic Alpha Beta performing worse. Faster search is not enough for solving Pente due to its large branching factor, and other techniques like stronger static board evaluation and move ordering are needed.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 16

    Pente

    David Kron, Matt Renzelmann, Eric Richmond, and Todd Ritland

    Introduction
    Game tree search algorithms in Pente
    NegaScout SSS-2 MTD(f) Alpha Beta with Transposition Table

    Pente
    Tic-Tac-Toe, with 5 in a row, a 13x13 board, and a couple other small twists

    NegaScout
    Developed by Alexander Reinefeld around 1983 Good: NegaScout dominates AlphaBeta
    Nodes searched by NegaScout are searched by AlphaBeta, but the reverse is not necessarily true

    Bad: NegaScout re-searches same subtrees


    Transposition tables become more important

    AlphaBeta vs. NegaScout

    AlphaBeta vs. NegaScout

    SSS-2
    Variant of SSS* Attempts to visit nodes in a best-first fashion Maintains a global solution tree which is generated by the expand function and is refined by the diminish function Nodes visited are a subset of nodes visited by Alpha-Beta In theory, slightly better than Alpha-Beta In practice, comparable with Alpha-Beta

    SSS-2
    G = {root}; //The global solution tree g = expand(root, +inf); //The "best-so-far" value do { temp = g; g = diminish(root, temp); } until (g >= temp);

    = leaf nodes of G after first expand(root, +inf) call

    MTD(f)
    Improvement to Alpha-Beta Always searches minimal windows
    nextCall(Alpha = beta -1 , Beta = beta)

    Can only return a bound on minimax value so it needs to converge towards it. Theoretically better than NegaScout Name From MTD(n,f)
    Memory-enhanced Test Driver f = guess

    //pos = boardState // d = depth // f = guess Int MTDF(node pos, int d, int f){ int score = f; upperBound = +Infinity; lowerBound = -Infinity; while(upperBound>lowerBound) do{ if(score == lowerBound) then beta = score +1; else = AlphaBeta(pos, beta-1, beta,d); if(score < beta) then upperBound = score; else lowerBound = score; return score;

    MTD(f)

    Alphabeta with Transposition Table


    for (all possible moves){ if (board with this move is in hash table){ get alphabeta value from table; } else { alphabeta(this table); store result in hash table; } update best move seen; }

    A transposition table is simply a hash table that stores previously calculated board configurations.

    10

    Alphabeta with Transposition Table


    Most difficult part is the hash function. If each board position can be occupied by player 1, occupied by player 2, or empty, we have 3*3*3*...*3 = 3^(number of positions). For a 13 by 13 board, the number of boards is 3^169 4.3 * 10^80 WAY WAY WAY too big.
    11

    Alphabeta with Transposition Table

    So, I made a 3dimensional hash table. 1st dimension is a hash on the middle row, 2nd dimension is a hash on the middle column, 3rd is on the forward diagonal.
    12

    Alphabeta with Transposition Table


    Doing this means that arrays will only be initialized when they are used, reducing a lot of space. This has time draw backs however (big arrays are initialized during crucial game 13 time).

    Results
    Algorithm Minimax AlphaBeta NegaScout SSS-2 MTD(f) AlphaBeta with TT Number of Wins 5 10 10 6 3 2

    Conclusion
    Fast tree search is not enough!
    A branching factor of 169 on a 13x13 board is problematic Pente actually uses a 19x19 board

    Need better SBE, move ordering,

    Demo (as time permits)

    You might also like