saush

Evolutionary Algorithms and Genetic Programming [3]

Posted in general by sausheong on April 14, 2006

Required theoretical background

Prefix Notation and S-Expressions

The most common way of writing down a function with two arguments, for example addition, is the infix notation. That is, the two arguments are connected with the operation symbol between them.

A + B

A different method is the so-called prefix (or polish) notation. Here the operation symbol is written down first, followed by its required arguments.

+ A B

While this may be a bit more difficult or just unusual for human eyes, it opens some advantages for computational uses.
The computer language LISP uses so-called symbolic expressions (or S-expressions) composed in prefix notation. Then a simple S-expression could be
(operator argument)

where operator is the name of a function (here with one argument). Argument can be either an atom (i.e. constant or variable) or either another symbolic expression (e.g. S-expressions can be nested).

(operator argument (operator argument) (operator argument))

In LISP, programs and data have the same structure providing an easy means of manipulation and evaluation. This is why LISP is popularly used for implementing genetic programming.

Program trees and Subtrees

A tree in this context is a hierarchical structure consisting of nodes and leaves. The simplest tree consists only of a single leaf. Nodes are inner points of trees and may have more nodes or just leaves connected to them. The topmost point of a tree is called the root of this tree.

A program tree is describes a computer program. Functions are written down as nodes, their arguments as leaves. There is a close relationship between these program trees and S-expression; in fact these trees are just another way of writing down the expressions.

Figure 1 : A program tree representing the expression (+ 1 2)

Figure 2 : A program tree representing the expression (* 3 (+ 1 2))

A subtree is the part of a tree that is under an inner node of this tree. If this tree is cut out from its parent, the inner node becomes a root node and the subtree is a valid tree of its own. Subtrees are equivalent to inner S-expressions in other S-expressions.

is a valid subtree of 

A method to measure the complexity of these trees is the depth, meaning the maximum number of parent nodes a leave might have, or the complete size, meaning the total sum of leaves and nodes a tree contains.

Functions and Terminals

While the term function is self-explanatory, the meaning of terminal is not so obvious. While functions will be the nodes of the trees (or the operators in the S-expressions) and can have other functions as their arguments, the leaves will be formed by terminals, that is symbols that may not be further expanded.
In this work, a variety of functions will be used. Simple arithmetic functions like addition or multiplication, more complex ones like sinus or highly specific functions like IF-FOOD-AHEAD (a conditional branch). Terminals can be variables, constants or specific actions that are to be performed.
The process of selecting the functions and terminals that are needed or useful for finding a solution to a given problem is one of the key steps in the preparation of genetic programming.

Evaluation

Evaluation of these structures is straightforward. Beginning at the root node, the values of all sub-expressions (or subtrees) are computed, descending the tree down to the leaves. Their return values will serve as arguments for the upper node.

(+ 3 ( - 4 2)) = (+ 3 2) = 5

(- (* 2 3) (+ 2 1)) = (- 6 (+ 2 1)) = (-6 3) = 3

If the function represents a conditional branch, it is imperative that just the designated argument is evaluated; the other(s) must be ignored.

Fitness Function

The most difficult and most important concept of genetic programming is the fitness function. The fitness function determines how well a program is able to solve the problem. It varies greatly from one type of program to the next. For example, if one were to create a genetic program to set the time of a clock, the fitness function would simply be the amount of time that the clock is wrong. Unfortunately, few problems have such an easy fitness function; most cases require a slight modification of the problem in order to find the fitness.

Evolutionary Algorithms and Genetic Programming [2]

Posted in general by sausheong on April 14, 2006

Genetic Algorithm

Genetic algorithms are a variation of evolutionary algorithms. Genetic algorithms model of machine learning that derives its behavior from a metaphor of the processes of evolution in nature. This is done by the creation within a machine of a population of individuals represented by chromosomes, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA.

