Subject: [article review] Mixing business with pleasure

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 15 Apr 2002 01:05:41 +0300

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
[email-masked]             |-----------------------------------------
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.

---

From: "Amir Abiri" <[email-masked]>
Date: Mon, 15 Apr 2002 13:57:08 +0200

From: "Nadav Har'El" <[email-masked]>

[snip]

> 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. :)

> nearly impossible, so most people just played for getting the maximum
"gold",

[snip]

> There are later games that are "rogue-like [11], such as Larn ([12] is the
Palm version)
> 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".

---

From: Shlomi Fish <[email-masked]>
Date: Mon, 15 Apr 2002 15:25:43 +0300 (IDT)

> writes a review to the list.

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

>         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?

> 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.

> 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.

> 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"

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.

> 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]

> see how research can actually be fun, and even "cool" (in a geeky sort

geeky cool is cool by any other standard!

Regards,

	Shlomi Fish

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 15 Apr 2002 16:24:00 +0300

> Is Appel the same guy who co-proved that all 2-dimensional maps can be

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.

> Technion student told me. ;-)

Yes, just look at the [13] I pointed to... That's why I added links :)

-- 
Nadav Har'El                        |        Monday, Apr 15 2002, 3 Iyyar 5762
[email-masked]             |-----------------------------------------
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.

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 15 Apr 2002 19:08:17 +0300

> Oh... man... what a nostalgy moment you brought up... i am tingling all

:)

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

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

-- 
Nadav Har'El                        |        Monday, Apr 15 2002, 4 Iyyar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I am logged in, therefore I am.
http://nadav.harel.org.il           |

---

From: "Amir Abiri" <[email-masked]>
Date: Mon, 15 Apr 2002 20:25:40 +0200

> 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".

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 15 Apr 2002 22:50:47 +0300

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

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
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |In Fortran, God is real unless declared
http://nadav.harel.org.il           |an integer.

---

From: "Amir Abiri" <[email-masked]>
Date: Tue, 16 Apr 2002 13:19:41 +0200

Oops... did i forget to mention that this was a commercial MS drug...? o_0
my bad... :)

--
http://abiri-e.com/
"God is a programmer".