Hallo,
ich fange an, ein vier gewinnt Spiel zu programmieren.
Das Spielfeld ist 7 Spalten mal 6 Zeilen gross.
Die Abfrage ob 4 Steine einer Farbe waagerecht in einer Reihe sind mache
ich so:
Peter Zz schrieb:> Es kommt mir dabei besonders auf die Geschwindigkeit des Programmes an.
willst du computer gegen computer spielen lassen? Wenn noch ein Mensch
daran beteiligt ist, brauchst du dir wirklich keine Gedanken wegen der
geschwindigkeit zu machen.
> oder kann man das eleganter lösen?
auf jeden Fall. Stell dir mal vor du sollst dein Programm mal schnell
auf 8 spalten umschreiben.
asdf schrieb:> guck dir arrays an (Felder)
Exakt.
Vor allen Dingen auch deshalb, weil diese Abfrage ja sowieso nur die
Viertel-Miete ist. 4 gewinnt ist ja nicht ausschliesslich dann zu Ende,
wenn 4 Steine in einer Zeile zu finden sind.
ABgesehen davon.
4 gewinnt ist ein 2 Personen Spiel. In einer derartigen Abfrage würde
ich irgendwie - nun ja - die Farbe der Steine erwarten. 4 Steine
nebeneinander reicht ja nicht. Sie müssen auch von derselben Farbe sein.
Peter Zz schrieb:> //*********************************************************************> unsigned char Gewinn_test(unsigned char Feldnummer,unsigned char Farbe)> {> unsigned char Zeiger = (Feldnummer * 12)+(Farbe * 6);
d.h. du hast 2 Arrays, für jede Farbe eine?
Ja, kann man machen.
Aber warum so kompliziert?
Wenn du konzeptionell 2 Arrays hast, dann mach doch gleich 2 Arrays. Was
bringt es dir, wenn du wegen jedem Krempel da jedesmal auseinander
dividieren musst? Ausser das sich alles verkompliziert, sehe ich da
keinen wirklichen Vorteil.
Dann kannst du dir diese ganze Auseinanderklamüserei in die Zeilen
sparen. Wo du doch so auf Speed erpicht bist.
Moment:
Wie entstehen eigentlich die 12 da drinnen?
d.h. du hast eigentlich pro Spieler 7 Arrays?
Denn für eine komplette Darstellung des Spielfeldes mittels Bits
brauchst du 6 Bytes.
84 / 6 = 14 Spielfelder. Es gibt 2 Spieler, daher 7 gespeicherte
Spielfelder pro Spieler.
wärs da nicht einfacher
1
typedefunsignedcharSpielFeld[6];
2
3
structSpieler_
4
{
5
SpielFeldSpielfelder[7];
6
};
zu machen, also erst mal ein bischen in Datenstrukturen zu investieren,
und dann
// untersuche ob in Feld eine Gewinnsituation vorliegt
9
}
Einfach alles unstrukturiert in ein großes Array zu stopfen, ist auch
nicht immer der Weisheit letzter Schluss. Dann verplempert man einen
Haufen Zeit damit, immer wieder Array-Indizes auszurechnen, für nichts
und wieder nichts.
Ich hab mal vor Jahren (erfolglos) versucht, 4 gewinnt mit neuronalen
Netzwerken zu programmieren.
Ein "Abfallprodukt" davon waren recht schnelle C-Datenstrukturen und
Algorithmen für Gewinner-Abfragen. Allerdings keine leichte Kost... (so
long long spielereien, war noch 32bit damals)
Karl Heinz Buchegger schrieb:> Wie entstehen eigentlich die 12 da drinnen?
Das Array ist so aufgeteilt:
6 char für rot Feld 0
6 char für gelb Feld 0
6 char für rot Feld 1
6 char für gelb Feld 1
6 char für rot Feld 2
6 char für gelb Feld 2
6 char für rot Feld 3
6 char für gelb Feld 3
usw.
Der µC muss ja mehrere z.B. 7 Spielzüge vorausberechnen (Brute Force),
deshalb so viele Spielfelder und der Wunsch das das Programm schnell
sein soll.
Ich habe die 3 Funktionen:
Peter Zz schrieb:> Der µC muss ja mehrere z.B. 7 Spielzüge vorausberechnen (Brute Force),> deshalb so viele Spielfelder
So was ähnliches hab ich mir schon gedacht
> und der Wunsch das das Programm schnell> sein soll.
Dann erst recht.
Wozu jedesmal durch diese ganze Indexrechnerei durch, um aus dem großen
Komplett-Array genau die Teile rauszuholen, die in der jeweiligen
Situation relevant sind, wenn du dir das ganze auch so organisieren
kannst, dass du diese Aufteilerei überhaupt nicht brauchst, weil sie
schon durch die Datenstruktur vorab vom Compiler erledigt wurde?
Karl Heinz Buchegger schrieb:> Wozu jedesmal durch diese ganze Indexrechnerei durch
Das sehe ich im Moment gar nicht als sooo grosse Belastung an.
Ich denke meine Gewinnabfrage ist so schon ganz gut. Oder?
Peter Zz schrieb:> Ich denke meine Gewinnabfrage ist so schon ganz gut. Oder?
Finde ich nicht. Aus meiner Sicht sehr unelegant, viel zu umständlich
und sobald mehr Zeilen oder Spalten hinzukommen muss man viel Arbeit
investieren um den Code anzupassen.
Peter Zz schrieb:> Ich denke meine Gewinnabfrage ist so schon ganz gut. Oder?
Für das oder schreibt man in Der Regel einen Unit-Test.
Ansonsten: Wie soll man mit vertretbarem Aufwand das aus deinem
Zahlen, schiebe und Magic-Numbers gewusel das in Sinnvoller Zeit
bewerten?
Schaff da doch erst mal eine sinnvolle Datenstruktur dann kann man das
auch besser bewerten.
Ein Algorithmus hat zuerst mal korrekt zu sein, und dann kann man (in
95% der Fälle durch Optimierung des Algorithmus) sich Gedanken über die
Geschwindigkeit machen.
Peter Zz schrieb:> Der µC muss ja [...] (Brute Force),
Bei Speilen, welche Regeln folgen nutzt man idr nicht BruteForce
sondern Backtracking und ggf. Zugtabellen.
Karl Heinz Buchegger schrieb:> Denn für eine komplette Darstellung des Spielfeldes mittels> Bits brauchst du 6 Bytes. 84 / 6 = 14 Spielfelder
Ich zähl auf dem Bild 6x7 = 42 (oh oh...) mögliche Positionen, wieso
nicht einfach ein Array[6][7] und dann 0 = unbelegt, 1 = rot, 2 =
gelb...
Wegen der paar Bytes und Speicherzugriffe ist es dann auch nicht schade,
das ganze Rechnen und maskieren verbrät auch Zeit.
Hi Peter
Ich stimme Läubi vollkommen zu.
Läubi .. schrieb:> Schaff da doch erst mal eine sinnvolle Datenstruktur dann kann man das> auch besser bewerten.
Für einen schnellen Algorithmus solltest du dir überlegen, wann man
gewonnen hat. Bei 4-Gewinnt ist es so, dass man nur gewinnen kann wenn
man vier Steine senkrecht in einer Spalte hat, oder einen Stein in der
Mitte besitzt!
Diese Überlegung gibt auch die optimale Gewinnstrategie vor. Bei
4-Gewinnt wirft man IMMER in die mittlere Spalte es sei denn der andere
hat 3 in einer Reihe und würde sonst gewinnen.
Gruß
Jens
Ich würde das so machen:
Es gibt für jedes Feld ja nur drei Zustände: kein Stein, rot oder gelb.
Das kodiere ich in 2 Bits 00 = leer, 01 = rot,10 = gelb.
Jede Zeile fasse ich zu einem 16-Bit-Wert zusammen. Ich muss dann diesen
Wert nur noch dreimal mit sich selbst UND verknüpfen, vobei ich den
zweiten Wert jedesmal vorher um 2 Bit nach links shifte. Kommt da am
Ende 0x0000 heraus, gibt es noch keine 4er Reihe.
Schneller dürfte es kaum gehen.
Detlev T. schrieb:> Schneller dürfte es kaum gehen.
hast du es getestet? Ich würde auch je feld ein byte machen. Da shiften
ist für einen Atmel auch nicht so einfach, er kann nur jeweil am 1
schiften. 2 links schifts sind also auch 2 enweisungen.
Peter II schrieb:> Da shiften> ist für einen Atmel auch nicht so einfach, er kann nur jeweil am 1> schiften. 2 links schifts sind also auch 2 enweisungen.
Das shiften ist hier kein Problem, da man dreimal shiften muss und jedes
Zwischenergebnis benötigt.
avr schrieb:> Das shiften ist hier kein Problem, da man dreimal shiften muss und jedes> Zwischenergebnis benötigt.
aber nur wenn genug register zum Merken vorhanden sind. Im schlimmsten
fall macht es es mehrfach.
> if(Zeile3 & (Zeile4 >> 1) & (Zeile5 >> 2) & (Zeile6 >> 3))return(vier_in_reihe);
hier wird ganz schön viel umgeschiftet.
Jens schrieb:> Diese Überlegung gibt auch die optimale Gewinnstrategie vor. Bei> 4-Gewinnt wirft man IMMER in die mittlere Spalte es sei denn der andere> hat 3 in einer Reihe und würde sonst gewinnen.
Das ist Schwachsinn. Lese dich mal in 4-Gewinnt Strategien ein. Bei
4-Gewinnt spielt man auf Zugzwang. Die mittlere Reihe ist wichtig, aber
viel wichtiger ist es 3 Reihen an der richtigen Position aufzubauen und
natürlich zu verhindern das der Gegner diese "richtigen" Reihen baut. So
schlägt man übrigens schon die meisten menschlichen Spieler, selbst mit
geringer Suchtiefe.
Peter II schrieb:> aber nur wenn genug register zum Merken vorhanden sind. Im schlimmsten> fall macht es es mehrfach.
Deswegen würde ich bei einer solchen Optimierung gleich zu Assembler
greifen. Mit Makros wird das ganze maximal doppelt so lang.
avr schrieb:> Deswegen würde ich bei einer solchen Optimierung gleich zu Assembler> greifen. Mit Makros wird das ganze maximal doppelt so lang.
auch mit ASM hast dir nicht unendlich viele Register frei. Ich sehe hier
für die paar Felder überhaupt kein Zeitproblem. Das erkennen ob jemand
gewonnen hat lässt sich sehr gut optimieren. Man braucht z.b. die
unteren reihen nicht zu prüfen wenn sich dort nichts ändert. Und das
lässt dich mit C einfacher machen als mit ASM.
Nachtrag:
wenn man darüber nachdenkt, dann würde ich sogar nur an der Stelle
prüfen wo der letzte Stein abelegt wurde. Dann nur dort kann es einen
gewinner geben. Von dem letzten stein aus kann es nur 7 richtungen geben
wo ein gewinn möglich ist.
Peter II schrieb:> Nachtrag:>> wenn man darüber nachdenkt, dann würde ich sogar nur an der Stelle> prüfen wo der letzte Stein abelegt wurde. Dann nur dort kann es einen> gewinner geben. Von dem letzten stein aus kann es nur 7 richtungen geben> wo ein gewinn möglich ist.
Da war woll jemand schneller ^^. Es gibt aber 8 mögliche Richtungen
Peter II schrieb:> Abstauber schrieb:>> Es gibt aber 8 mögliche Richtungen>> nö, dann über den Stein kann ja nichts liegen.
Na klar stimmt ;)
Hab mir mal n paar gedanken gemacht...
Es gibt um jeden stein 7 möglichkeiten für einen derselben Farbe. Wenn
du mit einem zweidimensionalen Array arbeitest könntest du dir sozusagen
die Richtiguns Vektoren definieren. Dan die Position des Steins +
Vektor*Iteration = zu Prüfendes Feld. Ist dort keine gleiche Farbe kann
man diese Richtung vergessen und bei der nächsten "Umgebungs Ebene"
nicht mehr mit einbeziehen.
Bei der nächsten Ebene musst du nur noch den Vektor mal zwei nehmen und
hast die Position des Nächsten Steins und kannst ihn Prüfen. Wenn nach
drei Iterationen noch ein Vektor übrig ist hast du deine Gewinn
Situation.
Abstauber schrieb:> Wieso prüfst du immer das kommplette Spielfeld
Weil vor lauter "Optimierungszwang" der TE halt schon den Blick für das
tatsächliche Problem verloren hat...
Läubi .. schrieb:> Abstauber schrieb:>> Wieso prüfst du immer das kommplette Spielfeld>> Weil vor lauter "Optimierungszwang" der TE halt schon den Blick für das> tatsächliche Problem verloren hat...
Ich versuche mal, meine Lösung zu verteidigen:
Die Funktion Gewinn_test soll testen,
ob nach einem realen oder einem simulierten Zug die soeben
eingeworfene Farbe gewinnt.
Wenn also z.B. soeben eine rote Scheibe eingeworfen wurde, wird getestet
ob Rot jetzt irgendwo im Spielfeld vier Steine in einer Reihe hat.
Ein Test, ob Gelb vier Steine in Reihe hat, ist erst notwendig,
nachdem Gelb einen Stein eingeworfen hat.
Da dieser Test nur aus einer absehbaren Anzahl boolscher Operationen
und Schiebeoperationen besteht, ist der Test vermutlich gar nicht so
ineffizient.
Peter Zz schrieb:> Da dieser Test nur aus einer absehbaren Anzahl boolscher Operationen> und Schiebeoperationen besteht, ist der Test vermutlich gar nicht so> ineffizient.
doch wenn er über das gesamt spielfeld sucht. Nur weil es es bool
liefert heist das noch lange nicht das es schnell ist.
Extrem beispiel:
Wenn der 1. Stein abgelegt wird, bräuchte mal überhaupt nicht suchen.
Peter II schrieb:> Extrem beispiel:>> Wenn der 1. Stein abgelegt wird, bräuchte man überhaupt nicht suchen.
Da hast du genau recht.
Und wenn der 2. Stein abgelegt wird brauche ich auch nicht zu suchen.
Und so könnte es 1000 Ausnahmen und Regeln geben, die man alle suchen
und dann programmieren müsste. Mein Ansatz, den ich verfolge, hat nur
diese eine Gewinn_test Routine die immer wieder aufgerufen wird.
Peter Zz schrieb:> Mein Ansatz, den ich verfolge, hat nur> diese eine Gewinn_test Routine die immer wieder aufgerufen wird.
dann mache doch einen Ansatz und du wirst merken das sie im durchschnitt
mindestens 10mal langsamer ist als ein Ansatz wo nur die aktuelle
Position bewertet wird.
Deine Routine ist einfach nicht wartbar, lesbar und dann auch noch
schwer optimierbar. Aber sammle ruhig deine eigenen Erfahrungen.
Peter Zz schrieb:> Und so könnte es 1000 Ausnahmen und Regeln geben, die man alle suchen> und dann programmieren müsste. Mein Ansatz, den ich verfolge, hat nur> diese eine Gewinn_test Routine die immer wieder aufgerufen wird.
Ich finde den ganzen Ansatz mit den Spieler-Bitmaps eigentlich gar nicht
so schlecht. Das interssante dabei ist, dass dieser Code das komplette
Spielfeld auf irgendeine Gewinnsituation mit relativ wenigen Befehlen
abklappern kann. Eine Abfrage in einer klassischen 2D-Matrix, ausgehend
von einer bestimmten Position dürfte auch nicht scheller zu realisieren
sein.
Ein paar Dinge würde ich anders machen. Die Sache mit der
Datenorganisation hab ich ja schon angesprochen.
Aber auch solche Sachen
Karl Heinz Buchegger schrieb:> Eine Abfrage in einer klassischen 2D-Matrix, ausgehend> von einer bestimmten Position dürfte auch nicht scheller zu realisieren> sein.
ich denke schon, denn wenn keine gewinn Situation vorherrst muss er alle
vergleiche durchgehen. Wenn man von der letzen position ausgeht, dann
kann man viel schneller festellen das kein Gewinn möglich ist. Wenn man
jetzt davon ausgeht das ein Gewinn seltener ist als ein nicht Gewinn
dann sollte man so programmieren das der "nicht gewinn" schneller
erkannt wird.
Peter II schrieb:> Karl Heinz Buchegger schrieb:>> Eine Abfrage in einer klassischen 2D-Matrix, ausgehend>> von einer bestimmten Position dürfte auch nicht scheller zu realisieren>> sein.>> ich denke schon, denn wenn keine gewinn Situation vorherrst muss er alle> vergleiche durchgehen. Wenn man von der letzen position ausgeht, dann> kann man viel schneller festellen das kein Gewinn möglich ist. Wenn man> jetzt davon ausgeht das ein Gewinn seltener ist als ein nicht Gewinn> dann sollte man so programmieren das der "nicht gewinn" schneller> erkannt wird.
Deine Indexrechnerei um in der Matrix die 3 darüber liegenden, 3
darunter liegenden, 3 Diagonal linksoben, 3 Diagonal rechtsoben, 3
diagonal linksunten, 3 diagonal rechtsunten liegenden Felder zu finden
und jeweils zu summieren, wenn sie die richtige Farbe haben, kosten dir
auch was.
Man müsste die Alternativen durchprobieren und in realen Spielen
durchprobieren was in Summe gesehen tatsächlich schneller ist.
Denn sowas
ist ziemlich schwer zu schlagen. Wenn der Compiler es schafft die Werte
in Registern vorzuhalten, dann sind das 3 Blöcke mit jeweils 3
Und-Operationen, und einem bedingten Sprung.
Diagonalen sind fast ähnlich unaufwändig.
Nicht zu vergessen: Seine Methode ist recht speichersparend. Und das
kann bei Rekursionstiefen von 14 (2*7) schon mit ein Argument sein.
Karl Heinz Buchegger schrieb:> Nicht zu vergessen: Seine Methode ist recht speichersparend. Und das> kann bei Rekursionstiefen von 14 (2*7) schon mit ein Argument sein.
warum sollte der speicherverbauch abhängig von der Rekursionstiefen
sein? (ok ein paar stack variablen, aber doch bitte nicht das Array
kopieren!)
in der Rekusion wird einfach der Stein gesetzt, dann getestet und dann
der stein wieder weggenommen. Dann an der nächste stelle der stein
probiert.
Damit spart man sich das umkopieren das arrays.
Peter II schrieb:> Karl Heinz Buchegger schrieb:>> Nicht zu vergessen: Seine Methode ist recht speichersparend. Und das>> kann bei Rekursionstiefen von 14 (2*7) schon mit ein Argument sein.>> warum sollte der speicherverbauch abhängig von der Rekursionstiefen> sein? (ok ein paar stack variablen, aber doch bitte nicht das Array> kopieren!)
da hast du recht. Da hab ich jetzt nicht nachgedacht.
Wobei ich mich gerade frage
(Man merkt schon, mit 4 gewinnt hab ich mich noch nie beschäftigt)
Gibt es eigentlich bei 4 gewinnt Stellungs-Bewertungsregeln? Also
ähnlich wie im Schach, bei dem man ja auch nicht aufs blaue hinein
einfach alle Zweige durchrechnet, sondern eine Stellungsbewertung macht
um rauszufinden, welche Zweige des Baumes gut sind und welche nicht.
Oder geht hier tatsächlich nur: rekursiv das Spielfeld anfüllen und der
'beste' Zug ist der, mit dem man am Ende in die meisten
Gewinnsituationen kommt?
Karl Heinz Buchegger schrieb:> Gibt es eigentlich bei 4 gewinnt Stellungs-Bewertungsregeln?
keine Ahnung, man könnte versuchen die anzahl der Möglichen
gewinnsitiuatioen zu bestimmen. Wenn man also 2 x 3 Steine senkrecht
hat, dann ist es viel besser als wenn man sie nicht hat. Also die Anzahl
der zusammenhängenden steine zählen wo noch ein gewinn möglich ist.
Peter Zz schrieb:> ist der Test vermutlich> so könnteKarl Heinz Buchegger schrieb:> Wenn der Compiler
Ja wenn, vermutlich und könnte ... ;-)
Das Ziel bei so einem BackTracking Problem ist immer Zweige möglichst
schnell auszuschließen, davon hängt alles ab. Und dafür muss man das
Problem Profilen und nicht mutmaßen, und vor allem muss das ganze in
erster Linie korrekt sein.
Peter Zz schrieb:> es 1000 Ausnahmen und Regeln geben, die man alle suchen> und dann programmieren müsste
Das ist doch Quatsch. Du musst nur strukturiert das obige Muster prüfen
(es wurden dir ja schon netterweise fast fertige Algorithmen genannt),
dann ergibt sich das automatisch.
Karl Heinz Buchegger schrieb:> ist ziemlich schwer zu schlagen
Kommt immer drauf an, wenn in 90% der Fälle kein Gewinn vorliegt kann
der "richtige" Algorithmus da ggf. deutlich besser sein und vorzeitig
abbrechen, während der "falsche" ständig alles durchnudelt. Sobald dann
nicht mehr zufällig alles in ein Byte passt wird auch interessant...
Karl Heinz Buchegger schrieb:> Gibt es eigentlich bei 4 gewinnt Stellungs-Bewertungsregeln?
Hab ich schon weiter oben geschrieben. Dreier-Reihen bringern fast
nichts wenn sie an der falschen Position sind, da die meisten Spiele im
Zugzwang enden. Der Spieler der seine Reihen klug positioniert hat, der
gewinnt durch Zugzwang (was von vielen Spieler als "Glück" bezeichnet
wird).
Ich würde:
- Das Spielfeld als Integerarray vorhalten. 0, 1, 2 = unbesetzt, blau,
gelb.
- Aus Performancegründen ein 1D-Array nehmen (xmax*ymax) Position:
(y*maxX+x)
- Ab dem vierten Stein pro Farbe nach jedem Zug einmal die umliegenden
Steine checken.
- wenn einer der umliegenden Steine identisch ist in die Richtung und
Gegenrichtung weiter suchen. Abbruch bei x = xmax oder y = ymax oder
andere Farbe. Geht schön mit der selben Funktion und 'nem
Richtungsparameter.
Das ist beliebig erweiterbar (Feldgröße, 4 gewinnt, 5 gewinnt,
wasweißich)
Aus Jux könnte man dann noch den Algo im Betrieb umstellen und die
Zeiten messen. Hey, schon fast ne Jugend-Forscht-Arbeit. Muss ich mal
meinem ehemaligen Informatiklehrer schicken :-).
Lukas T. schrieb:> - Aus Performancegründen ein 1D-Array nehmen (xmax*ymax) Position:> (y*maxX+x)
Wenn der Compiler ein zweidimensionales Array indiziert, ist das
natürlich viel komplizierter, und dauert daher länger ;)
Oliver
Lukas T. schrieb:> - Aus Performancegründen ein 1D-Array nehmen (xmax*ymax) Position:> (y*maxX+x)
Das bringt dir genau gar nichts, ausser Schreibarbeit und der
Möglichkeit blödsinnige Fehler zu machen.
Was glaubst du, wie ein Compiler 2-Dimensionale Arrays implementiert.
Implementieren muss, weil es anders eh nicht geht.
Peter II schrieb:> aber doch bitte nicht das Array> kopieren!)>> in der Rekusion wird einfach der Stein gesetzt, dann getestet und dann> der stein wieder weggenommen. Dann an der nächste stelle der stein> probiert.
Ich denke, mal aus dem Bauch heraus, ist das kopieren von 12 Byte
einfacher, als den Spielzug wieder zurückzunehmen?!
Peter Zz schrieb:> Ich denke, mal aus dem Bauch heraus, ist das kopieren von 12 Byte> einfacher, als den Spielzug wieder zurückzunehmen?!void> Feld_kopieren(unsigned char Feldnummer)> {> unsigned char Zeiger_quelle = Feldnummer * 12;> unsigned char Zeiger_ziel = Zeiger_quelle + 12;> // hier keine for-schleife um Zeit zu sparen!> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //1> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //2> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //3> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //4> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //5> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //6> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //7> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //8> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //9> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //10> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //11> Spielfeld[Zeiger_ziel++] = Spielfeld[Zeiger_quelle++]; //12> // oder besser mit Pointer?!> }
Guck mal du hast gerade 12 mal das selbe geschrieben.
Don't repeat yourself!
das könnte man mit einer Schleife viel schöner machen und das wäre in
meinen Augen auch noch deutlich angehmer zu lesen..
Peter Zz schrieb:> Ich denke, mal aus dem Bauch heraus, ist das kopieren von 12 Byte> einfacher, als den Spielzug wieder zurückzunehmen?!
org = feld[1,2];
feld[1,2] = ROT;
recursion();
feld[1,1] = org;
wobei man sich auch org auch sparen kann, denn das feld muss ja leer
gewesen sein.
Also der Code mit den & und | sieht nur groß aus, sollte aber am
schnellsten gehen.
Die Schiebungen lassen sich etwas optimieren, aber das wars dann.
Der AVR hats nicht so mit indirekter Adressierung.
Der muß 2 Register mit der Baseadresse laden, 2 * den Index addieren,
ehe er mit LD endlich zugreifen kann. Und bei Elementen > 1 Byte muß er
erst noch den Index mit der Anzahl multiplizieren.
Das kostet viel mehr Zeit, als einfach direkt mit LDS ins Register.
Eine verkettete Liste mag vielleicht weniger Vergleiche enthalten,
braucht aber erheblich mehr Adreßberechnungen.
Peter Dannegger schrieb:> Also der Code mit den & und | sieht nur groß aus, sollte aber am> schnellsten gehen.
aber das sieht doch einfach schrecklich aus
if(((Zeile6 & 0x78)==0x78)||((Zeile6 & 0x3C)==0x3C)||((Zeile6 &
0x1E)==0x1E)||((Zeile6 & 0x0F)==0x0F))return(vier_in_reihe);
das ist doch einfach unschön.
Peter II schrieb:> Peter Zz schrieb:>> Ich denke, mal aus dem Bauch heraus, ist das kopieren von 12 Byte>> einfacher, als den Spielzug wieder zurückzunehmen?!>> org = feld[1,2];> feld[1,2] = ROT;> recursion();> feld[1,1] = org;>> wobei man sich auch org auch sparen kann, denn das feld muss ja leer> gewesen sein.
Und wieder versuche ich meinen Ansatz zu verteidigen:
die Funktion:
liefert ja nicht zurück, wo genau der Stein gesetzt wurde.
Der Funktion wird ja lediglich:
1. die Feldnummer (wo ist die Rekursion im Moment)
2. die Spalte
3. die Farbe (rot/gelb)
übergeben. Die Funktion schaut dann, wie tief der Spielstein nach
unten fällt. Ist die Spalte voll, gibt die Funktion eine Fehlermeldung
zurück.
Peter II schrieb:> if(((Zeile6 & 0x78)==0x78)||((Zeile6 & 0x3C)==0x3C)||((Zeile6 &> 0x1E)==0x1E)||((Zeile6 & 0x0F)==0x0F))return(vier_in_reihe);>> das ist doch einfach unschön.
0x78 = 0b01111000
0x3C = 0b00111100
0x1E = 0b00011110
0x0F = 0b00001111
was ist daran unschön?
Naja, die Schönheit entsteht im Auge des Betrachters.
Peter Zz schrieb:> Alternativ zu Feld_kopieren bräuchte ich dann eine Funktion> Stein_setzen_zurücknehmen
feld kopieren würde ich auf jeden Fall vermeiden. Das begrenzt dir auf
jeden Fall die rekursion wegen speicher überlauf. Und das ist wohl auf
jeden Fall langsamer als wieder ein bit zu löschen.
Peter II schrieb:> feld kopieren würde ich auf jeden Fall vermeiden. Das begrenzt dir auf> jeden Fall die rekursion wegen speicher überlauf.
Die Rekursiontiefe ist eher durch die Rechenzeit begrenzt, ich denke
mehr als eine halbe Minute bis maximal eine Minute Rechenzeit ist
unzumutbar.
> Und das ist wohl auf> jeden Fall langsamer als wieder ein bit zu löschen.
Das sagst du nur so aus dem Bauch heraus, getestet hast du das auch
nicht, oder?
Peter Zz schrieb:> Das sagst du nur so aus dem Bauch heraus, getestet hast du das auch> nicht, oder?
also 6 byte kopieren oder 1 bit wieder zu löschen - was wird wohl
schneller sein?
Somal auch nocht die übergabe von array dazukommt. Die man dann nicht
bräuchte weil es nur ein array gibt. Damit kann auch der Compieler
besser optimieren weil alle Adresse fest stehen.
Peter II schrieb:> Somal auch nocht die übergabe von array dazukommt. Die man dann nicht> bräuchte weil es nur ein array gibt. Damit kann auch der Compieler> besser optimieren weil alle Adresse fest stehen.
Diese Argumentation ist gerade dabei, mich zu überzeugen.
Ich habe vor einer Zeit auch mal angefangen ein 4-Gewinnt mit KI zu
programmieren. Man kann gegen KI spielen aber das Programm ist immer
noch eine Baustelle. Das Projekt ruht seit längerem. Villeicht ist etwas
sinnvolles dabei. Ich hätte übrigens für interessierte noch 2 Platinen
übrig.
besten dank.
Leider kann ich die .sch und brd Datei nicht öffnen, ist wohl nicht
eagle 5.6 kompatibel?
Meine angestrebte Hardware sieht so aus, siehe Bild im Anhang.
Es gibt 3 rot/gelb Zweifarb-LED's
Mit zwei Tastern (Select & Enter) wird dem µC die Position mitgeteilt,
wo der Gegner seinen Stein (Gelb) eingeworfen hat.
Der µC antwortet dann nach einiger Zeit :-( und teilt im Binär-Code
001 = Spalte 1
010 = Spalte 2
011 = Spalte 3
100 = Spalte 4
101 = Spalte 5
110 = Spalte 6
111 = Spalte 7
mit, wo er seinen Spielstein (Rot) einwerfen würde.
Ich strebe ein möglichst kleines Volumen an, so das ich das Ding in der
Hand verbergen kann.
Dann hier der Schaltplan noch als PNG. Das eigentliche Spiel und die KI
sind in einer Klasse gekapselt. Es müsste leicht sein die Klasse mit
deiner Hardware zu benutzen.
Hier eine Idee wenn man etwas mehr Speicher spendiert:
Man könnte einmalig für jedes Feld berechnen an welchen möglichen
Gewinnvierern es beteiligt ist. Das sollten maximal 16 sein (am Rand
weniger). Jedem dieser Vierer ordnet man eine Nummer zu. Diese Nummer
ist Index in eine Zählertabelle pro Farbe. Erreicht ein Zähler 4 ist der
Gewinn da.
Die feste Datenstruktur könnte man sogar einmalig als Quellcode
generieren.
Ich denke das ist deutlich schneller, als mit allen notwendigen
Zusatzabfragen in 7 Himmelsrichtungen zu suchen.
Sollte nur eine Idee sein, kein Beweis. Und mit einer Idee fängt es
doch an, oder? Übrigens, mit "ich denke" wollte ich sagen, "ich gehe
nach meinen Erfahrungen davon aus".
Also ich würde das so probieren:
Stein wird eingeworfen.
1. Sind unter dem Stein drei weitere gleichfarbige -> Sieg.
2a. Steine der Gleichen Farbe nach links zählen.
2b. Steine der gleichen Farbe nach rechts zählen.
2c. Zusammenzählen, wenn größer 2 -> sieg.
3a. Steine diagonal nach links unten zählen.
3b. Steine diagonal nach rechts oben zählen.
3c. Zusammenzählen, wenn größer 2 -> Sieg.
4. Dasselbe mit rechts unten und links oben.
Das erschlägt alle möglichen Siegkombinationen ausgehend vom
eingeworfenen Stein.
:-)
Thread beobachten
Seitenaufteilung abschalten