Unbounded 1.3

Wrote a GDK version of Unbounded‘s drawing. Now it’s compile-time-selectable whether the drawing uses Cairo or GDK (Cairo is used if it is available).

The main benefit is that Unbounded compiles on Sarge, though it still requires gtk2hs, which is not in Debian, at build time.

Released Unbounded 1.3. Packaged it, too, but only unofficially. Downloads are here. There is no aptable repository. The debs are signed with my Debian key, there is no separate Debian source. The debs require only stuff that is in Debian.

5 thoughts on “Unbounded 1.3

  1. Sigh.
    I read through some of the sources (probably version 1.2) as at some time I was very interested in unbound checkers. Unfortunately for me haskell seems to be very undiscoverable language. I could of course look through some tutorial and eventually figure it out, but there’s little of interest to me.
    So what I’m getting at, is this solution of solution finding totally recursively functional or is it some kind of iteration? How good a player AI is?

  2. I believe the proper answer to your question “is it totally recursively functional or is it some kind of iteration” is “yes”. 🙂 In a functional language, recursion and iteration are for the most part indistinguishable.

    What I do is, essentially, calcluate two metrics for each position and for each mark (X or O) and each direction (horizontal, vertical, and the two diagonals). The “positive” metric says that if I place this mark on this position, then this mark would have this long straight on this direction. The “negative” metric says, this is the longest possible straight you can hope to create on this direction so that this position participates in that straight. Then, based on these metrics, I calculate a score for both players for every position: for this position and this player, if the negative metric does not exceed K in any direction, then the score is zero; otherwise, take the two’s power of the positive metric on each direction and sum the results. The AI selects randomly among positions that get the maximum score for either player. (Here, K is the required length of a winning straight.)

    You will notice that “far away” from the “action”, the positive score is always zero and the negative score is always infinite. Hence, it suffices to only consider the area fairly close to existing marks. I take the bounding box of the existing marks and widen the area by 2K on both the horizontal and the vertical direction. Inside this area, I represent the board as an array containing for each position the mark or its lack and the value of the metrics on each direction. Each time a move is made, I recalculate the metrics from scratch. Most of the game code is insulated from this representation by an interface that pretends that I actually store the metrics and the marks for the whole infinite board.

    This approach is certainly not opimal (for example, it doesn’t even attempt to look beyond the current move), but it manages to challenge me (but I don’t claim to be a very good player myself:)

    As to Haskell being undiscoverable, that’s because it’s sufficiently differrent to not be just another clone of Pascal 🙂 My professional advice to everybody who is serious about programming is to learn at least three or four very different languages. Haskell may not be listed on your next job description, but learning it will make you a better progammer even in your other languages.

  3. Hi,

    I scanned through your “unbounded ” code, since I’m currently “learning haskell properly” after having studied it briefly at uni, and as I suspected it’s largely written in the semi-procedural sublanguage of Haskell. Do you find that most GUI / interactive programs end up like this? If this is the case, then what does one gain from writing such a program in haskell besides the nice type system?

  4. Properly functional GUI combinator libraries are currently a research topic, and a complex one at that. There are indications that it ought to be solvable, but nobody has made a practical library yet. Therefore, currently GUI code is imperative even in Haskell. As for most of the code being in the IO monad, that’s just because the GUI takes a lot more lines of code than the rest of it 🙂

    More generally, I suggest you read Simon Peyton Jones’s paper Tackling the awkward squad, which deals with exactly the question you raise. The following soundbite I just love: “In short, Haskell is the world’s finest imperative programming language.”

    There are a few things that the monadic approach to IO buys over what IO is in most other languages. One of the things is the ability to write your own control structures. In unbounded, I made heavy use of the monad library function mapM_, which I could have written myself (no magic), and which basically implements a foreach loop. (In fact, when I first wrote the code, I did not remember mapM_, so I wrote my code by using sequence_ and map; but that’s just manually inlining one possible definition of mapM_! And I’ve since tried to convert those to mapM_ as I notice them.)

    Outside the GUI itself, I found it fairly nice to be able to define an array recursively by calculating each element of that array as a function of other elements in the array. This is only possible because of laziness. Because it was possible, I could define the “model” declaratively, mainly by writing out the math that I described in an earlier comment. In just about any other language, I would have had to think a lot more about how to lay it out in terms of sequencing.

    I’m now thinking of adding a more powerful AI, one that actually looks ahead. Because unbounded is written in Haskell, I can decompose the problem into two parts: generate the full game tree, and consume those parts of the game tree that I need. The laziness in Haskell will make it so that only those parts of the tree that I actually use are computed.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.