Orc Battle In Clojure

The goal of this is to explain how I implemented Orc Battle in Clojure and the changes I made. Part of my intent with implementing the program in Clojure was to rewrite it in a functional style. If you are interested in a straight port of the code, that can be found here: Orc Battle Online. As a bonus, this also includes a web interface using Ring and Hiccup.

The first big change is that this version does not make use of any global variables. A key concept of functional programming is that calling a function does not have any side effects. Any time we modify a value, such as attacking the player and decreasing his health, we cannot modify any external state. Rather we pass in the player as a parameter to the function, and generate a new object with this modified state and use the returned value later on in the program. Since we no longer have the global variables keeping track of the players stats, we need to create a structure to keep track of this:

	(defn create-player [max-health max-agility max-strength]
	{:health max-health :max-health max-health
	:agility max-agility :max-agility max-agility
	:strength max-strength :max-strength max-strength})

view raw create_player.clj hosted with ❤ by GitHub

Not only are we keeping track of the current stats, we have the original values. I plan on adding increasing rounds of difficulty and the ability of the player to level up.

For our first function, lets create one that damages a player's attribute by some amount. So given the player, attribute and damage we want to return a new player structure with the given attribute altered. We can use the assoc function, which takes a hash-map, the key and the new value. This function will return a new hash-map where everything is the same except for the specified key, which now has the new value.

	(defn hit-player [player attr dmg]
	(assoc player attr (max 0 (- (attr player) dmg))))
	orc.core> (def player (create-player 20 20 20))
	#'orc.core/player
	orc.core> (hit-player player :health 5)
	{:health 15, :max-health 20, :agility 20, :max-agility 20, :strength 20, :max-strength 20}
	orc.core> player
	{:health 20, :max-health 20, :agility 20, :max-agility 20, :strength 20, :max-strength 20}

view raw hit_player.clj hosted with ❤ by GitHub

As you can see above, after calling hit player we have a new object returned with the updated values, but we do not have to worry about our original player being changed. As a result testing become easier. You can reuse the same object over and over while testing a function, since most functions do not have side effects, so only the returned results matter.

The next piece is dealing with the monster methods and dispatching on type. In clojure there are several approaches to dealing with inheritance. One approach uses defrecord and protocols. I tried that way first, but with little experience using it, I found the resulting code less clear. An alternate approach that I used was multi methods. The main compents of a multimethod are the method name and the dispatch function. Since a key (e.g. :some-key) can act as a function, that means you can dispatch the method based on the value of a given key or set of keys of a map object. So in this case we have the following method signatures and implementations:

	(defmulti monster-show :type)
	(defmulti monster-attack :type)
	(defmulti monster-hit :type)
	::monster
	(derive ::orc ::monster)
	(derive ::hydra ::monster)
	(defn orc [health club-level]
	{:type ::orc :health health :club-level club-level})
	(defn hydra [health]
	{:type ::hydra :health health})
	(defmethod monster-show ::monster [m]
	(str "A " (monster-name (:type m)) " with " (:health m) " health."))
	(defmethod monster-show ::hydra [m]
	(str "A hydra with " (:health m) " heads!"))

view raw monster.clj hosted with ❤ by GitHub

All of the multi-methods are being dispatched on the type property of the maps. We then define the type hierarchy, with monster being the base type and both orc and hydra deriving from that. So now we have the polymorphism we'd expect. In each of the orc and hydra objects the type property is defined. This value will be used for dispatching. We have two implementations of the monster-show method. One defined for a generic monster and one specialized to the hydra. Since no specific orc defined method exists and orc is derived from monster, the generic version will be used when called with an orc. When called with a hydra we get the specialized hydra version.

