vrijdag 26 juni 2009

Gebruikte materialen

Voor dit project zijn verschillende dingen gebruikt:
- Umirtx robot-arm
- Umirtxsimulator
- UvA Linux computer met Eclipse om in te programmeren.
- de Java taal.
- Scrabblebord

Programma bestanden:

Hier

Resultaten

Vanaf donderdag zijn we voornamelijk bezig geweest om het programma 'werkend' te krijgen, daarbij mogelijke problemen omzeilend. Derhalve is ons huidige programma een beetje hackend aan de praat gekregen. Wat in ieder geval wel werkt: het selecteren van woorden op bepaalde rijen en/of kollommen. Deze kunnen ook terug gegeven worden aan de highpath, waarmee woorden kunnen worden gelegd. Het grootste probleem wat er is is dat de gevonden bordconfiguraties niet goed doorgegeven kunnen worden zodat ze vergeleken kunnen worden met andere configuraties. Daarom geeft het programma over het algemeen alleen voor rijen of alleen voor kolommen het beste woord terug, en dan altijd het kolom/rij die het laatst een letter heeft.

Vervolgonderzoek dat we kunnen aanraden:
- Verbeter het algoritme om woorden te plaatsen (op dit moment zijn we er achter gekomen dat alleen vanuit de laatste letter een woord wordt neergelegd).
- Zorg dat het checken in rows en columns van te voren bepaald wordt. Beide bestaan en werken, maar zodra ze tegelijk worden gebruikt gaat er informatie verloren(meer objectgeorienteerd programmeren dan nu gedaan is, is raadzaam).
- Integreer het spel met een mooie interface en meer gebruiksvriendelijkheid.

Dit waren allemaal punten die we hadden willen doen, maar het project bleek groter dan van te voren werd gedacht.

Wat we vooral geleerd hebben is hoe een dergelijk project het beste vanaf het begin ontworpen kan worden, en hoe we taken beter op moeten splitsen.

donderdag 25 juni 2009

Dag 4

De laatste dag:
Nu de woorden gegenereerd kunnen worden, moet er voor gezorgd worden dat er vanuit een scrabbleboard, met gegeven letters in de "hand". En idealiter moet de robot dit dan op het bord neerleggen.
De robotarm kan bewegen gegeven een positie, naar een gegeven andere locatie met MakePath.java, en daarna IK.java en dit uitvoeren met de umirtxsimulator.

Er zijn alleen problemen met het genereren van de juiste woord op de positie op het bord voor het woord dat de meeste punten oplevert. Het heeft de hele dag gekost om deze code goed te krijgen... enkele problemen welke we hadden:
  • het berekenen van de positie van een letter in het woord op het bord afhankelijk van de positie een andere letter van dat bord...
  • Vooral veel problemen met object georienteerd programmeren, zoals bijvoorbeeld wanneer objecten worden gekopieerd en wanneer ze worden geinstantieerd
Onze functie werkt nu alleen voor rijen, kolommen is niet moeilijk om uit te breiden. Wel belangrijk is dat er checks nog in moeten komen om voor ieder geplaatste letter te checken of die letter niet in een andere richting een woord vormt.

woensdag 24 juni 2009

Dag 3

Het dictionary algoritme(WordCombi.java) werkt volledig. De dictionary, die we gevonden hebben op www.pocketcm.com en gemaakt is door "Eppo", hebben we opgesplitst per beginletter(zoals een woordenboek) om de zoektijd te reduceren. Het woordenboek, dat we gebruiken, is 11300 woorden groot.
De bronnen voor onze Permutatie en Combinatie generator om woorden te genereren is afkomstig van www.merriampark.com/comb.htm (/perm.htm) en geplaatst door Michael Gilleland.


Vandaag afgekregen:

Algoritme voor scrabble helemaal uitgewerkt en geimplementeerd. moet nog getest worden. Dingen die nog niet zijn geimplementeerd zijn tests of een horizontaal woord ook verticaal woorden ergens maakt. Dit kan nog wel geimplementeerd worden morgen.

Er lijken problemen te komen met complexiteit. het permuteren van een lijst van woorden in de computer hand met 1 letter op het bord kan vaak nog wel, maar als de letters op het bord uitgebreidt worden wordt het niet meer berekenbaar. Mogelijk kan dit bij verandering van het algoritme wel voor strings van woorden achter elkaar, dit zou wel erg handig zijn, aangezien de makkelijkste moves bestaan uit uitbreidingen van al bestaande woorden. Deze kunnen nu echter niet goed onderzocht worden. Voor verdere verbetering van de prestaties zou het woordenboek gesplitst kunnen worden in aparte woordenlijsten per letter (gedaan) en per woordlengte (nog niet gedaan)