The individuals in the population then go through a process of evolution. The processes of nature boil down to different individuals competing for resources in the environment. Some are better than others. Those that are better are more likely to survive and propagate their genetic material.

Genetic algorithms are used for a number of different application areas. An example of this would be multidimensional optimization problems in which the character string of the chromosome can be used to encode the values for the different parameters being optimized. In practice, therefore, we can implement this genetic model of computation by having arrays of bits or characters to represent the chromosomes. Simple bit manipulation operations allow the implementation of crossover, mutation and other operations.

Although a substantial amount of research has been performed on variable-length strings and other structures, the majority of work with genetic algorithms is focused on fixed-length character strings. We should focus on both this aspect of fixed-lengthness and the need to encode the representation of the solution being sought as a character string, since these are crucial aspects that distinguish genetic programming, which does not have a fixed length representation and there is typically no encoding of the problem.

When the genetic algorithm is implemented it is usually done in a manner that involves the following cycle:
1.    Evaluate the fitness of all of the individuals in the population.
2.    Create a new population by performing operations such as crossover, fitness-proportionate reproduction and mutation on the individuals whose fitness has just been measured.
3.    Discard the old population and iterate using the new population.

One iteration of this loop is referred to as a generation. There is no theoretical reason for this as an implementation model. Indeed, we do not see this punctuated behavior in populations in nature as a whole, but it is a convenient implementation model. The first generation (generation 0) of this process operates on a population of randomly generated individuals. From there on, the genetic operations, in concert with the fitness measure, operate to improve the population.

Genetic Programming

Genetic programming is a branch of genetic algorithms. The main difference between genetic programming and genetic algorithms is the representation of the solution – genetic algorithms create a string of numbers that represent the solution while genetic programming creates computer programs as the solution.

The objects in genetic programming that constitute the population are not fixed-length character strings that encode possible solutions to the problem at hand, they are programs that, when executed, “are” the candidate solutions to the problem. These programs are expressed in genetic programming as program trees, rather than as lines of code. Thus, for example, the simple program “a + b * c” would be represented as:

Or, to be precise, as suitable data structures linked together to achieve this effect. Because this is a very simple thing to do in the programming language LISP, many GP programmers tend to use LISP. However, this is simply an implementation detail. There are straightforward methods to implement GP using a non-LISP programming environment. The programs in the population are composed of elements from the function set and the terminal set, which are typically fixed sets of symbols selected to be appropriate to the solution of problems in the domain of interest. In GP the crossover operation is implemented by taking randomly selected subtrees in the individuals (selected according to fitness) and exchanging them.   It should be pointed out that GP usually does not use any mutation as a genetic operator.

Further explanation of how genetic programming works is given in the section below.

Evolutionary Algorithms and Genetic Programming [1]

Posted in general by sausheong on April 14, 2006

Introduction

Evolution in general means change and adaptation to the changes by a population and not individuals, changes that are passed on to the next generations. The idea of applying the biological principle of natural evolution to artificial systems, introduced more than three decades ago, has seen impressive growth in the past few years. Usually grouped under the term evolutionary algorithms or evolutionary computation, we find the domains of genetic algorithms, evolution strategies, evolutionary programming, and genetic programming.
Evolutionary algorithms (EAs) are ubiquitous nowadays, having been successfully applied to numerous problems from different domains including optimization, automatic programming, machine learning, economics, operations research, ecology, studies of evolution and learning, and social systems. In this article, we consider genetic algorithms in general and genetic programming to be specific.

Evolutionary Algorithms

Evolutionary algorithm is an overall term used to describe computer-based problem solving systems that use computational models of some of the known mechanisms of evolution as key elements in their design and implementation.

A variety of evolutionary algorithms have been proposed. The major ones are: genetic algorithms, evolutionary programming, evolution strategies, classifier systems and genetic programming. They all share a common conceptual base of simulating the evolution of individual structures via processes of selection, mutation, and reproduction. The topic of discussion in this article concerns genetic programming, but to understand genetic programming it is necessary to first understand the basic concepts of evolutionary algorithms.

