Zahlenraten - Kann der Computer wirklich hellsehen?

Balancieren mit Bits: Bitoperatoren in Javascript

"Hast du das Progrämmchen auf www.gamecraft.de gesehen? Der hat wirklich die Zahl erraten, die ich mir gedacht habe" - "Alles fauler Zauber, ich habe mir gar keine gedacht, immer auf ja geklickt, und der kam auch mit einer Zahl an!"

So oder ähnlich stand es mal in irgendeinem Forum. Der zweite Zocker war da wohl bei der Beantwortung der Fragen des Computers nicht ganz ehrlich :-). Aber wie geht das nun mit dem Zahlenraten?

1. Die Theorie hinter dem Spiel

Eine beliebige Zahl lässt sich als Summe von 2er-Potenzen darstellen. Das Programm fragt nun simpel und einfach ab, welche 2er-Potenz (Summand) vorkommt. Für die Bitbeisser: Die Zahl wird als Binärzahl verwendet, es wird in Gruppen unterteilt, die ein bestimmtes Bit gesetzt haben oder nicht. Anschließend wird hintenherum nachgefragt, ob das Bit vorkommt oder nicht.

Damit man dem Programm nicht sofort auf die Schliche kommt, ist zum einen die Reihenfolge der Abfrage nicht streng nach Größe geordnet, sondern zufällig. Zum anderen wird zufallsgesteuert abgefragt, ob der Wert 2^x vorkommt oder nicht, die gesammelten Potenzen werden addiert, fertig!

Ein Beispiel soll dies verdeutlichen: Gedacht sein soll die Zahl 42, diese kann zerlegt werden in 2⁵+2³+2¹.

Der Computer teilt nun die Zahlenmenge in Gruppen, in denen eine bestimmte 2er-Potenz vorkommt oder nicht, und bietet diese an. Er würde folgende Antworten erhalten, wenn der Spieler ehrlich ist:

2⁰ (alle ungeraden Zahlen): nein
2¹ (Zahlen mit dem Bitwert 2): ja
2² (Zahlen mit dem Bitwert 4): nein
2³ (Zahlen mit dem Bitwert 8): ja
2⁴(Zahlen mit dem Bitwert 16): nein
2⁵(Zahlen mit dem Bitwert 32): ja
2⁶(Zahlen über 63): nein

Die Ja-Werte werden summiert und ergeben so die Zahl 42.

	zum Seitenanfang
	zum Seitenende

2. HTML-Teil

Wir brauchen:

den Kopfteil,
die Überschriftund und einen kurzem Text, der erklärt, worum es hier geht,
eine Tabelle, in der die abzufragenden Zahlen angezeigt werden,
eine Abfrage, ob die in frage kommende Zahl vorkommt sowie ein Eckchen, wo die erratene Zahl angezeigt wird, und eine Entscheidung, ob das Spiel von neuem losgehen soll,
und als "Sahnehäubchen" eine Anzeige für die Ungeduldigen, ob noch viele Fragen kommen.

2.1. Kopfdaten

Da das Spielchen selbst kurz und einfach ist, wurde mit durchgestylten Hintergründen zu Tabellen und Knöpfe gearbeitet. Diese wurden teils in CSS untergebracht, teils in "veralteten" background-Attributen. Damit streikt zwar der HTML-Validator, aber die Seite wird auch in älteren Browsern wie NN4 korrekt angezeigt. Die erste Zeile steht wegen dieser Rückwärtskompatibilität fest, und solange HTML4 noch nicht von allen Browsern *zuverlässig* unterstützt wird, sieht so die Kopfzeile aller etwas aufwändigeren Projekte aus:

<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">

Der Rest ist wie bekannt:

<html>
<head>
<title>Zahlenraten </title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">

Der letzten Zeile wird nachgesagt, dass sie NN4 zum Dauer-Reload verführen kann. Praxis ist hier allerdings, dass das Reload ausbleibt bei NN4.6+ auf Windows und Linux. Aber trotzdem belastet diese Zeile den NN4 ungefähr so wie ein Stylesheet mit borders und Hintergrundbildern. Macht der NN4 Probleme, so sind diese Elemente zu entfernen.

