Skip navigation
Welcome, Guest! Please Login or Join

Loading...

Programmatically brute-forcing an obscure Game Boy game Lazlos' Leap

May 16 at 5:55:20 PM
Splain (23)
avatar
< Meka Chicken >
Posts: 749 - Joined: 06/15/2016
Arizona
Profile
I've been playing a game called Lazlos' Leap for Game Boy. It's a simple marble-solitaire game, where you jump marbles to try and end up with one marble in the center. There are 100 puzzles in the game, and each has a "par," meaning you can (if you want) try to complete the puzzle in that minimum number of "moves." (If you jump over a marble, then jump another one with that same marble, that counts as one move. Kind of like checkers. You can clear a lot of marbles in one move if you set it up right.) If you use a whole bunch of moves to solve a puzzle, it doesn't seem to matter. You can still access any puzzle you want, just like you can on a fresh game.

It's not a remarkable game, but it does have a battery save feature and it records your scores for each puzzle, telling you that you either did "GOOD!" or "...OK!" per puzzle, depending on whether or not you got par. I started to like these puzzles, so last year I decided to beat the game, and I managed to solve all of them without any guides or help. But I didn't get par on all of them. Absolutely nothing happens when you solve all 100 puzzles.

Is there an ending or CONGLATURATION screen if you get par on every puzzle?  I tried Googling, but there doesn't seem to be any record of anyone getting par on every puzzle. Apparently I lack the mental acuity to figure out how to "more efficiently" solve many of these puzzles myself, so I went ahead and coded a Lazlos' Leap Solver to do it for me.

I started by being as lazy as possible, and I made an Excel spreadsheet with a VBA backend, because that would make it really easy to input each puzzle's starting position. I literally wrote a program that randomly makes moves and then checks if the puzzle is solved. And it actually worked pretty well for puzzles up to about 30, when it started coming back with nothing, even after millions of attempts. Ok, ok, I need to write a proper program that recursively tries every possible combination of moves until a solution is found. Well, even then, some of these runs take a very long time to return with a solution. But VBA isn't known for its speed and efficiency. And I'm not known for my good coding practices, especially when it comes to recursion. I might have to face the music again and re-write the whole thing in a proper language. Does anyone have any Tree Traversal tips?

But this has turned into a complicated programming project, all to see if there's an ending screen in a Game Boy game! I'm aware that I could dissect the ROM and hunt for assets, but I'd rather do all this with my original grey cartridge.

Just thought I'd report my progress here. That is all.

May 16 at 8:33:09 PM
bronzeshield (44)
avatar
(P. ) < Lolo Lord >
Posts: 1745 - Joined: 04/12/2009
New York
Profile
Ha, I thought about doing something similar for Qbillion, where I've never been able to get past the last two levels, but I don't have anything like the required programming skills to pull it off. Still, this is awesome!

May 17 at 5:36:22 AM
SUBSCRIBER
Krunch (142)
avatar
(My name's Krunch) < King Solomon >
Posts: 3730 - Joined: 11/08/2010
Alberta
Profile
I like this thread. Good luck on your programming quest

-------------------------
eBay - http://www.ebay.ca/sch/i.html?_nk...

#YKNOTK


Edited: 05/17/2018 at 05:36 AM by Krunch

May 17 at 7:49:37 AM
Cheesemeister (90)
avatar
< Eggplant Wizard >
Posts: 436 - Joined: 09/27/2014
Japan
Profile
This puzzle is also known as peg solitaire: https://en.m.wikipedia.org/wiki/P...

Try searching for peg solitaire solvers to see if there's a program that meets your needs.

May 17 at 10:52:44 AM
SUBSCRIBER
arnpoly (108)
avatar
(Aaron ) < King Solomon >
Posts: 3398 - Joined: 07/26/2013
Illinois
Profile
I'm probably wrong, but it sounds like you need some variant of the breadth-first search algorithm, which would, in theory, reveal the shortest solution first. I'm not at all sure how to do that.

I think we are cut of the same cloth. I remember getting stuck on the Knight's Tour puzzle in one of the Layton games and I wrote a C++ program to do a depth-first search and solved it that way.  

-------------------------

Take On The NES Library!
NES Games Finished: 100
--------------------------------------------------
Next Game: #101 - F-117A Stealth Fighter
Latest Post - 9/18/18 - #95 - Bomberman
--------------------------------------------------
Website | NA Thread | YouTube | Twitter | Twitch

May 17 at 11:21:11 AM
rlh (57)
avatar
( Potatoe!) < Ridley Wrangler >
Posts: 2718 - Joined: 09/06/2016
North Carolina
Profile
Alternatively, you could use your own implementation of a rather naive form of genetic algorithm. Basically, take, say, 20 random approaches to solving the puzzle, executing random moves. Take the top-10 best results, modify the various solutions at random then once again, take the top 10 results and modify.

Keep doing this until you find winners.

I'm actually cringing a little to hear you did this in VBA... nothing against you but as a pro dev whose been writing software in some form since 1996, working with VBA (and only when I've had too) has been some of the most difficult projects I've ever had. It's an easy tool to write in... but a pain for another dev to dissect. Lol.