dinsdag 23 juni 2009

Dag 2

Op dag 2 gedaan:

s'ochtends:

  • Scrabblebord meegenomen en opgemeten
  • Permutatie algoritme is af, dus we kunnen nu alle mogelijke Strings maken
  • Verdere functies voor Scrabble geimplementeerd
  • Scrabble werkend: printen van een scrabble bord, en andere functies. Inlezen van een bordopstelling nog niet
s'middags:
  • checken van woorden uit dictionary: mbv scanner werkt, maar tot 350 woorden. Verder gewerkt met buffer, maar deze werkt nog niet. Mogelijk verder gaan met lexicon van 26 * 350 woorden?
  • Algoritmes bekeken voor de 'move'
  • Cartesian bord notaties uitgewerkt.

maandag 22 juni 2009

ZSB2

Dit is de website van Ian Dashorst en Jurrien Boer voor het vrije experiment bij het van 'Zoeken sturen en bewegen'
Doel is een programma te maken welke het spel scrabble kan spelen. Dus een programma welke voor een ingelezen bordopstelling een zo hoog mogelijk woord kan bedenken, en deze vervolgens met de robot arm kan plaatsen.

Hoe gaan we dit doen:

Het probleem bestaat uit 4 delen:

Organiseren van de informatie: hoe lees je borden in, welke informatie haal je hieruit, etc.

Het zoeken van geschikte woorden.

geschikte plaatsen voor de woorden bedenken

Het plaatsen van de letters



Prioriteit is nu het genereren van mogelijke woorden,

daarna kan het probleem van het leggen van de correcte stukken worden aangepakt.
Planning
Maandag
--> zoeken goede database voor woorden
--> structuur van programmas bedenken
--> 'algoritme' bedenken
Dinsdag
--> programmas schrijven
--> programma scrabbleboard.java is een scrabblebord, met write en read methodes, etc.
--> programma generatepossibilities.java genereert mogelijke woord sequences
--> programma checkwords.java haalt sequences uit die niet legale woorden zijn

Woensdag
--> algoritme implementeren
--> programma uittesten
--> begin maken aan bewegen van scrabblestukken mbv robotarm
Donderdag
--> verder testen?
--> GUI?
Vrijdag
--> programma laten zien


Algoritme
Basis idee van het algoritme: je hebt een bord met mogelijk al een woord erin; ook heb je zelf een aantal letters. Wat je gaat doen is alle permutaties berekenen van een aantal van je eigen letters en 1 letter uit het bord. Vervolgens ga je uit deze lijst de woorden selecteren welke ook echt woorden zijn. Daarna ga je van elke overgebleven woord de woorden ordenen op hoeveel punten ze opleveren, en daarna nog kijken of het wel mogelijk is. (ivm met andere gezette woorden die in de weg zitten) Vervolgens die zet ook echt maken.


Dag 1
Bedacht dat we scrabble gingen doen .
Het is handiger de werking van de chessboard files uit week 2 & 3 te doorgronden dan om deze opnieuw te maken voor scrabbleborden. Echter die bestanden zijn voor ons (nog) niet beschikbaar, deze komen hopelijk deze week onze kant op.

Daarnaast de algemene werking van ons programma geschreven, hoe het moet interacten met de scrabblebord objecten. Kennis gemaakt met een aantal manieren om strings te combineren en te permuteren.
Wat we nodig hebben is het volgende:

gegeven een verzameling 'handletters' en 'bordletters', dwz de letters die in je hand zijn en de letters die op het bord al geplaatst zijn moet het volgende gedaan worden.
de set van alle combinaties van 1 t/m n letters uit handletters noemen we set a, dit is dus de superset van A, behalve de lege verzameling. Daarnaast hebben we de set nodig die alle mogelijkheden van 1 letter uit de bordletters beschrijft, in andere woorden alle losse letters. Voor iedere mogelijkheid hiervan moet die letter uit b aan alle opties van de superset van A worden toegevoegd. Dit geeft dan alle mogelijkheden van 'woorden' waar minstens 1 letter al op het bord gebruikt wordt. Vervolgens moet een functie deze sets permuteren. Al dan niet binnen de functie zelf moeten dan van al deze permutaties de woorden gefilterd worden van de niet-woorden. Dit gebeurt d.m.v. een test of het te testen woord voorkomt in een tekst bestand met woorden.

Er is bedacht dat als de 'bordletters' allemaal met hoofdletters in het bestand word gegooid, er later ook makkelijk op te sporen is waar in het scrabblebord het woord neergezet moet worden.

ZSB