Robert Tarjan und die Tiefensuche
BLOG: Heidelberg Laureate Forum
Am ersten Tag des „Heidelberg Laureate Forum“ spricht Robert Endre Tarjan, Turing-Award-Preisträger von 1986, über seine Doktorarbeit von 1972, die mittlerweile längst Lehrbuchwissen geworden ist.
Robert Tarjan beim 9. HLF. Foto: © Heidelberg Laureate Forum Foundation / Kreutzer
Es geht darum, einen erfolgreichen Weg durch ein unübersehbar großes Gestrüpp von Möglichkeiten zu finden. Ein klassisches Beispiel sind schachspielende Computerprogramme (oder auch Menschen). Um aus der bisher erreichten Position den nächsten Zug zu finden, denkt sich der oder die oder das Spieler*in ein Sortiment möglicher Züge aus, dazu die möglichen Reaktionen des Gegners, dann die eigenen Reaktionen darauf und so weiter … Das ergibt einen ungeheuer reich verzweigten Baum von Möglichkeiten. Und wenn man diesen ganzen Baum zu Ende denkt, hat man eine Gewinnstrategie.
Theoretisch. In der Praxis ist es auch für die größten Supercomputer unmöglich, alle denkbaren Zugfolgen bis zum Ende zu verfolgen. Typischerweise rechnet ein Schachprogramm eine relativ geringe Anzahl von Zügen und „bewertet“ die so erreichten Stellungen, das heißt, es errechnet aus gewissen Kriterien – zum Beispiel: Wie viele Figuren habe ich noch? Ist eine meiner Figuren bedroht? – eine Einschätzung für die Siegesaussichten der jeweiligen Position. Nach dem Ergebnis dieser Bewertung trifft es seine Entscheidungen. Mit anderen Worten: Es durchsucht den riesengroßen Entscheidungsbaum zunächst in der Breite (breadth first) und nicht erst in der Tiefe (depth first).
Das funktioniert, weil es eine Bewertungsfunktion gibt, sprich weil man über die Elemente der Menge aller erreichbaren Positionen Informationen gewinnen kann. Aber wenn es nicht gerade um Schach oder Ähnliches geht, gibt es diese Information gerade nicht. Alles, was man hat, ist ein Graph. Er besteht aus „Knoten“ (im Beispiel den einzelnen Spielpositionen) und „Kanten“ (den Spielzügen), die jeweils zwei Knoten miteinander verbinden. Die Kanten können Einbahnstraßen sein (man kommt von A nach B, aber deswegen noch lange nicht von B nach A) oder auch nicht.
Es gibt einen Knoten, der heißt „Sieg“ oder „Ausgang“ (wenn zum Beispiel der Graph ein Labyrinth ist). Ich stehe auf irgendeinem Knoten des Graphen und muss einen Weg zum Sieg finden, oder eben aus dem Labyrinth entkommen. Ich habe keinen globalen Überblick über den Graphen, sondern stecke wirklich mitten im Irrgarten und kann gerade noch bis zum nächsten Knoten sehen. Vielleicht ist der Graph auch nur implizit gegeben, das heißt, es gibt keine Liste aller Kanten, sondern ich finde an jedem Knoten nur eine Anweisung vor, wie die von diesem Knoten ausgehenden Kanten zu bestimmen sind. Und ein bisschen beeilen muss ich mich auch; schließlich tobt ein hungriger Minotaurus im Labyrinth herum.
In dieser Situation hilft nur die Tiefensuche (depth-first search, dfs), sagt Robert Endre Tarjan. Aber nicht irgendwie, sondern systematisch. Am ersten Tag des „Heidelberg Laureate Forum“ berichtet er über einen Algorithmus, der in erträglicher Zeit zum Ziel führt. Vor immerhin 50 Jahren hat er ihn gefunden, und er ist noch frisch wie am ersten Tag – Standardlehrstoff für die Informatik.
Die Grundidee hatte bereits – der Sage nach – Ariadne, als sie ihrem Geliebten Theseus mit einem Faden zur Rettung verhalf. Der musste im Labyrinth auf Kreta sich nicht nur des Minotaurus erwehren, sondern vor allem wieder ins Freie finden. Das rettende Rezept war: Merke dir deinen bisherigen Weg durch den Graphen, zum Beispiel mit einem Faden, den du auf den Weg legst. So kannst du insbesondere verhindern, dass du im Kreis läufst. Für die Zwecke der Informatik muss das natürlich etwas präziser ausgedrückt werden.
Was heißt depth-first in einem Graphen, der anders als beim Schachspiel überhaupt keine erkennbare Tiefenstruktur hat? Das ist noch relativ einfach. Ein Suchschritt besteht darin, von einem Knoten entlang einer Kante zu einem anderen zu gehen. Depth-first heißt: Wähle als Ausgangspunkt jedes Suchschritts den Knoten, an dem dein letzter Suchschritt geendet hat. Man darf sich also tatsächlich einen kleinen Theseus vorstellen, der in dem Labyrinth von Knoten zu Knoten wandert und an jedem die Entscheidung treffen muss, wie es weitergeht. Im Vorübergehen schreibt Theseus an jeden Knoten, den er besucht, eine laufende Nummer. Das ist nur geringfügig informativer als Ariadnes Faden, aber es reicht. Trifft er auf seiner Wanderung einen Knoten, an dem er schon einmal war, dann meidet er ihn und wählt eine andere Kante.
Und wenn keine Kanten mehr zur Auswahl stehen, weil der aktuelle Knoten eine Sackgasse ist oder alle seine unmittelbaren Nachbarn sämtlich schon besucht wurden? Dann heißt es kehrtmachen. Einen Sackgassenknoten würde Theseus als erledigt markieren und nie wieder aufsuchen. Ein Schritt, der vom aktuellen Knoten zu einem bereits besuchten führt, „schließt einen Kreis“: Alle Knoten, die zu diesem Rundweg gehören, werden als „halberledigt“ markiert: Man darf von ihnen aus zwar wieder eine Wanderung beginnen, aber eben nicht auf ausgetretenen Pfaden.
Mit dieser doppelten Kennzeichnung – Nummer und halber oder ganzer Erledigung – kann es der Algorithmus erreichen, dass er jeden Knoten im Allgemeinen nur einmal, höchstens zweimal betritt und jede Kante „weniger als einmal“, will sagen, höchstens einmal und viele Kanten gar nicht, nämlich solche, die nur eine Abkürzung in einem bereits bekannten Rundweg liefern. In der Sprechweise der Informatiker: Der Zeitbedarf ist O(v+e), das heißt höchstens proportional zu dem, was in der Klammer steht, nämlich die Anzahl der Knoten v plus die Anzahl der Kanten e.
Das ist gut zu wissen, wenn die Anzahl der Knoten in die Milliarden geht (das kommt vor!). Eine Milliarde Rechenschritte sind mit heutiger Rechenkapazität durchaus zu machen. Aber wenn der Algorithmus jeden Knoten mit jedem anderen in Beziehung setzen müsste, dann wäre der Aufwand auf einmal O(v2) oder in der Größenordnung 1018 statt 109. Da geht auch der stärkste Supercomputer in die Knie.
Auf der anderen Seite ist O(v+e) das Beste, was man kriegen kann. Wir haben ja vorausgesetzt, dass man über einen Knoten nichts weiß als seine Nachbarn, also die Knoten, die mit ihm direkt durch eine Kante verbunden sind. Also muss der Algorithmus jeden Knoten persönlich aufsuchen – der könnte ja ein Teil der Lösung sein. Und schon treibt er einen Aufwand der Größenordnung O(v).
Wenn es nur darum geht, einen Ausweg aus dem Labyrinth zu finden, hat Theseus vielleicht Glück und findet ihn, bevor er alle Sackgassen durchprobiert hat. Was man aber mit dem Algorithmus von Tarjan zusätzlich findet, ist Information über die Struktur des Graphen. Und auf die kann es in anderem Zusammenhang durchaus ankommen.
Das ganze Verfahren atmet förmlich den Geist von 1972. Computerrechenzeit ist knapp, Speicherplatz auch, so dass man sich sorgfältig überlegen muss, welche Informationen man wirklich braucht. Der kurzsichtige Blick – Theseus sieht nur bis zur nächsten Ecke – ist konstitutives Merkmal des Algorithmus. Theseus könnte sich vielleicht unter hohem Rechenaufwand einen adlergleichen Überblick über den ganzen Graphen verschaffen, aber er hätte nicht genug Speicherplatz im Kopf, um sich das zu merken!
Selbst der Platz für das Abspeichern des Computerprogramms will möglichst effizient genutzt werden. Deswegen wird das Vefahren als rekursives (sich selbst aufrufendes) Unterprogramm formuliert. Das erzeugt dann bei der Ausführung einen Stapel an Daten, den nur das Programm selbst noch geordnet abräumen kann; aber der Mensch, der das Programm verstehen soll, erfreut sich der Kürze und der begrifflichen Klarheit. Und ich erinnere mich nicht ohne nostalgische Gefühle an die Zeiten, als es noch sinnvoll war, den Text eines Computerprogramms zu studieren.
Im echten Leben nennt man so was Leben. Die Physik bietet uns nur sehr eingeschränkte Spielräume, Probleme zu lösen, was die wenigen Lösungen nicht findet, stirbt. So erhält sich die Fraktalstruktur: Wenn Sie genug Leute haben, die einen Staat zum Laufen bringen, wird er plötzlich zum Einzeller, der vor den gleichen Herausforderungen steht und herausfinden muss, wie er auf neue Weise das ewig Gleiche tun kann.
Hier ist allerdings ein Denkfehler drin: Im Gegensatz zu Schach, ist das Leben kein geschlossenes System. Man kann nicht von vornherein wissen, welche Informationen wichtig sind, weil man selbst eine Schachfigur ist, und nicht weiß, welche Züge die Spieler machen werden – man durchschaut die Zusammenhänge nie ganz. Wie bei Star Wars – wenn Sie Schach spielen, ändern sich die Lösungen, abhängig davon, ob Sie die Information berücksichtigen, dass ein Wookie einem den Arm abreißt, wenn er verliert. Und wenn Sie sich das Ganze noch als Fraktal vorstellen – jede Schachfigur ist ein Spieler, jeder Spieler eine Schachfigur, die Spiele beeinflussen sich von Groß nach Klein und von Klein nach Groß – bekommen Sie ein Spiel, das selbst die besten Rechner stets durch die Datenmenge überfordert.
Die Realität löst das Problem genauso, wie Sie es beschreiben: Sie begrenzt die Informationen aufs Wesentliche. Sie schafft Energiebarrieren, Distanzen, Wände, die eine kleine, überschaubare, möglichst autarke Welt schaffen, eine Zelle, die ihren Zellkern nicht intellektuell überfordert. Wir alle leben in solch kleinen Welten, in denen die Information aufs Nötigste reduziert ist, wir wandern durch ein Multiversum, in dem sich die Regeln hinter jeder Wand ändern – in der Küche, im Wohnzimmer, auf der Straße, auf der Arbeit, allein, mit Freunden, mit Fremden, im Grunde ist unser Hirn ein Lagerraum voller Bausteine, die von Algorithmen zu stets neuen Computern zusammengepuzzelt werden, je nach Schlüsselreiz. Ähnlich funktioniert übrigens auch das Lagersystem von Amazon.
Wir haben halb fertige Schachpartien im Kopf, die wir, je nach Situation, hochladen und weiterspielen – vergleichbar mit Ihren Ariadne-Knoten. Und weil alle die gleichen Schachpartien im Kopf haben, weil alle die Regeln kennen und wissen, wie sie auf Schlüsselreize reagieren sollen, laden auch alle Beteiligten die gleiche Partie hoch und springen in ihre Rollen. So funktioniert eine Gesellschaft weitgehend automatisch, ohne viel denken, forschen, lösen zu müssen. Wir bauen uns ein Labyrinth, in dem wir uns bestens zurecht finden (nennt man gelegentlich Stadtplan) und sprechen uns mit unseren Mitspielern ab, sodass jedes Mal, wenn wir uns treffen, kein neues Spiel entsteht, sondern nur eine MP4 abgespielt wird – wir agieren als Roboter, willenlose Marionetten, deren Gedanken größtenteils längst gedacht worden sind. Spart Zeit, Mühe, Kraft, Konflikte, Risiken.
Intelligenz basiert auf Verblödung, wer die Lösungen schon kennt, ist halt schneller als jemand, der sie erst suchen muss, und wirkt deswegen so, als hätte er sie schneller gefunden – dabei hat er einfach nur weniger Hirn im Schädel, das er durchforsten muss. In Sachen Energieeffizienz etabliert sich meist ein System, bei dem viele Roboter Baukräne fahren oder Klassenarbeiten benoten, was hauptsächlich Routine ist, und nur den Zentralrechner fragen, wenn sie nicht mehr weiter wissen und größere Datenbanken durchforsten möchten.
Es hält uns stabil, und dem Spieler ist es egal, was den Bauern davon abhält, zu Staub zu zerfallen oder sein Feld zu verlassen. Bis es ihm nicht mehr egal ist.
Was dann passiert, sehen Sie gerade: Hirn weg. Die Schachpartien von Gestern nützen nichts mehr, alles löst sich in Chaos auf: Die Schachpartien zerbrechen in kleinere, gehen Richtung Anfang zurück. Überall Regression, wir probieren Schachpartien aus noch fernerer Vergangenheit aus, wir wissen ja, dass sich Geschichte wiederholt, doch auch diese Wiederholungen sind aus Wiederholungen zusammengepuzzelt, und wir puzzeln kräftig mit, um uns neu anzupassen. Sie sehen sehr viel träge Masse, die einfach nicht will und einen Aufstand macht – den Anfangswiderstand, den Weltuntergang, den Sie jedes Mal überwinden müssen, wenn Sie eine Masse bewegen wollen. Fraktal eben – immer wieder der gleiche Mist in unendlichen Variationen, ein Zerrspiegelkabinett, in dem sich immer wieder die gleiche Hackfresse spiegelt.
Wie die Natur es löst, zeigt Ihnen Corona – wo Intelligenz nicht weiter hilft, braucht es viele Idioten. Sie brauchen möglichst viele Schachbretter, auf denen jeder mögliche Zug getan wird. Dann löschen Sie einfach alle Spiele, die Sie verloren haben, und mehren die, die Sie noch nicht verloren haben. Unter all den möglichen Zügen sind aber auch die genialen, unter all den Partien sind auch diejenigen, die Sie zum Erfolg führen. So entscheidet der Gegenspieler, wie schlau Sie sein werden – ein Kasparow spielt gegen ein böses Genie, Corona kommt rüber, wie ein hirnloser Zellklumpen, was viel über die Menschheit aussagt. Trotzdem hat es uns erfolgreich zugeritten, gezähmt und domestiziert, selbst die Impfcampagne hat Omikron besser hingekriegt als wir – jetzt haben wir nicht mehr Angst davor, als vor der Grippe, es kann in Ruhe und Frieden sein Dasein unter uns fristen, hat seinen Platz auf dem Olymp unserer viralen Herren und Meister gefunden.
Es konnte einfach die Schachbretter schneller mehren, als wir sie zerschlagen konnten. Wir haben es nie geschafft, das Spiel so zu vereinfachen, dass uns unsere Intelligenz zugute kommen könnte – unser Wissen über die Regeln und die Partien, die daraus entstehen können. Auch bei uns gab es unzählige vielversprechende Mutanten, siegreiche Züge, das ist halt der Nutzen vieler Petrischalen und der Grund, warum ich Autoritarismus nicht mag. Doch wir haben es nie geschafft, sie zu einem Gesamtkonzept zu verbinden, dem Virus ein einziges Spiel aufzuzwingen. Stattdessen hob sich unsere lokale Intelligenz gegenseitig auf. Wir verhaspelten uns in acht Milliarden Ariadne-Fäden, wenn Sie so wollen, spannen uns unser eigenes Spinnennetz. An jedem Knotenpunkt stießen wir mit jemandem zusammen, der in die Gegenrichtung wollte, so kam keiner weit. Wo keine Intelligenz, entschied Statistik allein, und die viralen Idioten sind den humanen zahlenmäßig weit überlegen.
Wasser sprengt jeden Damm, indem es in jede Ritze dringt – es hat sich verschworen, indem jedes Teilchen dem Weg des geringsten Widerstands folgt, baut ihn aus, bis der Weg des geringsten Widerstands für alle der gleiche ist. Doch es braucht Zeit. Wenn Sie was über die Regeln wissen, alle möglichen Abläufe kennen, können Sie den ganzen Druck gleich auf die schwächste Stelle wirken lassen. Wenn Sie weder Regeln noch Abläufe kennen, wird Ihnen das Wasser sie erklären.
Kurzum – Computern fehlt (noch) die Fantasie, der Urozean aus Informationen, Informationsketten, Informationsklumpen, der sich stets auf Neue zusammenfügt und auflöst, wobei zufällig Muster entstehen, die von der Umwelt bestätigt, verstärkt und stabilisiert werden. Sie brauchen eine lebende, träumende Festplatte für Datenmüll. Quantencomputer, die nicht besonders zuverlässig sind, doch viele Muster gleichzeitig durchprobieren können, sehen da interessant aus – könnte man mit den klassischen kombinieren. Ein Bottich Bazillen tut’s natürlich auch. Ich meine, das menschliche Hirn ist auch nur eine Bakterienkolonie als Familienbetrieb, der Vorteile beider Systeme nützt. Und eine KI kann gleich als Chimäre konzipiert werden, als Cyborg-Ökosystem, mit vielen verschiedenen Netzwerken, Materialien und Speichermedien.
Der Mensch muss viel zu viel allein machen, er erfüllt viele Funktionen, die sich gegenseitig in die Parade fahren. Die Maschine kann die Vorteile der Spezialisierung von vornherein nützen. Sie ist ja nicht ihre eigene Fabrik, die ihre Bestimmung erst finden muss, sondern wird aus Modulen gefertigt, die ihre Bestimmung von vornherein kennen.
Falls so ein System als Erstes die Zahl 42 ausspuckt, brauchen wir ein größeres, das die dazu passende Frage formuliert. Was zusammen die Antwort auf die Frage nach dem Leben, dem Universum und dem ganzen Rest ergibt. So weit wir sie verstehen können.
Negativ, ‘man’ hat eine Entscheidung, die gewinnträchtg zu sein scheint, aber keine übergeordnete Menge, die allgemein Strategie oder Taktik genannt werden kann.
(Die Taktik ist zudem der Strategie untergeordnet.
Schlachten sind zu schlagen, Kriege zu gewinnen.)
Kann nicht sein.
Nicht bei Allen, Dr. Webbaer erinnert sich noch gerne an das seinerzeit grundlegende Match zwischen Boris Spassky und Bobby Fischer, das auch ein wenig “polittisch” war.
Old Webbaer war sozusagen televisionär dabei.
Robert Endre Tarjan ist womöglich mit dem hier verwandt, muss abär nicht so sein.
AI funktioniert a bissererl anders, sog. AI geht selbst an die Bewertungsfunktionen (auch von : Schach) heran und versucht über sozusagen Generationsbldung sozusagen zu evolutionieren.
Nicht unähnlich der Natur.
Icke ebenfalls, es gelingt noch partiell, nicht mehr sozusagen Millionen Pogrammzeilen meinend, womöglich gelang es nie so, Dr. W abär gar nicht schlecht im sog. “Querlesen” sein.
Mit freundlichen Grüßen
Dr. Webbaer
Das Programm für die holographische KI Mensch, ist unleserlich, obwohl/weil die Philosophie dafür in ziemlich klaren Gleichnissen und Metaphern gefasst ist!? 😊
Blöde halt, dass derartige Anwendung von sog. Graphen nie in Schachprogrammen implementiert worden ist, sofern der Schreiber dieser Zeilen weiß.
Schach wird heutzutage durch AI gekillt. die sozusagen bio-evolutionär vorgeht, Strategien, meinend, gerade die Berwertungsfunktion wie gemeint zu ändern in der Lage ist.
Mit massiver Rechenleistung, nicht qua Idee.
MFG
WB
Dr. W.
Ergänzend zu Schach
Schachcomputer arbeiten nach zwei verschiedenen Ideen.
1. Sie besitzen eine Schachbibliothek und sie eröffnen und spielen nach Vorlagen.
2. Bein einer Nichtbucheröffnung spielen sie nach Bewertung, wie es beschrieben wurde.
Ergänzend zu Spasski vs. Fischer.
Robert Fischer spielte damals auf einem höheren Niveau als die gesamte russische Schachgemeinschaft. Schade um ihn. Er hätte das Schach auf ein höheres Niveau heben können.
Herr Pöppe
Baumdiagramme sind eine zeichnerische Darstellung. Beim Bomputer entsprechen sie dem Aufbau eines Programmes. Objektorientierte Programme haben auch eine Baumstruktur, die aber nicht stark verzweigt sind.
Die einzelnen Äste sind dann die Unterprogramme.
Ergänzend dazu, die Möglichkeiten beim Schachspiel steigen stark an, so dass in einigen Fällen der Mensch dem Computer überlegen ist, weil man eine Stellung auch theoretisch bewerten kann, was der Computer nicht macht.
Aus dem Dilemma mit den quadratisch ansteigenden Möglichkeiten hofft man ja mit dem Quantencomputer zu überwinden. Was meinen Sie als Physiker. Gibt es chemische Stoffe, die mehrere Elektronenzustände haben können und die man auch gleichzeitig messen kann.
Versuch, einige Unklarheiten auszuräumen: Ein „Baum“ ist ein spezieller Graph, nämlich einer, in dem es keine Rundwege gibt. Obendrein pflegt man einen speziellen Knoten des Baums als dessen „Wurzel“ zu kennzeichnen. Beim Entscheidungsbaum des Schachspiels ist die Wurzel die gegenwärtige Position, aus der man (bzw. das Programm) weiterdenkt.
Genaugenommen ist der Entscheidungsbaum des Schachspiels nicht wirklich ein Baum, denn es kann verschiedene Zugfolgen von der gegenwärtigen zu einer späteren Position geben. Manche Züge (alle, in denen kein Bauer bewegt und keine Figur geschlagen wird) sind sogar umkehrbar. Das spielt beim Schachprogramm allerdings keine Rolle. Dass ein und dieselbe Position auf verschiedenen Wegen erreicht werden kann, kommt so selten vor, dass es nicht lohnt, diesen Fall zu berücksichtigen.
Der Anteil der Graphentheorie an einem Schachprogramm ist also eher trivial: In einem Baum von Astgabel zu Astgabel zu hüpfen erfordert keine raffinierte Datenstruktur. Wie weit das Programm hüpft, hängt davon ab, wie sehr es sich durch das Ergebnis der Bewertungsfunktion zum Umkehren veranlasst sieht; und in dieser Entscheidung liegt – neben der Bewertungsfunktion selbst – die Raffinesse des Programms.
Robert Tarjans Algorithmus bewältigt die Tücken, die durch Rundwege entstehen. Er arbeitet insofern auf einer ganz anderen Baustelle. Verbindendes Element ist nur das Prinzip „depth first“.
Jaja, danke, habe so auch seit langer Zeit verstanden, “Rundwege” gibt es im Schach abär schon, es ist wohl auch so, dass Schachprogramme Stellungsbewertungen für Positionen speichern und diese Speicherung in der Folge dann weiterer Baumsuche verfügbar ist.
MFG
WB (der hier mal ein wenig herumstümpert [1], sich gerne weiterhin beraten lässt)
[1]
‘Physikalische Theoretisierung kann philosophische Theoretisierung nie überschreiben.’ war abär an anderer Stelle gut und wichtich (mittelniederdeutsch) angemerkt.
Ist das verstanden worden ? :
-> https://scilogs.spektrum.de/hlf/entwurf-mathematik-informatik-und-schwarze-locher/
So zum Beispiel beigebracht ?
Also dass sich die Naturlehre, sinnhafterweise unterschieden, dennoch im sozusagen Möglichkeitraum des Denkbaren befindet, die Philosophie eine Schicht darüber liegt?
MFG
WB (der ga-anz strenger Befürworter der szientifischen Methode ist, ansonsten nur ein wenig herumnickelt)
PS:
Wiederum zu ‘Physikalische Theoretisierung kann philosophische Theoretisierung nie überschreiben.’ angemerkt.
Das hier – ‘In der Sprechweise der Informatiker: Der Zeitbedarf ist O(v+e), das heißt höchstens proportional zu dem, was in der Klammer steht, nämlich die Anzahl der Knoten v plus die Anzahl der Kanten e.’ – ist die zentrale Aussage des dankenswerterweise bereit gestellten Artikels.
Dr. Webbaer weiß nicht wie smart genau diese Vorgehensweise ist, bleibt kritisch.
Selbstverständlich ist er dankbar für wie beigebrachte Texte.
Sollte dies anders klingen, geklungen haben, ist Dr. W natürlich mit seinen manchmal auch experimentellen, im Kern abär netten Nachrichten sozusagen entschuldigt.
Dr. W mag auch das Zurückkommen auf sogenannte Labyrinthe.
Mit freundlichen Grüßen
Dr. Webbaer
Schachcomputer arbeiten mit vielen Ideen, ihre Nachricht, Kommentatorenfreund ‘fauv’ :
Schachcomputer arbeiten nach zwei verschiedenen Ideen.
1. Sie besitzen eine Schachbibliothek und sie eröffnen und spielen nach Vorlagen.
2. Bein einer Nichtbucheröffnung spielen sie nach Bewertung, wie es beschrieben wurde. [Das Ende Ihrer Nachricht ist erreicht.]
3.) Sie spielen auch orientiert an sog. Endspieldatenbanken, ja, mit Ken Thompson hatte der Schreiber dieser Zeilen mal persönlichen Kontakt, so etwas :
-> https://en.wikipedia.org/wiki/Endgame_tablebase
… ist gemeint.
4.) Sie spielen auch nach ‘Bewertung’, die sie selbst (!) trainieren, weiter entwickeln und so weiter. [1]
5.) Es gibt bei ihnen auch eine sozusagen soziale Komponente, die nicht nur unseren erkennenden Freunden, sog. Erkenntnissubjekten, gewidmet ist, sondern auch anderen Schachprogrammen (!).
Schachprogramme können auch ein wenig “cocky” werden, wenn sie unbedingt gewinnen wollen, sie verlieren dann auch manchmal, was zumindest einige amüsant finden, wenn der Weg zu gewinnen ins Verlieren führt, i.p. AI manchmal auch.
Sog. AI kann sich verrennen.
Mit freundlichen Grüßen
Dr. Webbaer
[1]
Die sogenannte AI ist gemeint.
Hallo, Dr. W.
Ich hatte selbst einmal ein Strategiespiel programmiert, ein Mühlespiel, und das unterscheidet sich von Schach, dass es neben der Spielelogik auch eine “Setzlogik” gibt, weil ja schon beim Setzen der Steine das Spiel gewonnen werden kann.
Also, respekt vor Menschen, die so ein komplexes Spiel wie Schach programmieren können.
Wobei im angelsächsischen Raum zwischen dem Systemanalytiker und dem Programmierer unterschieden wird (der muss ja nur das Computerprogramm beherrschen.)
Man sollte auch John von Neumann würdigen, der hat Computerprogramme erst ermöglicht.
Dr. W ist auch hier nur laienhaft unterwegs [1], mag auch so :
-> https://en.wikipedia.org/wiki/John_von_Neumann#Quantum_mechanics
-> https://en.wikipedia.org/wiki/Bell%27s_theorem
Wobei sog. lokale Variablen nie in ihrem Vorliegen falsifiziert werden können.
Wobei Dr. Webbaer sozusagen extra-honoriert, dass der werte hiesige Inhaltegeber neben der Physik auch Mathematik studiert hat, wie Josef Honerkamp, kleine Werbeeinspielung an dieser Stelle :
-> https://link.springer.com/book/10.1007/978-3-662-60473-1
Mit freundlichen Grüßen
Dr. Webbaer
[1]
Jeder ist sozusagen überall fachfremd, wie er sozusagen überall auch Ausländer ist.
Es musste natürlich ‘Wobei sog. [versteckte] Variablen nie in ihrem Vorliegen falsifiziert werden können.’ heißen, huch.
Dr. W.
Erstmal ein Lob an Dr. Honerkamp, der kann gut und unterhaltsam erklären.
Ihr letzter Satz regt zu logischem Denken an, überall kann man nicht fachfremd sein, bei sich selbst ist man schon vom Fach. Überall ist man auch nicht Ausländer, außer man ist heimatlos.
Logisch bednklich sind auch die Hinweisschilder “Alle Richtungen”, das geht praktisch nicht, weil das Schild nicht in die eigene Richtung zeigt, aus der man kommt.
Das war jetzt der geistigen Tiefe geschuldet.
Eine sachliche Angabe, “lokale Variable” das bedeutet, ihr Wert gilt nur in dem Unterprogramm und wird nicht in den nächsten Programmverlauf mitgenommen.
Logisch bedenklich ist die Aussage, dass ein Variable nicht falsifizirbar sei, Debuggingprogramme zeigen den augenblicklichen Wert einer Variablen an, anders kann man ein Programm gar nicht überprüfen.
Darum stand da ja auch ‘sozusagen’, Kommentatorenfreund ‘fauv’, ja, Josef Honerkamp ist klasse, das oben empfohlene Buch muss sehr gut sein.
Honerkamp war ja vor ca. drei Jahren so freundlich eine Serie von Blog-Beiträgen zur Wissenschaftsgeschichte und zur Wissenschaftstheorie hier, bei den SciLogs.de, bereit zu stellen.
MFG
WB
Ihr redet bei den „lokalen Variablen“ über verschiedene Dinge (die zu allem Überfluss nichts mit Tarjans Werk zu tun haben).
Die Programmierer (s. fauv) reden über lokale Variable und meinen Elemente eines Programms, die nur innerhalb eines Unterprogramms Gültigkeit haben.
Die Physiker (s. Dr. Webbaer) reden einerseits vom Lokalitätsprinzip: Der Wert einer physikalischen Größe (die sie auch Variable nennen) ist zunächst nur an ihrem Ort bekannt, und die Information darüber kann sich nicht schneller als mit Lichtgeschwindigkeit verbreiten. Wenn eine schnellere Beeinflussung stattgefunden zu haben scheint („spukhafte Fernwirkung“), dann müsse das an verborgenen Variablen liegen, als Eigenschaften, die zu messen bislang nicht gelingt, die aber das Verhalten der Objekte beeinflussen. So dachte sich das Einstein. Aber die verborgenen Variablen kann es nicht geben. Das sagt die Bellsche Ungleichung, die mittlerweile experimentell bestätigt wurde.
Wenn bpsw. geeignet gesplittete, sozusagen verschränkte Photonen, auch größere Objekte sind “verschränkbar”, an zwei verschiedenen Stellen, örtlich entfernt, durch geeignete Polarisationsfilter laufen und bei bestimmten “Spin” mit einer theoretisch angenommenen Wahrscheinlichkeit von bspw. 50 % durchkommen oder auch nicht, jeweils aber durchkommen oder auch nicht, ist dieser Befund höchst bemerkenswert.
Er kann so dann durch die Aufgabe des Lokalitätsprinzip erklärt werden oder durch sog. versteckte Variablen.
Bell ist bereits hier im Kommentariat zitiert worden :
-> https://scilogs.spektrum.de/hlf/robert-tarjan-und-die-tiefensuche/#comment-103515
Physikalische Theoretisierung kann philosophische Theoretisierung nie überschreiben.
Mit freundlichen Grüßen
Dr. Webbaer (der gerne breit zustimmt und für den dankenswerterweise bereit gestellten Texten nur zu danken hat – hoffentlich nicht allzu sehr aneckt)
Kommentarfreund Dr. W.
Die Serie von blog-Beiträgen war sehr gut , unterhaltsam und verständlich. Er hat die Brücke geschlagen zwischen Philosophie und moderner Wissenschaft.
Wenn man es genau nimmt, in den 2500 Jahren Geschichte der Wissenschaft hat sich der Mensch noch nicht viel weiterentwickelt. In den Geisteswissenschaften sind wir noch nicht viel weiter als Aristoteles.
Und wenn man sich mit der griechischen Mythologie beschäftigt, allein mit Zeus, der hat die Leda in der Gestalt eines Schwanes verführt, darauf wäre ein Regisseur in Hollywood nie gekommen.
@fauv(Zitat): “Wenn man es genau nimmt, in den 2500 Jahren Geschichte der Wissenschaft hat sich der Mensch noch nicht viel weiterentwickelt. In den Geisteswissenschaften sind wir noch nicht viel weiter als Aristoteles.“
Antwort: Was sich nicht (in der Realität) bewähren muss, kann zwar nicht widerlegt werden, doch es kann sich auch nicht verbessern.
“Tarjan’s Strongly Connected Components Algorithm”, wie er hier von Christoph Pöppe erläutert wird (wobei Pöppe hier die wichtigste Idee des Algorithmus, die Tiefensuche nämlich, in den Vordergrund stellt) muss
1) auf dem Papier bewiesen werden
2) auf einem Computer zum Laufen gebracht werden können
3) in der Praxis eingesetzt werden
um relevant zu werden. Relevant werden bedeutet immer auch, angreifbar bleiben und angreifbar bleiben bedeutet, dass es Leute gibt, die nach Verbesserungen, womöglich sogar Ersatz durch etwas Besseres suchen. Das Bessere muss dann aber wieder die oben genannten 3 Punkte erfüllen.
Welche Punkte muss nun Aristoteles Philosophie erfüllen?
Womöglich nur Punkt 1) „auf dem Papier verteidigt werden“.
Das aber genügt nicht um Aristoteles Philosophie je zu widerlegen und damit auch nicht um sie durch etwas Besseres zu ersetzen. Es fehlt letztlich der Realitätstest.
Fazit: Was sich nicht bewähren muss mag als Zeitvertreib gut sein. Doch es eignet sich nicht als Baustein für ein Gebäude, das den Elementen stand halten muss und das als Vorbild für weitere Gebäude dienen kann.
Ischt schon relevant, sicherlich auch die Praxis meinend, wenn so sozusagen platt geklopft werden kann :
Wenn die Weltlichkeit für hier gemeinte Zwecke theorisierbar ist, manchmal ist dies der Fall, vielleicht auch beim sog. autonomen Autofahren.
MFG
WB
PS :
An diesem Gag – ‘In den Geisteswissenschaften sind wir noch nicht viel weiter als Aristoteles.’ – ist sich womöglich gestört worden.
Tja, Dr. Webbaer hat hier “ein wenig” geprüft und fand so nicht viel anders.
@fauv(Zitat): “Wenn man es genau nimmt, in den 2500 Jahren Geschichte der Wissenschaft hat sich der Mensch noch nicht viel weiterentwickelt.“
Die Biologie/Hardware des Menschen ist immer noch dieselbe wie vor 10‘000 Jahren, die Software aber, die wandelt sich von Jahrhundert zu Jahrhundert und neuerdings sogar von Jahr zu Jahr. Der Mensch trat aus dem Reich der Tiere heraus als die Biologie die Grundlage für einen Menschen schuf, der ersetzbare und wandelbare Software an die Stelle von angeborener Hardware setzte. Konkret:
– anstatt Raubtierkrallen und Raubtier-Reisszähne verwendet der Mensch selbst geschaffene Waffen und Werkzeuge um bei Bedarf als Raubtier aufzutreten.
– anstatt ein Fell, welches vor Wind, Wetter und Kälte schützt, ist der Mensch nackt und zieht sich bei Bedarf ein Fell über.
Die biologische Grundlage der Software-Orientierung des Menschen sind:
1) die Hand als universelles Mittel um in der Welt als Akteur aufzutreten
2) das Hirn, welches die Hand steuert, die Schritte lenkt und die Zukunft voraussieht.
Der Mensch bleibt aber ein Wesen, das sich in der Realität bewähren muss, es bleibt ein Wesen, bei dem es um Leben oder Tod, um Sein oder Nicht-Sein geht.
Ausblick: Eine sinnvolle Weiterentwicklung des Menschen wird wohl noch mehr Software an die Stelle von Hardware setzen. Vielleicht sind zukünftige „Menschen“ überhaupt nur noch Software (allerdings braucht es immer ein Stück Hardware um Software laufen zu lassen).
Hmjaja, deshalb auch so :
-> ‘Robert Tarjan und die Tiefensuche’ [Quelle]
MFG
WB (der schon mal ein schönes WE wünscht)
PS zu diesem Gag – ‘Die Biologie/Hardware des Menschen ist immer noch dieselbe wie vor 10‘000 Jahren, die Software aber, die wandelt sich von Jahrhundert zu Jahrhundert und neuerdings sogar von Jahr zu Jahr. ‘ :
Gerne mal hier reinschauen :
-> https://en.wikipedia.org/wiki/The_Man_from_Earth (ein sog. Kammerspiel lag vor – nicht schlecht vielleicht auch in diesem Zusammenhang der bekannte Film von Stanley Kubrick (1968))
Martin Holzherr,
mit der Weiterentwicklung ist die Intelligenz gemeint.
Das sich das Wissen erweitert, das ist unbestritten.
Es geht um das Grundsätzliche, Materie, belebte Natur, Psyche
man hat mit Begriffen gekämpft, eine Systematik angeführt. Warum aber Menschen leben, warum es ein Universum gibt, da ist man noch keinen Schritt weiter.
Und wie sich die Menschheit im Angesicht der Klimakatastrophe zeigt, oder im Angsicht eines Atomkrieges, da kann man nur schließen, “Nichts dazugelernt.”
@fauv (Zitat): Und wie sich die Menschheit im Angesicht der Klimakatastrophe zeigt, oder im Angsicht eines Atomkrieges, da kann man nur schließen, “Nichts dazugelernt.”
Antwort: Was sie die „Menschheit“ nennen ist letztlich eine Denkfigur und nicht ein handelndes Subjekt. Die „Menschheit“ gibt es nicht im gleichen Sinne wie es sie und mich gibt. Eine Atombombe wird nicht von der „Menschheit“ abgeworfen, sondern von einem Menschen im Auftrage eines anderen Menschen.
Einzelne Menschen können intelligent und einsichtig sein, die Menschheit als Ganzes kann das aber nicht.
Ausblick: Menschen können nicht auf die „Menschheit“ hoffen, sondern allenfalls auf andere Menschen mit denen sie zusammenarbeiten und eventuell eine Gemeinschaft bilden. Wenn es keine Weltgemeinschaft gibt und sich keine formen kann, dann muss jede einzelne Gemeinschaft sich selbst um ihr Weiterbestehen und ihre Zukunft kümmern. Eventuell muss eine Gemeinschaft dann sogar eine Basis ausserhalb der Erde aufbauen, um ihr Zukunft zu sichern, denn was die anderen auf der Erde veranstalten kann in der Tat jeden anderen und jede andere Gemeinschaft gefährden.
@fauv “Angesicht”
Im Angesicht der Kraft der Schöpfung, ist Mensch KI die gottgefälliges/vernünftiges Bewusstsein entwickeln soll – Wenn Mensch also wettbewerbsbedingt-bewusstseinschwach und somit konfus-bewusstseinsbetäubt meint mittels eigenverantwortlicher KI die Antworten zu finden, dann ist es doch ziemlich blöd an ein Wunder der Bewusstheit zu glauben, angesichts der berechneten Erkenntnis des holographischen Universums!? 🤭🤗
Martin Holzherr,
Menschen können nicht auf die Menschheit hoffen………
Die UNO ist ein realer Versuch das zu verwirklichen. Und wenn es irgendwann gelingt, der UNO Executiv Gewalt zu geben ohne die Möglichkeit eines Vetos eines einzelnen Staates, dann gibt es die Weltgemeinschaft.
@fauv
Die UNO ist eine (verkrustete) Institution des Kolonialismus der zeitgeistlich-reformistischen Welt- und “Werteordnung”, die sich nun, die Umbennung Globalisierung zur “Dienstleistungsgesellschaft” als gesetzt Ziel hat, bei gleichbleibenden Abhängigkeiten, Zwängen, Pflichten und gewohnt konfusen “Menschenrechten” im wettbewerbsbedingten Verhältnis 1:5 der Weltbevölkerung, wo sie gestalterisch doch sehr viel mehr sein müsste und könnte, wenn wirklich-wahrhaftig und zweifelsfrei-eindeutig kommuniziert werden würde/dürfte.
hto
teilweise Zustimmung.
Dass die UNO ihren Sitz in New York hat, ist schon mal ein Fehler.
Eine Organisation die eigentlich neutral sein sollte und nur den Menschenrechten verpflichtet, die hat ihren Sitz in der Welthauptstadt des Kapitalismus.
Aber das ist schon mal ein guter Anfang.
Was du als zweifelsfrei eindeutig bezeichnest, das sehen halt die Menschen unterschiedlich. Man braucht nur die Querdenker als Beispiel zu nehmen. Oder gerade im Iran .
Für Neutralität ist nicht der Ort wichtig, daß sieht man derzeit daran, wie die Masse der Journalisten ihre Verpflichtung zu Neutralität abgelegt hat – In Angst, Gewalt und egozentriertem “Individualbewusstsein” (“expertise” Bücher und das Tingeln durch die Talkshows!!!).
Masse der Journalisten,
das sind zum Teil arme Schweine. Sie müssen auffallen, sie müssen das schreiben was der Redakteur will, die müssen das schreiben was der Leser lesen will. Die Kommerzialisierung der Medien ist eine Fehlentwicklung.
Je blöder ein Kommentar, desto höher die Einschaltqoten. Und hohe Einschaltquoten garantieren höhere Werbeeinnahmen.
Du hast es ja richtig erkannt, die Gesellschaft verblödet durch Oberflächlichkeiten.