Unter HTML3.2 wurde folgerichtig diese Zeile einfach weggelassen, damals gab es nicht diese Codepage-Vielfalt wie heute, und jeder Browser wusste, was er mit Entities zu tun hatte. Das ist heute zwar auch der Fall, aber die Spezifikationen für HTML4 bestehen auf einer Codepageangabe, auch unter "Transitional". Sollte es dadurch aber zu Problemen kommen, empfehle ich, auf die Spezifikation zu pfeifen, denn das, was der Betrachter sieht, ist das, was der Browser darstellt, nicht, was laut Spezifikation dargestellt werden sollte!

Auf Futter für die Suchmaschinen wurde hier verzichtet, da zum einen das Teil zu einer Sammlung gehört, zum anderen ist es nicht mehr als ein netter, kleiner mathematischer Spaß.

Kommen wir zum "Verschönerungsteil" dem CSS. Natürlich muss sich das Teil in die Sammlung einfügen und bekommt somit den Gamecraft-08/15-Style verpasst:

Da dieser nicht ausreicht, werden noch ein paar Extras für dieses Spielchen definiert:

<style type="text/css"> 
.in2   { background-color:#ccccdd; } 
.bgr2  { background-color:#778899; 
         background-image:url(backgr1.jpg); 
       }
</style>

Damit ist der Kopfteil erst mal fertig und kann abgeschlossen werden:

</head>

2.2. Überschrift und Text

.. wurden hier ganz trivial untereinandergesetzt. Damit die Tabelle noch auf kleineren Seiten voll angezeigt wird, wurde hier eine möglichst kleine Schrift gewählt. Da meine Augen nicht die besten sind, ist meist bei 10pt die untere Grenze erreicht. Der Text sollte herausfordernd sein, und wenn das Ganze die obige Reaktion ergibt, so war er schon ganz gut!

<body class="mono">
<h4>Zahlenraten</h4>
<p>
Denke dir eine Zahl zwischen 0 und 127 aus, und ich versuche, sie zu erraten!
</p>

Der Rest steht in einer breitenbegrenzten, "blinden Tabelle", um zu verhindern, dass die Elemente bei höheren Auflösungen quer über den Bildschirm verstreut werden. Die linke Zelle enthält die Zahlentabelle, die rechte den Rest. Und weil hier Formularelemente als I/O für Javascript genommen wird, steckt diese Aussentabelle in einem Form-Block namens form1.

<form name="form1" action="tunix" onsubmit="return false;">
 <table width=540>
  <tr>
   <td>
    <!-- hier kommt die Zahlentabelle rein -->
   </td>
   <td>
    <!-- hier Anzeigen und Buttons rein -->
   </td>
  </tr>
 </table>
</form>

onsubmit="return false;"> verhindert, dass das Formular irgendwelche Aktionen auslöst.

2.3. Tabelle für die abzufragenden Zahlen

Für wechselnden Inhalt gibt es in punkto Einfachheit und Kompatibilität nichts Besseres als Input-Formfelder. Wir brauchen bei einem Zahlenvorkommen von 0 bis 127 genau 128/2 = 64 Felder. Da Programmierer aber naturgemäß faule Hunde sind, wird die Tabelle nicht explizit in HTML hingeschrieben, sondern man lässt machen, und zwar von Javascript. 64 Input-Felder werden hier untergebracht in einer 8x8-Tabelle. Jede Zelle bekommt einen netten Hintergrund, einmal mit CSS für die modernen, einmal mit dem background-Attribut, so dass auch Fossilien damit zurechtkommen, ein cellpadding von 4 wird eingestellt, dass man den Hintergrund auch sieht, der Input-Hintergrund wird mit der passenden Pastellfarbe eingetönt, so dass das strahlende Weiss, was einige Vorsintflut-Browser daraus machen, dem Auge nicht so wehe tut. Und so sollte eine Zelle aussehen:

gewünschter Zelleninhalt

<td bgcolor="#778899" background="backgr1.jpg" class="bgr2">
 <input class="in2" type="text" name="z_laufende_nr" size=2>
</td>

Diese Zellen lassen sich unter Javascript mit document.form1.elements['z'+laufende_nr].value neu beschreiben. Und so werden die Zelle erzeugt:

Inhalt der linken Zelle

<script>document.writeln(tabelle());</script>

Und da ich kein Unmensch bin, folgt die Javascript-Funktion aus dem Header-Teil, der den HTML-Code für die Tabelle erzeugt:

function tabelle()
{ var i,j,k,temp;
  temp='<table border=0 cellpadding=4 cellspacing=2>';
  k=0;
  xmax=8;
  ymax=8; 
  for (j=0; j<ymax; j++)
  { temp=temp+'<tr>';
    for (i=0; i<xmax; i++)
    { temp=temp+'<td bgcolor="#778899" background="backgr1.jpg" ';
      temp=temp+'class="bgr2">';
      temp=temp+'<input class="in2" type="text" name="z'+k+'" size=2>';
      temp=temp+</td>'; 
      k++;
    }
    temp=temp+'</tr>';
  }
  temp=temp+'</table>';
  return temp;
}

Damit ist die linke Zelle fertig.

2.4. Abfrage und Anzeige der erratenen Zahl

Interaktion in HTML soll über Formularelemente gehen, also wird die Anzeige auch so angelegt:

Die Zahl ist:<br><br>
<input type="text" name="zahl" value="?" size=4 class="in2">

Folgerichtig wäre die Abfrage, ob die Zahl vorkommt, ein Radiobutton-Feld mit den Auswahlen "ja" oder "nein". Aber wenn Spieleprogrammierer sich immer an die reine Lehre halten würden, sähen die Spiele alle etwas langweilig aus, wie zahlreiche Beispiele mit Javascript-Spielen im WWW leider bestätigen. Also basteln wir uns 2 schicke Buttons für die Auswahl. (Bei der ersten Version des Spiels gab es noch keinen Typ "button", später keine Notwendigkeit, die eigenen Buttons zu ersetzen.)

Ist sie in dieser Tabelle? <br>
<table border=0>
 <tr>
  <td width=48 height=32 background="backgr1.jpg" class="bgr2">
   <a href="javascript:aktion(true)">ja</a>
  </td>
  <td width=48 height=32 background="backgr1.jpg" class="bgr2">
   <a href="javascript:aktion(false)">nein</a>
  </td>
 </tr>
</table>

Wie wird die Anzeige jetzt angesprochen? Richtig, mit document.form1.zahl.value!

Der Vollständigkeit halber folgt der Button für den Neustart, diesmal mit div erstellt:

<div class="button">
 <a href="javascript:init()">auf ein Neues</a>
</div>

2.5. Das "Sahnehäubchen": die Fortschrittsanzeige

Bei 128 in frage kommenden Zahlen ist die gesuchte in 7 Versuchen gefunden (2⁷=128). Also braucht der Balken 7 Abschnitte. Dies sind kurz und schmerzlos 7 benamte Bildelemente, einmal mit komplett durchsichtigem Bild, einmal mit einem farbigen Streifen. Diese 7 Bildelemente müssen nahtlos aneinanderstoßen, das erreicht man am besten mit einer "knapp bemessenen" Tabelle. Und wie praktisch: die rechte Zelle hat exakt die passende Breite!

Man startet mit einer durchsichtigen Reihe, nach jeder Frage wird dann ein Bildelement umgefärbt. Damit nichts schiefgeht, wird wieder Javascript eingesetzt:

einzelnes Bildelement

<img src="leer.gif" width=16 height=8 name="hxx">

Erzeugung mit Javascript

var i,t='';
for (i=0; i<nab; i++)
t=t+'<img src="leer.gif" width=16 height=8 name="h'+i+'"> alt=""';
document.writeln(t);

Die Zeitanzeigen in Bubbles und anderen Spielen wurde auch nach genau diesem Muster hergestellt. Wichtig ist, dass zwischen den Images kein Leerzeichen, Zeilenumbruch oder sonstiger Müll steht, sonst ist die Anzeige unterbrochen. Würde man die einzelnen Bilder je mit document.writeln(...) schreiben lassen, hätte man auf der Quelltextebene Zeilenumbrüche dazwischen, und die Bilder hätten Lücken. Wer will, kann's probieren!
Wichtig ist auch, dass die Tabelle trotz ihrer Enge keinen Zeilenumbruch fabriziert, notfalls muss jedes Bild in eine Zelle gesteckt werden, was den Ladeaufwand bei großen Anzeigen aber leider erhöht.

Damit ist der HTML-Teil erledigt.

	zum Seitenanfang
	zum Seitenende

Javascript-Teil

ein fast reines Top-Down-Vorgehen

Vorarbeiten

Was braucht der Computer, um die Zahl zu bestimmen?

Erst mal ein Array antw, in dem die Reihenfolge der Abfragen auf die 2-er Potenzen gespeichert werden soll,
dann ein Array flag, um zu entscheiden, ob der Teil der Untermenge gezeigt werden soll, der die Zahl enthält oder der, der sie nicht enthält.
Dazu gehört dann auch ein Array wert, um die 2er-Potenzen unterzubringen, um Rechenzeit zu sparen.
zusätzlich ein Array, um die Untermenge anzuzeigen, hierzu wird das Input-Feld herangezogen.

Tja, etwas Algorithmenverschleierung muss sein! :-) -
Wir brauchen noch eine Variable, die speichert, ob das Spiel gerade läuft oder zu Ende ist aktiv, eine Variable für die Summe sum und für die Fortschrittsanzeige count runden das Ganze ab.
Blieben noch die beiden Konstanten für den Maximalwert max und die zugehörige Potenz nab. Ist die Anzahl count==nab, ist es Zeit, die Summe auszugeben.

max=128,nab=7;
wert=new Array(64,32,16,8,4,2,1);

var sum,count,aktiv;
var flag=new Array(nab);
var antw=new Array(nab);

Spielstart

Bei Start eines Spiels wird festgelegt, in welcher Reihenfolge die Untermengen dargeboten werden, ob die "positiven" oder "negativen" Teilmengen gezeigt werden, Schrittzahl count und Summe sum werden auf 0 gesetzt, die Fortschrittsanzeige zurückgesetzt und das Ergebnisfeld mit einem ? beglückt:

function init()
{ var i,j,k;

  // alles zurücksetzen:
  count=0; 
  sum=0;
  document.form1.zahl.value='?';
  for (i=0; i<nab; i++) 
  { document.images['h'+(i+1)].src='hell.gif';
    antw[i]=wert[i]; //2er Potenzen
  }

  // Reihenfolge der Abfragen mischen: 
  for (i=0; i<nab; i++)
  { j=Math.floor(nab*Math.random());
    k=antw[i]; 
    antw[i]=antw[j];
    antw[j]=k;
    flag[i]=(Math.random()<0.5); mal positiv, mal negativ abfragen
  }

  fuellen(antw[0],flag[0]); // erste Teilmenge anzeigen
  aktiv=true;               // Spiel läuft, Anwender darf klicken
}

