🚀 go-pugleaf

Passero wrote:

> Voor school moeten we voor het vak AI een schuifraam maken die de pc
> oplost. We moeten 3 methoden implementeren waaronder 1 blinde en 2
> heuristieke. 
> 
> Bij mijn blinde methode krijg ik soms volgende fout:
> java.lang.OutOfMemoryError
> Het rare is dat hij niet uit mijn programma springt en dat ik die
> error ook niet kan opvangen. Het is duidelijk dat er geen geheugen
> meer vrij is en dat hij daarom moet stoppen. Kan ik dat toch opvangen
> zodat ik de gebruiker een bericht kan geven of kan ik het geheugen
> aanpassen zodat hij toch verder kan rekenen? Het is mij ook opgevallen
> dat hij soms die error geeft ergens tussen stap 257000 en 258000 en
> dan een andere keer tussen 256000 en 257000. Hoe komt dat en wat zou
> ik eraan kunnen doen? 

Je algoritme herzien. Wat is je blinde methode?

-- 
John Bokma
                 Voorbeeldscripts in Perl: http://johnbokma.com/perl/
Ervaren Perl / Java programmeur beschikbaar:  http://castleamber.com/
Tevreden opdrachtgevers:     http://castleamber.com/testimonials.html

"John Bokma" <postmaster@castleamber.com> schreef in bericht
news:Xns95978C98DB168castleamber@130.133.1.4...
> Passero wrote:
>
> > Voor school moeten we voor het vak AI een schuifraam maken die de pc
> > oplost. We moeten 3 methoden implementeren waaronder 1 blinde en 2
> > heuristieke.
> >
> > Bij mijn blinde methode krijg ik soms volgende fout:
> > java.lang.OutOfMemoryError
> > Het rare is dat hij niet uit mijn programma springt en dat ik die
> > error ook niet kan opvangen. Het is duidelijk dat er geen geheugen
> > meer vrij is en dat hij daarom moet stoppen. Kan ik dat toch opvangen
> > zodat ik de gebruiker een bericht kan geven of kan ik het geheugen
> > aanpassen zodat hij toch verder kan rekenen? Het is mij ook opgevallen
> > dat hij soms die error geeft ergens tussen stap 257000 en 258000 en
> > dan een andere keer tussen 256000 en 257000. Hoe komt dat en wat zou
> > ik eraan kunnen doen?
>
> Je algoritme herzien. Wat is je blinde methode?

Diepte-eerst methode. Dus hij gaat random een beweging genereren,
controleren of hij die mag doen, stel dat het lege blokje uiterst links
staat en hij wil links bewegen dan mag hij dat niet. En dat doen tot wanneer
je de juiste oplossing hebt. Als je op het einde zit keer je 1 knoop terug.
Het is letterlijk het algoritme uit de cursus dus dat klopt wel degelijk ;)

>
> --
> John Bokma
>                  Voorbeeldscripts in Perl: http://johnbokma.com/perl/
> Ervaren Perl / Java programmeur beschikbaar:  http://castleamber.com/
> Tevreden opdrachtgevers:     http://castleamber.com/testimonials.html

In article <0owid.11639$qg2.603190@phobos.telenet-ops.be>, Passero wrote:

> Diepte-eerst methode. Dus hij gaat random een beweging genereren,
> controleren of hij die mag doen, stel dat het lege blokje uiterst links
> staat en hij wil links bewegen dan mag hij dat niet. En dat doen tot wanneer
> je de juiste oplossing hebt. Als je op het einde zit keer je 1 knoop terug.
> Het is letterlijk het algoritme uit de cursus dus dat klopt wel degelijk ;)

Misschien vind je de
http://java.sun.com/j2se/1.4.2/docs/api/java/beans/VetoableChangeListener.html wel interessant.

Toepassing in sokoban: http://home.mysth.be/~timvw/programming/java/sokoban.zip

-- 
Met vriendelijke groeten,
Tim Van Wassenhove <http://www.timvw.info>

