A smarter bilge bot/more depth

[CrimsonVex]

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?

[CrimsonVex]

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')

[Triump]

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

[CrimsonVex]

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?