Ich habe heute gestern seit langen mal wieder ein Gesellschaftsspiel gespielt: Rummikub. Rummikub ist wie Rommé nur ohne Karten. Besonders interessiert mich an solchen Spielen immer, ihre Reglen in Algorithmen zu fassen. Obwohl das Spielprinzip von Rummikub simpel ist, fällt es schwer einen effiziente Algorithmus zu entwickeln. Bei meinem Ansatz das Spiel auf einen Graphen abzubilden, dass die Rekursion ziemlich teuer werden könnte.
Einen viel versprechenden Ansatz gibt Hendrik Lübben in seinem Artikel Playing Rummikub using a “human based” approach. Mal sehen, ob ich es schaffe den Algorithmus in Mono zu implementieren. Ein so interessantes Projekt könnte mir den nötigen Anreiz geben endlich Mono/C# vernünftig zu lernen.
10Mrz07
Rummikub algorithmisch lösen
3 Comments
Leave a Reply
Using Gravatars in the comments - get your own and be recognized!
XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>
Gibt es hierzu etwas Neues? Was ist daraus geworden?
Ich bin leider noch nicht dazu gekommen etwas zu implementieren.
Aber eine brauchbare Info, wie sich das Problem mithilfe linearer Optimierung lösen lässt, findet sich hier:
http://agilejava.com/blog/?p=80
Deine Website gefällt mir übrigens.
vielen Dank. Eine ähnliche Formalisierung hatte ich auch in Arbeit. Mittels des LP’s hat man (hoffentlich) eine gute untere Schranke für ein Branch&Bound-Verfahren.