On Thu, 04 Nov 2004 20:35:08 GMT, the lifeform known as "Passero"
<bla@bla.be> wrote:

>> > Voor school moeten we voor het vak AI een schuifraam maken die de pc
>> > oplost. We moeten 3 methoden implementeren waaronder 1 blinde en 2
>> > heuristieke.
>> >
>> > Bij mijn blinde methode krijg ik soms volgende fout:
>> > java.lang.OutOfMemoryError
...

>> Je algoritme herzien. Wat is je blinde methode?

>Diepte-eerst methode. Dus hij gaat random een beweging genereren,
>controleren of hij die mag doen, stel dat het lege blokje uiterst links
>staat en hij wil links bewegen dan mag hij dat niet. En dat doen tot wanneer
>je de juiste oplossing hebt. Als je op het einde zit keer je 1 knoop terug.
>Het is letterlijk het algoritme uit de cursus dus dat klopt wel degelijk ;)

Hmmm, ik ken jouw algorithme natuurlijk niet maar een diepte-eerst
methode daarvan kun je toch wel stellen dat zoiets binnen een vrijwel
vaste hoeveelheid memory moet kunnen plaats vinden. Is dat zo ? Als
dat niet zo is probeer dan eens een afschatting te maken hoeveel
objecten je maximaal aanwezig hebt in je systeem.

Mijn eerste instinct is overigens dat je bij het backtracken een
aantal referenties naar objecten blijft hebben, dus die objecten
blijven bestaan en worden niet door de garbage collector opgeruimd. 

Ik hoop dat je hier wat aan hebt.

-- 
Niels.

Drs. ir. Niels Basjes - http://niels.basjes.nl/ - VCV 20000302
mailto:`echo 'Niels Basjes'|awk '{print$1"@"$2".nl"}'`
Hacker: One who enjoys the intellectual challenge of 
creatively overcoming or circumventing limitations.

Passero wrote:
> "John Bokma" <postmaster@castleamber.com> schreef in bericht
> news:Xns95978C98DB168castleamber@130.133.1.4...
> 
>>Passero wrote:
>>
>>>Voor school moeten we voor het vak AI een schuifraam maken die de pc
>>>oplost. We moeten 3 methoden implementeren waaronder 1 blinde en 2
>>>heuristieke.
>>>
>>>Bij mijn blinde methode krijg ik soms volgende fout:
>>>java.lang.OutOfMemoryError
>>>Het rare is dat hij niet uit mijn programma springt en dat ik die
>>>error ook niet kan opvangen. Het is duidelijk dat er geen geheugen
>>>meer vrij is en dat hij daarom moet stoppen. Kan ik dat toch opvangen
>>>zodat ik de gebruiker een bericht kan geven of kan ik het geheugen
>>>aanpassen zodat hij toch verder kan rekenen? Het is mij ook opgevallen
>>>dat hij soms die error geeft ergens tussen stap 257000 en 258000 en
>>>dan een andere keer tussen 256000 en 257000. Hoe komt dat en wat zou
>>>ik eraan kunnen doen?
>>
>>Je algoritme herzien. Wat is je blinde methode?
> 
> 
> Diepte-eerst methode. Dus hij gaat random een beweging genereren,
> controleren of hij die mag doen, stel dat het lege blokje uiterst links
> staat en hij wil links bewegen dan mag hij dat niet. En dat doen tot wanneer
> je de juiste oplossing hebt. Als je op het einde zit keer je 1 knoop terug.
> Het is letterlijk het algoritme uit de cursus dus dat klopt wel degelijk ;)

Een zoekdiepte van 256000 moves? Dan werkt depth-first echt niet.

Waarschijnlijk blijft je algorithme een schuifje heen en weer schuiven.
Nadat hij dat zo'n miljoen keer heeft gedaan, zul je vast wel door je
geheugen heen zijn. En zo niet: dan schuift hij gewoon nog een miljoen
keer op en neer. De kans dat je toevallig de goede oplossing gokt is erg
klein. Depth-first werkt gewoon niet zo goed met onbeperkte zoekruimtes.