Zahlengruppe anzeigen

Die Funktion fuellen belegt also die Anzeigen mit den entsprechend ausgesuchten Gruppen. Als Parameter bekommt sie die Gruppennummer, die gleichzeitig der Index des Array wert ist, welches die 2er-Potenz/das Bit enthält, nach der die Gruppen gebildet werden sollen. Der 2. Parameter ist das Flag, was bestimmt ob die positive Gruppe (Zahl mit entsprechender 2er-Potenz/gesetztem Bit ist drin) oder die negative (Zahl mit entsprechender 2er-Potenz/gesetztem Bit ist nicht drin) angezeigt wird.

function fuellen(ant,flag)
{ var i,k=0; // Laufnummer für Anzeige in der Tabelle

  // bei allen Zahlen Gruppenzugehörigkeit checken,
  // entsprechend flag anzeigen  
  for (i=0; i<max; i++)  
  { if (gruppe(i,wert[ant])==flag) 
    { document.form1.elements['z'+k].value=i;
      k++;
    }
  }
}

Zahlengruppe bestimmen

In der nächsten zu erstellenden Funktion gruppe(nr,gnr) arbeiten wir mit Bitoperatoren. Da diese in SelfHTML(8) äusserst stiefmütterlich behandelt werden, folgen erst mal ein paar Informationen.