EAs maintain a population of structures that evolve according to rules of selection and other operators that are referred to as genetic operators, such as recombination and mutation. Each individual in the population is measured for its fitness in the environment. Reproduction focuses on high fitness individuals and recombination and mutation agitate those individuals, providing general heuristics for exploration.

To understand EAs, it is necessary to have some appreciation of the biological processes on which they are based. In nature, the encoding for genetic information (genome) admits asexual reproduction. Asexual reproduction typically results in offspring that are genetically identical to the parent. (large numbers of organisms reproduce asexually; this includes most bacteria which some biologists hold to be the most successful species known.) Sexual reproduction allows some shuffling of chromosomes, producing offspring that contain a combination of information from each parent.

At the molecular level what occurs (wild oversimplification alert!) is that a pair of almost identical chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the recombination operation, which is often referred to as crossover because of the way that biologists have observed strands of chromosomes crossing over during the exchange.

Recombination happens in an environment where the selection of who gets to mate is largely a function of the fitness of the individual, i.e. how good the individual is at competing in its environment. Some “luck” (random effect) is usually involved too.

Some EAs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or asexual reproduction (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. Much EA research has assumed that the two processes that most contribute to evolution are crossover and fitness based selection/reproduction.

Evolution, by definition, absolutely requires diversity in order to work. In nature, an important source of diversity is mutation. In an EA, a large amount of diversity is usually introduced at the start of the algorithm, by randomizing the genes in the population. The importance of mutation, which introduces further diversity while the algorithm is running, therefore continues to be a matter of debate. Some refer to it as a background operator, simply replacing some of the original diversity that may have been lost, while others view it as playing the dominant role in the evolutionary process.

It cannot be stressed too strongly that an evolutionary algorithm (as a simulation of a genetic process) is not a random search for a solution to a problem (highly fit individual). EAs use stochastic processes, but the result is distinctly non-random (better than random).

Algorithm EA is

// start with an initial time
t := 0;

// initialize a usually random population of individuals
initpopulation P (t);

// evaluate fitness of all initial individuals in population
evaluate P (t);

// test for termination criterion (time, fitness, etc.)
while not done do

// increase the time counter
t := t + 1;

// select sub-population for offspring production
P' := selectparents P (t);

// recombine the "genes" of selected parents
recombine P' (t);

// perturb the mated population stochastically
mutate P' (t);

// evaluate its new fitness
evaluate P' (t);

// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.

Using YAML to transport data in ActionWebService

Posted in Rails, Ruby by sausheong on April 13, 2006

Here’s a handy tip for ActionWebService. Sometimes it could be a bit tedious to create the correct SOAP or XML messages to pass back and forth the webservices. If you’re using a Ruby 3rd party client (or even another Rails app as a client) you might want to try out YAML. It’s not entirely conventional but it works like a breeze and it sure beats the hell out of all that XML tagging.

Here’s the code to zip it up to as a YAML object:

yaml_obj = YAML::dump(your_object)

Even quicker — you can use a Hash and stuff everything inside the Hash. Then at the other end:

original_obj = YAML::load(yaml_obj)

There’s YAML for Java, Python, Perl and even Javascript. Check it out here

Don’t come after me if something doesn’t work though — it’s quite experimental at this moment, but it’s a pretty neat alternative to XML tagging.

[The Lands] – Tidings of War

Posted in Stories, The Lands by sausheong on April 9, 2006

Wilhelm crept up slowly to the small nook, as silent as any of his grandfather’s many spies. He was already familiar with the spot so the darkness posed no real problem – he just felt his way around until he reached the slight ledge which indicated that he should stop. He did just that, about twenty feet up above his grandfather’s Inner Court. It was a spot he came not infrequently, mostly just to daydream or to escape his all too boring court etiquette classes with Madame Voliante. Sometimes he just came to listen in to some of his grandfather’s conversations with his advisors. It was not really eavesdropping or anything. He decided that particular moral question a long time ago when he first discovered the small crack in the ceiling during his long and meandering wanderings in the ancient castle. His grandfather just happened to discuss Kingdom matters when he was up there, minding his own business really. Most of the things he heard were boring stuff like who did what and when and why it should be done. Sometimes though, more serious matters were discussed – some skirmishes with the Horde, some brilliant manoeuvres and not so brilliant routs, even some border disputes with Wranydis to the south. At times visiting dignitaries, usually royalty and sometimes merchants consulted with his father. The King even talked about his political strategies in his Inner Court though it was never the same with two different advisors. Wilhelm was intelligent enough a boy to realise some very interesting things were happening during those times.

The King was not a particularly physical person, tending towards the rotund in his old age. His four strapping sons sufficed in being physical, ranging from tall and commanding to simply large and burly. His red face, snowy white hair and long majestic beard in fact gave him the appearance of a kindly old man, not too bright perhaps, but rather a symbolic icon of monarchy in the kingdom of Liemia. Most of his subjects believed the real power behind the throne lie with his eldest son Johann, the Prince Regent and heir apparent. In fact none except his sons knew otherwise. Wilhelm, rich with knowledge from his hidey-hole knew only too well about his grandfather’s sharp mind and cunning plots.

Orphaned at the age of two when the first wave of the Horde massacred the previous border town of Kordelus, he had since stayed in the ancient seat of Liemian power, the Casa del Liem. His father was the Duke of Kordel, his mother the youngest daughter of the King of Liemia. Not a single soul survived the ravaging of the duchy of Kordelus. It was very fortunate that Wilhelm was spending the summer with his grandfather at the Casa del Liem when the the Horde swept through the eastern borders and obliterated more than fifty villages and towns in three kingdoms. They were not merely conquered but totally massacred and uprooted. Entire towns and villages ravaged and depopulated. Any resistance was swept away with brutal efficiency – no captives were ever kept beyond a few days. the Horde ate what they could, including humans. Those whom they could not eat, they decapitated and their heads piled up in the centre of the town. Fields bearing the rich loa grains Kordelus was famous for were burnt to the ground, the careful irrigation making it possible to grow loa grains savagely destroyed and whole rivers dammed and diverted just to flood over the crops. The horrors of the invasion were so great that the lands the the Horde so barbarously decimated were still left barren after all these years.

The bloodied Horde was finally met with the combined forces of the Federated Five Kingdoms on the plains of Suondy. The titanic battle raged throughout the day and when it was done, less than a fifth of the fifty thousand brave men was left standing. The Horde however, was no more.
The terrible battle took an even worse toll on the survivors. Thousands of able-bodied men had been conscripted for the war and only the women, children and disabled were left to till the land and grow the crops. Whole counties and provinces were abandoned in flight as the horde approached. To those who returned, disease and starvation overtook them. Plagues wiped out entire villages and towns and the lack of food only bred the horrors of malnutrition and raised the even uglier spectre of crime. Widespread looting and robbing became common in those early years after the battle, groups of ragtag bandits taking over whole provinces even. However, order soon prevailed as the kingdoms recovered and after a couple of years of chaos and mayhem, matters returned to almost normality. All has been quiet and peaceful for five years now; even bandits were a rare sighting. This year however, the first sign of hostile orcish activity has been sighted since almost fourteen years ago.

Wil settled in nicely on his favourite spot. Something exciting was about to happen that day. All week long ambassadors, princes, dukes and all sorts of diplomats have invaded the capital city Rourin. The Council of the Lands, convened once every two years at different kingdoms and duchies have finally arrived after thirty years, once more to Liemia. For months now, his Uncles Johann and Rikard have busied themselves with the arrangements and accommodations for dignitaries from almost fifty recognised members of the Council. It all came down to today, the first day of the Council, which was to last until all matters have been discussed over a period of four weeks, after which the Council will be reconvened two years from now.

“Your Majesties and Your Highnesses,” declared a gaunt, bony man clothed in precise finery, “May I have your attention please.” He stepped briskly forward in stiff formal protocol then made a small well-defined bow. “May I present His Highness Prince Mattheus of Nalvia.”

Wil recognised him as Roderic Thaddieu, his grandfather’s High Chamberlain, meaning he gets announce the guests as they arrive, something that he does with a very irritatingly and pompous manner.

Prince Mattheus was a dark-haired young man, copper of skin and a cheerful smile on his face. Wil liked him at once, even though he had never actually seen him before. He knew though that Mattheus was the youngest son of the king and has a tainted reputation of being brash and immature. Nalvia was a neighbouring kingdom, smaller than Liemia by almost half, but she has one of the largest seaports and the largest fleet of warships among the Lands. She was also a member of the Federated Five Kingdoms that stemmed the tide of destruction brought by the invading hordes.

The other guests nodded or bowed in acknowledgement according to their station. A few frowned at him openly for being almost half an hour late, others just ignored him completely, something Wil knew as quite foolish. Being hostile or snubbing Nalvia or her representative was not a good idea, since the break-up of the Federated Five Kingdoms after Battle of Soundy. The Council is about the only thing she even considers to attend. They needed her fleet of fast and sleek warships because that is the only thing that the the Horde did not excel humans in. Somehow, the Horde disliked water and their ships were not very well built. In one of the decisive and dramatic battles before the Plains of Suondy, five of the swift Nalvanian warships darted in between the massive galleons the orc tend to build and crippled ten of them before the the Horde could react. Then the larger Nalvanian battleships swept in and crushed each and every one of them, losing only three ships compared to the twenty-over manned by the the Horde.

Roderic nodded perceptibly then announced in a grand manner, “The last representative of the Council of the Lands has arrived. The Council will proceed to convene.” A few of the representative coughed and one yawned. Roderic cleared his throat importantly and continued, “Presiding as host shall be King Boric del Liem of Liemia. Your Majesty?” With that, he bowed low and backed out of the room, closing the door behind him.
“Ah, yes,” nodded King Boric. “Ahem. Shall we begin now?”

“Your Majesty,” said a tall gangly man politely, rising to his feet. Wil recognised him as a Semprian and noted that he wore the customary gown of minor nobility and carried an ceremonial hriss, a wicked-looking hooked dagger. He concluded that the Semperian was an ambassador, most probably recently arrived. Not only he was wearing gold earrings on both ears and one in his nose but heavy looking gold chains with intricate designs hung over his neck. Any person wearing that amount of gold in Rourin will not survive more than a few hours in broad daylight and much less after dark.

“I be Illrendris sa Ragedren, on behalf of my lord of Rallaka-Iss,” he introduced himself and flicked his hriss casually. “We shall get to the point now, yes?” Without waiting for an answer, he continued.

“I see the Horde!” he spat to the ground. Wil’s grandfather winced noticeably, along with some of the other representative. “I see them everywhere! They be coming for our eyes up north, hundreds and ten hundreds of them. But strange, they not attacking, just looking.”

“Ahem,” said Wil’s grandfather slightly ruffled after the abrupt speech. “Yes, we were about to get to that. About – “

“As what the Semperian put so succinctly,” interrupted a large middle-aged man, also ostentatiously clothed in fine Arian silk and wearing a ring of different stone in each of his ten fat fingers.

Wil sat up and stared at the fat man. Something about him told Wil that he was a dangerous man and should not be trifled with. He was not sure if anyone else noticed the way that the man moves. The arrangement of his rings, which could be interpreted as a crude display of wealth, was in the ready pattern of power. It could have been accidental. However, those small deft gestures he so casually and probably subconsciously performed were definitely a weaving and from the looks of it, a weaving of minor protection. Wil wondered whom he could be representing.

“We have Horde trouble at our doorsteps again, what can we do?” he said quite grimly. Some of the other Council members frowned at him and even in puzzlement. None of the others recognised him either. Prince Johann stepped forward from behind his father and said quietly, “Our guest is the representative from the Isle of Mullind, his Eminence Duke kil Roadac.”

There were loud murmurs in the Inner Court and Wil furrowed his forehead. Mullind is a small island off the southern shore, beyond even Nalvia. Her population consisted of mostly fishermen and sea harvesters. She had royalty of some sort a long time ago but the line had since died. She kept to herself mainly and did not have a voice in the Council even before the first orcish invasion. So what was a representative of Mullind doing in Liemia now and in the Council of the Lands of all places? Wil added another mystery to it himself – a skilled magic-weaver representing them? He suddenly felt very uncomfortable. Should the man from Mullind cast any weavings of detection, he would most definitely be found and that could be unpleasant.

Wil’s grandfather looked nonchalantly at the Council. Wil wondered what his plan was – it has been quite educational so far and he was very much eager to know what followed. Things were rarely this exciting. His cousins found him strange that he does not enjoy riding and swordplay as much he loved books and reading. Books and lessons by the royal tutors were a drag and only served to impede them from the real purpose of the day – sword fighting, archery or horse riding. The older cousins readily admit that books have their usage, though limited. Any serious reading if necessary can be acquired by using the services of a cleric or a monk. So when they realised Wil had a passion for books of any sort over the more physical aspects of growing up, they were quite mystified. He could not tell them the sweet thrill of the unknown, the mysteries that were locked behind the innocent seeming covers of a book and the excitement of gathering knowledge and applying them readily like what he was doing now.

By six, he could read and write, storing what became later his massive library of notes and books. It was really quite fortunate that he was a prince – otherwise he could have never afforded to even have the paper for his notes! Seeing his potential, his Uncle Johann hired the best tutors for him and by the time he was twelve, he could easily surpass most of them. The only thing that balked him so far was the firm belief of his grandfather that no true son of del Liem should be involved in the dark arts of magic weaving. Therefore he resorted to learning what weaving is instead of learning how to weave magic himself. The roundabout way did not exactly please his grandfather but he was not disobeying his grandfather’s wishes. What surprised him later was that not many sorcerers were not sure precisely what they were doing when they actually spin from the web of magic to form what they generally know as spells.

As a result of his dedication to the literary and subsequent neglect of other matters, Wil remained gangly, large boned and not much good in any physical sports, much to the regret of his Uncle Xavier. It was not that he was poor at swordplay or could not ride a horse – in fact he was reasonably good with a broadsword and had such instinctive skills that he nearly defeated cousin Nikolas, his Uncle Johann’s eldest son. Unfortunately he lacked the power, stamina and determination of a true swordsman. Once Nikolas knew his weakness, he merely wore Wil out and waited for an opening, both which came soon enough. It was not long before Wil was thoroughly beaten by almost every boy his age in swordplay.

“So what is our neighbour Mullind’s interest in the matters of the Lands?” asked the representative from Toumheilm boldly, clearly voicing the sentiments of the gathered Council. Mullind was never popular among the Council of the Lands, isolating herself from the mainland and keeping only minimal trading contacts. Most took offence to that, especially Nalvia who declared herself as having the greatest Fleet in the Lands but could not even land on Mullind. Some believed there were countless treasures in Mullind, selfishly hoarded by the Muls, others spoke of an island of horror and monstrous tyranny and yet others spoke of and island of powerful but mad magic-weavers. Folklore were rarely accurate, decided Wil.

“Our interest is the preservation of our lives and our land,” replied the fat man coolly, staring at his enquirer.

“So says you,” sneered the ambassador from Toumhielm. “We says you be traitorous scum ally with the filthy the Horde!”

Some of the Council backed away hurriedly. Wil gulped. No one has ever fought in the Inner Court before. Not since Ka’lent the Usurper murdered King Dekliem the Mad. Now it looked like someone or more could be killed. Wil’s mind raced madly – this could be really bad. If the fat man kills the Toumite, which Wil had no doubt he could, Toumhielm might crush Mullind – Toumhielm is one of the largest Kingdoms in the and the second largest army. Not good.
Before Johann could step out again, the fat man scowled and said, “Peace! Are we to fight the Horde or among ourselves?”

“But first, we must be assured that you are not allied with the Horde against us,” quickly answered a gaunt old man whose hair was almost all white. Wil recognised him as the Prince of Moroug, Treldin ran Holdiem, a distant cousin of the del Liems. He is a well-known figure of authority among the northern kingdoms and many of them look toward him for advice. As a result Wil knew Treldin has the backing of the powerful mining kingdoms of the Northern Reaches even though Moroug herself is but a small mountain kingdom. A good ally to have.

“I can furbish no further evidence than this – the Horde have been observed by the Lords of Mullind to possess skill of magic weaving equal that of any among us, including those who dwell in Mullind. Without us, you have not the power to stop them if they employ the arts.”

There was a small shocked silence. Then almost everyone started to speak at the same time. No, it could not possibly be! How could such they know of such? The Mul is over exaggerating their powers. The Mul is in league with them! But yet … Even the rash Toumite hesitated. The Horde were uncouth savages and possesses only brute strength and a mad will to destroy. But magic-weaving? It was arrogance on the part of humans and Wil regretted to realise that he had felt the same way about the the Horde too. Borick lifted his hand in a plea for silence and only when Treldin spoke did most of the Council listened again.

“What sort of magic do they possess?” asked Treldin finally.

Some of the faces in the Council were blank. To them, magic is magic, woven by the practitioners of the dark arts. Wil understood what he meant though, as with his grandfather and Uncle Johann, both who seem to fade into the background. Wil kept a sharp eye on both of them. Wil almost automatically recalled his lessons on magic. There is basically two major variations of magic. Essentially, all magic flowed from the same source, the power of existence. He remembered from his notes on the subject – every single object contains certain innate raw power of its own, it is the power which keeps it in existence. This power can be drawn out by careful weaving and repositioning of the powers surrounding it, always careful to retain an overall balance. This is what magic-weavers do. Priests and other holy men derive their power from their gods by praying for them.

“This is sacrilegious!” sputtered a middle-aged man, who Wil know as The Archbishop of Mendachia. Mendachia is one of the few free city-states in the Lands, free only because of its enormous influence as the holy city of Mendach, father of gods. “Are we to listen to these godless men? The Almighty will surely protect us from the monsters!”

Some of the Council members looked uneasy while the kil Roadac completely ignored the interruption. Most religious men believe that only the gods has the right to grant powers of magic and the lay magic-weavers were godless heretics. “Very strange weavings – the likes which was never seen before. Their weavings seem extremely intricate and powerful. We are still investigating it.”

“King Borick,” demanded the Archbishop. “Are we to listen to any more of this heretical drivel? Should you not impose the will of Thiara, your patron goddess and wife of Mendach to lead them away from sin?”

Wil could understand his indignance. From what he read (many of the books that he learnt from were banned in most kingdoms, including Liemia) the gods were another source of the power of existence. He was shocked initially and still remained somewhat uncertain, having being brought up quite religiously to worship Thiara. However, the book he read described the gods as highly concentrated sinkholes of power. To enable miracles as performed by priests like the archbishop, the god has to yield a part of his power, essentially his very being. In return, he demands prayers, which will be transformed by the power of faith into the power of existence, which in turn can be released to their faithful, the cycle going on and on eternally. The book was quite thick and had no pictures. Wil read it from cover to cover ten times before grasping what the author meant to say. Somehow Wil struggled to agree with the author, who was quite anonymous. Putting his name on the book would of course be like signing his own death warrant.

Wil’s grandfather replied mildly, “The matters of the Council are worldly, my dear brother. Let us hear them out fully before exacting penance.”

Liemia’s patron goddess was Thiara, wife of Mendach and the King was nominally the High Priest of Liemia as well. Wil admired his grandfather and his choice of reply. He just reminded the Archbishop of his spiritual authority, asking him subtly to relinquish his authority to himself and allow him to make judgement. The Archbishop has no choice but to accede, since the Council is held in Liemia and the highest spiritual authority in Liemia was none other than the King. The Archbishop nodded grudgingly and the rest of the more religious members of the Council seem appeased for the moment.

“It is apparent that they stole the secrets of Arachdes from us,” claimed the representative from Brunnel, a large golden-haired man, glaring at kil Roadac. “The thieving demons!”

“Or perhaps the Muls sold it to them,” sneered a shorter bulkier man by his side.

Treldin’s face hardened.

“That is a possibility, who are we to say not that you taught them the dark arts,” said Treldin. “They surpassing you and now you are seeking our help to destroy all evidence of your treachery!”

“Preposterous!” exploded kil Roadac, his face reddening. “What is wrong with you people? Can you not see beyond your miserable squabbling that we face a foe more deadly than we did fourteen years ago?”

Traitor scum Horde-lover!” spat the hot-tempered Toumite ambassador. “We destroyed them once, we destroy them again!” He half drew his sabre out of his scabbard. The Archbishop stepped back, hands swiftly drawing a circle. A circle of protection, noted Wil critically. Very well practised, very well formed. The Brunnelian ambassador and his friend went straight for their daggers while the Semperian has already flashed his hriss out. Maybe it was not that ceremonial after all.

“You fools!” raged kil Roadac. “You – “

“Peace,” interrupted King Borick gently, his voice a calming contrast with the fuming Mul. “We are here to talk, not fight.”

Kil Roadac sat back heavily on his seat and Treldin held the Toumite with a restraining grip. The others, realising their awkward display has broken all protocols by going for their weapons in the Inner Court, sheathed their weapons. Everyone also noticed that Prince Johann and the King were not armed at all.

The Semperian bowed low and said, “Apologies, King Borick, one gets the temper not befitting. Begs for forgiveness now.”

“Don’t worry,” assured the King gently. “We are all uncertain and uneasy about these new happenings. I too have an announcement to make.” He paused for a moment, they surveyed the room in practised hesitation. “We have also sighted the Horde and we have fought them.”
Silence.

“What!” the Toumite shouted and drew his sabre in a sweeping arc and brandishing it before him.

“Put that thing down, Joraqk!” commanded Treldin sharply. “You are not going to fight any the Horde in Borick’s court!”

Looking rather foolish, Joraqk sheathed his weapon.

“Thank you, Treldin,” said Borick. Treldin nodded curtly. He does not really like surprises and there were one too many surprises already.
“What do you mean, you have fought the the Horde?” demanded kil Roadac. “Where did you do that and why were we not informed earlier?”

Borick sighed softly. For all Wil knew, it was a true expression of sadness? Resignation?

“Please understand what we have gone through.”

Borick signaled to Johann and with a slight nod, he walked quickly out of the room.

“My eldest son will bring in one of the the Horde we have captured. Let me explain what had happened and let you be the judge of it right here in my court.”

Wil sat terrified up in his hole. What is going on? How did he manage to miss it all? He accused himself mercilessly. He should have caught on to the signs – all that secrecy before the Council. He has thought it was because of the Council itself which was the commotion but never did he imagine -. He was going to meet, for the first time in his life, the creatures that killed his parents and ravaged his birthright. He trembled in fear and anticipation, heart beating so loudly he was positive they could hear him from below. Do I feel anger? he wondered to himself. Should I? All his life, Wil had imagined what he would do if he faces a creature from the Horde. Kill it! Torture it! Make it pay for what it did! Holding on to his breath, he stared below.