Probeer eens iterative deepening. Dat houdt in dat je een limiet aan
de diepte stelt. Als je dan binnen maximale diepte n niets vindt,
dan ga je het opnieuw proberen met (n+1) als maximale diepte.
Dit is in het algemeen een goede tussenvorm tussen geheugengebruik
(dat is veel minder dan breadth-first) en snelheid (die mislukte
diepten kosten niet veel extra tijd vergeleken met de tijd die de
juiste diepte kost en je zoekt nooit te diep).

Een extra optimalisatie is om nooit je vorige zet ongedaan te maken.

Met recursie is dit allemaal erg kort op te schrijven. 20-50 regels
moeten genoeg kunnen zijn voor de kern van je algorithme.

Sjoerd

PS: Heb ik de truk die je zelf had moeten uitvinden verklapt?

On Thu, 04 Nov 2004 19:09:55 +0000, Passero wrote:

> Bij mijn blinde methode krijg ik soms volgende fout:
> java.lang.OutOfMemoryError

Even afgezien van het commentaar op je algoritme kan het natuurlijk zijn
dat je "net" niet genoeg geheugen hebt. De Java VM zet default een maximum
geheugengebruik van 128mb, wat je evt. zou kunnen ophogen als je meer in
je systeem hebt zitten ( voor een 512mb machine is bv: java -Xmx400m ...
interessant). Zie ook de fine manual voor andere tuning tips...

Klaasjan

Sjoerd A. Schreuder wrote:

> Probeer eens iterative deepening. Dat houdt in dat je een limiet aan
> de diepte stelt. Als je dan binnen maximale diepte n niets vindt,
> dan ga je het opnieuw proberen met (n+1) als maximale diepte.
> Dit is in het algemeen een goede tussenvorm tussen geheugengebruik
> (dat is veel minder dan breadth-first) en snelheid (die mislukte
> diepten kosten niet veel extra tijd vergeleken met de tijd die de
> juiste diepte kost en je zoekt nooit te diep).
> 
> Een extra optimalisatie is om nooit je vorige zet ongedaan te maken.

Me even aansluiten bij de poster: ik zou nooit depth-first gebruiken bij
schuifpuzzels. Je gaat echt in de problemen komen als je alle vorige
situaties bijhoudt om loops te vermijden (ik vermoed dat je dat doet als je
een deftige depth-first gebruikt?).

Soit tis een leuke AI oefening als je ze goed doet :-)
-- 
"May the source be with you"

Klaasjan Brand wrote:
> On Thu, 04 Nov 2004 19:09:55 +0000, Passero wrote:
> 
> 
>>Bij mijn blinde methode krijg ik soms volgende fout:
>>java.lang.OutOfMemoryError
> 
> 
> Even afgezien van het commentaar op je algoritme kan het natuurlijk zijn
> dat je "net" niet genoeg geheugen hebt. De Java VM zet default een maximum
> geheugengebruik van 128mb, wat je evt. zou kunnen ophogen als je meer in
> je systeem hebt zitten ( voor een 512mb machine is bv: java -Xmx400m ...
> interessant). Zie ook de fine manual voor andere tuning tips...
> 
> Klaasjan
> 
Dat is niet helemaal waar:
-Xmxn
     Specify the maximum size, in bytes, of the memory allocation pool. 
This value must a multiple of 1024 greater than 2MB. Append the letter k 
or K to indicate kilobytes, or m or M to indicate megabytes. The default 
value is 64MB. Examples:

        -Xmx83886080
        -Xmx81920k
        -Xmx80m

Dit gaat op voor JDK/JRE 1.4.2
Je kan natuurlijk de max-heap wel vergroten, maar ik denk, net als 
andere posters, dat het algoritme niet goed gebruikt wordt.

Vincent