idee zu algorithmus ...

Ich haette folgende frage zur folgenden problematik:

wie koennte ein algorithmus aussehen der folgendes leisten muss:

man stelle sich als input fuer den algorithmus folgendes bitmuster vor (z.B. 1Byte lang), z.B.

0 1 1 0 1 0 0 0

^
|--- Diese Bit-Stelle ist wichtig

Das Ausgabe-Bitmuster soll wie folgt aussehen:

0 0 1 1 0 1 1 1

D.h. es wird von der markierten Stelle aus in jede richtung (links, rechts)
alle stellen mit 1 aufgefuellt bis eine 1 auftaucht (die zu erst auftauchenden 1'en werden belassen). Alle dahinterliegenden bits werden geloescht. Die markierte Stelle soll ebenfalls geloescht werden.

Hintergrund:

Man stelle sich ein Schach-Spiel vor. Das Input-Bitmuster ist eine Zeile des Schachbrettes. Eine 1 bedeutet das Feld ist von einer Figur belegt (andernfalls nicht belegt). Die markierte Bitstelle entspricht einem
Turm. Es soll nun herausgefunden werden, welche Brettfelder vom Turm angegriffen werden. Das resultat-Bitmuster zeigt welche Stellen diese Stellen sind (d.h. alle leeren Felder in beide Richtungen und einschliesslich die zuerst auftauchende Figur).

Die Frage ist nun, ob es eine Sequenz von logischen Operationen gibt, die obiges leisten koennte (nicht ganz trivial glaube ich), oder ob die einzige Alternative darin liegt, iterativ in beide Richtungen (von der markierten Bit-Stelle aus) zu gehen und entsprechend ein Vorhandensein einer 1 abzufragen (Abbruchkriterium sozusagen) und 1'en aufzufuellen!?!?

Fuer Ideen hierzu waere ich sehr dankbar.

Grussle.

Blue-Tiger

warum nimmst du statt Bitfeldern nicht einfach ein Array aus bool-Werten? Ich glaub den Anstieg an Speicher kannst du dir erlauben

(BTW glaub ich schonmal gehoert zu haben, dass ein vector<bool> intern eh Bitfelder verwendet)

Mein Problem ist nicht, keine passende Datenstruktur finden zu koennen.

Die Problembeschreibung ist voellig unabhaengig von der gewaehlten Datenstruktur.

Kurz: Es ist mir Sch....-egal mit welcher Datenstruktur das Problem geloest wird, solange es keine andere effizientere methode gibt ;))

(Im uebrigen bezweifle ich, dass bei den von mir angefuehrten Beispielen
Bit-Arrays besser waeren als z.B. ein unsigned long)

gruss.

Hi,

ich bin mir ziemlich sicher, dass du die ersten beiden Einsen per
Schleife suchen musst. Ab da kannst du dann mit logischen Operatoren
arbeiten, oder gleich die Schleifen zu ende laufen lassen.
Ich sehe da auch kein Problem (Performance? Unschön?).

Jockel

jo, das habe ich auch schon vermutet.
jedoch hatte ich gehofft, dass es vielleicht doch noch eine besonders schoene
folge von logischen Operationen gaebe, die sowas leistet (ohne Schleifen).

Hi,

ich bin mir ziemlich sicher, dass du die ersten beiden Einsen per
Schleife suchen musst.

Wieso bist Du Dir so "sicher" (waere nicht schlecht zu wissen :))

Unschoen ist etwas nur dann, wenn es beispielsweise um Performance geht und es bessere methodiken gaebe, die performance-maessig schneller waeren.

Zwar ist das beschriebene Problem nun kein riesen-rechenaufwand aber bei wie bereits als beispiel angefuehrten Schachprogrammen sind solche kleinen Details bei Suchalgorithmen schon sehr wichtig. Apropos Schnelligkeit:
Die gewaehlte Datenstruktur ist natuerlich hier auch sehr wichtig (Overhead, kompliziertheit der algorithmen)

Mein Algorithmus wird ja nur einmal bei programm-start passieren (Vorberechnung), von daher duerfte es, wie bereits von euch gesagt, nicht so schlimm sein, dass mit ner schleife zu machen.

Trotzdem danke.
gruss.

Ich bin mir deshalb sicher, da durch die logischen Operatoren immer
alle Bits geändert werden. Ausser du weisst einen bestimmten Bereich,
der sich anders verhalten soll. Und da sind wir ja wieder beim ersten
Satz: Diesen Bereich kannst du durch logische Op. nicht finden.

Ist natürlich kein echter Beweis, erscheint mir aber sinnvoll.

Jockel

semeltheone

Hört sich nach einem Schachprogramm an das den Bitboard Ansatz zur internen Board repräsentation verwendet.

Fals es wirklich ein Schachprogramm werden soll kannst du ja mal nach Beowulf googlen.Beowulf verwendet soweit ich mich erinnern kann Bitboards und ist Opensource.

Du könntest allerdings auch die 0x88 Methode verwenden die ist IMHO einfacher und auch recht schnell.

Die Sache mit den Bitboards hört sich zwar am Anfang verteufelt schnell an aber man sollte beachten das bei der Weiterverarbeitung z.B in der Bewertungsfunktion und im MiniMax Alg. die Bits auch wieder aus der (64 Bit) Zahl extrahiert werden müssen.

Aber vieleicht willst du ja gar kein Schachprogramm schreiben

peterchen

Du brauchst das nur für den Turm? Da bist du mit einem Lookup-Table wahrscheinlich schneller.