Code Monkey home page Code Monkey logo

Comments (3)

AdamStelmaszczyk avatar AdamStelmaszczyk commented on May 17, 2024

According to Alpha-Beta Search Enhancements in Practice (pages 5-6), what 33b08fa added is not a killer heuristic.

It is just using a transposition table for move ordering (if the state was found in TT, but now we can go deeper, at least start with the best move as it can cause a lot of cut-offs).

Killer heuristic is storing the moves which cause cut-offs ("killers") and reusing them later.

Also, according to the paper, killer heuristic is very similar to history heuristic, but weaker. Thus, history heuristic will be implemented (#9).

from gtsa.

AdamStelmaszczyk avatar AdamStelmaszczyk commented on May 17, 2024

History heuristic was removed in 3207258.

Reasons are in the commit message. Generally it was decreasing performance (because of sorting).

This opens up a door for killer heuristic. It doesn't require sorting, so it actually may be worth its salt.

from gtsa.

AdamStelmaszczyk avatar AdamStelmaszczyk commented on May 17, 2024

Tested on Isola from initial state, 10 seconds per move, 20 moves limit:

Minimax<IsolaState, IsolaMove> a(10, 20);

Without killer heuristic:

goodness: 111 time: 0.00s move: 3 6 3 5 3 1 nodes: 21 leafs: 20 beta_cuts: 0 cutBF: -nan tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 1 max_depth: 1
goodness: -38 time: 0.00s move: 3 6 3 5 3 1 nodes: 135 leafs: 114 beta_cuts: 16 cutBF: 2.12 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 21 max_depth: 2
goodness: 90 time: 0.00s move: 3 6 2 5 2 1 nodes: 805 leafs: 716 beta_cuts: 53 cutBF: 1.58 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 89 max_depth: 3
goodness: 1 time: 0.01s move: 3 6 3 5 3 1 nodes: 4731 leafs: 3613 beta_cuts: 796 cutBF: 1.72 tt_hits: 171 tt_exacts: 22 tt_cuts: 132 tt_size: 949 max_depth: 4
goodness: 41 time: 0.03s move: 3 6 2 5 3 1 nodes: 29727 leafs: 24745 beta_cuts: 2831 cutBF: 2.23 tt_hits: 1051 tt_exacts: 214 tt_cuts: 762 tt_size: 4099 max_depth: 5
goodness: -7 time: 0.11s move: 3 6 4 5 3 1 nodes: 115057 leafs: 84062 beta_cuts: 17470 cutBF: 2.32 tt_hits: 10293 tt_exacts: 409 tt_cuts: 9360 tt_size: 22248 max_depth: 6
goodness: 59 time: 0.51s move: 3 6 2 5 4 1 nodes: 564288 leafs: 440655 beta_cuts: 64598 cutBF: 3.65 tt_hits: 45563 tt_exacts: 5253 tt_cuts: 37165 tt_size: 81172 max_depth: 7
goodness: -8 time: 2.39s move: 3 6 3 5 3 1 nodes: 2748509 leafs: 1947742 beta_cuts: 368784 cutBF: 3.61 tt_hits: 382467 tt_exacts: 13320 tt_cuts: 346574 tt_size: 421503 max_depth: 8

First, I kept 1 killer move for each ply:

goodness: 111 time: 0.00s move: 3 6 3 5 3 1 nodes: 21 leafs: 20 beta_cuts: 0 killer_cuts: 0 cutBF: -nan tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 1 max_depth: 1
goodness: -38 time: 0.00s move: 3 6 3 5 3 1 nodes: 135 leafs: 114 beta_cuts: 16 killer_cuts: 0 cutBF: 2.12 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 21 max_depth: 2
goodness: 90 time: 0.00s move: 3 6 2 5 2 1 nodes: 721 leafs: 636 beta_cuts: 44 killer_cuts: 9 cutBF: 1.61 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 85 max_depth: 3
goodness: 2 time: 0.01s move: 3 6 3 5 3 1 nodes: 4331 leafs: 3392 beta_cuts: 501 killer_cuts: 189 cutBF: 1.80 tt_hits: 102 tt_exacts: 13 tt_cuts: 77 tt_size: 841 max_depth: 4
goodness: 41 time: 0.03s move: 3 6 2 5 3 1 nodes: 24837 leafs: 20755 beta_cuts: 2045 killer_cuts: 547 cutBF: 2.08 tt_hits: 551 tt_exacts: 93 tt_cuts: 399 tt_size: 3708 max_depth: 5
goodness: -7 time: 0.13s move: 3 6 4 5 3 1 nodes: 121360 leafs: 90790 beta_cuts: 15321 killer_cuts: 4197 cutBF: 2.48 tt_hits: 7636 tt_exacts: 362 tt_cuts: 6774 tt_size: 24188 max_depth: 6
goodness: 50 time: 0.63s move: 3 6 2 5 2 1 nodes: 626930 leafs: 510523 beta_cuts: 49818 killer_cuts: 15635 cutBF: 3.88 tt_hits: 32817 tt_exacts: 3038 tt_cuts: 27142 tt_size: 91864 max_depth: 7
goodness: -8 time: 2.62s move: 3 6 3 5 3 1 nodes: 2603159 leafs: 1931285 beta_cuts: 289911 killer_cuts: 78543 cutBF: 3.49 tt_hits: 241442 tt_exacts: 7775 tt_cuts: 220606 tt_size: 461893 max_depth: 8

I tried also to keep 2 killers for each ply:

goodness: 111 time: 0.00s move: 3 6 3 5 3 1 nodes: 21 leafs: 20 beta_cuts: 0 killer_cuts: 0 cutBF: -nan tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 1 max_depth: 1
goodness: -38 time: 0.00s move: 3 6 3 5 3 1 nodes: 135 leafs: 114 beta_cuts: 16 killer_cuts: 0 cutBF: 2.12 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 21 max_depth: 2
goodness: 90 time: 0.00s move: 3 6 2 5 2 1 nodes: 760 leafs: 668 beta_cuts: 45 killer_cuts: 21 cutBF: 1.69 tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_size: 92 max_depth: 3
goodness: 9 time: 0.01s move: 3 6 4 5 4 1 nodes: 4084 leafs: 3107 beta_cuts: 298 killer_cuts: 615 cutBF: 1.94 tt_hits: 153 tt_exacts: 27 tt_cuts: 118 tt_size: 842 max_depth: 4
goodness: 40 time: 0.03s move: 3 6 2 5 3 1 nodes: 18244 leafs: 14633 beta_cuts: 1159 killer_cuts: 1645 cutBF: 2.15 tt_hits: 738 tt_exacts: 97 tt_cuts: 614 tt_size: 3174 max_depth: 5
goodness: -1 time: 0.22s move: 3 6 3 5 3 1 nodes: 172202 leafs: 127648 beta_cuts: 18607 killer_cuts: 14105 cutBF: 2.60 tt_hits: 12527 tt_exacts: 621 tt_cuts: 11292 tt_size: 32567 max_depth: 6
goodness: 49 time: 1.30s move: 3 6 3 5 2 1 nodes: 969208 leafs: 787812 beta_cuts: 72125 killer_cuts: 52671 cutBF: 4.13 tt_hits: 49309 tt_exacts: 2675 tt_cuts: 42557 tt_size: 147487 max_depth: 7
goodness: -10 time: 4.68s move: 3 6 3 5 3 1 nodes: 3596699 leafs: 2651717 beta_cuts: 368636 killer_cuts: 253976 cutBF: 3.46 tt_hits: 330039 tt_exacts: 9643 tt_cuts: 305083 tt_size: 689675 max_depth: 8

Looking at depth 8: enabling killer heuristic didn't improve the time. It caused less tt_hits, tt_cuts, tt_exacts and beta_cuts. It improved cutBF slightly tough, however it didn't on depth 7, so it looks like just noise, I also don't see logical reasoning why it would improve cutBF. It's possible that in other games it brings some improvement, but to have it in general library, it doesn't look like it's worth its additional code.

from gtsa.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.