Bitoperatoren in Javascript

Alle Bitoperatoren wirken so, als ob sie auf eine 32bit-Integer wirken. Zur Erinnerung: das Bit aussen links gibt an, ob die Zahl positiv oder negativ ist, und man hat die 31 restlichen Bits, die den Absolutwert angeben, der von 0 bis irgendwas am Anfang von 2Giga (2^31-1 für positive Zahlen, 2^31 für negative Zahlen) läuft. Und so kommt es, dass (2^31-1)+1 0 ergeben kann! ;-)

ECMAScript definiert est mal alle Zahlen als Number, da man hiermit aber nicht vernünftig mit dem DOM (HTML-Interfacedefinition) zusammenarbeiten kann, gibt es die "Unterabteilung" Integer (Javascript 1.5 = ECMAScript-262-3, 24.Mar.00 Kap.9.4ff). Hier sind Funktionen beschrieben, die bestimmte Integers für bestimmte Zahlensysteme ergeben. (Natürlich arbeitet die Math-Bibliothek auch mit Integern (gleiches Dokument)).

ECMAScript (Javascript 1.5) verleibt die so erhaltenen neuen Werte, falls passend, seiner "Integer-Sammlung" ein (passend heisst z.B. bei ECMA-262-3, Kap 8.5: bis max. 2⁵³). Umgänglich sind die neuen Integers in IE6 bis ca. 2⁶⁹ bis 2⁷⁰. Danach werden sie zwar angezeigt bis ca. 2¹⁰²⁴-1, verhalten sich aber wie Strings. Danach heisst es lapidar: Infinity (eigene Versuche). Bei letzteren kann man sogar die Buchstaben abfragen :-))

&, bitweises AND

& vergleicht zwei Zahlen bitweise, gibt eine Zahl aus, in der nur gemeinsame Bits vorkommen:

Anweisung	Bit-Darstellung
a = 6;	0110
b = 10;	1010
c = a & c;	0010
ergibt 2	gemeinsame Bits

|, bitweises OR

| vergleicht zwei Zahlen bitweise, gibt eine Zahl aus, in der alle Bits der 1. und 2.Zahl vorkommen:

Anweisung	Bit-Darstellung
a = 6;	0110
b = 10;	1010
c = a \| c;	1110
ergibt 14	alle vorkommenden Bits

^, bitweises XOR

^ vergleicht zwei Zahlen bitweise, gibt eine Zahl aus, in der die Bits der 1. und 2.Zahl nur je 1x vorkommen:

Anweisung	Bit-Darstellung
a = 6;	0110
b = 10;	1010
c = a ^ c;	1100
ergibt 12	Bits kommen an den entsprechenden Stellen in a und b nur 1x vor

Bis hier ist es relativ egal, ob man sich im 8-Bit, 16-Bit oder 32-Bitsystem befindet, ab hier sollte man ein wenig Kenntnisse über die interne Darstellung der Zahlen innerhalb eines Computers haben.

~, bitweises NOT

~ gibt eine Zahl aus, in der alle Bits der Eingabezahl geändert sind:

