Results 1 to 4 of 4
Like Tree2Likes
  • 2 Post By CrimsonVex

Thread: A smarter bilge bot/more depth

  1. #1
    Junior Member
    CrimsonVex is offline


    Lightbulb A smarter bilge bot/more depth

    Hi all, new to the forum. Have done lots of reading through the history of the forum.

    There's lots of bilge bots. I've even found a few opensource ones - most boast about 3 or 4 depth depth-first searching for optimal moves.

    I've been working on a personal project - a manual bilge bot. I've used this as an excuse to get back into programming and exercise my mind.

    I've spent about 2 weeks so far, and I've got a 4-depth DFS running in 0.3 seconds on a mid-range laptop from 2015.
    • Reads screen on a range of game resolutions
    • Depth-first searching to a given depth (4 is fast)
    • Outputs a visual representation of the best next move

    I'm very keen to keep optimising, as well as introduce smarter features for identifying 'good' boards.

    Some more details:
    • I haven't yet got multi-threading working, but I'm very close
    • Screen-reading and visual output is done in Python 3.8
    • Algorithm/bot logic is written in C++ (via Cython)
    • I'm just starting to look into using pattern heuristics
    • Currently getting consistent excellents but very rare increds (Emerald)

    I understand the current best bilging bot can get vegases and sea-donkeys, and my question is whether that's being achieved via:
    • Alpha-beta pruning
    • GPU-acceleration
    • Pattern heuristics
    • Deep learning
    • Something else? A novel algorithm?

    Any tips?
    vice655 and Zantac like this.

  2. #2
    Junior Member
    CrimsonVex is offline

    I've done some more work on it - I've added minor pruning optimisations and multithreading.

    I'm now doing 4-depth in just under 0.1 seconds (2-3x speed up). I've now got 5-depth in about 4-5 seconds, but I'm keen to do even better.

    Next task is to get some better heuristics to evaluate preset board patterns to give increased pseudo-depth at terminal branches (likely necessary for sea-donkeys and vegas')

  3. #3
    Triump is offline

    Very interesting.. keep it up. Curious to watch it run.

  4. #4
    Junior Member
    CrimsonVex is offline

    Alright - have done further small optimizations:
    • Don't evaluate moves with empty spaces
    • Avoid duplcate puffers/jellies
    • Avoid evaluating crab moves
    • Use a localised search for clear checks first

    I've also purchased a new PC (goodbye circa 2015 laptop - new Ryzen 3700x speeds things up considerably)

    Currently achieving depth of 5 in ~700ms (depth 4 in ~15ms).

    Next optimizations:
    • Transposition tables using hashing to avoid re-evaluating board states - unsure how much improvement I'll get
    • Pattern heuristics to further score boards for terminal evaluation branches (looking ahead without looking ahead)
    • Refine current algorithm implementation to better use CPU cache/C++ optimizations

    I think my overall aim is to bring depth-5 down to under 250ms, with that extra boost in spotting sea-donkey/vegas potential using pattern tables. I think achieving that will put my bot in good standing to compete for #1 .. maybe?
    Last edited by CrimsonVex; 12-20-2019 at 05:26 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts