[Programming Contest 5] Tuintopia

[Daos]

Memorice schreef op zaterdag 27 april 2013 @ 06:41:
P.S. Ik heb zelf geen tijd om aan deze contest mee te doen

De hoeveelheid code valt mee. Ik heb na 3 dagen een oplossing van ongeveer 700 regels c# ingeleverd (waarvan 100 niet meer aangeroepen wordt: mijn output.ini teller). Voor het parsen van speelveld.ini en kaarten.ini gebruikt ik een ini-parser gevonden op internet: https://code.google.com/p/ini-parser/

ik dacht ik gooi maar een paar ideeen in de groep, aangezien ik het wel een interessant topic vind, hopelijk is dat ok.

Breng de concurrentie nou niet op ideeen Ik had mijn oplossing gisteren al ingeleverd; ik hoop dat de jury dat ziet en dat ik nog kans maak op de originaliteitsprijs

[Memorice]

De hoeveelheid code valt mee. Ik heb na 3 dagen een oplossing van ongeveer 700 regels c# ingeleverd

Het aantal regels code zegt niet zoveel over hoe lang het kost deze te schrijven. Verder ben ik het wel met je eens dat het niet heel veel tijd hoeft te kosten, maar ik zou willen stellen dat mijn prioriteiten elders liggen.

Breng de concurrentie nou niet op iedeeen

Ik denk eigenlijk dat mijn ideeen vrij triviaal zijn en kan me moeilijk voorstellen dat men hier niet al aan heeft gedacht, vandaar dat ik me in de discussie meng. Ik verwacht namelijk niet dat iemand anders mijn ideeen gaat uitvoeren omdat ik daar zelf geen zin/tijd voor heb.

[Creepy]

Hmja, ik denk dat je toch wel wat tips geeft die in elk geval wat tijd qua denkwerk gaat schelen voor sommigen.
En Daos: ik heb hem gezien hoor

[Bolukan]

Als jullie het hebben over bruteforcen, is dat echt lomp maar met super slimme en efficiente code, of prunen jullie heel veel weg en maakt dat het mogelijk?

[Anoniem: 303530]

Beide. Op het dataset van pedorus genereer ik een 3x3 node per 10 klok cycles per thread, worst-case. En dat is zonder de pruning die best efficiënt werkt. Ik heb er veel moeite in gestoken met intel Vtune om de code zelf zo efficiënt mogelijk te maken. Er zitten echt stukjes code tussen waar miljoenen malen per seconde overheen wordt geloopt. Dan wordt het algoritme opeens 2x zo snel als je een virtual function call vervangt door een inline function of je datastructuren wat meer cache-friendly maakt...

Domweg alle mogelijkheden langs lopen zonder pruning of andere slimmigheden moet je inderdaad niet doen. Dan ben je -op mijn CPU- 138000000 jaar bezig met het dataset van pedorus. Doch ben ik van mening dat bruteforce een betere term is dan A* of DFS of BFS voor mijn algoritme.

Hoe de boel met echt grote velden ( zoals 6x6 ) om gaat moet ik overigens nog zien. Erg veel vertrouwen heb ik er niet in.

Zijn er trouwens al mensen met een werkende verificatie? Mijn algoritme geeft andere scores terug dan mijn verificatiemethode, maar ik heb geen idee welke correct is en welke niet...

[ Voor 9% gewijzigd door Anoniem: 303530 op 27-04-2013 22:00 ]

[CodeCaster]

Ik neem trouwens aan dat de in- en output van de kaarten onbeperkt zijn? Wanneer je, om 1 kaart met output X,8 kaarten legt met input X, je 8 punten krijgt en vice versa?

En voor wat betreft zon en wind, betekent een "mismatch", waarvoor je een punt aftrek krijgt, dat bijvoorbeeld een kaart die zon levert onder een kaart ligt die schaduw vraagt?

[raptorix]

Ik hoop in ieder geval de jury ook 1 set doet welke in principe niet te bruteforcen is, bijvoorbeeld een 100*100 set, sets onder de 10x10 lijken me toch wel relatief makkelijk te bruteforcen.

[raptorix]

Overigens moet ik herschrijven, in mijn structuur had in een class gemaakt met een dictonary object, waarbij ik coordinaten als identifier gebruik, echter in c# blijkt dat niet te kunnen.

[Anoniem: 303530]

Dan ga je elke keer dat je een kaart wil plaatsen de coordinaten hashen, dat is echt extreem inefficiënt. Gebruik gewoon arrays.

Een hash table kan wel zin hebben, maar dan alleen als het hashen en een potentiele cache mis sneller zijn dan het berekenen van die informatie.

[Daos]

raptorix schreef op zondag 28 april 2013 @ 11:12:
Overigens moet ik herschrijven, in mijn structuur had in een class gemaakt met een dictonary object, waarbij ik coordinaten als identifier gebruik, echter in c# blijkt dat niet te kunnen.

Je kan je eigen comparer maken die bijvoorbeeld twee Point objecten vergelijkt. Een 2d array is ook mogelijk.

Voorbeeldje (al wil ms dat je liever de EqualityComparer<T> gebruikt):

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TestDictionary
{
    class Point
    {
        private int x, y;

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public bool Equals(Point p)
        {
            return x == p.x && y == p.y;
        }

        public override int GetHashCode()
        {
            return (x << 16) ^ y;
        }
    }

    class MyComparer : IEqualityComparer<Point>
    {
        public bool Equals(Point x, Point y)
        {
            return x.Equals(y);
        }

        public int GetHashCode(Point obj)
        {
            return obj.GetHashCode();
        }
    }

    class MyObject
    {
        private string name;

        public MyObject(string name)
        {
            this.name = name;
        }

        public override string ToString()
        {
            return "a MyObject with name: \"" + name + "\"";
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // with dictionary
            // create
            Dictionary<Point, MyObject> my_dictionary = 
                        new Dictionary<Point, MyObject>(new MyComparer());

            // add
            my_dictionary.Add(new Point(1, 2), new MyObject("object at 1, 2"));

            // retreive
            MyObject my_dict_object;
            my_dictionary.TryGetValue(new Point(1, 2), out my_dict_object);
            Console.WriteLine(my_dict_object);


            // with 2d-array
            // create
            MyObject[,] my_array = new MyObject[3, 3];

            // fill
            my_array[2, 1] = new MyObject("object at 2, 1");

            // retreive
            MyObject my_array_object = my_array[2, 1];
            Console.WriteLine(my_array_object);

            Console.ReadKey();
        }
    }
}

[ Voor 11% gewijzigd door Daos op 28-04-2013 11:49 . Reden: Het belangrijkste paste niet in het scherm; verder volgorde anders ]

[raptorix]

Daos schreef op zondag 28 april 2013 @ 11:48:
[...]


Je kan je eigen comparer maken die bijvoorbeeld twee Point objecten vergelijkt. Een 2d array is ook mogelijk.

Voorbeeldje (al wil ms dat je liever de EqualityComparer<T> gebruikt):

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TestDictionary
{
    class Point
    {
        private int x, y;

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public bool Equals(Point p)
        {
            return x == p.x && y == p.y;
        }

        public override int GetHashCode()
        {
            return (x << 16) ^ y;
        }
    }

    class MyComparer : IEqualityComparer<Point>
    {
        public bool Equals(Point x, Point y)
        {
            return x.Equals(y);
        }

        public int GetHashCode(Point obj)
        {
            return obj.GetHashCode();
        }
    }

    class MyObject
    {
        private string name;

        public MyObject(string name)
        {
            this.name = name;
        }

        public override string ToString()
        {
            return "a MyObject with name: \"" + name + "\"";
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // with dictionary
            // create
            Dictionary<Point, MyObject> my_dictionary = 
                        new Dictionary<Point, MyObject>(new MyComparer());

            // add
            my_dictionary.Add(new Point(1, 2), new MyObject("object at 1, 2"));

            // retreive
            MyObject my_dict_object;
            my_dictionary.TryGetValue(new Point(1, 2), out my_dict_object);
            Console.WriteLine(my_dict_object);


            // with 2d-array
            // create
            MyObject[,] my_array = new MyObject[3, 3];

            // fill
            my_array[2, 1] = new MyObject("object at 2, 1");

            // retreive
            MyObject my_array_object = my_array[2, 1];
            Console.WriteLine(my_array_object);

            Console.ReadKey();
        }
    }
}

thx, ik had vergelijkbare code gevonden op StackOverflow, vanmiddag maar eens kijken.

[raptorix]

Anoniem: 303530 schreef op zondag 28 april 2013 @ 11:30:
Dan ga je elke keer dat je een kaart wil plaatsen de coordinaten hashen, dat is echt extreem inefficiënt. Gebruik gewoon arrays.

Een hash table kan wel zin hebben, maar dan alleen als het hashen en een potentiele cache mis sneller zijn dan het berekenen van die informatie.

Mee eens, ik ga het nog eens overdenken en kijken wat nog meer geschikt is, ik had het zo op gezet omdat je op die manier natuurlijk wel heel makkelijk Linq queries kunt doen.

[Daos]

CodeCaster schreef op zaterdag 27 april 2013 @ 23:11:
Ik neem trouwens aan dat de in- en output van de kaarten onbeperkt zijn? Wanneer je, om 1 kaart met output X,8 kaarten legt met input X, je 8 punten krijgt en vice versa?

En voor wat betreft zon en wind, betekent een "mismatch", waarvoor je een punt aftrek krijgt, dat bijvoorbeeld een kaart die zon levert onder een kaart ligt die schaduw vraagt?

Voordat deze reactie ondersneeuwt:
Wat ik er van begrijp is dat je dan 8 punten krijgt en niet vice versa (16). Elke verbinding telt maar 1 keer. Zelf tel ik alles dubbel en deel later door twee.

Let wel: Ik ben niet van de organisatie. Aan mijn reactie kunnen geen rechten worden ontleed.

[CodeCaster]

Met vice versa bedoelde ik uiteraard het omdraaien van in/output (1 input, 8 outputs), niet het dubbel tellen van de punten.

[ Voor 12% gewijzigd door CodeCaster op 28-04-2013 13:19 ]

[Daos]

Een verbinding heeft een begin- en eindpunt en telt als 1 punt. Dus als je een kaart met input x en output y hebt en daaromheen 8 kaarten met input y en output x, dan is het hele veld samen 16 punten waard.

Er was hier iemand die telde alleen de binnenkomende verbindingen. Zelf tel ik zowel de binnenkomende en vertrekkende verbindingen en deel ik op het eind door 2.

[Corniel]

Anoniem: 303530 schreef op zaterdag 27 april 2013 @ 21:59:

Zijn er trouwens al mensen met een werkende verificatie? (..)

Dat is waar ik mee begonnen ben.

Nog wat laatste optimalisaties en inzenden maar

Ik weet het niet hoor maar iemand die denk dat je 10x10 kan bruteforcen? Dat is potentieel 98! mogelijkheden. Zuivere brute-force houdt mijnsinzien binnen deze oplossing op bij 11 à 13 vrije-kaarten. In alle andere gevallen kan je maar een fractie van de mogelijke borden bekijken.

[Anoniem: 303530]

Ik denk dat 6x4 nog wel te bruteforcen is, maar alles daarboven zeker niet meer. Ik heb momenteel al moeite met het bruteforcen van 6x3 met de zon en wind erbij...

Met het dataset uit de topicstart, met alles aantal=1.

[ Voor 15% gewijzigd door Anoniem: 303530 op 28-04-2013 17:35 ]

[Corniel]

Anoniem: 303530 schreef op zondag 28 april 2013 @ 17:35:
Ik denk dat 6x4 nog wel te bruteforcen is, maar alles daarboven zeker niet meer. Ik heb momenteel al moeite met het bruteforcen van 6x3 met de zon en wind erbij...

Met het dataset uit de topicstart, met alles aantal=1.

Bij 6x4 heb je 22 verschillende velden waar je een kaart voor moet bepalen. Dit kunnen allemaal verschillende kaarten zijn. Alleen het berekenen van de 22! verschillende permutaties gaat niet lukken in 5 minuten (of het moet extreem veel sneller kunnen dan mij bekend). Door de wind en de zon zijn er geen symmetrieën mogelijk.

Het berekenen van wind en zon verdubbeld de rekentijd van een de score van een veld. Elke kaart erbij maakt het aantal mogelijkheden maakt de rekentijd vele malen meer groter.

[Anoniem: 303530]

Mijn algoritme is ongeveer lineair met de hoeveelheid kaarten. (gemeten met het dataset van pedorus tussen de 28 en 31 kaarten), maar ik kan dat persoonlijk niet verklaren. Vermoedelijk ligt dat aan de testdata.

Corniel schreef op zondag 28 april 2013 @ 17:51:
Het berekenen van wind en zon verdubbeld de rekentijd van een de score van een veld. Elke kaart erbij maakt het aantal mogelijkheden maakt de rekentijd vele malen meer groter.

Als ik het voor elkaar krijg het berekenen van de wind/zon voor elkaar te krijgen met 'slechts' 2x zoveel rekenkracht als zonder, dan zou ik heel erg blij zijn. Ik zit nu tegen een factor 10-20 aan te hikken met uitschieters naar 100.

[Corniel]

Anoniem: 303530 schreef op zondag 28 april 2013 @ 18:03:
Mijn algoritme is ongeveer lineair met de hoeveelheid kaarten. (gemeten met het dataset van pedorus tussen de 28 en 31 kaarten), maar ik kan dat persoonlijk niet verklaren. Vermoedelijk ligt dat aan de testdata.

Dat heb je geen burte-force-algoritme. Dat geeft verder niet natuurlijk.

[Anoniem: 303530]

Dat hangt er vanaf hoe je bruteforce defineert. Hashcat met een dictionary erbij is ook bruteforce, maar de gemiddelde tijdscomplexiteit van het vinden van een correct password is een stuk beter dan n^lengte.

Edit: kijk, hier. There's my problem. Sinds het toevoegen van de zon en wind is de effectiviteit van mijn pruning algoritme gedaald van 99.9% naar 3.6%

Edit: ik ga stoppen met de bruteforce variant. Ondanks dat het op het dataset van pedorus uitstekend werkt, krijg ik het simpelweg niet voor elkaar het met de zon en de wind efficiënt te implementeren.
Met goede optimalisaties kan ik misschien de pruning opkrikken van 3.6% naar de 99.9% van het dataset van pedorus. Met nog betere optimalisaties zal ik er misschien in slagen het algoritme als geheel 2 a 5x zo snel te maken. Maar dan is het alsnog niet vooruit te branden met meer dan 31 kaarten. En dan heb ik het huis nog niet eens geïmplementeerd.

Tijd voor iets compleet anders, dus.

[ Voor 69% gewijzigd door Anoniem: 303530 op 28-04-2013 23:28 ]

[raptorix]

Onder bruteforce versta ik het systematisch afgaan van mogelijkheden zonder dat je daarbij op een slimme manier de kaarten bekijkt.

[Corniel]

@raptorix: Dan zijn wij het eens.

@creepy: You've got mail.

Zo, vanmorgen nog net op tijd een pijnlijke bug gefixt. Concreet zag ik dat in sommige testsets, het huis niet meer uit twee velden naast elkaar bestond. Foutje was gelukkig snel gevonden.

Alle publieke methoden van commentaar voorzien, unittests meegezonden (97% coverage). Je wint er de eerste prijs niet mee, maar je kan het maar gedaan hebben.

Ik ben redelijk tevreden over het resultaat. Ben ook benieuwd of ik me een beetje kan meten in deze contest.

[raptorix]

Klinkt goed Corniel, welke taal gebruik je? Ik vind zelf ook dat schoonheid boven snelheid hoort te gaan, hoewel ik nog wel hoop dat ik tijd kan vinden om het slimmer te maken, een goede opzet maakt dat natuurlijk wel makkelijker ipv keihard over sets loopen

[Corniel]

@Raptorix: C# (.NET 4.0). Mijn aanpak was als volgt:

Eerst zorgen dat alle regels geïmplementeerd werden (Heb de regels omtrent het huis later nog iets moeten aanpassen, ik gebruikte twee buren niet als wind/beschutting) en unittests die zorgden dat dit werd gevalideerd.

Daarna een random-solver gebouwd, om te testen of het vinden van oplossingen e.d. ook leidde tot het schrijven van output, en om te kijken waar het berekenen van de score beter (=sneller) kon.

Daarna verschillende zoekstrategieën geprobeerd en verder getweakt. Soweiso kan echt blind loopen niet. Zoals gezegd: simpelweg alle combo's proberen loopt met 13 vrij te vullen velden (buiten de twee huiskaarten om) al spaak.

[raptorix]

Corniel schreef op maandag 29 april 2013 @ 14:44:
@Raptorix: C# (.NET 4.0). Mijn aanpak was als volgt:

Eerst zorgen dat alle regels geïmplementeerd werden (Heb de regels omtrent het huis later nog iets moeten aanpassen, ik gebruikte twee buren niet als wind/beschutting) en unittests die zorgden dat dit werd gevalideerd.

Daarna een random-solver gebouwd, om te testen of het vinden van oplossingen e.d. ook leidde tot het schrijven van output, en om te kijken waar het berekenen van de score beter (=sneller) kon.

Daarna verschillende zoekstrategieën geprobeerd en verder getweakt. Soweiso kan echt blind loopen niet. Zoals gezegd: simpelweg alle combo's proberen loopt met 13 vrij te vullen velden (buiten de twee huiskaarten om) al spaak.

Ah nice, hier ook c#, het maken van unittests is zeker voor dit soort projecten natuurlijk super, scheelt waarschijnlijk veel frustratie

Ik heb ongeveer zelfde strategie, eerst random, dan tweaken, maar moet eerst nog wat dingen omschrijven.

[Daos]

Mijn code is standaard zo goed als foutloos

Ook ik heb eerst een puntenteller gemaakt. Ik kreeg in de twee gevallen dezelfde waarde als wat Corniel had gepost dus ik dacht het zit wel goed (ik tel 34 bij de output.ini uit de startpost, maar niemand heeft dat nog bevestigd)

[Memorice]

raptorix schreef op maandag 29 april 2013 @ 13:52:
Klinkt goed Corniel, welke taal gebruik je? Ik vind zelf ook dat schoonheid boven snelheid hoort te gaan, hoewel ik nog wel hoop dat ik tijd kan vinden om het slimmer te maken, een goede opzet maakt dat natuurlijk wel makkelijker ipv keihard over sets loopen

Ik vind absoluut niet dat schoonheid ten koste mag gaan van snelheid. Verder wil ik ook wel het nut van unittests voor een klein project zoals dit, waar je waarschijnlijk nooit weer iets mee doet, in twijfel trekken. Idem voor code coverage, leuke statistiek maar meer ook niet (afhankelijk van hoe je het meet).

[Corniel]

@Memorice: Ook projecten als deze schrijf is zelf test-driven. Code coverage is geen doel op zich, maar heeft me geholpen code op te sporen die ik niet meer gebruikte. Verder is zijn performance (snelheid)metingen ook relatief makkelijk herhaalbaar uit te voeren door ze in een unittest op te schrijven.

Maar het is een kwestie van smaak, en iemand die dat niet fijn vindt ontwikkelen moet het vooral niet doen.

[Daos]

Ik heb 22 functies met in totaal 46 if-statements waarvan 9 met een else en 29 for/do/while-loops. Als ik zou willen unit-testen kom ik over de honderd test-cases.

In plaats daarvan heb ik zorgvuldig gewerkt en alleen een paar system-tests gedaan.

[ Voor 5% gewijzigd door Daos op 30-04-2013 11:35 . Reden: loops vergeten ]

[Memorice]

Daos schreef op maandag 29 april 2013 @ 17:56:
Mijn code is standaard zo goed als foutloos

Ook ik heb eerst een puntenteller gemaakt. Ik kreeg in de twee gevallen dezelfde waarde als wat Corniel had gepost dus ik dacht het zit wel goed (ik tel 34 bij de output.ini uit de startpost, maar niemand heeft dat nog bevestigd)

Ik zag dat de deadline pas in juni is, dus wellicht dat ik nog wat tijd kan vinden om iets in te zenden. Om te beginnen heb ik net maar even een simpele validator geschreven. Mijn validator komt ook op 34 punten uit, je andere scores in dit topic (61, 96 en 98) kan ik ook bevestigen.

Wat ik me afvraag is hoe efficient mijn validator is, want een uur geleden toen ik er aan begon dacht ik het best wel handig te doen, maar na al die regeltjes met zon/wind en het huis is de code eigenlijk best lomp geworden. Nu heb ik op zich geen moeite met lompe code, mits het maar snel genoeg is (snelheid > schoonheid , al hoewel ik moet toegeven dat ik de code in java geschreven heb ). Om de score van een 6 x 3 bord te berekenen kost 1/600000 seconde (op een core i7). Verder kan het rond de 10 miljoen borden per seconde doorrekenen. Dit is uiteraard exclusief het inlezen van de .ini bestanden. Ik vraag me af hoeveel tijd dit bij jullie kost?

[Anoniem: 303530]

raptorix schreef op maandag 29 april 2013 @ 09:35:
Onder bruteforce versta ik het systematisch afgaan van mogelijkheden zonder dat je daarbij op een slimme manier de kaarten bekijkt.

Maar volgens die definitie zijn BFS en DFS ook 'bruteforce. Sterker nog, het 'bruteforcen' van een password door alle mogelijkheden af te gaan beginnend bij 00000 en daarna 00001 volgt exact hetzelfde patroon als DFS.

[Sjaaky]

Anoniem: 303530 schreef op woensdag 01 mei 2013 @ 00:15:
Maar volgens die definitie zijn BFS en DFS ook 'bruteforce. Sterker nog, het 'bruteforcen' van een password door alle mogelijkheden af te gaan beginnend bij 00000 en daarna 00001 volgt exact hetzelfde patroon als DFS.

Klopt. Een simpele DFS of BFS loopt alle mogelijkheden af en is bruteforce. Door het toevoegen van pruning, dus het slim verkleinen van de te doorzoeken oplossingsruimte, is het geen brute-force meer.

[Soultaker]

Je kunt natuurlijk twisten over de vraag of een zoek-algoritme mét pruning niet net zo goed brute force is, al is het wat slimmer dan zonder pruning.

[Daos]

De halve tuin van 3 bij 6 is waarschijnlijk wel volledig door te rekenen door van links naar rechts bij elke mogelijke waarde voor een kolom het beste veld tot dan te berekenen. Je heb dan aantal kaarten tot de derde speelvelden die je combineert met de kolom (ook aantal kaarten tot de derde) en je houdt aantal kaarten tot de derde speelvelden over (de beste voor elke waarde van de kolom). Volgende iteraties doe je hetzelfde met dezelfde aantallen.

Bij een hele tuin van 5 bij 6 wordt het het aantal kaarten tot de vijfde. Het combineren gaat dan met complexiteit van het aantal kaarten tot de tiende. Dat is waarschijnlijk niet meer te doen (in vijf minuten).

[Anoniem: 303530]

Mijn algoritme werkt door zo snel mogelijk 3x3 velden te genereren. Het (6x3) veld wordt opgedeeld in een linker en rechterhelft. Eerst worden alle mogelijke linkerhelften gegenereerd. Daarna genereert hij voor elke linkerhelft alle rechterhelften boven een bepaalde treshold ( uit de 31 - 9 = 22 overgebleven kaarten ). Die helften worden daarna gecombineerd.

