Maze Gen Mac OS
A maze generator written in javascript, and is able to be printed or played through a web browser. The maze is fully customizable with many options. Mazesmith 0.7.0 released Added ability to shift the design in the style toolkit. Maze generation algorithms are automated methods for the creation of mazes. This maze generated by modified version of Prim's algorithm, below. Set the MAZE-FILE chooser to the maze file you want to use. Adjust the slider parameters (see below), or use the default settings. Press the SETUP button. Press the GO button to begin the simulation 4B. Press the STEP button to go through one generation at a time. This add-in will enable you to create a 3D model of a random 3D maze in a very simple and efficient way. The random 3D maze is automatically generated from user-specified columns and rows. There is also an option to change the width of the maze 'path' and add a fillet to the path edges.
GeneticProgramming Maze Rules
(ByForrestSondahl, 2005)
The applet requires Java 1.4.1 or higher. It willnot run on Windows 95 or Mac OS 8 or 9. Mac users must have OS X10.2.6 or higher and use a browser that supports Java 1.4. (Safariworks, IE does not. Mac OS X comes with Safari. Open Safari and setit as your default web browser under Safari/Preferences/General.) Onother operating systems, you may obtain the latest Java plugin fromSun'sJava site.
Created with NetLogo* View/download model file:GeneticProgramming Maze Rules.nlogo
View Analysis for thisModel * Back to Forrest's Final ProjectMain Page.
WHAT IS IT?
This model demonstrates the use of genetic programming toevolvemovement rules that agents can use to solve mazes. Genetic programming(sometimes abbreviated GP) is a technique in Computer Science that usesthe concepts of natural selection, genetics, and evolution to generatecomputer programs to solve a particular problem. In this case, theproblem is navigating mazes. (This model is similar to GeneticProgramming Maze Marchers, but instead of evolving the steps an agentshould take to solve a particular maze, this model evolve movementrules that are applicable to solving mazes in general.)
WHAT IS GENETIC PROGRAMMING?
In the world of biology, species evolve by means of natural selectionand the interactions of DNA. Genetic Programming takes these ideas, andapplies them in the field of computer science. Given a problem, thegoal is to evolve a computer program that can solve the problem. Itstarts with a population of randomly generated computer programs. (Theingredients of these randomly generated computer programs are chosenbased on the problem that is to be solved.) Each program is run, andits performance is measured by a 'fitness function', which reflects howgood each program is at solving the problem. Then programs are chosenfrom the population to 'reproduce'. The programs are chosen randomly,but with a weighting mechanism that makes it more likely that the more'fit' programs are chosen. (Analogously in the biological world,defective organisms can get lucky and pass on their DNA, but the morefit organisms have a better chance of doing so.) There are three formsof reproduction that occur:- Cloning (the child program is identical to its parent)
- Mutation (the child program has some of its code replaced byrandomlygenerated code)
- Crossover (two parent programs are chosen from the population,andthe child program consists of a mixture of code from the two parents)
http://www.geneticprogramming.com/Tutorial/index.html
http://www.genetic-programming.com/gpanimatedtutorial.html
HOW IT WORKS
In many NetLogo models, agents are given predetermined rules, and thenthe emergent behaviors that form through the interactions of theseagents are studied. In contrast, this model is starts with a desiredbehavior (solving a maze) and works on trying to discover the agent'srules, through use of Genetic Programming, as described in the sectionabove.In this model, the maze-solving programs are represented by'codeturtles'. Codeturtles each have a piece of NetLogo code assignedto them, and it's their job to perform it. Codeturtles will then bechosen, based on their fitness, to reproduce and create anothergeneration of codeturtles.
The ingredients from which the code is built are fairly simple:
Four commands:
- maze-turn-right(think 'rt 90')
- maze-turn-left(think 'lt 90')
- ifelse controlstructure
- ' ' blank command (does nothing)
- maze-wall-ahead? (Isthere a wall in front of me?)
- maze-wall-right? (Isthere a wall to my right?)
- maze-wall-left? (Isthere a wall to my left?)
maze-turn-right ifelse maze-wall-ahead? [ maze-turn-left ] [ maze-turn-right ifelse maze-wall-right? [ maze-turn-left maze-turn-left ] [ maze-turn-left ] maze-turn-right ] |
(The internal representation of the program is actually a treestructure, since this has been often found to produce better resultsfor genetic programming. The code trees are then compiled into the formyou see above, to be run as NetLogo code.)
You may be wondering about the blank command. Since it does nothing,what purpose could it possibly have in the program ingredients?Basically, it provides a placeholder -- for instance, you can have an'if' without an 'else', simply by having the else block be made up ofblank commands.
You may also be wondering how it is the codeturtles move, since theyhave no 'forward' command. This is because each codeturtle's program isjust the rules to decide where to go in each given step. Codeturtleshave a lifespan of 480 steps (enough to get them to the goal in mostmazes, if they have a decent movement strategy). During each step, thecodeturtles execute their code, and then move forward one square in thedirection they are pointing (unless a wall blocks their path).
The fitness function, which measures each codeturtles progress, is asimple one: 'What is the geometric distance to the goal square?' Thelower this number is, the more fit a turtle is. It is easy, of course,to create mazes where this is clearly not the case (e.g. load'maze4.txt') but for many mazes, this distance measurement serves as adecent heuristic. A better (in fact, perfect) fitness function wouldcount the minimum number of open path squares that the codeturtle wouldhave to cross to reach the goal. However, if we had such a fitnessfunction, then we would already have some algorithm for computing thesolution to our maze! And if we had such an algorithm, then why wouldwe be trying to evolve codeturtles to solve it? Using the solution tofind the solution seems like a cheap trick that turns this modelentirely into a toy problem. Also, fitness is computed for eachcodeturtle after each step it takes -- not just at the end of the run.Since fitness is calculated so often, the efficiency of computingfitness is important, and this is another advantage for geometricdistance fitness, as opposed to true walking distance to goal fitness.
HOW TO USE IT
1. Set the MAZE-FILE chooser to the maze file you want to use.2. Adjust the slider parameters (see below), or use the defaultsettings.
3. Press the SETUP button.
4A. Press the GO button to begin the simulation
4B. Press the STEP button to go through one generation at a time.
5. Watch the View, to see the codeturtles attempt to solve the mazewith their given code DNA.
6. Watch the FITNESS plot, to see how the population is doing.
7. If a codeturtle successfully gets to the end of the maze, then thesimulation will stop. To stop it earlier, press the GO button again.(It may take some time for the current generation to finish.)
8. Press the REPLAY-STEP button to watch the last generation runthrough the maze again.
9. Press the SHOW-BEST button to see the code for the current best(most fit) codeturtle.
Parameters:
MAZE-FILE: The maze file to be loaded.
POPULATION-SIZE: The number of codeturtles in each generation
INITIAL-CODE-MAX-DEPTH: The maximum depth of randomly generated codetrees, that codeturtles start with. (It also affects the size ofmutations that occur). In general, a larger number generally meanslonger programs are created.
BRANCH-CHANCE: Controls the amount of branching in the generation ofrandom code trees. Again, a larger number generally means longerprograms are created.
CLONE-CHANCE, MUTATE-CHANCE, CROSSOVER-CHANCE: These three sliderscontrol the relative probability of each genetic operation occurring,with respect to the others.
(Examples: If the sliders are set to 10, 10, 10, then there is a 1/3chance of each genetic operation happening. If the sliders are set to10, 10, 20, then there is a 25% chance of cloning, 25% chance ofmutation, and 50% chance of crossover. If the sum of these threesliders is 100, then each slider represents the percent chance of thatgenetic operation being chosen to create an offspring for the newgeneration.)
FIX-RANDOM-SEED?: If true, then RANDOMSEED is used to start theprocess. This allows a particular run to be reproduced exactly, andthus examined more closely, (provided that the parameters are thesame). If false, then RANDOMSEED is not used.
RANDOMSEED: This is the number used to seed the random numbergenerator, if FIX-RANDOM-SEED? is true, to allow for reproducibleresults.
THINGS TO NOTICE
For humans, some mazes are easier to solve than others. Likewise, somemazes are easier for this model to solve than others. Which of the fiveincluded mazes are easiest for this model, and which are hardest? Whymight maze0.txt be easier than maze3.txt? Think about the fitnessfunction, as well as other factors.The average and best fitness values shown in the plot sometimes go upand sometimes go down. Why do you think this is? Does geneticprogramming always find a solution?
Usually the best fitness value makes a sudden jump down to the solutionat the end. Why is this? Why aren't there codeturtles that get within 2or 3 squares of the goal, but don't actually make it all the way?
Occasionally, a codeturtle that was in a very early generation, maybeeven Generation 0, finds the solution. What do you think this saysabout the difficulty of the problem? Do you think that geneticprogramming is a good choice for solving this problem?
You may notice that during a generation, after a certain number ofsteps, many of the codeturtles have turned to sad faces, while theturtles that are still moving will speed up. There is a reason forthis. Because the genetic programming process runs quite slowly,especially with large populations, some heuristics are applied in thismodel to stop codeturtles that are looking hopeless. For instance, if acodeturtle doesn't move or change its heading in a given step, then itis stuck, (because it will do the same thing next turn) and we do notneed to keep running it. Weeding out bad turtles helps speed up themodel.
The colors of the codeturtles have some meaning. They are initiallyrandomly colored, but:
* When a codeturtle results from cloning, it has the same color as itsparent.
* When a codeturtle results from crossover, it has a color averagingits two parents.
* When a codeturtle is mutated, it has a random color.
THINGS TO TRY
Try changing the POPULATION-SIZE slider. With a very small population,each generation moves by much more quickly, but it generally takes moregenerations to find a solution. Also, small populations mean increasedinbreeding. What affect does this have on the process? How low can thepopulation go such that the process still works?Try changing the INITIAL-CODE-MAX-DEPTH and the BRANCH-CHANCE. Notethat if INITIAL-CODE-MAX-DEPTH <= 3, then IFELSE statements can'tform, meaning that the codeturtles are doomed. Note also that if thecodeturtles' code gets long, then the codeturtles run very slowly.
Crossover is usually the driving force of genetic programming. Trymoving the genetic operations sliders around, and run the model. Whathappens if you only cloning, and no mutation or crossover? Onlymutation? Only crossover?
EXTENDING THE MODEL
There is a model called Genetic Programming Maze Maker, which can beused to create maze files. Create several interesting maze files, andadd them to the MAZE-FILE chooser. What types of mazes does the modeldo well with? What types of mazes are hard for the model to handle?What types are impossible?Sometimes over the generations, the code trees expand and get verylarge. (In crossover, a new codeturtle can be made up of the largerpart of its two parents, and basically double in size. In mutation, asingle node can be replaced by a medium-sized subtree.) If one of theselarge-tree codeturtles is highly fit, the largeness can quickly spreadto most of the population. This can result in some incredibly slowperformance for the model when this happens. Thus, a nice extension tothe GP Library would be to have a 'maximum-tree-size' parameter, andwhen trees that are too large get created, they should be trimmed offsomehow.
Right now, these turtles have no memory of where they've been. They canonly decide which direction to move based on which squares around themhave adjacent walls. This really only gives them one solution they canfind -- the well known 'right hand rule' (or the 'left hand rule', ofcourse). (It is worth noting that this rule only works on a certainclass of mazes.) In any case, it would be interesting to give thecodeturtles more information to base their decisions on. Consider tworeporters called 'maze-already-traveled-ahead?' and'maze-already-traveled-here' which report true if the turtle hasalready traveled on the square they see in front of them, or the squarethey are currently on. Would these additions be useful? Would it bepossible to give the turtles primitives such that they could learn todo a depth first search? Or come up with your own codeturtleprimitives, and see whether they help or hurt the efficiency of findinga solution.
NETLOGO FEATURES
The NetLogo feature on which this whole model stands is the ability totake a string of text, and run it as NetLogo code. This is achievedthrough the 'run' primitive.Extensive use of recursion and lists has been employed, especially todeal with the tree structures which codeturtles use to store code.Since trees are not natively supported in NetLogo, they have beenimplemented as nested lists.
It is also interesting to note that this model is built from two parts.The first part is the 'GP Library for NetLogo', which consists of aframework of procedures that are useful for any model that is usinggenetic programming. The second part consists of procedures that arespecific to this model. Since NetLogo doesn't support any formalconcept of code libraries, this separation is largely achieved throughpositioning of the code, naming conventions, and comments.
RELATED MODELS
'Genetic Programming Maze Marchers' - The brother model to this one.'Genetic Programming Maze Maker' - A tool for loading/saving maze filesthis model uses.
'Genetic Programming Demo' - A simple model demonstrating how to usethe GP Library.
Start here if you want to build your own genetic programmingmodel.
There are several models out there that work with Genetic Algorithms,which are closely related to Genetic Programming. See:
'Echo' under Biology
'ARS-Genetics' and 'BinaryGA' by Thomas Hills, in the User CommunityModels.
CREDITS AND REFERENCES
Maze Gen Mac Os Download
Author: Forrest SondahlDate: November 28, 2005
Project Web Page: http://cs.northwestern.edu/~fjs750/netlogo/final/
Part of the Genetic Programming Library for NetLogo project, whichconsists of a library of code that makes it easier to write geneticprogramming models, as well as several sample models that demonstratethe use of the library.
Created for the course CS 460 Multi-Agent Modeling, at NorthwesternUniversity.
Back to Forrest's Final Project Page.
It’s been a long time since we’ve seen Apple roll out a revamped and next-gen MacBook Pro. In fact, the entirety of Apple’s Mac lineup has been in dire need of a meaningful refresh for an embarrassingly long time.
Maze Gen Mac Os 11
Thankfully, we won’t have to endure Apple’s stale and stagnant Mac lineup for much longer. Earlier this week, Apple sent out invitations for a special media event set to take place on October 27. Apple, in typical fashion, hasn’t told us what’s on the agenda but it’s no secret that the event will focus primarily on new Macs. It’s also no secret that the star of the show will be a completely retooled MacBook Pro with a number of snazzy new bells and whistles.
DON’T MISS: Google’s new Pixel XL is no match for iPhone 7 Plus in one key area
If you’ve been in the market for a new Mac, you certainly won’t want to miss next week’s event. And to get you primed for what will hopefully be some compelling new products, we’ve put together a list highlighting everything we know about Apple’s upcoming MacBook Pro.
First things first, the killer feature on Apple’s 2016 MacBook Pro will reportedly be the addition of an OLED display panel located towards the top of the keyboard. Rather than expanding the existing keyboard, it’s believed that the OLED panel will be located where the function keys typically reside.
This past May, photos purporting to be from Apple’s new MacBook Pro leaked online and, surprise surprise, note the empty space where the function row keys usually are.
As to the inherent advantages of such a design, an OLED display on the keyboard would allow the keys to dynamically change to more appropriately fit whatever app you happen to be using.
As an illustrative example, designer Martin Hajek earlier this year produced a number of tantalizing concept images which showcase how the feature might operate.
The images below, for example, show what the OLED display might look like with Spotify running.
These are just concepts, remember, but the possibilities of an OLED display offering up app-specific shortcuts is certainly compelling. All the more intriguing are reports that users will have the ability to customize app-specific shortcuts to their liking. Late this August, the French site Consomacunearthed code from Apple’s Pages app which strongly hints that the shortcuts on the OLED display — which Apple internally calls the Dynamic Function Row — can be tweaked by users. Imagine, for example, selecting a block of text and with the tap of a button instantly formatting it to your liking without having to go sifting through a maze of menus.
We would imagine that Apple will have more appealing examples to show us come next Thursday.
Another intriguing detail about Apple’s forthcoming MacBook Pro models is that they will have Touch ID integrated into the keyboard itself. This should be particularly useful given that users running Mac OS Sierra can now take advantage of Apple Pay on the web.
As for other details, Apple’s new MacBook Pro will reportedly be a little bit thinner than its predecessor, will feature a larger trackpad, and will include a keyboard based on the butterfly mechanism Apple first introduced us to with the 12-inch MacBook. If this particular rumor pans out, expect the keys on the new MacBook Pro to have a slightly larger surface area.
Apple touts the benefits of its butterfly mechanism thusly:
Traditional keyboards use a scissor mechanism, which tends to wobble around the edges. This creates a lack of precision when you strike anywhere except the center of the key. We needed to reduce key wobbling for a keyboard this thin; otherwise, striking a key off-center could result in the keycap hitting bottom before a keystroke registers. So we designed a unique butterfly mechanism, which is wider than the scissor mechanism and has a single assembly made from a stiffer material — allowing for a more stable, responsive key that takes up less vertical space. This innovative design improves stability, uniformity, and control — no matter where you press on the key.
Maze Gen Mac Os Catalina
Additionally, don’t be surprised if the trackpad on the new MacBook Pro is completely stationary a’la Apple’s current 12-inch MacBook.
As far as ports are concerned, consumers can likely kiss the beloved MagSafe adapter and traditional USB ports goodbye and instead say hello to new USB-C and Thuderbolt 3 ports. While Apple may very well just include one USB-C port, one would imagine that Apple would outfit its Pro notebook with more than just USB-C port.
With respect to internals, we can naturally expect to see some great speed and graphics improvements. Specifically, the new MacBook Pros will reportedly house Intel Skylake processors which should make the machines much more power efficient, a welcome perk on a Pro device that will likely be used as a workhorse by many. On the graphics front, don’t be surprised to see a GPU which takes advantage of AMD’s Polaris architecture.
Size wise, Apple will reportedly release two MacBook Pro models, one in a 13-inch form factor and another in a 15-inch form factor.
While there was some concern that Apple might do away with the headphone jack on its new MacBook Pros, the leaked chasis below should help alleviate any concerns in that regard.
Last and not least, expect to see Apple’s revamped MacBook Pro hit store shelves in 2016, presumably before the busy holiday shopping season kicks off. One rumor