Loading ...
Sorry, an error occurred while loading the content.
 

[article review] Mixing business with pleasure

Expand Messages
  • Nadav Har'El
    I m trying to start a new tradition here on hackers-il: a person reads a book or an article that are relevant to hacking , programming or computer science
    Message 1 of 8 , Apr 14 3:05 PM
      I'm trying to start a new tradition here on hackers-il: a person reads a book
      or an article that are relevant to "hacking", programming or computer science
      (but not requiring more than a basic foundation in computer science), and
      writes a review to the list.

      My first review is titled "Mixing business with pleasure", and it's about
      the article [1]:

      ROG-O-MATIC: A Belligerent[2] Expert System
      by Michael L. Mauldin[4], Guy Jacobson[5], Andrew Appel [3] and
      Leonard Hamey[6], Carnegie Mellon University

      Appeared at the Fifth Biennial Conference of the Canadian
      Society for Computational Studies of Intelligence, May 1984

      Most of you have seen Shlomi writing here enthusiastically about his
      freecell solver [7]. Now, imagine you could actually do serious research and
      get academic credit for messing around with your favorite game. Well,
      you don't need to imagine this! computer scientists have been "mixing
      business with pleasure" like that for years.

      The game whose research got most publicity is probably Chess (it's gotten
      such a media hype that IBM chose to spend millions on building a super-
      computer and software to play chess and beat the world champion).
      But people have also been researching how to solve other board games, such as
      Checkers, Backgammon and Go (the last one still doesn't have a good computer
      program to play it), and even Minesweeper [13]. My "Introduction to AI"
      teacher told us that the best research on game solving is done by people who
      love the game themselves; He said that he had a graduate student who was a
      very good Bridge player, and made good advancements in Bridge playing
      algorithms.

      The article [1] I'm reviewing here is about ROG-O-MATIC, a program which
      automatically plays the computer game of Rogue.

      What is Rogue, you might be asking? Well, many people might need an
      introduction so here it goes. Rogue [8] is a role-playing game where
      you wonder around a maze of rooms in various levels, trying to complete
      an almost impossible mission or survive as long as you can. While wondering
      around need to fight monsters that are trying to kill you, pick up useful
      objects (weapons, armors, magic potions, etc.) that help your quest, and
      building up experience and attributes (such as "hit points", "strength",
      and so on) which will help you fight monsters, carry more weight, and so
      on.
      Rogue was started around 1980, together with the "curses" library (see [8]
      for an historical overview). In fact its distinguishing feature was that
      instead of being text-oriented (like its predecessor "adventure") it was
      character-graphics oriented (using curses). You'd move your character (which
      looked like a "@") around the screen which showed a top-view of the current
      level, fight monsters (that looked like capital letters, e.g., a "B" was a
      bat) and pick up objects (which looked like !, $, ?, and so on - you can
      probably guess what the "$" was!). You'd typically have a lot of fun before
      some really nasty monster killed you (actually "winning" the game was
      nearly impossible, so most people just played for getting the maximum "gold",
      or score).
      According to [8], "Rogue became the undisputed most popular game on college
      campuses.". much of this is due to the fact that it was distributed with BSD,
      and later also with some versions AT&T's Unix (which is where I myself got
      to know this game, and also rog-o-matic, in 1985).

      If any of you want to play rogue, it's available for various systems in
      [9], and a nice Palm Pilot version [10] is also available. There are later
      games that are "rogue-like [11], such as Larn ([12] is the Palm version)
      and Nethack [13] which is most popular today (Redhat even includes its
      package, albeit with ugly QT graphics instead of ascii characters).

      But let's return to Rogue, and Rog-O-Matic, the subject of this article.
      The four guys who wrote Rog-O-Matics were some of the many people at CMU
      addicted to playing Rogue. So they decided to somehow bring together their
      profession (computer science) and hobby (rogue-playing) and write a program
      which automatically plays rogue. This was no easy feat: Rog-o-matic would
      need to interact with the same user-interface the ordinary human users would
      see (so that it could be played on normal versions of rogue). Also, Unlike
      games like Chess, in Rogue a lot of the gameplay depends on chance (you find
      random objects, fighting has some random aspects, and so on) and on things
      you don't know (invisible monsters, monsters hiding for you in the next
      room, and so on). You also have a large number of opponents (the monsters)
      that don't necessarily play for their own benefits (by definition, all
      monsters you meet in the game except the last one will be killed :)) and
      there's usually a huge number of things you can do at each turn.

      The article describes, very shortly and in simple terms, how Rog-O-Matic
      played Rogue. One nice feature of the game-playing branch of AI (and
      rogue playing in particular) is that it is easy to test your new program
      or algorithms: in this case they let Rog-O-Matic play rogue, and compared
      its scores to the scores of 15 people in CMU that played at least 10
      games over a two month period in 1983. Rog-O-Matic compared to the human
      players very favorably, and even got the highest median score of all players
      (but only the 7th best high score - I guess Rog-O-Matic was a consistently
      good player, but did not have "strokes of genius" (or just had bad luck)).
      It appears, by the way, that the human players in CMU were also very good,
      because I remember Rog-O-Matic was *much* better at rogue than I ever was...

      So this is not just an interesting article for AI aficionados (AI aficionados
      will find it severely lacking in detail, but that's why the source-code is
      available!), or for Rogue (or Nethack) addicts - it's also interesting to
      see how research can actually be fun, and even "cool" (in a geeky sort
      of way) :)



      -----------------
      [1] http://www.cs.princeton.edu/~appel/papers/rogomatic.html
      [2] http://www.m-w.com/cgi-bin/dictionary?va=belligerent
      [3] http://www.cs.princeton.edu/~appel/
      [4] http://www.fuzine.com/lti/vita.html
      [5] http://web.syr.edu/~rsholmes/reads/reading/panama.html
      [6] http://www.comp.mq.edu.au/~len/
      [7] http://vipe.technion.ac.il/~shlomif/freecell-solver/
      [8] http://www.wichman.org/roguehistory.html
      [9] http://www.win.tue.nl/~kroisos/rogue/index.html
      [10] http://home8.highway.ne.jp/~tota/html/palmware/index.html
      [11] http://www.win.tue.nl/~kroisos/roguelike.html
      [12] http://roguelike-palm.sourceforge.net/iLarn/
      [13] http://www.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm


      --
      Nadav Har'El | Sunday, Apr 14 2002, 3 Iyyar 5762
      nyh@... |-----------------------------------------
      Phone: +972-53-245868, ICQ 13349191 |A messy desk is a sign of a messy mind.
      http://nadav.harel.org.il |An empty desk is a sign of an empty mind.
    • Amir Abiri
      From: Nadav Har El [snip] ... Oh... man... what a nostalgy moment you brought up... i am tingling all over... :) I used to play
      Message 2 of 8 , Apr 15 4:57 AM
        From: "Nadav Har'El" <nyh@...>

        [snip]

        > The article [1] I'm reviewing here is about ROG-O-MATIC, a program which
        > automatically plays the computer game of Rogue.

        Oh... man... what a nostalgy moment you brought up... i am tingling all
        over... :)
        I used to play rogue for hours. And my old man two. I even remember now that
        actually the first item in my life programming TODO list is my promise to my
        old man that someday i'll write a better version of rouge for him. :)

        > What is Rogue, you might be asking? Well, many people might need an
        > introduction so here it goes. Rogue [8] is a role-playing game where
        > you wonder around a maze of rooms in various levels, trying to complete
        > an almost impossible mission or survive as long as you can. While
        wondering
        > around need to fight monsters that are trying to kill you, pick up useful
        > objects (weapons, armors, magic potions, etc.) that help your quest, and
        > building up experience and attributes (such as "hit points", "strength",
        > and so on) which will help you fight monsters, carry more weight, and so
        > on.
        > Rogue was started around 1980, together with the "curses" library (see [8]
        > for an historical overview). In fact its distinguishing feature was that
        > instead of being text-oriented (like its predecessor "adventure") it was
        > character-graphics oriented (using curses). You'd move your character
        (which
        > looked like a "@") around the screen which showed a top-view of the
        current
        > level, fight monsters (that looked like capital letters, e.g., a "B" was a
        > bat) and pick up objects (which looked like !, $, ?, and so on - you can
        > probably guess what the "$" was!). You'd typically have a lot of fun
        before
        > some really nasty monster killed you (actually "winning" the game was
        > nearly impossible, so most people just played for getting the maximum
        "gold",
        > or score).

        [snip]

        > There are later games that are "rogue-like [11], such as Larn ([12] is the
        Palm version)
        > and Nethack [13] which is most popular today (Redhat even includes its
        > package, albeit with ugly QT graphics instead of ascii characters).

        One thing you forgot to mention is that Blizzard's famous Diablo is highly
        inspired by Rogue.

        And about computer AI in computer games in general there a lot more to be
        said. All the famous 3D shooters and Real-Time strategy have AI in various
        qualities, and the AI is an important part of a those games, sometimes as
        important as the graphics itself. Just by googling any combination of
        "computer games" and "AI" you can get to some very interesting articles
        about the subject.

        Also, since anything that comes out of Epic Megagames or ID software (and
        more i guess, i just don't know) these days is in fact mostly written in an
        internal scripting language that the engine exports for the developer, one
        can have a peek in some sophisticated AI scripts by exporting those scripts
        and poking through them, even hack them a little bit and experiment with
        them.

        And for a last remark it can be said that some of the bigger contributers to
        the worldwide AI technology are among the computer gaming industry. But that
        can be said about a couple of other programming aspects as well...

        --
        http://abiri-e.com/
        "God is a programmer".
      • Shlomi Fish
        ... It s not exactly new, but I think it s a good one. ... Is Appel the same guy who co-proved that all 2-dimensional maps can be coloured with 4 colours? ...
        Message 3 of 8 , Apr 15 5:25 AM
          On Mon, 15 Apr 2002, Nadav Har'El wrote:

          > I'm trying to start a new tradition here on hackers-il: a person reads a book
          > or an article that are relevant to "hacking", programming or computer science
          > (but not requiring more than a basic foundation in computer science), and
          > writes a review to the list.
          >

          It's not exactly new, but I think it's a good one.

          > My first review is titled "Mixing business with pleasure", and it's about
          > the article [1]:
          >
          > ROG-O-MATIC: A Belligerent[2] Expert System
          > by Michael L. Mauldin[4], Guy Jacobson[5], Andrew Appel [3] and
          > Leonard Hamey[6], Carnegie Mellon University
          >
          > Appeared at the Fifth Biennial Conference of the Canadian
          > Society for Computational Studies of Intelligence, May 1984
          >

          Is Appel the same guy who co-proved that all 2-dimensional maps can be
          coloured with 4 colours?

          > Most of you have seen Shlomi writing here enthusiastically about his
          > freecell solver [7]. Now, imagine you could actually do serious research and
          > get academic credit for messing around with your favorite game. Well,
          > you don't need to imagine this! computer scientists have been "mixing
          > business with pleasure" like that for years.
          >

          Actually, I tried to get some academic credit for Freecell Solver.
          However, the Engineer of the EE department's software lab said that they
          only give credit for projects done inside the lab. Then I suggested to her
          that we translate the code to Java, but she did not seem enthusiastic
          about it for some reason. Then there was the cross-platform Freecell
          implementation which I initiated, but since my partner and I found a more
          attractive project, it was dropped too.

          Mixing business with pleasure is a bit hard for an Undergraduate student.

          > The game whose research got most publicity is probably Chess (it's gotten
          > such a media hype that IBM chose to spend millions on building a super-
          > computer and software to play chess and beat the world champion).

          And the software was not particularily sophisticated. It just scanned all
          the positions 10 or so steps from the current one, and evaluated the best
          path. With a substantially slower computer (such as the desktop
          workstations that were common at the time) it would have taken much too
          long to be effective.

          > But people have also been researching how to solve other board games, such as
          > Checkers, Backgammon and Go (the last one still doesn't have a good computer
          > program to play it), and even Minesweeper [13].

          Solving MineSweeper was shown to be NP-Complete according to what a fellow
          Technion student told me. ;-)

          > My "Introduction to AI"
          > teacher told us that the best research on game solving is done by people who
          > love the game themselves; He said that he had a graduate student who was a
          > very good Bridge player, and made good advancements in Bridge playing
          > algorithms.
          >

          Which probably means that I should not try to write a Chess program. I
          hate Chess. Re: Freecell Solver - many of the changes I incorporated in it
          were not directly related to AI. Some of them were purely C-ish changes.

          > The article [1] I'm reviewing here is about ROG-O-MATIC, a program which
          > automatically plays the computer game of Rogue.
          >

          Guy Keren once said to me that I could try writing a program that plays
          MUDs, if I'm looking for a further game AI challenge. He said I should
          concentrate first on Diku-MUDs, whose playability was very simplistic. I
          said I'll keep that in mind, but would probably not work on it anytime
          soon.


          > [Snipped]

          > So this is not just an interesting article for AI aficionados (AI aficionados
          > will find it severely lacking in detail, but that's why the source-code is
          > available!), or for Rogue (or Nethack) addicts - it's also interesting to
          > see how research can actually be fun, and even "cool" (in a geeky sort
          > of way) :)
          >

          geeky cool is cool by any other standard!

          Regards,

          Shlomi Fish

          >
          >
          > -----------------
          > [1] http://www.cs.princeton.edu/~appel/papers/rogomatic.html
          > [2] http://www.m-w.com/cgi-bin/dictionary?va=belligerent
          > [3] http://www.cs.princeton.edu/~appel/
          > [4] http://www.fuzine.com/lti/vita.html
          > [5] http://web.syr.edu/~rsholmes/reads/reading/panama.html
          > [6] http://www.comp.mq.edu.au/~len/
          > [7] http://vipe.technion.ac.il/~shlomif/freecell-solver/
          > [8] http://www.wichman.org/roguehistory.html
          > [9] http://www.win.tue.nl/~kroisos/rogue/index.html
          > [10] http://home8.highway.ne.jp/~tota/html/palmware/index.html
          > [11] http://www.win.tue.nl/~kroisos/roguelike.html
          > [12] http://roguelike-palm.sourceforge.net/iLarn/
          > [13] http://www.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
          >
          >
          > --
          > Nadav Har'El | Sunday, Apr 14 2002, 3 Iyyar 5762
          > nyh@... |-----------------------------------------
          > Phone: +972-53-245868, ICQ 13349191 |A messy desk is a sign of a messy mind.
          > http://nadav.harel.org.il |An empty desk is a sign of an empty mind.
          >
          >
          > To unsubscribe from this group, send an email to:
          > hackers-il-unsubscribe@egroups.com
          >
          >
          >
          > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
          >
          >



          ----------------------------------------------------------------------
          Shlomi Fish shlomif@...
          Home Page: http://t2.technion.ac.il/~shlomif/
          Home E-mail: shlomif@...

          "Let's suppose you have a table with 2^n cups..."
          "Wait a second - is n a natural number?"
        • Nadav Har'El
          ... No, that was *Kenneth* Appel, together with Wolfgang Haken. I think they were both working in UIUC (University of Illinois, Urbana-Chapain), and they did
          Message 4 of 8 , Apr 15 6:24 AM
            On Mon, Apr 15, 2002, Shlomi Fish wrote about "[hackers-il] Re: [article review] Mixing business with pleasure":
            > > by Michael L. Mauldin[4], Guy Jacobson[5], Andrew Appel [3] and
            > > Leonard Hamey[6], Carnegie Mellon University
            >
            > Is Appel the same guy who co-proved that all 2-dimensional maps can be
            > coloured with 4 colours?

            No, that was *Kenneth* Appel, together with Wolfgang Haken. I think they were
            both working in UIUC (University of Illinois, Urbana-Chapain), and they
            did it around 1977 (when, incidentally, I happened to be a toddler living
            in Urbana Illinois :) ).

            > Mixing business with pleasure is a bit hard for an Undergraduate student.

            Undergraduates are not supposed to have pleasure ;)

            Actually, to be serious for a moment, even undergradutes can do research
            and write papers - but this usually requires working with some professor
            who'll set you on the right path (undergraduates usually don't have enough
            experience to research alone!) and (if you're lucky) get your paper
            published. You won't get "points" (what you probably assumed I meant when
            I said "credit") for such research, however. If you're very lucky, you can
            get a couple of left-over shekels from the professor's research grant :)

            Most people only do such things (if ever) when graduate students, when
            you have more time to pursue wild research interests.

            > > Checkers, Backgammon and Go (the last one still doesn't have a good computer
            > > program to play it), and even Minesweeper [13].
            >
            > Solving MineSweeper was shown to be NP-Complete according to what a fellow
            > Technion student told me. ;-)

            Yes, just look at the [13] I pointed to... That's why I added links :)
            > > [13] http://www.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm

            --
            Nadav Har'El | Monday, Apr 15 2002, 3 Iyyar 5762
            nyh@... |-----------------------------------------
            Phone: +972-53-245868, ICQ 13349191 |What's tiny, yellow and very dangerous? A
            http://nadav.harel.org.il |canary with the super-user password.
          • Nadav Har'El
            ... Maybe you meant you feel warm all over :) (for those who don t understand the rogue reference, see http://www.monmouth.com/~colonel/rvm-msg.html) ...
            Message 5 of 8 , Apr 15 9:08 AM
              On Mon, Apr 15, 2002, Amir Abiri wrote about "Re: [hackers-il] [article review] Mixing business with pleasure":
              > > The article [1] I'm reviewing here is about ROG-O-MATIC, a program which
              > > automatically plays the computer game of Rogue.
              > Oh... man... what a nostalgy moment you brought up... i am tingling all
              > over... :)

              :)

              Maybe you meant you "feel warm all over" :) (for those who don't understand
              the rogue reference, see http://www.monmouth.com/~colonel/rvm-msg.html)

              > One thing you forgot to mention is that Blizzard's famous Diablo is highly
              > inspired by Rogue.

              Actually, I never heard about game. What is it?


              --
              Nadav Har'El | Monday, Apr 15 2002, 4 Iyyar 5762
              nyh@... |-----------------------------------------
              Phone: +972-53-245868, ICQ 13349191 |I am logged in, therefore I am.
              http://nadav.harel.org.il |
            • Amir Abiri
              From: Nadav Har El ... which ... understand ... highly ... A Rogue lover who never heard of Diablo...!? that s a shame... Just
              Message 6 of 8 , Apr 15 11:25 AM
                From: "Nadav Har'El" <nyh@...>

                > On Mon, Apr 15, 2002, Amir Abiri wrote about "Re: [hackers-il] [article
                review] Mixing business with pleasure":
                > > > The article [1] I'm reviewing here is about ROG-O-MATIC, a program
                which
                > > > automatically plays the computer game of Rogue.
                > > Oh... man... what a nostalgy moment you brought up... i am tingling all
                > > over... :)
                >
                > :)
                >
                > Maybe you meant you "feel warm all over" :) (for those who don't
                understand
                > the rogue reference, see http://www.monmouth.com/~colonel/rvm-msg.html)
                >
                > > One thing you forgot to mention is that Blizzard's famous Diablo is
                highly
                > > inspired by Rogue.
                >
                > Actually, I never heard about game. What is it?

                A Rogue lover who never heard of Diablo...!? that's a shame...
                Just Google it.

                --
                http://abiri-e.com/
                "God is a programmer".
              • Nadav Har'El
                ... For those who also do this search, watch out: http://www.diablo.org/ is *NOT* the site you re after ;) It appears to be some sort of commercial game for
                Message 7 of 8 , Apr 15 12:50 PM
                  On Mon, Apr 15, 2002, Amir Abiri wrote about "Re: [hackers-il] [article review] Mixing business with pleasure":
                  > > > One thing you forgot to mention is that Blizzard's famous Diablo is
                  > highly
                  > > > inspired by Rogue.
                  > > Actually, I never heard about game. What is it?
                  > A Rogue lover who never heard of Diablo...!? that's a shame...
                  > Just Google it.

                  For those who also do this search, watch out: http://www.diablo.org/
                  is *NOT* the site you're after ;)

                  It appears to be some sort of commercial game for Windows. I found a review
                  in http://www.avault.com/reviews/review_temp.asp?game=diablo
                  Indeed looks like yet another rogue/larn/AD&D spinoff with several interesting
                  twists and fancy graphics and sound effects.

                  Apparently there's also Diablo II: see a review in
                  http://www.avault.com/reviews/review_temp.asp?game=diablo2

                  --
                  Nadav Har'El | Monday, Apr 15 2002, 4 Iyyar 5762
                  nyh@... |-----------------------------------------
                  Phone: +972-53-245868, ICQ 13349191 |In Fortran, God is real unless declared
                  http://nadav.harel.org.il |an integer.
                • Amir Abiri
                  Oops... did i forget to mention that this was a commercial MS drug...? o_0 my bad... :) From: Nadav Har El ... review ...
                  Message 8 of 8 , Apr 16 4:19 AM
                    Oops... did i forget to mention that this was a commercial MS drug...? o_0
                    my bad... :)

                    From: "Nadav Har'El" <nyh@...>

                    > On Mon, Apr 15, 2002, Amir Abiri wrote about "Re: [hackers-il] [article
                    review] Mixing business with pleasure":
                    > > > > One thing you forgot to mention is that Blizzard's famous Diablo is
                    > > highly
                    > > > > inspired by Rogue.
                    > > > Actually, I never heard about game. What is it?
                    > > A Rogue lover who never heard of Diablo...!? that's a shame...
                    > > Just Google it.
                    >
                    > For those who also do this search, watch out: http://www.diablo.org/
                    > is *NOT* the site you're after ;)
                    >
                    > It appears to be some sort of commercial game for Windows. I found a
                    review
                    > in http://www.avault.com/reviews/review_temp.asp?game=diablo
                    > Indeed looks like yet another rogue/larn/AD&D spinoff with several
                    interesting
                    > twists and fancy graphics and sound effects.
                    >
                    > Apparently there's also Diablo II: see a review in
                    > http://www.avault.com/reviews/review_temp.asp?game=diablo2


                    --
                    http://abiri-e.com/
                    "God is a programmer".
                  Your message has been successfully submitted and would be delivered to recipients shortly.