Announcement

Collapse
No announcement yet.

Carpentry Solving

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Carpentry Solving

    The following has to do with programming. It's not really a general programming question, and it pertains to a specific YPP puzzle, so I stuck it here.

    I've been poking around with Carpentry for a while now, and I've come to the point where I need to write an algorithm to solve the puzzle. I know it sounds like I've done nothing, but there's more: I've read a single space in the carpentry puzzle (one area where you need to patch up) and determined what is a space that needs filling, and what is a space that needs filling and can have a piece placed on it successfully, for lack of a better name I refer to them as "corner" pieces. The "pieces" are divided into small squares that when put together form a carpentry piece, again for lack of a better name I call these "bits."
    Since I'm not sure I've explained it well enough here's a picture of the bot's debug visual:
    Click image for larger version

Name:	visualboard.png
Views:	1
Size:	16.8 KB
ID:	156457
    Blue denotes a "corner" bit and white is a bit that is not filled, and not a corner. A few of them you might notice aren't completely white although they should be. This is not the fault of the board reading but the way I visualize it (it's just colored squares on top of each other so they overlap causing the wrong color to show occasionally).

    Here's where the algorithm specific things start (I assume, I'm still rather new to algorithms for puzzle solving). I've read in the board successfully, and now I attempt to solve the board by iterating through each "bit." If the bit is a "corner" bit then I attempt to fit in a puzzle piece that is presently in the toolbox by checking the area of each piece and seeing if the spots are all unfilled, if they are I move on to another variation of the piece (flips/rotations) and if that fails again I move on to another piece before attempting to place pieces in another bit of the board. Currently I have only one piece (the fatter one that's really easy to work with as a human) that I've coded in but I can already see this growing into a tremendously slow process. Initially reading the single zone of the carp board takes around 2-4 seconds on my laptop, and an additional 0.5-1.5 seconds to re-check the board for any changes to it. I can only imagine what iterating through each bit and each piece's variation would do to performance. Ignoring performance however, I've found that this would easily lead to gaps in the board, so my second pass at the idea is to attempt to fit as many bits from a piece into the board's corner bits as possible, which I think might help but I've yet to attempt anything. I feel like I'm going about this all wrong, any input is appreciated. I'd really love a point in the right direction or a jumping off point (maybe some puzzle solving article you read somewhere?) for this. Thanks!
    Attached Files

    #2
    I barely understood any of that but if you want help understanding how your scored for Carp I can point you towards someone who can help you.

    Comment


      #3
      The carpentry guide on the YPPEDIA is quite in depth.

      I won't post a link but a simple google search will uncover it for you

      If you need any help feel free to poke me on Skype.

      Comment


        #4
        You say reading a single zone from the board takes 2-4 seconds on your laptop. That means the board reading algorithm is tremendously flawed. However, reading the board from screen and calculating a solution are two completely seperated processes and you need not focus on both at once.

        I've never taken the time to implement a carpentry bot myself, but I imagine I would try something like this:
        (if you don't understand my epic pseudo code, too bad )
        Code:
        // Board definitions
        let Tile be a boolean value representing
        whether or not the tile is filled.
        let CarpHole be any 8x8 matrix of Tile.
        let CarpBoard be CarpHole[4]
        
        // Toolbox/piece definitions
        let Piece be an 5x5 matrix of Tile, representing a puzzle piece
        let AvailablePieces be the list of all available flips and rotations of the pieces in toolbox, sorted by rarity of piece (low to high)
        
        // Functions
        bool Fit(CarpHole, Piece, Point) {
        	// Use some clever matrix math to see
        	// if Piece, fits at Point in CarpHole
        }
        
        PointList AvailableTiles(CarpHole) {
        	// Returns the list of corner tiles
        	// (marked blue on your images)
        	// The order of these points may affect
        	// the performance of bot, and various
        	// orders should be tested
        }
        
        class Result { CarpHole, Piece, Point }
        
        // Algorithm for placing next piece
        for each CarpHole in CarpBoard do
        	availableTiles = AvailableTiles(CarpHole)
        	for each Piece in AvailablePieces do
        		for each Point in availableTiles do
        			if(Fit(CarpHole, Piece, Point))
        				return Result(CarpHole,Piece,Point);
        }
        As for the board reading algorithm: Reading one and one pixel from the screen is generally a slow process. If that's what you're doing, don't. You're better off capturing the entire carpentry board in one operation and storing it in memory, and then access each required pixel from memory.

        Making bots is fun fun fun, and I wish you good luck and patience on your quest to become a bot developer (official or not!)

        Comment


          #5
          I lost my last long message so here's a watered down version:

          I'm basically doing everything in your pseudo code right now, but the outline helps. I don't use matrices right now, I use something resembling them (which are just arrays of x, y coordinates). I'm not sure if Java supports matrices natively, I'll check up on that. And I am having loads of fun so far .

          Edit: Is a 2D array considered a matrix? If so then I'm using matrices haha.

          I'll certainly try to access the pixel data from memory instead, I'll post back and let you know what the performance changes are! Love the suggestion.

          I've got another quick question: right now I continuously (every time the while loop fires) read in the board and update it. This is a bit of an issue because it takes maybe 0.5-1s to read in the area without attempting to update what the new corner pieces are. I'll try to read the data form memory like you said, but I'm just wondering if there is some better way to read in the data only when a change occurs. I don't think I can listen to any mouse click events outside of my own window, so that's not exactly an option..

          Thanks for the replies!

          - - - Updated - - -

          Originally posted by Scarecrow View Post
          The carpentry guide on the YPPEDIA is quite in depth.

          I took a look at that, it seems "squaring the hole" is the way to go.
          Last edited by savagesun; 10-01-2013, 08:16 PM.

          Comment


            #6
            Also, if you're developing something that you want to use for your Laptop only, and want maximum speed, try multithreading or keeping some of the code out of the main UI thread. If you need a return value, don't shove all of that into the UI thread, create a different class and call it to the main using Synch or Asynchronous calls. Chances are you already knew this, but you'd be surprised what BIG projects aren't multithreaded... For example, a game I used to like until I heard about its code and method naming etc, Minecraft isn't multithreaded, and is obviously very CPU intensive on a core. Just a suggestion

            *edit*

            Also, you could have that loop sleep until the event is called so that it isn't reading until it is needed. I may have misinterpreted this but from what I understand the problem you're having is the loop firing before it is called. Correct me if I'm wrong.
            Last edited by Run; 10-01-2013, 08:15 PM.
            Keep running,
            -Run

            Comment


              #7
              I do a lot of Minecraft programming so I know where you're coming from. The code is atrocious, particularly their multiplayer coding. But that's another thread.

              I just tried to read the pixel data from memory and it runs much faster! I'm loving it, it takes maybe a second to read the board and maybe a fourth of a second to update itself.

              I'm not sure where you got the loop firing before anything is called, but the problem is that I'm not sure if I should be reading in the board to check for updates every time the loop runs. It works much better now since the pixel reading change, but it does seem like doing it constantly is just poor planning. I thought about putting the thread to sleep for a bit, but that would just slow down the update times.

              Also thanks for the Thread suggestion. Are you suggesting I just separate the UI and the processing in threads? Right now since there's no UI or anything yet I haven't threaded anything, but I do plan to do so. If you're suggesting putting more than just the UI in one thread and the processing in another I'm all ears! I'm not great with threads. My last project ran a separate thinking thread to puzzle out the board so the UI wouldn't freeze up, but I could never seem to safely cancel the thread. Still I'll do more research so when the time comes to thread I'll know what I'm doing.
              Last edited by savagesun; 10-01-2013, 08:06 PM. Reason: Grammar!

              Comment


                #8
                Whatever works! And yeah, I misread, glad it works now. Good luck.
                Keep running,
                -Run

                Comment


                  #9
                  Solving algorithm
                  Yes, a matrix would be a 2D array. You would define them as <type>[][] (basically an array of an array of a type), like so:
                  Code:
                  boolean[][] CarpHole = new boolean[8][8]; // if my Java doesn't stink
                  This would be a most effective way of representing the carpentry hole.

                  I don't know how much optimizing you've done, but if you have a predefined width and height for every carp piece you can drastically lower the total amount of "does-this-piece-fit-here"-checks.

                  Consider this: Assume a carp hole has 8x8 non-filled tiles. For every available piece you have, you would have to check if a piece fits (8*8) * amount of available pieces. In a worst case scenario the amount of available pieces would be 48, 3 pieces with 4 rotations and 4 flips. This would require 3072 checks.

                  In comparison, assume the same except you have a width and height predefined for every piece. Now you know that a piece of width 3 can't possible fit in any position in the matrix with x greater than (8-3) = 5, so that you only need to check the x positions from 0 to 5. If the piece also has a height of 2, you only need to check y positions from 0 to 6. Assuming you have 48 pieces all with width and height of 2 and 3 or 3 and 2, the required amount of checks would now be (5*6)*48=1440 checks. That is 0.47x of the non-optimized algorithm's checks.

                  On smaller boards the difference would be even greater in terms of relationship. On a 7x7 board the non-optimized algorithm would use 2352 checks against the optimized algorithm's 960, being 0.41x of the non-optimized algorithm's checks.

                  I'm sure there are more ways to further reduce the number of required checks. Remember that you have the advantage of being able to store as much data as you want about the carp pieces and carp holes before you start the brute force algorithm.

                  Board reading
                  1 second is still a lot. For each of the four holes you need to test 8x8 pixels to see if the tile is empty (black) or not. You also don't need to check more than 5x5 pixels for every carpentry piece in the toolbox (not including possible bucket). That makes no more than 331 comparisons. If your bot uses ~3ms per pixel there's something very wrong somewhere. However I won't be able to help you much here as I never did work with screen reading in Java.

                  A way to require less screen reading is is to
                  1. Read Board
                  2. Read Toolbox
                  3. Calculate next move
                  4. Place piece in PP
                  5. Assume piece was placed in PP, and change the tiles in the carp board to filled
                  6. If one of the carpentry holes has been (assumedly) filled, go to step one else go to step two

                  This way is very cost effective and lets you build the board quickly, but you're risking that misplacement or failure to place pieces will mess up the board.

                  Threading (Structure is nice!)
                  As for threading, using a seperate thread for each hole would drastically lower the calculation time, but make sure you do it correctly to prevent terrible horrifying disastrous simultaneous memory write errors.

                  Comment


                    #10
                    I already represent pieces as 2D arrays so I'm half way there haha.

                    I think I'll opt for continuous reading of the board since that sounds really unfriendly. I found a good way to find whether the piece was actually placed or the user is just hovering over the board, so the update happens very quickly after the user has set the piece and it doesn't continue without them and accounts for mistakes that can't be undone. I had built a small bot before and it did what I think you're suggesting where it continues regardless of user input and it was really quite annoying to keep up with sometimes. It also didn't account for mistakes..

                    I test for something like 9x9 pieces initially in order to retrieve the corner bits, and then I remove any non essential ones. I also remove any non essential bits after iterating over the board again and finding the new corner bits, so the iterations get smaller ever time a piece is placed. A second perhaps is a bit of an exaggeration since almost as soon as I place the piece the board updates. It's still noticeable though, but its current state is fine for now.

                    Your check ideas are good, I had considered something similar but it wasn't as put together as your explanation haha. You've been a great help to me, thanks so much! I'll post back later with updates and questions if they arise.

                    P.S. your Java is spot on!

                    Comment


                      #11
                      Originally posted by Emaziz View Post
                      Solving algorithm
                      Threading (Structure is nice!)
                      As for threading, using a seperate thread for each hole would drastically lower the calculation time, but make sure you do it correctly to prevent terrible horrifying disastrous simultaneous memory write errors.

                      ^
                      Keep running,
                      -Run

                      Comment


                        #12
                        Originally posted by Run View Post
                        ^
                        Totally looked over that. Will do!

                        Edit: quoted the wrong thing, but it works. hehe

                        Comment


                          #13
                          As I understand it the thread has gotten kind of side tracked. Lol. I present an algo i would use to solve a puzzle, and it will do it by squaring, however it is not optimized at all.
                          1. search for c's. a c is the following:
                          ###
                          #
                          ########
                          astrics are board. these are the first to fill as the pieces required are rarest compared to use. next get the best rotation ie:

                          .....#
                          ####

                          this is pest fit piece

                          .....##
                          ###

                          this is worst fit because it builds another c which cuts down on the number of pieces that can be used to fill it.
                          i would do that by getting the most bits to touch corner bits.

                          2. I would determine which pieces will be corner pieces after the piece is placed and if that builds a very rare shape that is not in the toolbox then that placement is thrown out. ie
                          a good placement builds

                          ##
                          ###

                          a bad placement builds

                          #
                          #
                          ###

                          to reiterate, check pieces available against corner bits and determine which one builds the most common piece shape, or assists in it by filling 2 long c holes. hope that helps! let me know if you need anything cleared up!
                          Last edited by Luriebot; 10-02-2013, 03:16 AM. Reason: Using periods as spaces cus it wont post right otherwise

                          Comment


                            #14
                            I've tried checking if a bit is a corner piece, it doesn't do quite as well as I had hoped. I do have an answer to it though so hopefully I'll see some slight increase in ability afterwards. Currently I only have one piece programmed into the bot (the fatter squarish piece). The bot seems to have a basic understanding of what to do, although I see it missing some chances to get more corner bits than the move it chooses. It can attain able

                            Also I like the idea you're pitching but I'm not sure how I would manage to shape areas that resemble the more common pieces when there is more empty space left over than a single piece could fill. Otherwise I suppose I could check through the left over space after simulating what the board would be after placing a piece during the corner check loop.

                            Click image for larger version

Name:	visualboard.jpg
Views:	1
Size:	5.1 KB
ID:	155291

                            Comment


                              #15
                              Have you considered using pre-computed tables

                              Comment

                              Working...
                              X