Page 1 of 4 123 ... LastLast
Results 1 to 10 of 31
Like Tree5Likes

Thread: Forage Bot

  1. #1
    Member
    savagesun is offline

    Posts
    72

    Forage Bot

    After a hiatus from Puzzle Pirates I decided to take a crack at a bot again. This time my aim is foraging, since it seems no one has any bot out for it yet. Progress so far has be phenomenal. I feel I've grown immensely as a programmer since my last attempt at a bot, and the code is far cleaner and well managed than it used to be. In my excitement seeing the bot go so well I thought it would be fun to write a little post/blog about it here!

    What's done right now?
    - Threaded
    - 4 move depth
    - Proper simulation
    - Manual mode!
    - Regular foraging
    - CI (testing)

    Updates etc.:

    Fun notes about foraging!
    I've noticed that the game has these little stars that like to shine around the crates of goods. They get in the way of the color detection when reading the board. Originally I thought this would be a big issue. However, as the bot is right now (1 move depth) it runs fast enough so even if it improperly reads the thing once it will correct itself almost immediately. This is subject to change, but the answer is pretty simple. Just tedious so lets hope it stays a non-issue!

    That's all folks! I'll try to post a video or some pictures tomorrow.

    Update 5/7/2014:
    So since I figured it would be trivial to add extra move depth I went ahead and did it this morning. It's up to 2 with seemingly no problems. It passed the "offline" tests where the bot acts upon screenshots of the board in different situations. Now just have to test it in game and make sure it's working properly. Turns out it was a little less trivial than I thought, but it works great.
    Some issues I did confirm for the moment are the 2x2 crates being improperly simulated. This will cause some issues as the depth search gets larger. What happens currently is that if something breaks below a 2x2 crate the crate will get split by columns in the simulation so it doesn't stay as a whole 2x2 crate and sort of ends up as a 1x2 and a 1x2. I'm still working on a fix for it.

    Finals and tests everywhere for the next two weeks but I'll try to get a video or some pictures out later tonight.

    1 Move Depth video:
    Removed, can still be found on Youtube if you want to see it.

    2 Move depth was acting up so I just went with the 1. Keep in mind the bot does not do non-solving moves yet so any move that does not have a little square on it was made by me. As it stands now the bot is actually rather helpful with clearing chests faster than normal. It picks things up I don't see! Also not that it completely reflects the bot or anything but the two DRs were incredible and excellent respectively.

    Update 5/8/2014:
    Fixed some of the simulation issues I found. Running crazy great! Finds some amazing clears for boards. It seems the 2 depth is working correctly but the moves are improperly drawn sometimes. Still investigating this. But if you guess where the bot is actually talking about it clears amazingly!

    Edit: Fixed the issue with the drawing! Works great at a depth of 2.
    Edit 2: Found a few more issues with simulation. One appears to be fixed, still working on solving the 2x2 crates staying together issue. It turns out the problem gets more important to solve the more move depths are included. Proper simulation is important!

    Update 5/9/2014:
    Fixed a huge simulation bug, 2 move depth works for the most part now. There is still a logical hiccup I'm aware of and working on. I solved the 2x2 crates problem and a few other minor search issues.

    2 move depth:

    Keep in mind I'm making any move that isn't denoted by a colored square. On that note it's important to note without the bot's help I get fines/goods. Heh

    Update 5/10/2014:
    Happily reporting in! Fixed the logical issues I mentioned last time. Turns out it was the way I was doing threading. I took threading out for the time being. Everyone always says premature optimization is the death of software! Anyways I tested it out and got from proficient to master in three or four boards. It was thrilling! Consistently gets excellent at the moment, but there is still human aid required.

    Update 5/11/2014:
    Started on the non-solving algorithm to drop boxes lower down the board properly. It's really unreliable, but it's just a start! I also thought it would be fun to up the move depth to 3 and see what the effects were. It got me GM from distinguished in maybe 5 boards. It was fun! Unfortunately it slowed down notably with the move depth at 3. It's still sustainable but it looks like I'll need to work with it to speed it up. Naturally if I can figure out how to properly thread it it should handle it no problemo!

    Edit: Added preliminary threading in the algorithm, sort of sped up but it still needs a few more passes to go faster! I've got a few ideas to try out.
    Edit 2: Tried the bot out in a fully autonomous state (no human thinking required) and it maintains around respected-master. Not bad for a first pass on the non-clearing algorithm!

    Update 5/13/2014:
    These past few days have been pretty much all about my finals. I did have some time to work on the bot a bit though. I reworked the non-clearing algorithm and made some attempts at making the clearing algorithm run faster. Unfortunately I screwed up my algorithm while making those changes so my time has mostly been spent fixing it haha. I got it to run about 60ms faster on average but not a huge impact. Usually the move takes about 1/3 of a second in practice though. The bot doesn't really get consistent DRs without human interaction yet, but it seems to stay around excellent as long as the chests don't get stuck (which they do occasionally).

    Update 5/15/2014:
    With finals over I'll have a little more time to work on this now! I fixed an issue with my threads where they weren't actually running concurrently. It makes the bot blazing fast at depth 3. I also added preliminary special piece usage. There are still issues to be worked out with that. With the concurrency issues worked out a few more issues have risen with moves occasionally overwriting each other and causing the GUI to display the right move rather erratically. Once I get these worked out and fix up the non-clearing algorithm I'll post a new video.

    Update 5/17/2014:
    Fixed the overwriting issue. Changed how the non-clearing algorithm works. It doesn't function properly yet but the idea behind it should be invariably better than the last one!

    Update 5/19/2014:
    Seeing Rigger's bot get up to depth 4 at 2 seconds made me really consider going for depth 4. So I did! I took his advice of pruning the board and employed a few changes to the way the bot searches the board and I'm happy to report an average of 1.5 seconds for depth 4! As far as I can tell it has REALLY paid off! It clears chests almost completely without human input in most cases! I'll throw up a video after I do a bit more testing!

    Edit: I thought it'd be fun to try out a depth of 5 as well, it runs between 5 - 10 seconds. 5 being a board with things in it 10 being a board with nothing solvable. Might be able to trim it down to something people can run optionally!
    Last edited by savagesun; 05-20-2014 at 11:45 AM. Reason: Updates
    Gauge and pas like this.

  2. #2
    Senior Member
    Atothek is offline

    Posts
    278
    Awesome work, looking forward for the video !

  3. #3
    Junior Member
    Steven Malstrom is offline

    Posts
    14
    Cant wait

  4. #4
    Member
    PackADap is offline

    Posts
    34
    Awesome idea! I've been waiting for this for a while. Will it be sold to the public? or private only? Also, is it aimed for CI (speed foraging) or normal foraging?

  5. #5
    Senior Member
    Shaaagg is offline

    Posts
    105
    Wow nice! If sucessful and public would really help the game push CI in my opinion! some dont get jobbed due to lack of frenetic forager etc

  6. #6
    Member
    savagesun is offline

    Posts
    72
    Quote Originally Posted by PackADap View Post
    Awesome idea! I've been waiting for this for a while. Will it be sold to the public? or private only? Also, is it aimed for CI (speed foraging) or normal foraging?
    I'm not sure I want to hand it away for free but I think it's too early to talk money haha. Right now the bot only works with regular foraging, but adding CI support is more than simple. I have yet to test anything out on CIs since it's not ready for that kind of field testing, but in the future I hope that it will support any type of foraging you might find yourself doing.

  7. #7
    Senior Member
    TheRigger is offline

    Posts
    641
    Quote Originally Posted by savagesun View Post
    What happens currently is that if something breaks below a 2x2 crate the crate will get split by columns in the simulation so it doesn't stay as a whole 2x2 crate and sort of ends up as a 1x2 and a 1x2. I'm still working on a fix for it.
    And this is why I never bothered to start a TH/Forage bot :S.
    Wayyyy too lazy for that. I saw this about like 2 minutes into a bilge bot when I thought about converting it to TH.
    Technically you could kinda-sorta brute force it since there can only be so many chests on the board at a time (store the bottom locations of all chests on the board, then move things down, then move the chests down if all their bottom locations are free until you can't anymore, then move things down one final time). Might be a problem if you have something like this though:
    [C][C][x]
    [C][C][C]
    where you have a big chest next to a small chest and you only move down if ALL the locations are free.
    So yeah :/ not going to think this through right now, but a possible approach.
    Edit: Theoretically you could number the chests during detection and do it that way, but tbh that would be less of a pain than figuring it out during runtime.

    Code:
    public enum Chest
    {
             ONE,TWO,THREE;
    }
    So while reading in a board, the first chest you detect becomes Chest.ONE(s if bigger chest), next becomes Chest.TWO(s), next becomes Chest.THREE(s) and so on, if you can get more than 3 chests on a board (I don't think so)
    Then as following:

    Simulate move (simple)
    while(morePiecesCanBeCleared())...
    clearPieces();
    while(nonChestsExistWithEmptySpacesBelow())...
    Move pieces down if not a Chest.ONE or Chest.TWO or Chest.THREE (simple once you figure it out)
    Move chests down (less complicated than before)
    Move pieces down if not a Chest.ONE or Chest.TWO or Chest.THREE
    end (inner loop)
    end (outer loop)

    This does a move, clears matches, moves stuff down, and clears concurrent clears.
    You probably already have something like this already, but the chest piece is the focus here.


    This is also ridiculously long, though it covers all three chests.

    You might have to check the i's and j's.

    Assume for simplicity's sake that board.width and board.height are the width and height of the board,
    though it'd be somewhat different codewise.
    Code:
    ////////////////////////////////////////////////
    // LOOKS MUCH BETTER IN NOTEPAD //
    ///////////////////////////////////////////////
    enum Pieces
    {
    	Pz1,Pz2,Pz3, EMPTY, ONE, TWO, THREE; //didn't bother looking up the pieces, but whatever
    }
    public void moveChestsDown()
    {
    	for(int count = 0; count < 9; count++)
    	//maximum repeats in the unlikely scenario you have a shovel under a small chest
    	{
    	for(int i = 0; i < board.width; i++)
    	{
    		for(int j = board.height-1; j >= 0; j--)
    		{
    			//Three-wide Chest
    			if(j > 0 &&j<board.height - 1 && i <= board.width - 3 && board[j][i] == board[j][i+1] && board[j][i] == board[j][i+2] 						&& (board[j][i] == Pieces.ONE || board[j][i] == Pieces.TWO || board[j][i] == Pieces.THREE)
    						&& board[j+1][i] == Pieces.EMPTY && board[j+1][i+1] == Pieces.EMPTY && board[j+1][i+2] == 							Pieces.EMPTY)
    			{
    				board[j+1][i] = board[j-1][i];
    				board[j+1][i+1] = board[j-1][i+1];
    				board[j+1][i+2] = board[j-1][i+2];
    				board[j-1][i] = Pieces.EMPTY;
    				board[j-1][i+1] = Pieces.EMPTY;
    				board[j-1][i+2] = Pieces.EMPTY;
    
    			}
    			//Two-wide Chest
    			if(j > 0 && j<board.height - 1 && i <= board.width - 2 && board[j][i] == board[j][i+1] && (board[j][i] == Pieces.ONE 						|| board[j][i] == Pieces.TWO || board[j][i] == Pieces.THREE)
    						&& board[j+1][i] == Pieces.EMPTY && board[j+1][i+1] == Pieces.EMPTY)
    			{
    				board[j+1][i] = board[j-1][i];
    				board[j+1][i+1] = board[j-1][i+1];
    				board[j-1][i] = Pieces.EMPTY;
    				board[j-1][i+1] = Pieces.EMPTY;
    			}
    			//One-wide Chest
    			if(j<board.height - 1 && i <= board.width - 1 && (board[j][i] == Pieces.ONE|| board[j][i] == Pieces.TWO || 								board[j][i] == Pieces.THREE) && board[j+1][i] == Pieces.EMPTY )
    			{
    				board[j+1][i] = board[j-1][i];
    				board[j][i] = Pieces.EMPTY;
    			}
    		}
    	}
    	}
    }
    ////////////////////////////////////////////////
    // LOOKS MUCH BETTER IN NOTEPAD //
    ///////////////////////////////////////////////
    Last edited by TheRigger; 05-08-2014 at 12:57 AM. Reason: Now to get to that chest method...

  8. #8
    Member
    savagesun is offline

    Posts
    72
    Quote Originally Posted by TheRigger View Post
    Snip
    Well the way the code is set up it simulates everything in steps and the piece movement is the very last step. I spent a little time working on it earlier today and it looks like the solution will not be too difficult to factor in. Just an extra method that corrects the error or a slight change to the movement method. Certainly not impossible to any extent haha

  9. #9
    Senior Member
    TheRigger is offline

    Posts
    641
    Your code or my code?

  10. #10
    Member
    savagesun is offline

    Posts
    72
    Mine haha

Page 1 of 4 123 ... LastLast

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
  •