Of course, cheesmeister and arnpoly have good suggestions too. You can look up either specific algorithms OR search for solution algos for this specific game. That said, genetic algorithms are part of AI development, and this is a way you can write code that solves problems "on it's own". It doesn't follow rules, it simply changes it's methods by randomly modifying parameters. It's not a silver bullet in solving difficult problems but it's kind of crazy how it can work in certain use cases and this sounds like a good one.

-------------------------
Please check out my -->WANTED<-- list of games.
[NES/SNES/GB/GG/GEN/N64/PS1/PS2]
I prefer trades but I buy too.
Switch ID: SW-8142-3998-4206

May 17 at 12:23:52 PM
Splain (23)
avatar
< Meka Chicken >
Posts: 749 - Joined: 06/15/2016
Arizona
Profile
QBillion would be a neat one to try next!

I looked up some Peg Solitaire solvers online, I'd need to make sure they have a mechanism for chaining the jumps together and counting them as one move. I'll look deeper into it if I hit a wall.

This is way more fun than coding for money!
 
Originally posted by: rlh

I'm actually cringing a little to hear you did this in VBA...

Lol, I get it. Just so you don't lose too much respect for me, understand that I've done lots of professional work in lots of different languages. But you're totally right, I definitely shouldn't have gone with VBA for this project. I thought it would be worth it for the ease of visualizing and entering the puzzles, but... I should have gone with a real language. Recursion in VBA is a special kind of wonky. And the compile-time errors are misleading 90% of the time.

Welp, I added a global flag to the loop, so that if a solution is found, it won't keep trying every possible solution. Now it jumps out as soon as it solves it. (I had put that in from the start, but it hadn't been working right.) That has made a lot of them MUCH faster, and I'm about 2/3 of the way through the game. It's tedious to enter each puzzle, then solve it on the Game Boy, and repeat. But I'll get there. This is important.

May 25 at 4:11:19 PM
Splain (23)
avatar
< Meka Chicken >
Posts: 749 - Joined: 06/15/2016
Arizona
Profile
Quick update just to vent. I've got solutions to every puzzle I need, except for #98 and #99. I found an optimized solution for #100 online, (which is the classic all-marbles puzzle) thank goodness. I've been in this position for a week. I've let this thing run for entire days at a time with no solutions found for either. I went into the code and reversed the logic, so that it starts from the bottom and works backward, in case the solution is toward the "end" of the logical sequence. No dice. Right now I'm trying to find solutions that use one too many moves, so I can try to consolidate them by hand. If/when that fails, I'll break each puzzle down by doing the first move myself, and making a list of all the puzzles that result from doing each possible first move, and searching for solutions to those puzzles. Then maybe I can keep track of the dead ends better? I don't know.

QBillion is going to be very tricky, but it will definitely be next. And not in VBA.


Edited: 05/25/2018 at 04:12 PM by Splain

May 25 at 8:03:47 PM
rlh (57)
avatar
( Potatoe!) < Ridley Wrangler >
Posts: 2718 - Joined: 09/06/2016
North Carolina
Profile
You know, I've had a long hard week at work and I could use something fun. Is there a way you could post the details of these levels and the general rules? I think I might enjoy trying to take a couple of ours and see if I can code a solver. You certainly don't have to, but I figured I'd ask.

-------------------------
Please check out my -->WANTED<-- list of games.
[NES/SNES/GB/GG/GEN/N64/PS1/PS2]
I prefer trades but I buy too.
Switch ID: SW-8142-3998-4206

May 29 at 2:04:40 PM
Splain (23)
avatar
< Meka Chicken >
Posts: 749 - Joined: 06/15/2016
Arizona
Profile
Ah, sorry I didn't see this sooner. Just in case you're still interested...

Each level is a different configuration of marbles on the same board. https://en.wikipedia.org/wiki/Peg... (It uses the "English" board, not the "European" board.)

A valid move is one where a marble "jumps" over an adjacent marble and lands in an empty space. The "jumped" marble disappears. (not the "jumping" marble.) There are no diagonal jumps. A puzzle is "solved" when there is only one marble remaining, and that marble is located in the very center of the board.

The catch is the "par" mechanic. In Lazlos' Leap, each puzzle is presented with a par value. Consecutive jumps are counted as one single move, meaning if a marble is able to jump (e.g. North) over a marble, then immediately jump (e.g. West) over another marble, this counts as one move. Some of these chains can be many jumps long, and some optimal solutions consist of many single-jump moves to set up one final (or almost-final) many-jump move. So any solver needs to be able to either find a solution in the fewest number of moves possible, or it needs to take a target number of moves as an input.

Let me know if any of that doesn't make sense, and if you're still interested, I'll give you some sample puzzles for testing, and the 2 I haven't solved yet. You could also fire up Lazlos' Leap in an emulator for all the puzzles you could ever want.