De 3x3 velden worden op een zuivere bruteforce manier gegenereerd. Ik ga niet zeggen hoe dat precies werkt, maar met 10 klok cycles per kaart werkt het aardig snel... FYI: een branch miss op mijn architectuur is 14 cycles. Bij elke unieke set kaarten houd hij in een hash table wat data bij.

Er bestaan triviale algoritmes -ik heb er 3- om de uitkomst van de 3x3 blokken te voorspellen met een redelijk succespercentage. Verder zit er wat simpele wiskunde achter om er A) voor te zorgen dat ik de zeker weten de optimale score vind en B) om te voorkomen dat je 10.000 3x3 velden met 10.000 andere gaat combineren. Het combineren werkt namelijk met O( n² ). En dan ga je met deze aantallen zeer rap door je tijd heen..

Er zijn 3 redenen waarom dit niet meer werkt met de regels van tuintopia:
• Er bestaat geen efficiënt algoritme om een 3x3 node te genereren met de zon en wind regels. Zoals gezegd doe ik er elke 10 klok cycles een op het dataset van pedorus, reken met de zon en wind erbij op een factor 10 extra. Best-case. Gemiddeld is het waarschijnlijk 200x trager.
• met het toevoegen van de tuintopia regels is de pruning in effectiviteit van 99.9% naar 3.6% gedaald.
• door de zon en de wind is de spreiding van scores binnen een 3x3 node veel groter. Concreet betekent dat dat er bijna niets te prunen valt. Zelfs met een heuristic welke exact gelijk is aan de score.

En dan zit je nog met het probleem hoe je in hemelsnaam dat huis implementeert. En wat dacht je dan van velden als 4x6. De oplettende lezer zal opmerken dat je van 4x2 nodes kan genereren. Alleen het combineren van die nodes werkt zo traag dat ik betwijfel of het efficiënter werkt dan native bruteforce. Ik voorspel alvast dat het niet vooruit te branden is..


Waarom ik dit vertel? Als je mijn algoritme op basis van deze post weet te implementeren en het ook nog eens voor elkaar krijgt de bovenstaande problemen op te lossen, dan verdien je het om te winnen. . Ik heb overigens al een ander algoritme bedacht.

[ Voor 5% gewijzigd door Anoniem: 303530 op 01-05-2013 20:23 ]

[Corniel]

En hoe ga je dat oplossen voor een bord van zeg 53 x 67? Ik ga niet zeggen hoe ik het aanpak, maar mijn algoritme doet het zowel bij 2x2 als iets in de ordegrote 127x200. Merk op dat symetrie-voordelen volledig wegvallen zon/schaduw en wind/beschutting.

Ik denk dat je op de verkeerde weg zit. En over het huis, volgens mij is de oplossing vrij triviaal bij de meeste representaties van het speelveld. Zeker nu precies duidelijk zijn welke buren van het huis bij welke subcategorie horen.

[Creepy]

Corniel: heb je mijn e-mail gezien? Zo niet, mail mij even opnieuw maar dan deze keer met attachment

[Anoniem: 303530]

Corniel schreef op woensdag 01 mei 2013 @ 20:52:
En hoe ga je dat oplossen voor een bord van zeg 53 x 67?

En over het huis, volgens mij is de oplossing vrij triviaal bij de meeste representaties van het speelveld.

Dat zeg ik net. Ik ben erachter dat het niet praktisch is, en heb iets anders bedacht

[Corniel]

Anoniem: 303530 schreef op woensdag 01 mei 2013 @ 21:20:
Dat zeg ik net. Ik ben erachter dat het niet praktisch is, en heb iets anders bedacht

Verstandig. Maar het was niet voor niets dat ik direct welwillend was om hele grote testsets te genereren.

@creepy: It's a classic. Mailtje niet gezien, maar wel in de herkansing.

[Daos]

Ik ben er van uitgegaan dat een hele tuin (5 bij 6) het maximum is.

[Corniel]

@Daos: Wat gebeurt er als je een grotere tuin hebt? Zoals bijvoorbeeld in een van mijn testsets?

[Anoniem: 303530]

Mijn nieuwe algoritme werkt ook theoretisch met grotere tuinen, maar in de praktijk waarschijnlijk niet. Omdat de score (unsigned char) wrapt of omdat een ander datatype te klein is.

Daarnaast is het best mogelijk dat-ie met een veld van 5k bij 5x zo lang bezig is met het berekenen van de heuristic dat-ie niet eens 1 node kan uitklappen. Sowieso heb ik bij een dergelijk veld al meer geheugen nodig dan er in mijn bak zit alleen al voor de score tables.

Kortom: voldoende issues die schaling boven de pak-m-beet 20 bij 20 verhinderen

[Daos]

Corniel schreef op donderdag 02 mei 2013 @ 10:29:
@Daos: Wat gebeurt er als je een grotere tuin hebt? Zoals bijvoorbeeld in een van mijn testsets?

Bij die van 10 x 10 stop ik waarschijnlijk te vroeg. Bij de grootste velden duurt het langer dan vijf minuten.

005x004_-001
blijft hangen (krijg veld niet gevuld)

005x004_+001
blijft ook hangen (krijg veld weer niet gevuld door huis volledig buiten veld)

005x004_+003

code:

Score:136
[k005][k003][k002][k003][k006]
[k005][k003][k002][k002][k006]
[huis][huis][k001][k001][k001]
[k004][k008][k004][k007][k008]

005x004_+029 (weer huis buiten het veld)

code:

Score:174
[k003][k003][k003][k003][k005]
[k002][k002][k002][k002][k005]
[k001][k001][k001][k001][k001]
[huis][k007][k007][k007][k005]

010x010_+000

code:

Score:728
[k007][k013][k005][k006][k001][k001][k004][k006][k004][k007]
[k010][k013][k005][k014][k015][k015][k015][k011][k003][k007]
[k010][k013][k005][k014][k012][k012][k012][k010][k013][k005]
[k007][k006][k001][k016][k018][k018][k018][k002][k013][k006]
[k004][k003][k014][k016][k012][k010][k010][k010][k003][k005]
[k011][k008][k001][k018][k012][k017][k017][k017][k006][k014]
[k004][k015][huis][huis][k015][k015][k015][k010][k003][k005]
[k012][k011][k011][k008][k008][k001][k001][k001][k006][k014]
[k004][k012][k004][k015][k015][k015][k009][k009][k009][k005]
[k007][k011][k011][k001][k001][k001][k001][k009][k009][k007]

017x013_+020

code:

Score:1757
[k004][k014][k021][k021][k029][k008][k029][k026][k009][k030][k030][k009][k009][k009][k026][k014][k014]
[k021][k021][k020][k020][k017][k028][k007][k018][k030][k030][k030][k030][k018][k028][k007][k004][k021]
[k021][k020][k020][k020][k029][k008][k012][k029][k030][k030][k028][k028][k007][k029][k009][k009][k009]
[k021][k021][k020][k020][k017][k025][k025][k010][k010][k028][k007][k007][k007][k028][k010][k010][k010]
[k004][k014][k020][k020][k016][k031][k016][k006][k029][k029][k007][k023][k008][k019][k029][k028][k017]
[k021][k021][k025][k025][k017][k031][k018][k028][k028][k015][k015][k004][huis][huis][k017][k008][k008]
[k019][k024][k012][k012][k016][k031][k007][k007][k007][k013][k011][k011][k023][k008][k029][k031][k031]
[k001][k001][k025][k025][k017][k018][k023][k018][k023][k005][k015][k015][k005][k005][k015][k015][k018]
[k024][k024][k023][k008][k012][k018][k027][k003][k013][k013][k013][k013][k003][k003][k016][k009][k009]
[k024][k001][k017][k025][k027][k025][k017][k014][k015][k015][k015][k002][k002][k002][k002][k010][k010]
[k024][k024][k023][k008][k012][k008][k004][k004][k004][k011][k011][k003][k002][k002][k001][k001][k005]
[k021][k005][k016][k025][k012][k018][k023][k008][k015][k015][k015][k015][k022][k022][k016][k016][k016]
[k021][k005][k016][k006][k012][k018][k031][k009][k009][k009][k009][k022][k022][k022][k031][k006][k006]

061x043_+172
geen score binnen 5 minuten

105x184_+000
geen score binnen 5 minuten

905x784_+097
niet getest

[Corniel]

@Daos: je gebruikt nog de oude test-sets zo te zien. Ik heb een geüpdatet versie waarin geen kaarten voorkomen die een resource zowel vragen als leveren. Dat levert minder kaarten van het zelfde soort naast elkaar (en lagere scores).

Verder lijkt er hier en daar iets niet helemaal goed te gaan. #oeps

[ Voor 13% gewijzigd door Corniel op 02-05-2013 13:26 ]

[Daos]

Kwak je eigen resultaten dan ook even neer, dan kunnen we ze vergelijken.

Met je nieuwe testset:

004x003_+003

code:

Score:26
[huis][huis][k001][k002]
[k005][k001][k002][k002]
[k003][k005][k002][k006]

005x003_+002

code:

Score:71
[k002][k002][k004][k007][k008]
[k005][k006][k005][k007][k008]
[huis][huis][k004][k007][k001]

005x004_-001
blijft hangen (krijg veld niet gevuld)

005x004_+001

code:

Score:62
[k002][k004][k006][k006][k006]
[k002][k004][k001][k007][k003]
[k002][k005][k001][k008][k008]
[k005][huis][huis][k008][k003]

005x004_+003

code:

Score:68
[k005][k001][k005][k001][k006]
[k004][huis][huis][k007][k006]
[k008][k001][k008][k003][k006]
[k004][k003][k008][k003][k008]

005x004_+029

code:

Score:93
[k008][k003][k006][k007][k006]
[k008][k003][k006][k007][k006]
[huis][huis][k008][k007][k006]
[k008][k003][k008][k003][k008]

010x010_+000

code:

Score:599
[k001][k001][k001][k001][k001][k001][k005][k011][k011][k002]
[k004][k006][k014][k006][k001][k006][k005][k011][k002][k002]
[k003][k009][k010][k006][k010][k006][k005][k011][k011][k011]
[k003][k008][k010][k008][k010][k006][k001][k006][k005][k011]
[k004][k009][k014][k012][k004][k004][k004][k003][k005][k015]
[k003][k008][k010][k016][huis][huis][k008][k008][k011][k011]
[k004][k009][k014][k012][k012][k004][k017][k004][k005][k015]
[k008][k008][k016][k016][k018][k018][k018][k015][k013][k015]
[k003][k014][k014][k012][k012][k015][k017][k015][k017][k015]
[k008][k001][k016][k012][k018][k015][k013][k015][k013][k015]

017x013_+020

code:

Score:1439
[k008][k008][k008][k008][k014][k006][k013][k006][k013][k021][k026][k021][k020][k023][k028][k022][k009]
[k026][k026][k026][k028][k007][k006][k013][k006][k013][k005][k029][k029][k029][k020][k020][k010][k010]
[k008][k008][k012][k028][k007][k028][k007][k006][k013][k021][k026][k021][k021][k023][k023][k023][k023]
[k003][k015][k003][k014][k007][k028][k003][k021][k003][k021][huis][huis][k029][k029][k020][k020][k022]
[k030][k008][k030][k001][k007][k021][k029][k021][k029][k021][k026][k021][k021][k005][k023][k023][k005]
[k019][k019][k030][k001][k007][k021][k029][k015][k025][k015][k025][k020][k029][k020][k012][k015][k012]
[k018][k019][k019][k001][k007][k003][k028][k015][k004][k015][k004][k020][k005][k022][k011][k027][k009]
[k010][k025][k010][k014][k007][k028][k028][k015][k004][k015][k004][k015][k005][k024][k017][k010][k002]
[k009][k005][k006][k014][k007][k026][k012][k015][k004][k015][k004][k015][k012][k024][k012][k016][k016]
[k010][k030][k030][k014][k008][k008][k008][k015][k011][k027][k011][k027][k017][k011][k022][k028][k022]
[k001][k001][k019][k027][k009][k026][k028][k027][k012][k024][k017][k024][k017][k024][k018][k025][k018]
[k030][k030][k030][k010][k002][k002][k002][k002][k017][k027][k017][k024][k017][k016][k018][k018][k019]
[k019][k019][k019][k016][k002][k016][k002][k016][k025][k016][k018][k016][k018][k016][k025][k018][k025]

048x039_+040
geen score binnen 5 minuten

061x043_+172
niet getest

105x184_+000
niet getest

[Corniel]

Vooruit dan maar.
met de nieuwe testset:

004x003_+003

code:

Score:24
[huis][huis][k002][k001]
[k004][k006][k001][k002]
[k004][k005][k002][k002]

005x003_+002

code:

Score:70
[k006][k007][k008][k007][k008]
[k005][k002][k005][k007][k001]
[huis][huis][k002][k004][k004]

005x004_-001

code:

Score:57
[k006][huis][huis][k001][]
[k006][k007][k008][k008][k004]
[k006][k003][k001][k002][k002]
[k003][k008][k005][k005][k002]

005x004_+001

code:

Score:45
[k005][k004][k006][k002][k002]
[k001][k007][k006][k006][k005]
[k008][k008][k003][k008][k001]
[k003][huis][huis][k008][k004]

005x004_+003

code:

Score:60
[k005][k005][k001][k008][k003]
[k006][huis][huis][k008][k003]
[k006][k007][k006][k008][k004]
[k001][k008][k003][k001][k004]

005x004_+029

code:

Score:92
[k003][k006][k006][k006][k006]
[k008][k003][k007][k007][k007]
[huis][huis][k008][k001][k006]
[k008][k003][k008][k003][k008]

010x010_+000

code:

Score:543
[k015][k013][k001][k001][k001][k011][k011][k015][k015][k015]
[k015][k002][k014][k006][k004][k006][k005][k005][k013][k005]
[k011][k006][k010][k016][k004][k004][k009][k014][k006][k015]
[k015][k005][k014][k012][k012][k012][k016][k004][k003][k011]
[k011][k013][k018][k018][k018][k016][k017][k008][k008][k015]
[k002][k001][k003][k012][huis][huis][k017][k004][k003][k011]
[k003][k006][k014][k012][k018][k017][k016][k008][k005][k015]
[k004][k009][k010][k008][k004][k012][k004][k006][k014][k011]
[k003][k008][k010][k006][k010][k008][k010][k008][k005][k015]
[k002][k001][k001][k009][k001][k008][k001][k001][k011][k011]

017x013_+020

code:

Score:1384
[k003][k015][k031][k001][k001][k021][k021][k006][k006][k006][k014][k006][k006][k013][k008][k026][k008]
[k028][k028][k030][k030][k029][k029][k003][k003][k014][k007][k007][k007][k007][k014][k008][k026][k008]
[k012][k015][k015][k021][k021][k021][k021][k008][k008][k026][k021][k026][k021][k014][k008][k026][k008]
[k019][k028][k002][k029][k029][k029][k013][k013][k014][k007][huis][huis][k007][k003][k008][k026][k008]
[k018][k025][k015][k004][k020][k023][k027][k006][k007][k007][k028][k015][k021][k026][k021][k026][k015]
[k016][k004][k015][k004][k020][k023][k013][k011][k028][k007][k028][k024][k021][k029][k024][k025][k005]
[k015][k030][k015][k004][k020][k023][k027][k012][k028][k027][k011][k024][k017][k011][k022][k017][k016]
[k031][k030][k015][k004][k020][k023][k013][k012][k015][k017][k017][k024][k017][k024][k024][k005][k016]
[k031][k030][k015][k021][k020][k023][k027][k011][k027][k002][k017][k016][k017][k012][k012][k012][k015]
[k001][k001][k029][k029][k029][k023][k012][k005][k010][k016][k025][k027][k002][k003][k028][k023][k028]
[k030][k030][k001][k021][k028][k019][k019][k010][k009][k009][k004][k010][k002][k018][k020][k020][k020]
[k019][k019][k030][k016][k002][k018][k005][k010][k010][k009][k009][k018][k018][k025][k005][k005][k022]
[k018][k019][k019][k016][k002][k025][k025][k010][k009][k010][k002][k025][k016][k018][k016][k025][k018]

048x039_+040

code:

Score:14510 (..)

061x043_+172

code:

Score: 21352 (..)

105x184_+000

code:

Score: 172713 (..)

Conclusie: Mijn implementatie kan (veel) grotere tuinen aan, maar komt minder dicht bij het optimum (ik ben bij de 10x10 en kleiner binnen de 2 minuten klaar). Ik heb me gefocust op grote afmetingen. De keuzes van de wedstrijdleiding zullen bepalen of dat een gelukkige keuze is geweest.

[Daos]

Alles hoger waar ik uitvoer krijg

Ik ga er dus ook vanuit dat er meer/evenveel kaarten zijn als de grootte van het spelveld. Ik hoop dat deze aanname juist is (al blijft het slordig van mij dat hij blijft hangen en niet met een foutmelding komt).

[raptorix]

Vanavond weer verder, het inlezen vanmorgen afgemaakt, voorts zware dag waar we 15 klanten met spoed moesten patchen

[raptorix]

Arg zie nu pas dat die coordinaten van onder naar boven lopen, grrrrrrrrrrrrrrrrrrrr.

[Anoniem: 303530]

Daar zat ik inderdaad ook vrij hard mee te klooien.... Dat is vast niet gemaakt door een IT-er

[raptorix]

Anoniem: 303530 schreef op vrijdag 03 mei 2013 @ 13:52:
Daar zat ik inderdaad ook vrij hard mee te klooien.... Dat is vast niet gemaakt door een IT-er

Gelukkig viel het mee, en hoefde ik alleen deze functie beetje om te draaien

code:

        public List<Kaart> Buren(Kaart thisCard)
        {
            return (List<Kaart>)Kaarten.Where(
                (
                //West
                k => k.X == thisCard.X - 1 && k.Y == thisCard.Y ||
                //Oost
                k.X == thisCard.X + 1 && k.Y == thisCard.Y ||
                //Noord
                k.X == thisCard.X  && k.Y == thisCard.Y +1 ||
                //Zuid
                k.X == thisCard.X && k.Y == thisCard.Y -1  ||

                //NoordWest
                k.X == thisCard.X - 1 && k.Y == thisCard.Y +1 ||
                //NoordOost
                k.X == thisCard.X -1 && k.Y == thisCard.Y - 1 ||
                //ZuidWest
                k.X == thisCard.X +1  && k.Y == thisCard.Y + 1 ||
                //ZuidOost
                k.X == thisCard.X + 1 && k.Y == thisCard.Y - 1
                )
                ).ToList();
        }

[king_charles]

Nederlands en engels door elkaar

In je code kun je natuurlijk prima de 'normale' array coordinaten gebruiken, zolang je ze bij het schrijven naar de output.ini maar reversed.

[ Voor 64% gewijzigd door king_charles op 03-05-2013 16:21 ]

[Memorice]

king_charles schreef op vrijdag 03 mei 2013 @ 16:19:
Nederlands en engels door elkaar

In je code kun je natuurlijk prima de 'normale' array coordinaten gebruiken, zolang je ze bij het schrijven naar de output.ini maar reversed.

Je hoeft geen coordinaten te schrijven toch, het enige wat je hoeft te doen is de y-coordinaat van het huis aan te passen bij het inlezen, wat gelijk wordt aan de hoogte van het veld - de y-coordinaat van het .ini bestand.

[Daos]

king_charles schreef op vrijdag 03 mei 2013 @ 16:19:
Nederlands en engels door elkaar

Doe dan ook mee als je zo'n grote mond hebt.

[liquid_ice]

Daos schreef op donderdag 02 mei 2013 @ 17:41:
Ik ga er dus ook vanuit dat er meer/evenveel kaarten zijn als de grootte van het spelveld. Ik hoop dat deze aanname juist is (al blijft het slordig van mij dat hij blijft hangen en niet met een foutmelding komt).

Zou er niet te hard vanuit gaan

[Daos]

liquid_ice schreef op vrijdag 03 mei 2013 @ 20:41:
[...]


Zou er niet te hard vanuit gaan

Dat is balen. Ik heb hem al ingeleverd. Er is dus niets meer aan te doen.

edit:
Ik heb hem gefixt en krijg weer hoger dan Corniel (twee punten). Deze telt dus niet meer mee
005x004_-001

code:

Score:59
[k006][huis][huis][k001][k004]
[k006][k007][k008][k001][k005]
[k006][k003][k008][k005][k002]
[k008][k003][][k002][k002]

[ Voor 38% gewijzigd door Daos op 03-05-2013 21:07 ]

[Anoniem: 303530]

Tsja.. Daarom moet je dus wachten tot de laatste week voordat je je project inlevert. Misschien krijg je vlak na het inleveren opeens een briljant idee voor een algoritme.

[raptorix]

king_charles schreef op vrijdag 03 mei 2013 @ 16:19:
Nederlands en engels door elkaar

In je code kun je natuurlijk prima de 'normale' array coordinaten gebruiken, zolang je ze bij het schrijven naar de output.ini maar reversed.

Jaja, het was me zelf ook al opgevallen, ik refactor het wel even

[raptorix]

Ik heb nu redelijk werkend voorbeeld, volgens mij heb ik nog een issue gevonden, het kan voorkomen, dat je een kaart niet wilt leggen, bijvoorbeeld omdat hij negatief resultaat oplevert, wat moet je dan als output wegschreven?

[Anoniem: 303530]

gewoon

code:

[]

.

Is het trouwens legaal dat een kaart een score geeft aan zichzelf? Ik snap dat als ik een kaart heb die zowel water nodig heeft als levert, en ik leg er 2 naast elkaar, dat je dan 2 punten krijgt. Maar levert zo'n kaart los ook punten op?

[raptorix]

Anoniem: 303530 schreef op zaterdag 04 mei 2013 @ 12:36:
gewoon

code:

[]

.

Is het trouwens legaal dat een kaart een score geeft aan zichzelf? Ik snap dat als ik een kaart heb die zowel water nodig heeft als levert, en ik leg er 2 naast elkaar, dat je dan 2 punten krijgt. Maar levert zo'n kaart los ook punten op?

Hoe ik het interpreteer is dat een kaart zichzelf niet beinvloed, maar dat als 2 gelijke kaarten naast elkaar liggen dat het gewoon net zo telt als dat een andere kaart zou zijn.

[liquid_ice]

Een kaart, zonder buren levert nooit punten

[Anoniem: 303530]

Mijn nieuwe algoritme werkt nu ook. 003x003_+003 en 004_003_+002 zijn optimaal te berekenen in een fractie van een seconde. Bij de rest geraak ik uit mem na iets meer dan een minuut.

Dat is overigens een groot voordeel van een bruteforce achtig algoritme: er zijn maar enkele states die je moet bijhouden.

[raptorix]

Anoniem: 303530 schreef op zaterdag 04 mei 2013 @ 18:49:
Mijn nieuwe algoritme werkt nu ook. 003x003_+003 en 004_003_+002 zijn optimaal te berekenen in een fractie van een seconde. Bij de rest geraak ik uit mem na iets meer dan een minuut.

