\documentclass[a4paper]{article}

\usepackage[latin1]{inputenc}
\usepackage[german]{babel}
\usepackage{hyperref}
\usepackage[top=2cm, left=2cm, right=2cm, bottom=2cm, a4paper]{geometry}
\usepackage{tikz}

\usepackage{haskell}
\lstset{firstnumber=last}

\title{Hangman-AI in Haskell}
\date{10.7.2006}
\author{Joachim Breitner}

\begin{document}
\maketitle

\begin{abstract}
In meinem \href{http://www.joachim-breitner.de/wiki/Info\_II\_Tutorium\_SS\_06}{Informatik-II-Tutorium} habe ich heute (mangels besseren Themen) gemeinsam mit meien Tutoranten ein Programm geschrieben, das relativ gut Hangman-Spiele, auch bekannt als Galgenmännchen, lösen können sollte.
\end{abstract}

\section*{Übersicht}

Die Logik des Programme ist folgende: Wir haben eine Liste von möglichen Wörtern. Aus dieser wählen wir jene aus, die nach dem aktuellen Wissenstandt (dem "`Pattern"') in Frage kommen und schauen, welche noch nicht gefragte Buchstabe kommt am häufigsten vor, und den Raten wir dann.

\section*{Die Worliste}
Die Wortliste habe ich auf meinem Debian-Sytem wie folgt generiert:
\begin{lstlisting}[language=bash,numbers=none]
cat /usr/share/dict/words |
	iconv -f latin1 -t utf8 |
	perl -n -p -e 's/ä/ae/ig; s/ö/oe/ig; s/ü/ue/ig;s/ß/ss/g;' > words
\end{lstlisting}

\section*{Der Code}

Erst einmal laden wir einige nützliche Funktionen
\begin{code}
import IO
import Char
import List

\end{code}


Dann brauchen wir eine Funktion, die schaut, ob ein gegebenes Wort (3. Parameter) noch in das Pattern (2. Parameter) passt, wobei Buchstaben, die im 1. Paramter vorkommen, nicht mehr hinzukommen dürfen.
\begin{code}
match seen [] [] = True   
match seen []  _ = False
match seen _  [] = False
match seen ('_':ps) (b:ws) | b `elem` seen = False -- Der Unterstrich ist der Platzhalter
                           | otherwise     = match seen ps ws
match seen (a:ps) (b:ws) = a == b && match seen ps ws

\end{code}

Eine weitere Funktion durchsucht die Worliste nach den Wörtern, die zum Pattern passen.
\begin{code}
myfilter pat list seen = filter (match seen pat) list



\end{code}

\lstinline-countb- ist eine Abkürzung für \lstinline-lenght $ filter (==b)-, die hoffentlich etwas schneller ist.
\begin{code}
countb _ [] = 0
countb b (x:xs) | b == x    = 1 + countb b xs
                | otherwise =     countb b xs

\end{code}	

Diese Funktion ist aus dem Übungsbetrieb bekannt, hier jedoch etwas effizienter implementiert, da die rekursive Variante, wie sie auf Abgaben vorkam, bei unserer Wortliste zu einem Stack Overflow führte. Das Ergebnis ist eine Liste von Tupeln mit der Häufigkeit des Buchstabens und dem Buchstaben selbst.
\begin{code}
count stat text seen = [ (countb b text, b)
				| b <- ['A'..'Z'],
				  b `notElem` seen ]

\end{code}				

Hier ist die Hauptfunktion, welche rekursiv für jeden Zug ausgeführt wird. Zuerst fragen wir nach dem Pattern, schauen, ob es überhaupt zum vorherigen passt (um ggf. nochmal zu fragen). Dann verkleinern wir die Worliste auf die noch möglichen Wörter. Bliebt nix mehr übrig, geben wir auf, kommt nur noch ein Wort in Frage, so geben wir dieses aus, ansonsten nehmen wir den häufigsten Buchstaben, und rufen uns selbst wieder rekursiv auf.
\begin{code}
denken liste seen' oldpat = do 
	putStrLn $ "Wie sieht das Pattern denn grad aus?"
	pat' <- getLine
	let pat = map toUpper pat' -- nachsichtige Eingabe
	if not $ null oldpat || match [] oldpat pat  -- oldpat ist am Anfang leer
		then do putStrLn "Nein, ich esse mein Pattern nicht, mein Pattern ess ich nicht!"
			denken liste seen' oldpat -- Wiederholung der Eingabe
		else do
	          -- Zeichen im Pattern sind "`gesehen"'
	let seen = seen' ++ [ b | b <- pat, b /= '_', b `notElem` seen']
	let filtered = myfilter pat liste seen
	if null filtered -- keine Ahnung mehr
		then    putStrLn "Ich gebe auf..."
		else do 
	if all (/='_') pat' -- Keine unbekannten mehr
		then putStr "Juhuuuh.\n"
		else do
	if null $ tail filtered -- nur noch ein Kandidat
		then    putStrLn $ "Ich löse: "++(head filtered)
		else do 
	if length filtered < 5 -- kleine Ausgabe bei wenig Kandidaten
		then putStr $ "Hmm, eigentlich nur: \n"++(unlines $ map ("    "++) filtered)
		else return ()
	let (_,guess) = last $ sort $ count [] (concat filtered) seen
	putStrLn $ "Ich kaufe ein "++(show guess)
	denken filtered (guess:seen') pat -- und weiterraten

\end{code}

Das Hauptprogramm läd die Wortlistendatei und macht daraus eine Liste von Wörtern aus Großbuchstaben, um dann obige Funktion ohne Pattern und gesehenen Buchstaben aufruft.
\begin{code}
main = do
	wortliste <- readFile "words"
	let woerter = map (map toUpper) $ lines wortliste
	denken woerter [] []

\end{code}
\section*{Fazit}

Das Ergebnis war zufriedenstellend. Das Programm war zwar nicht schnell, aber die Wartezeite nwaren nicht zu lange (dramaturgisch eher besser), und die Rategenauigkeit war gut. So brauchte das versammelte Tutorium für "`OMEGA"' 10 Buchstaben, das Programm nur 7\ldots 
\end{document}