Results 1 to 9 of 9
Like Tree3Likes
  • 1 Post By erik
  • 1 Post By Dan
  • 1 Post By TheRigger

Thread: Bilge Depth Algorithm

  1. #1
    VIP Member
    Luponius is offline

    Posts
    2

    Bilge Depth Algorithm

    So I have to ask, out of curiosity and because I'm attempting to do a simple bot for fun, starting with bilging because some on this forum said it's easiest...

    Does the depth function do what I dread to think it does? As in do a swap of every location, with 4 internal iteration per possibility aka the entire board worth of swaps to the power of 4?

    And keep track of the best location score to find out which one scored highest, effectivelly finding the best 4 depth move possible - but then you redo it after every time the user makes a move?

    I mean it's about 15k combinations each time, or is it more? Is this the right approach to a simple bilge bot?

    I can't imagine it would yield donkeys and vegases with any consistency however, I know that building those usually takes well upwards of 4 moves, and it requires them to be focused. Oceanus doesn't seem to work this way, and has a better shot at donkeys and vegases, what's the difference? Any speculation?

  2. #2
    Senior Member
    Papaoutai is offline

    Posts
    220
    You're correct - it does every possible move, followed by every other possible move, etc, using the depth to limit how far ahead it searches. It's more formally known as depth first search, which is a graph/tree searching algorithm (in the context of bilge each node in the graph would be a position, and each edge would be a move).

    Since bilging has 12 rows, and 5 possible swaps on each row, it's 60 moves per state (? I think), which then translates to 60^4 for a depth-4 search, so approximately 13 million positions. Though I'm sure this number could be reduced somehow with some optimization

    My rough speculation with Oceanus is that it's really nicely optimized depth-4 search (not sure how - either it avoids evaluating some states or it's fast at evaluating them, some clever pruning of some sort), and it prioritizes the horizontal 3*3 because it leads to a higher chance of an SD/Vegas.

  3. #3
    Senior Member
    erik is offline

    Posts
    321
    Quote Originally Posted by Papaoutai View Post
    You're correct - it does every possible move, followed by every other possible move, etc, using the depth to limit how far ahead it searches. It's more formally known as depth first search, which is a graph/tree searching algorithm (in the context of bilge each node in the graph would be a position, and each edge would be a move).
    It's called breadth-first princess.
    Sobo likes this.

  4. #4
    Senior Member
    Papaoutai is offline

    Posts
    220
    Quote Originally Posted by erik View Post
    It's called breadth-first princess.
    ? It's a depth first search. It traverses each node to the bottom of the tree before it goes back up to level 1 and starts on the next one. It's definitely not breadth-first lol

  5. #5
    Dan
    Bot Coder
    Dan is offline

    Posts
    210
    Quote Originally Posted by Papaoutai View Post
    ? It's a depth first search. It traverses each node to the bottom of the tree before it goes back up to level 1 and starts on the next one. It's definitely not breadth-first lol
    It could be either. L2Algorithm.

    .. Also what you described was definitely BFS.
    Last edited by Dan; 1 Week Ago at 05:26 PM. Reason: Derp
    Sobo likes this.

  6. #6
    Senior Member
    Papaoutai is offline

    Posts
    220
    Quote Originally Posted by Dan View Post
    It could be either. L2Algorithm.

    .. Also what you described was definitely BFS.
    Although your point is true, it's completely impractical to use BFS for bilge. Enjoy storing millions of positions in memory I guess?

    I don't think I described BFS. I said
    it does every possible move, followed by every other possible move
    - you could apply that to both DFS or BFS. It's just a tree of moves.

  7. #7
    Senior Member
    TheRigger is offline

    Posts
    622
    Quote Originally Posted by Papaoutai View Post
    I don't think I described BFS.
    ... but you did
    Sobo likes this.

  8. #8
    Senior Member
    erik is offline

    Posts
    321
    Quote Originally Posted by Papaoutai View Post
    it does every possible move, followed by every other possible move
    definition of BFS

  9. #9
    Junior Member
    snipesy is offline

    Posts
    3
    The GPU bot uses something like BFS, at first. And then resorts to the DFS.

    It is not a true BFS though. Each time you want to go and test to a level you just go there directly with some preconditions. This means you only need enough working memory for your threads, which should always be lower than the number of preconditions.

    You can calculate for every 6th order move with this method. Breaks included., with no complicated optimization, in reasonable time (0.7 seconds), on a modern gpu. That is 46 billion moves to put it into perspective.


    Also another note on the threads vs preconditions.

    You want preconditions / threads to be as close to a factor as possible.

    If I have 39 threads and 80 preconditions, then I may as well have 117 preconditions because we must wait on 2 threads to finish up in the end. This is less of an issue if you have A LOT more preconditions than threads, but is something to be mindful of.
    Last edited by snipesy; 6 Days Ago at 03:51 PM. Reason: on threads vs preconditions

Posting Permissions

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