Dat is overigens een groot voordeel van een bruteforce achtig algoritme: er zijn maar enkele states die je moet bijhouden.

Memory is hier ook niet zo een probleem, ik bereken nu elke keer de hele score opnieuw, maar ik kan dat nog optimaliseren om de score per veld op te slaan, en alleen voor de velden die van status zijn veranderd opnieuw te berekenen. Ik zit nu met een klein suf probleem, waarbij ik waarschijnlijk een variabele moet dereferencen, maar kost me voorlopig al 4 uur

[Anoniem: 303530]

Als ik elke keer de score opnieuw zou berekenen zou het algoritme zo traag zijn dat memory ook geen probleem zou zijn, nee

[liquid_ice]

@Darkstone, ik ben echt heel nieuwsgierig naar het hoe en wat van jou optimalisaties mbt het buffering/memory gebruik.

Ik snap de concepten, maar heb bij dit probleem niet kunnen bedenken wat exact op te slaan, hoe die situatie later weer te herkennen en snel weer terug te zoeken.

Daarom ben ik zo nieuwsgierig om jou code door te spitten
(ik hoop op veel en duidelijk commentaar, haha)

[Anoniem: 303530]

Heb geduld.

Mijn laatste uitspraak is overigens iets overdreven, als ik elk frame de score opnieuw bereken ben ik 8x zo lang bezig op 005x004_+029. Overigens nog steeds optimaal binnen de tijd.

[Anoniem: 303530]

Ik denk dat het lastigste van deze opdracht is : Wanner stop je met rekenen?

Neem 005x004_+001. De score van 62 is snel gevonden. Maar hoe lang moet je daarna nog doorrekenen om je progsel te laten begrijpen dat dat de beste score is. 1 minuut? 2 minuten?

[KopjeThee]

Anoniem: 303530 schreef op donderdag 09 mei 2013 @ 13:44:
Ik denk dat het lastigste van deze opdracht is : Wanner stop je met rekenen?

Neem 005x004_+001. De score van 62 is snel gevonden. Maar hoe lang moet je daarna nog doorrekenen om je progsel te laten begrijpen dat dat de beste score is. 1 minuut? 2 minuten?

Mogelijk is dit stukje theorie nog interessant in dit verband:
Wikipedia: Secretaresseprobleem
Het is natuurlijk eigenlijk de variant waarbij je secretaresses weer terug mag oproepen. Dat probleem ken ik verder niet zo goed, maar google eens op: Secretary problem recall

[ Voor 14% gewijzigd door KopjeThee op 09-05-2013 22:14 ]

[Anoniem: 303530]

Ik voer een aantal keer mijn algoritme uit met afwijkende parameters. Ik heb het nu zo ingesteld dat elke opeenvolgende keer ~5x zo lang duurt als de vorige. Dat is niet echt van toepassing op het secretaresseprobleem.

Er moet een soort van benadering bestaan dat als ik dit algoritme draai met deze parameters, dat ik dan kan bewijzen dat de oplossing optimaal is. (of iig met redelijke zekerheid). Maar dat lukt momenteel slecht: op 004x003_+003 mis ik een puntje, terwijl hij bij 005x004_+001 na 3 seconden de score 62 vindt maar vervolgens blijft rekenen en op een gegeven moment een out of memory exception gooit.

[Anoniem: 303530]

Het is een beetje stil in dit topic

Mijn algoritme vind nu consistent de maximale bekende score in alle velden onder de 10x10. Bij de -1's blijf ik echter hangen. Bij de 10x10 blijf ik hangen op een score rond de 560 tot 580 afhankelijk van de precieze parameters. Met name omdat mijn heuristiek het maken van goede zetten aan het begin van het spel juist ontmoedigt...

Ik denk dat de eindstand voornamelijk beslist wordt door de snelheid van de algoritmes. De beste score vinden is niet direct een probleem voor mij, zolang de grootte van het veld beperkt blijft.

Ik heb overigens wel interesse in meer testsets.

[liquid_ice]

Ik ga dit weekend eens aan de uiteindelijke validator beginnen.

[CodeCaster]

Anoniem: 303530 schreef op zaterdag 11 mei 2013 @ 20:35:
Het is een beetje stil in dit topic

Ik heb maar een paar uurtjes per week de tijd. Mijn scoreteller werkt wel, dat project staat helemaal los van de rest. Het webproject dat ik er omheen heb gebouwd neemt een speelveld.ini, kaarten.ini en output.ini als input en tekent het bord met per kaart per richting de berekende score van de output. Voor de hier in dit topic gegeven outputs (van TS en Daos) klopt de score.

M'n AI.LayRandom()-methode werkt ook, daarmee haal ik op de set uit de TS binnen vijf minuten een score van 30-60. Als ik er niet meer aan toekom, lever ik die wel in.

[ Voor 5% gewijzigd door CodeCaster op 14-05-2013 11:04 ]

[liquid_ice]

Altijd iets inleveren

[Pete]

Leuk dat er weer een contest is! Gelukkig had ik het gezien, want ik zit niet zo vaak meer op GoT.

Ik zag dat een vraag van MLM nog niet beantwoord is (zover ik kan zien).

MLM schreef op woensdag 17 april 2013 @ 19:52:
...
Daarnaast, klopt dit ook:
3) In de TS gesproken word over "Elke beurt leg je een kaart aansluitend aan de al bestaande kaarten aan". In de invoer is geen sprake van een volgorde van kaarten, dus ik kan uit het gehele deck kiezen? Tevens impliceert dit dat in geval van meer ruimte op het speelveld dan er kaarten in het deck zitten (ie, er moeten lege kaarten in de uitvoer zitten), je moet garanderen dat alle kaarten verbonden zijn (ie, geen eilandjes van kaarten).

Daarbij, als er evenveel of meer kaarten zijn dan plekken, mag ik nog steeds voor lege plekken in de output kiezen?

[Anoniem: 510923]

Je wordt er niet voor gedisqualificeert, maar probeer zoveel mogenlijk kaarten te gebruiken voor een zo'n hoog mogelijke score.

[Vaan Banaan]

Inderdaad kan je beter een plaats leeg laten, als elke overgebleven kaart een lagere totaalscore geeft.
Ik heb inmiddels ook een werkende validator gemaakt, althans een die dezelfde scores berekent als in dit topic.
Dus nu maar eens nadenken over een goede combineer strategie.

[Anoniem: 303530]

Zo. Ook even een testset generator gemaakt. Dan valt er wat beter te testen. Het algoritme werkt wel, maar het is lastig om een goede heuristic te bedenken over het juiste moment om te stoppen.

Edit: aargh nu gaat er weer een assert van mijn score verificatie af

[ Voor 16% gewijzigd door Anoniem: 303530 op 22-05-2013 21:25 ]

[CodeCaster]

Met de laatste aanpassingen heb ik de helft van m'n unit tests gesloopt (eigenlijk alleen maar door het ombouwen van properties naar expliciete getters en setters), maar nu krijgt mijn eerste 'algoritme' wel een score van 77 op de set uit de TS.

Deze score is nog relatief laag omdat de score van de te plaatsen kaart nog maar één kant op wordt berekend, namelijk wat 'ie z'n buurman aan punten oplevert. Hierdoor liggen er nu een paar kaarten op een plek waar ze van alle kanten 0 punten krijgen, maar wel wat uitdelen.

[ Voor 3% gewijzigd door CodeCaster op 23-05-2013 00:21 ]

[Corniel]

CodeCaster schreef op donderdag 23 mei 2013 @ 00:13:
Deze score is nog relatief laag omdat de score van de te plaatsen kaart nog maar één kant op wordt berekend, namelijk wat 'ie z'n buurman aan punten oplevert. Hierdoor liggen er nu een paar kaarten op een plek waar ze van alle kanten 0 punten krijgen, maar wel wat uitdelen.