Anweisung	Bit-Darstellung
a = 6;	0000 0000 0000 0000 0000 0000 0000 0110
c = ~ a;	1111 1111 1111 1111 1111 1111 1111 1001
ergibt -7	Bits sind " geflippt", das Minus-Bit ist jetzt gesetzt, dann ist die Zahl - (2³¹ - gesetzte restliche Bits)

<<, bitweises SHIFTL

<< gibt eine Zahl aus, in der alle Bits der Eingabezahl nach links gewandert sind:

Anweisung	Bit-Darstellung
a = 6;	0000 0110
b = a<<1;	0000 1100
ergibt 12	(Bits sind um 1 Stelle nach links geschoben)
c = a<<2;	0001 1000
ergibt 24	(Bits sind um 2 Stellen nach links geschoben)

<<1 wirkt wie *2 (entspricht *2¹), <<2 wie *4 (entspricht *2²)

>>, bitweises SHIFTR

>> gibt eine Zahl aus, in der alle Bits der Eingabezahl nach rechts gewandert sind:

Anweisung	Bit-Darstellung
a = 6;	0000 0110
b = a>>1	0000 0011
ergibt 3	(Bits sind um 1 Stelle nach rechts geschoben)
c = a>>2	0000 0001
ergibt 1	(Bits sind um 2 Stellen nach rechts geschoben)

>>1 wirkt wie Math.floor(a/2) (entspricht /2¹), >>2 wie Math.floor(a/4) ( entspricht /2²)

Für das Programm brauchen wir nur &, das bitweise AND, um nachzuprüfen, ob ein Bit/eine 2er-Potenz in einer Zahl vorkommt.

 function gruppe(zahl,my_bit) { return (zahl&my_bit>0); }

2.5. Interaktion mit dem Benutzer

Der Anwender bekommt die Zahlen serviert und darf dann auf [Ja] oder [Nein] drücken, je nachdem ob seine Zahl vorkommt oder nicht. Die Funktion bekommt dabei als Parameter mitgegeben, welcher Knopf gedrückt wurde, true, wenn die Zahl vorkommt, false, wenn nicht. Es werden die Bitwerte addiert, die in der positiven Gruppe sind, und die direkt oder indirekt vom Anwender als Bestandteil seiner gedachten Zahl bestätigt wurden. Aus logischen Gründen gilt:

Wird eine positive Gruppe angezeigt (Bitwert kommt in den Zahlen der Gruppe vor), und der Anwender drückt: [ja], so wird der Wert addiert. Das Vorkommen des Bits in der gedachten Zahl wurde vom Anwender bestätigt.
Wird eine positive Gruppe angezeigt, und der Anwender drückt: [nein], so passiert nichts. Es wurde vom Anwender bestätigt, dass der Bitwert nicht in seiner Zahl vorkommt.
Wird eine negative Gruppe angezeigt, und der Anwender drückt: [ja], so passiert nichts. Es wurde vom Anwender bestätigt, dass seine Zahl dieses Bit nicht enthält.
Wird eine negative Gruppe angezeigt, und der Anwender drückt: [nein], so wird der Wert addiert. Es wurde vom Anwender bestätigt, dass seine Zahl nicht in den Zahlen der negativen Gruppe vorkommt, also ist sie in der positiven Gruppe.

Kurz und einfach, überall, wo kommt_vor==flag[count] ist, wird addiert.

function aktion(kommt_vor)
{ if (aktiv) // es darf nur während des laufenden Spiels geklickt werden
  { if ((kommt_vor==flag[count])) sum=sum+wert[antw[count]];
    document.images['h'+count].src='dunkel.gif';  // Fortschrittsanzeige
    count++;                                      // hochzählen
    if (count==nab)                               // bei 7 ist Ende
    { document.form1.zahl.value=sum;              // gedachte Zahl ist Summe,
      aktiv=false;                                // Spiel ist zu Ende
    }  
    else fuellen(antw[count],flag[count]);        // neue Gruppe anzeigen
  }
}

That's all, Folks!
zum Spiel

	zum Seitenanfang
	zum Seitenende

zur Textauswahl
Gamecraft nachladen