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 (21)
avatar
< Meka Chicken >
Posts: 551 - 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: 1701 - 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 (141)
avatar
(My name's Krunch) < King Solomon >
Posts: 3629 - 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: 427 - 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 (106)
avatar
(Aaron ) < King Solomon >
Posts: 3304 - 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: 85
--------------------------------------------------
Next Game: #86 - Kung-Fu Heroes
Latest Post - 5/22/18 - #76 - The Rocketeer
--------------------------------------------------
Website | NA Thread | YouTube | Twitter | Twitch

May 17 at 11:21:11 AM
rlh (50)
avatar
( Potatoe!) < Kraid Killer >
Posts: 2383 - 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 (21)
avatar
< Meka Chicken >
Posts: 551 - 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.