Als je het omdraait: dat je per kaart alleen bijhoudt wat ie aan punten oplevert, dan zit je in een keer goed.

[heinoh]

Ook maar even begonnen gisteren. Ik heb mijn validator af. Op de sets in dit topic krijg ik dezelfde waarden als hier door anderen gepost: 34, 96,98,93 en 61.

Just a heads up. De code is nog wel ugly, maar ik ben allang blij als ik een goed algoritme heb bedacht in de spaarzame tijd tussen het werken door!

Mijn random algoritme wordt het niet na 10000 runs:

Score: 65
[heg,0][rijbessen,4][huis,4][huis,1][terras,4][groentetuin,0]
[groentetuin,2][kippenhok,8][mesthoop,6][rijbessen,5][notenboom,7][terras,3]
[kas,2][dierenstal,3][boomgaard,5][mesthoop,5][vogelhuisje,4][insectenhotel,2]

[ Voor 32% gewijzigd door heinoh op 23-05-2013 15:22 ]

[CodeCaster]

Corniel schreef op donderdag 23 mei 2013 @ 11:10:
[...]

Als je het omdraait: dat je per kaart alleen bijhoudt wat ie aan punten oplevert, dan zit je in een keer goed.

Dan draai je het probleem alleen maar om: dan kun je een veel punten gevende kaart X naast reeds liggende kaart Y leggen, maar als Y dan aan X 0 of minder punten geeft, ga je alsnog de mist in (ik tel alleen de input).

[ Voor 3% gewijzigd door CodeCaster op 23-05-2013 15:34 ]

[Corniel]

CodeCaster schreef op donderdag 23 mei 2013 @ 15:33:
[...]

Dan draai je het probleem alleen maar om: dan kun je een veel punten gevende kaart X naast reeds liggende kaart Y leggen, maar als Y dan aan X 0 of minder punten geeft, ga je alsnog de mist in (ik tel alleen de input).

Volgens mij praten we langs elkaar heen (lees: ik las je opmerking niet goed genoeg). Maar wat je moet doen is bepalen of een mutatie winst, of verlies oplevert ten opzichte van de beginsituatie. Hiervoor heb toegang tot de totaalscore nodig, en de mogelijkheid om snel de verandering van de score te bepalen.

[Anoniem: 303530]

Voor een mutatie heb je geen toegang tot de totaalscore nodig. Je kan hypothetisch alleen de score-delta teruggeven. (wat mijn algoritme ook doet). Op een hoger level kan je dan iets doen met die totaalscore.

[ Voor 17% gewijzigd door Anoniem: 303530 op 23-05-2013 16:32 ]

[Corniel]

Anoniem: 303530 schreef op donderdag 23 mei 2013 @ 16:31:
Voor een mutatie heb je geen toegang tot de totaalscore nodig (..)

@Darkstone: Ten eerste moet de medestrijder nog wat zelf uit te puzzelen hebben, en ten tweede ligt het zoals je schrijft aan je algoritme.

[F.West98]

Ik ga morgen ook maar eens bezig denk ik. Kijken hoe ik het ga aanpakken

[Pete]

Mijn huidige versie doet al aardig mee:

Testset	Corniel	Daos	Pete
start post	96	98	96
004x003_+003	24	26	24
005x003_+002	70	71	71
005x004_-001	57		57
005x004_+001	45	62	60
005x004_+003	60	68	64
005x004_+029	92	93	93
010x010_+000	543	599	548
017x013_+020	1384	1439	1360
048x039_+040	14510		14996
061x043_+172	21352		21582
105x184_+000	172713		172767

Bij mij is het grootste probleem om mijn pruning goed te krijgen....

Gebruikt iemand al meerdere threads in hun programma?

[ Voor 0% gewijzigd door Pete op 29-05-2013 15:30 . Reden: Nieuwe scores voor grote datasets ]

[Anoniem: 303530]

Mijn programma pakt zo veel threads als er zijn, maar de schaling is niet erg goed (4 threads -> 3x zo snel als 1 thread, 8 threads (waarvan 4 virtueel met HT) -> 4x zo snel als 1 thread ) door de concurrency op een centrale datastructuur.

[Daos]

Mijn progsel is gewoon single-threaded.

[Pete]

@Darkstone heb jij al resultaten op de testsets? (Of hou je die liever geheim?)

[Anoniem: 303530]

Ik haal op alle testsset behalve de 599 en groter dezelfde score als Daos. Zoals vermeld is het vinden van de score niet het grootste probleem, correct bepalen wanneer te stoppen wel. Ik heb het nog niet voor elkaar gekregen de parameters zo te tweaken dat hij een redelijke kans heeft op het vinden van de juiste score, maar ook dat hij niet te lang doorgaat.

[Corniel]

Nog 10 dagen. Spannend.

[Pete]

Mijn huidge scores:

004x003_+003	26	0m0.067s
005x003_+002	71	0m0.065s
005x004_+001	62	1m20.252s
005x004_+003	68	3m25.828s
005x004_+029	93	0m14.583s
005x004_-001	61	0m10.196s
010x010_+000	506	5m0.002s
017x013_+020	1369	5m0.002s
048x039_+040	14952	5m0.002s
061x043_+172	21577	5m0.003s
105x184_+000	172852	5m0.005s
905x784_+097	8446840	5m0.025s
testset		98	3m34.519s

Op dit moment ga ik nog de mist in bij de 'middelgrote' velden (100-300 vakjes). Ook gaan sommige algoritmen net iets te ver door.

[ Voor 14% gewijzigd door Pete op 07-06-2013 11:10 ]

[Daos]

Kan je de oplossing van 005x004_-001 hier neerleggen? Ik kom in mijn verbeterde versie (die niet meetelt) niet hoger dan 59.

[cosmo50]

Mooie wedstrijd en leuk spel! Vorige week pas begonnen dus dat wordt een strak tijdschema. (En super onverstandig door een aankomende toetsweek, maarja ). Kaarten worden ingelezen, en nu de rest nog:)

Waarschijnlijk domme vraag, maar in de testsets van Corniel (dank daarvoor trouwens!) staat de grote van het bord, en dan _xxx. Wat wordt hiermee bedoeld?

[Daos]

Dat is het aantal kaarten dat overblijft als het hele veld gevuld is. Bij 005x004_-001 kom je er dus 1 tekort.

[Anoniem: 303530]

Voeg in de avond doxygen ontdekt, de rest van de avond bezig geweest met documenteren

Met deze hitte valt er toch niet fatsoenlijk te slapen...

[Daos]

@Pete:

Daos schreef op vrijdag 07 juni 2013 @ 13:36:
Kan je de oplossing van 005x004_-001 hier neerleggen? Ik kom in mijn verbeterde versie (die niet meetelt) niet hoger dan 59.

Ik vraag alleen jouw output.ini met de score van 61.

@Darkstone:
Kan jij geven hoeveel jij haalt op 005x004_-001?

[Anoniem: 303530]

Daos schreef op zaterdag 08 juni 2013 @ 15:19:

Kan jij geven hoeveel jij haalt op 005x004_-001?

Mijn algoritme heeft nog geen ondersteuning voor dat scenario. Het is wel in te bouwen in een uurtje, maar ik ben er nog niet aan toe gekomen.

Edit: ik kom op 56 met één lege kaart, of 58 met 2 lege kaarten. Maar dat is niet admissable (de admissable variant geraakt uit mem na ~20s. Ik heb maar 4GB.)

Edit: het is ook goed dat ik dit even test, want ik zie dat bij gebruik van mijn admissable heuristic de CPU usage rond de 40% zweeft vanwege het geknok om mutexen...

Edit: met een admissable heuristic krijg ik na 5½ minuut geknok met de pagefile en mutexen de score van 59. Dat is de maximale score die mogelijk is. Of er moet een bug zitten in mijn logica.

[ Voor 49% gewijzigd door Anoniem: 303530 op 08-06-2013 17:39 ]