We also need some addition methods to help with I/O. When using swank in emacs, the regular read-line method does not work. Fortunately swank-clojure provides a method to work around this problem. Also, read-line returns a string with a newline character so we need a method to parse the integer.

	(defn read-from-in []
	(swank.core/with-read-line-support (read-line)))
	(defn read-int []
	(let [x (clojure.string/replace (read-from-in) "\n" "")]
	(if (every? #(Character/isDigit %) x)
	(Integer/parseInt x)
	-1)))

view raw read_in.clj hosted with ❤ by GitHub

The last major change was dealing with the monster attacks and player attacks. I struggled with this a little, since this step is really where most of the regular state change was occuring. My first attempt used loop/recur. While it worked, the resulting code was not idiomatic and was not using the sequence library to process the code. With some help (Stackoverflow question) I was able to use a solution which made better use of the sequence library using reduce. Similarly I was able to use reduce for the player attacks, with the list being n copies of the player where n is the number of attacks the player has.

	(defn monster-round-original [player monsters]
	(loop [n 0 p player]
	(if (>= n (count monsters))
	p
	(recur (inc n)
	(if (monster-dead? (nth monsters n))
	p
	(let [r (monster-attack (nth monsters n) p)]
	(print (:attack r))
	(:player r)))))))
	(defn- attack-player [player monster]
	(if (monster-dead? monster)
	player
	(let [r (monster-attack monster player)]
	(print (:attack r))
	(:player r))))
	(defn monster-round-improved [player monsters]
	(reduce attack-player player monsters))
	(defn- attack-monsters [monsters player]
	(if (monsters-dead? monsters)
	monsters
	(do
	(show-monsters monsters)
	(player-attack player monsters))))
	(defn num-attacks [player]
	(inc (Math/floor (/ (max 0 (:agility player)) 15))))
	(defn player-round [player monsters]
	(reduce attack-monsters monsters
	(repeat (num-attacks player) player)))

view raw monster_round.clj hosted with ❤ by GitHub

The one place where I did stick with a loop/recur was with the main game loop. Since I am not specifically using a data structure to loop on, I am uncertain if there is a better way to implement this.

	(defn level-loop [player monsters]
	(loop [m monsters p player]
	(if (or (monsters-dead? m) (player-dead? p))
	p
	(do
	(print (str "\n" (show-player p)))
	(let [m2 (player-round p m)]
	(recur m2 (monster-round p m2)))))))

view raw level.clj hosted with ❤ by GitHub

The full code can be found here along with the original common lisp code.

What is Math

I have been thinking about this question because of my decision to go back to school for a PhD in math. Of course when I tell people this, I am confronted by most peoples' misconceptions about what math is. For most people, arithmetic is math - adding, subtracting, multiplying and dividing numbers. If you are good at math, then you must be good at arithmetic. While I am better then most, I have a tendency to make silly mistakes with computations and I am not always the best at arithmetic. In reality arithmetic is only a tiny part of what math is and does not convey its essence. I do not blame people for having these misconceptions, because this is what they were exposed to as being math.

A popular example of what math really is like would be Sudoku. While most instructions say it does not involve math, what they are really saying is that it does not involve arithmetic. A sudoku puzzle involves the layout of the grid and the constraints for filling in the values. Each set of 3 x 3 box can only have the numbers 1-9 in it, with each number appearing only once, and each horizontal and vertical line can only have one occurrence of each number in it.

Given these rules and a partially fulled in grid, you should be able to fill in the remaining blank spots. The process of filling in the remaining grid mimics the process of math. Based off of the constraints in the system, you are able to infer other facts that you did not know before. You can do this using different techniques to eliminate possibilities and reason out the only remaining choice for a square. One way to do this is by using proof by contradiction. You make a reasonable guess for a box and see what the logical consequences are. If this ends up causing a violation of the rules then you know this is not a valid value for that square and eliminate the possibility. You are able to further refine the constraints using deductive logic and finally end up with a completed square.

Now someone with a more mathematically inclined mind would start asking questions of a different sort. One such line of questioning is - What is the minimum number of starting conditions needed to uniquely identify a puzzle and is this unique for each puzzle. If a puzzle can have more then one starting condition, which is not a super set of a different starting condition (i.e. this starting condition has all of the same stuff in a different starting condition plus some additional spots filled out), given two starting conditions can we determine if they are referring to the same puzzle.

Or we could ask questions about the number of puzzles per board size. As the board size increases, how do the number of puzzles for that size increase. Lets say I have a 9 x 9 board, and of all the possible configurations only 20% fulfill all of the conditions. If I move to a 16 x 16 board, does the percentage remain about the same and as I move to bigger and bigger boards does any pattern emerge? Maybe the percentage tends toward 0, or oscillates, or stays about constant. Is there a way to get a count of how many puzzles there are per grid size. Do we have to manually have to find them, can we create a formula to give an approximation?

I could continue on like this, trying to examine various properties and what the properties mean, and what other facts I can infer from what I already know. But the process for exploring these facts are similar to the initial problem of trying to fill in the remaining values given the starting constrains.

Given this example, I can now give one definition of math -
Mathematics is the creation and study of abstract objects and their properties using logic.

In this case our abstract object is the sudoku puzzle. A more common example are the integers or rational or real numbers and their properties. Or we could move on to more complex objects like functions, ploynomials or geometric shapes. The study of these objects will leads us to subjects such as number theory, abstract algebra, real analysis, or topography. Related to the objects we study are the tools we just to study them, such as logic or computers, and how all of these interact.

As you can see, math is much more then simple arithmetic.

Reinventing the wheel

This is just a rant against the advice of not reinventing the wheel, which is often raised when some one creates a new implementation of a well known concept or idea.

My biggest gripe about this phrase is the fact that the idea conveyed does not match reality. The idea behind this advice is to reuse what is already out there and not create you own implementation of something. One problem with this, is every implementation of an idea will have a different set of tradeoffs associated with it. You may have a wheel that is able to work on nearly any terrain, but is dangerous to use at high speeds, or a wheel that is long lasting but costs more money. Certain situations will require you to create your own individual wheel, that is unique to your own needs.

One of the important tradeoffs that needs to be considered is how much you need to understand how the wheel works and how much additional customization you will need to perform to it. When considering these ideas, you start to consider a wheel factory, rather then just a wheel. When you have a wheel factory you can produce a range of different types of wheels to fit your own set of needs. By building the facotry yourself, you gain additional knowledge of not only how the factory operates but how wheels are created. Knowledge of the facotry allows you to make the most use out of it, while knowledge of wheel creation and the wheels themselves can be applied in any situation where wheels are required. The process has added value to your skill set.

Of course, building the factory can be time consuming and resource intensive. The best way to minimize the cost is to only build the bare minimum. After this you will have more knowledge on how to improve it or make additions when the need arises, but until that need arises, nothing extra should be done.

The only time the advice to not reinvent the wheel is useful is when someone is blindly tries to make one, without investigating what is already out there and considering if the time would be best spent learning how to use it. And lets just reinvent the phase to be don't reimplement the wheel, which is what is really meant.

Multi Threading

Multi-threaded programs have been marked as the next big thing. With the recent shift in processors from improvements in speed to improvements in number of cores instead, there is a stronger push for creating more multi threaded applications.

The problem with this is that creating multi-threaded applications is hard, except for a few classes of applications where this already occurs. Things need to happen in sequence, and there is only so much that can be done to change that. The processor companies want programmers to create applications which can get better by just adding more cores, so that they can sell more.

That is not the best use of the programmers time. In general, a programmer may have to work harder to improve performance, and a program may only get faster by making it smarter, rather then the underlying processor just getting faster.

But with the proliferation of smart phones (iPhone, Blackberries, ect.), subnote books and netbooks, pure speed is no longer the driving factor. So programs will have to be made to run with lower speeds, and not multi core. So the focus should be on creating tools to help programmers improve performance in general, not just for a specific optimzation of multi threading.

There are plenty of applications where multi threading will be beneficial, and nothing special needs to be done to take care of. A great example is webservers and web applications. Having mroe threads means it can server a larger number of people. As more and more new and existing applications are ported to the web, servers will need to handle more and more demands. So you have this split of writing applications for the personal computer, in what ever form only have limited resources and needing to optimize for that, then the big computers running the web based software which will naturally benefit from the increase in cores with out much additional effort of the programmers.

There is no real crisis coming up. Yes programmers will have to work harder to improve performance, but the performance increases will not come in the means of multi threading (in most cases anyways) but from other areas. They will still receive free performance enhancements as SSD drives become prevalent and disk speeds start to scale, along with increases in performance in memory in general.

Edit: I came across this after writing this entry about P-Completeness here and here that talks about issue of some problems just being inherently serial and that there is no way to create a solution using parallel processes.

Creating Wealth

I have been reading a number of interesting articles over at Paul Graham's website about wealth creation. For me, the most new point that I picked up is that wealth is created. Many, along with me consider the point of view wanting to make money. But rather then consider making money, the point of view is of creating wealth. Since wealth is a more general view, and money is just a medium of exchange.

When you consider it from the point of view of creating wealth, then the idea of money being limited and only having so much to go around, goes out the window. To create a wealthier society, the society needs to be creating more wealth then it is consuming.

One of the main components of this is being able to have enough intrinsic reward to what you are doing that you are being satisfied by the process of wealth creation. Not only that, but the person who is being driven by a love of what they are doing will far outperform another person who is just doing it as a job, even if they are of comparable skills and ability.

Of course, the ability of someone to be rewarded based on their performance varies from profession to profession. Because for one to be rewarded based on performance, the performance needs to be measurable. Trying to reward excellent teachers is hard. How does one identify excellent teachers? It would have to be related to the students and having a positive impact on their lives. Even if one is created, how do you prevent teachers from gaming the system.

This pattern can be repeated from job to job. I think that any solution would require at least two parts. A way to measure and link performance and reward, and a policing type mechanism to reduce or discourage gaming of the system.

The way things are

The world does not need to be that way that it is. Much of how it is, we just take for granted and assume that is the way it should be. We have this basic template of going to school when we are young, graduating from high school, then moving onto college, getting a job, getting married and then having kids.

Yet at every step along the way, we lose people. Not everyone finished high school, not everyone finishes college, not everyone gets a steady job and not everyone gets married and has children. At every step of the one, on needs to wonder is this actually the best way to be doing this in general and is this the best thing for me.

On of the strongest clocks in our society is the school schedule. We all feel the ebb and flow of the school season, with or with out any direct connection to the schools. During the summer, the commutes are easier with out all of the school buses, and as the school season starts the traffic increases. Parents and children alike are transitioning from the lazy days of summer back to the hectic days of school.

The parents are governed by their daily work schedule and the children theirs. This is not unreasonable given the basic idea of central control. The only way to organize the movement and scheduling of people, parents and teachers is to have a strongly regulated schedule.

I wonder how much of it has to be this way. We have built up this concept of the hugely central schools with a massive number of children that need to be governed and monitored. If we were to some how decentralize this, could we alleviate some of the problems of having so many kids together.

Why do we as adults need to be on such a regulated schedule. I know that I find that my productivity and motivation can vary from day to day and week to week. Right now it is evening and I am feeling motivated to write and do this, yet during the afternoon I was mostly not wanting to much of everything.

So much of the way we currently live our lives runs against the way we are currently built to work. I would not go so far as to say unnatural, because that implies that there is a certain way we have to be. But rather that the environment that we are currently living in is different from the environment we as humans developed in, that we have created a number of inefficiency's where we are having to constantly fight ourselves and who we are, with little benefit and great costs.

Come closer my dear

We recently bought a new oil painting for our apartment. As I was examing it, I was struck by the fact that, when looking closely, the picture itself looses focus and you are only able to notice the individual paint strokes. Only once you have backed up enough do you see the picture again. This is most likely due to the fact that when you are too close, your brain is unable to group the brush strokes making up the tree and identify them as representing a tree. If you back up, your brain is able to see enough to fire 'tree' in your brain. 

Much of life appears to be like this, examine something too closely and it starts to fall apart. For example with language and words, when examined they start to look and sound like nonsense. This can easily be experienced by saying the same word over and over again out loud. We start to pay attention to the sequences of sounds we are producing, rather then the meaning behind the word. The picture we are creating with our words starts to fall apart and look like nothing.

A similar phenomenon can be witnessed by looking at matter. The closer and closer we look, the less and less it looks like anything. Seems to be mostly empty space scattered with probabilities of something being there and that something turns out to be not much of anything as well.

Yet there still appears to be something there. Just so long as I am not looking too closely.