Programmer's Notebook

Towards Truly Useful Computer Applications

2006-01-15T23:24:00.000-08:00

In thinking about Personal Information Management or PIM, the main topic of this the January 2006 Communications of the ACM monthly, I started thinking deeply about how useless I find computers. And by that I mean simply the user interfaces we all have to work with and that come with the operating systems from which we all have to choose (and there aren't many). It seems to me that it's a constant battle to do anything useful on or with these things. Although not necessarily in bad shape I sometimes get winded just trying to get work done. These machines are stupid. They are certainly not a natural extension of us, and they certainly do not help us. We are users indeed. Like a heavy, lifeless, inanimate hammer, a computer today is simply a tool that does nothing lest we take it by the handle (or the keyboard) and wield it, blow after blow, until we've nailed down our poblem...or until we just finally give up and realize that we have little aptitude for tools of any sort.

I've been having these emerging thoughts (keep "emerging" or "emergence" in mind for later) about how a computer might become more useful, and it all stems from my work in Presence (when I was at Personity working with Thanos Diacakis on Presence and Instant Messaging systems) and my recent readings regarding PIM, computational linguistics and the relationship between geometry and meaning (Dominic Widdows' book).

One of the things I got out of reading some of the PIM articles was an idea about Contexts, Perspectives and Aspects when browsing, bookmarking and searching the Internet and the Web (I make the destinction because although the Web, today, seems to be the primary portal to the Internet for the common person, it's not the only way. There still remains email systems of course, and various other protocols such as network news (USENET), etc.) and how a more intellegent system that learns by observing will eventually, and seemingly Serendipitously, become more useful by assisting you because it comes to "know you." It comes to know your patterns, your ways of thinking, your interests and your desires. It becomes and extension of you. But before any of that you need to know yourself.

When it comes to knowing who I am or what I like, I have a hard time categorizing myself. The best way to describe me is to describe me as a kind of polymath or Homo Universalis (Universal Man or Person, if you prefer), although certainly not in the same way as one might describe Archimedes or Aristotle, da Vinci or Copernicus, or, in modern history, someone such as Chomsky or Feynman, Fuller or Gell-Mann, Von Neumann or Douglas Hofstadter as being a polymath. For these men were born great. I was simply born.

But Contexts, Perspectives and Aspects. What do I mean by them? Imagine someone polymathic, and my definition here is "someone with a great many and varied interests in the arts and humanities and whatnot who does not necessarily excel at them all." In fact he should consider himself lucky if he excels at just one of them. And this would describe me, I think.

Now imagine that this person's interests lie within the following categories, broadly speaking (the idea is that we can get more specific later which will help our new Intelligent PIM system get to know us better):

Computers
Books
Art
Music
Science
Mathematics
History
Sports
Games
Gormet Food
Movies
Politics

There is a lot of stuff in this list, but it's all fairly vague and not necessarily indicitive of the genius of a budding polymath. But these words, these "Contexts" are enough for the computer to begin with in order for it to begin to understand the nature of its user and thus to begin to learn how its user thinks and eventually augment the user's own mental functions. In other words, a computer system that makes it simpler for someone to think and to work (that is to think better and to work better), is a very worthwhile computer system indeed.

A polymath is described by his interests, he is described by what he is and what he does. Looking at our list we see that these are simple objects. What we need, however, are descriptive nouns, things that describe who we are and that can provide "contexts" for the various "roles" we play, whether professionally or otherwise. Therefore my interest in computers is more than a passing interest. I am a computer scientist, a software engineer, a software architect, etc.

As one interested in Books I would refer to myself as a "reader" or, more strongly still, a "bibliophile," which conveys my love of books and would go far in explaining the thousands of books that crowd our home.

With Art there are several avenues one could explore. There is the appreciator or art, the collector, say, or the art historian. And then there is the artist himself; the producer of art. Two branches from a single interest that would certainly assist our Intellegent PIM in segregating seemingly related material. Of course the artist is himself an appreciator of art, but it certainly is not always the case that the appreciator of art, the art collector, necessarily is an artist.

The New Computer Science?

2005-03-20T17:49:00.000-08:00

Computer Science traditionally is known as the branch of mathematics that concerns itself with the analysis of computer programs, or algorithms. Over the years, I think, the term has blurred, and has grown to encompass more meaning so that if you enter college as an undergraduate to study “Software Engineering” you get your degree in Computer Science. In a recent article in Software Development Times entitled “Is Software Engineering an Oxymoron?” Allen Holub, however, puts forth the proposition that this traditional discipline, Computer Science, has little to do with actually creating computer programs. In fact he states that while computers are good at solving mathematical problems the “vast majority of programs have little or nothing to do with algorithms and number crunching. Consequently, training in mathematics is of little or no value when it comes to writing good computer programs.” His argument, of course, is that if training in mathematics was valuable in writing good computer programs then mathematicians and physicists would be brilliant programmers. He then states without demonstration, although he must know something about this group because he states it, that this group [mathematicians and physicists] “tends to write miserable code that's focused too much on algorithms and too little on structure.”

Because computer science encompasses software engineering he then continues, “...computer science is neither a science nor an engineering discipline.” “Science,” he argues, “concerns itself with the formulation of proof of hypotheses.” Which, explains, we programmers simply just don't do. Engineering, on the other hand, is primarily concerned “with the mathematical analysis of structures, by they physical structures or electronic circuits.” We don't concern ourselves with that, either. The one odd thing to note here is that when Allen speaks about how mathematicians and scientists aren't brilliant programmers specifically because they focus too little on structure, he seems to imply that as good programmers what we do is focus both on algorithms and structure, in other words strike some sort of balance between the two. But then as he continues he describes how programmers aren't engineers either because we don't concern ourselves with structure as engineers do. Which is true in the ways he points out, which is to say we don't concern ourselves with the analysis of either physical structures or electronic circuits, unless we're designing software for engineers, for example, that requires us to have this sort of knowledge built into it, and then, of course, we would need to understand whatever it is that we would need to in order to design the target system.

What he finally goes on to say is that software engineering is about process and not about structural analysis, which is apparently what real engineering is all about. But for some reason, and I don't know why, I thought, too, that real engineering disciplines concerned themselves as well not only with structural analysis but also with structural synthesis, but then I would be digressing, so never mind.

According to Holub the closest that software engineering gets to real engineering is in the study of design patterns which, in his words, are “nebulous...because there is no single 'correct' structure for the realization of a design pattern.” And while you can present a real engineer with a structure and test him by asking whether or not the structure is sound, in other words whether it will stand or fall because “there is a provable right answer and a wrong answer. You can't do this with software... there's no right design and wrong design, just different designs.” Of course with this I would add good and bad designs but then he rebuts “the only definition of 'good' is 'I agree with the test writer.'” His point being that “it's not possible to certify software engineers,” how certification has to be based on standards of correctness as within the engineering disciplines, but that within software engineering there is no such thing despite the numerous certification programs available to programmers or “software engineers” or what have you—I am presuming that he means that certification programs (past, present and any foreseeable programs) for software engineers are essentially meaningless.

It's at this point where I found the article to become extremely interesting. If there is one thing that Allen Holub's words do it's to inspire ideas. I haven't explored any of his other works, so I'm no expert on Holub, but his short columns in SD Times, the few I've read, certainly contain nuggets of ideas that just inspire one to want to think further. There are times when I don't agree with a lot of what he might have to say and then there are other times when he makes a lot of sense, but always there seems to be something to fuel the imagination.

And so it's at this point where he begins to redefine programming, certainly not an original stance, but one that I've not heard in a while. In his mind programming should no longer be seen as a science nor as an engineering discipline because programming was really never either of these, but rather as a “liberal art.” He compares programming more to creative writing than to either engineering or physics and this is where I begin to understand him and in fact where I begin to even empathize and perhaps even “agree.” He continues, “to create a program is almost identical to the process that you use to write a book: research, formulating a thesis (or problem definition), an orderly exposition of the thesis.” He says that “these steps are central to both expository writing and object-oriented analysis and design,” and that “UML diagrams are really an application of symbolic linguistics...they diagram the structure of the problem statement and use cases in the same way that a sentence diagram illustrates the structure of a sentence.” He argues that the best way to train for this is not, if we look back to his opening argument, mathematics but rather the study of languages and writing. We should, instead of learning hard-core mathematics be learning English composition and “which teaches [us] how to write large, complex, documents like computer programs...and Latin...which teaches [us] how to analyze complex linguistic systems.”

He reminds us that Logic, which is a branch of mathematics, is not taught in the mathematics department but rather by the philosophy department, which I presume is further evidence for his ultimate thesis. And what mathematics we programmers might actually need, that is to say, what he believes to be relevant such as “set theory and the like...is easily covered in a one-semester class on the order of the Math-for-English-Majors classes offered by most universities.

And so his ultimate thesis, then, is that programming has changed and is no longer the “study and implementation of algorithms.” Programming, instead, has become the creation of complex documents. It's move, as if it were somehow inevitable, from the realm of mathematics and science to the realm of English composition and, I suppose, art is now complete. In other words, we programmers are not to be seen as the nerdy, analytical, number crunching geeks; the Fermats and the Newtons and the Liebnitzes of the twenty-first century. Rather we are now to be seen as some new kind of cyber avant-garde that somehow combines literature, linguistics, philosophy and logic to compose and so create not just English compositions, but rather compositions that move, or rather works of active complexity, documents in motion, if you will. We are the Shakespeares and the Miltons, the Whitmans and the Wordsworths, and the Keroucs and the Creeleys of the new Computer Science and for the new millennium.

Exception Handling and Design Techniques in Java

2005-02-05T20:12:00.000-08:00

In an effort to put together information about good practices in exception handling, especially when it comes to design issues, I've written a paper called Exception Handling and Design Techniques, which is a work in progress and not quite complete.

Thoughts on XML and Beyond

2005-02-01T18:32:00.000-08:00

XML is verbose. It seems necessary that we need to describe a thing by naming it and so we start out by delimiting it in XML with an element. The root element names and, by its name, should tell us something about the entire XML document (still unsure about 'document' as the name for the XML thing/bundle/blob).

And so we make an attempt as we might when considering what we'd do when modeling classes of objects in an object oriented language—or so this is how I see it. Let's describe in an XML document a book, but we'll leave out all the details. I am just starting out by naming the what I want my document to eventually contain, information about a book, which we'll see might not be enough, but then this might also be a fundamental shortcoming of the language. I don't know.


<?xml version=”1.0” ?>

<book>

</book>

So far so good, if not a little verbose already. Ignoring attributes for the moment and sticking with elements (and from this point forward assuming the <?xml?> header, let's put some more meat into what kind of information a book XML document would contain (for brevity, for now, I will use the short-form for elements that contain no sub-elements because I don't, as yet, intend to include any actual information about any particular book.


<book>

    <title/>

    <author/>

    <isbn/>

</book>

This, I think, would be the minimum amount of information one might need to collect about a book. Perhaps, for convenience, you could also add the elements <publisher/> and <publication-date/>, but having the <isbn/> would allow you to discover this information. Then again if you simply collected the ISBN and did away with every other element then you'd have a truly minimalist representation of a book XML entity. But we'll just keep things as we have them.

With this XML entity we can, in a single document (unfortunately, or fortunately, however you see it), describe a single book. To describe more than one book you'd have to create many such documents or revisit the structure of your document and consider revising it just a bit.


<books>

    <book>

        <title/>

        <author/>

        <isbn/>

    </book>

    <book>

        <title/>

        <author/>

       <isbn/>

    </book>

</books>

Now our new structure allows us to place many book elements within a single document under the <books> root elements (note the clever use of plural). Anyway, this is all leading up to something else entirely.

When I first heard of XML I thought it was a very cool idea. When I saw an example very much like this one, my imagination took off and I didn't bother reading on until a little later. For one I thought that the XML described the structure of the document and I didn't think that the actual XML elements accompanied the data itself (I had been working on an odd kind of object/relational mapping technology using some client/server middle ware for E-Transport at the time and XML was still in it's infancy... in fact I hadn't heard about it until after we were all well into the project).

Upon seeing the XML structure above I imagined that the stream of data, flattened for transfer for example, looked something like the following (I didn't know about attributes).

<<<The Odyssey><Homer><0140268863>><The Iliad><Homer><0140275363>>>

Unflattened, for readability, I thought it might look like this


<

    <

        <The Odyssey>

        <Homer>

        <0140268863>

    >

        <The Iliad>

        <Homer>

        <0140275363>

    >

>

Then, as with simple expression parsing (e.g. matching the '<' and '>'), you'd know which piece of data matched which element in the XML “document” description. But I was mistaken. For every XML document we have a crap load of overhead. Every piece of data that has an element naming it is accompanied by that element... twice; not to mention the the parent element, book (open and close elements), one for every book and of course the root element. Oh, right, and for every close element there is one extra character, the '/'.


<books>

    <book>

        <title>The Odyssey</title>

        <author>Homer</author>

        <isbn>0140268863</isbn>

    </book>

    <book>

        <title>The Iliad</title>

        <author>Homer</author>

        <isbn>0140275363</isbn>

    </book>

</books>

But I was thinking that it might be interesting it you could standardize on a compact form of XML where instead of the XML we've come to know and love, come up with (or perhaps just use XSD) a standard for describing in XML the structure of data (a document, for example, or an image or whatever). Or perhaps this should just be for documents (see the OpenDocument standard presented by the OpenOffice people for the new OpenOffice 2.0 stuff—not sure what this is).

Anyway, you could do something like I had naively imagine oh so many years ago:


<?xml version=”1.x” document-definition=”books.xdd” ?>

<

    <

        <The Odyssey>

        <Homer>

        <0140268863>

    >

        <The Iliad>

        <Homer>

        <0140275363>

    >

>

So I just now made up the first line, taking artistic license. Xdd, XML Document Definition. Why not? It's up to the system to find the definition in some way, maybe via JNDI.

On McCulloch-Pitts Artificial Neural Networks

2004-11-24T22:36:00.000-08:00

I’ve spent several weeks, on and off, learning about artificial neural networks and, thus like my GO-writing days, I am attempting to put down on paper my understanding of artificial neural networks (ANN from now on).

I have been reading, albeit slowly, a book called “Fundamentals of Neural Networks: Architectures, Algorithms and Applications,” by Laurene Fausett. There is no code in the books, but rather it is filled with diagrams, explanation of the kinds of ANNs out there and the algorithms that they employ. It is also heavy in mathematics, but I have been slowly pressing my way through, trying to understand.

As I’ve been going along in the book, I’ve been thinking about how to go about writing a general library of classes that would allow me to model the kinds of ANNs and then execute them given some input data. So far I’ve designed a crude little class library that contains the following classes: Edge, Neuron, Activation, and Network. The Network class is not completed or working yet, but I have been able to, by hand, string together Neurons and Edges with simple Activation objects and get something to work.

A little bit of theory

The following diagram shows the general architecture of a McCulloch-Pitts Neural Network. The weights on X1 and X2 are said to be “excitatory,” while the weight, -1, coming from X3, because it is negative, is said to be “inhibitory.”

Figure 1. McCulloch-Pitts General ANN Architecture.

So far I can model McCulloch-Pitts neurons for solving simple binary logic functions (AND, OR, AND NOT, and XOR). Here is a diagram of an XOR network. Its interesting to look at.

Figure 2. A McCulloch-Pitts neural network for XOR function.

Z1, Z2, and Y each have a threshold of 2. If you follow, in turn, the input bits for the XOR truth table:

A	B	XOR	C
1	1		0
1	0		1
0	1		1
0	0		0

Thus ‘a XOR b’ where a=1 and b=1 yields 0. If you input a into X1 and b into X2 and run the network, Y will yield 0 when completed.

The routines I’ve am designing work with the different layers. For example, X1 and X2 are layer 0, or the input layer (I’ve read many documents online and such that do not treat the inputs as neurons and thus layer 0, in their models, would begin at Z1 and Z2. In the book, Fausett talks about the inputs as neurons, and so I’ve taken to viewing them as a layer. Thus while the diagram above shows a 2-layer network, my layer architecture would have three layers.

Originally I had a separate vector of input neurons, but then the code began to look a little more complicated than it really was. The Activation class is where some of the magic occurs. Essentially the Activation function for the McCulloch-Pitts neuron states the following: f(x) = {1 if x >= θ, 0 if x < θ}, where θ is the threshold.

On Artificial Neural Networks

2003-11-26T21:56:00.000-08:00

I've always had a fascination with artificial neural networks although I have only a vague idea of how they work. I suppose that I’ve feared the mathematical aspects that I have imagine accompany them. But this evening taking a stab at reading a book entitled “The Fundamentals of Neural Networks,” I finally began to understand more than I had thought I might.

I was reading about the McCulloch-Pitts neuron and the book demonstrates how to use it as a function that solves simple logic equations: AND, OR and AND NOT. I decided to see if I could code something in C++ that would model these kinds of neurons and my solution worked. I’ll have a little more on this later.

Thoughts about Graphs and Artificial Neural Networks

2003-11-24T21:07:00.000-08:00

I’ve been reading about Graph algorithms and a book called Fundamentals of Neural Networks. Both of these topics really interest me, but I think I am more interested in graphs and graph theory, but learning about graphs in computer science, the algorithms, etc., really help me understand some of the theory.

Sometimes I’ll close my eyes and see small graphs in my head. Usually they’re not directed, but I’ll imagine myself traversing the graph, going from node to node, seeing where an edge takes me, trying to think how I might automate a process to do this in order to find its way around. I sometimes thing that a process could have memory or perhaps lay breadcrumbs at the vertices. I then sometimes think about how a process could solve a maze and I sit again in the dark with closed eyes and imagine a small square (A. Square?) running around the maze in a certain way that will make him always solve the maze. I am afraid to try to solve these problems myself. I think that I am entirely too stupid, and that I will fail. Then there are times when these thoughts don’t even enter into my mind and I try, perhaps foolishly, to solve these problems.

I learned the other day about two kinds of a. neural networks. One, a single level network and a multi-level network with the first level (after the input) being a hidden level within the network. I also discovered that the edges connecting nodes to other nodes hold great significance. They are weighted and it apparently is the fundamental reason why neural nets work. Calculating the weights properly helps the network sense the pattern it needs to sense in order to create an output of something it recognizes. I suppose this could be used in reading in a scanned report written on a typewriter, for example. Or a scan from a page of a book. When you scan these sorts of things you get an image, which is simply a bunch of seemingly random goop that some program knows how to display. Using neural nets (that are trained) you can teach it to recognize the pixels of the scanned image as actual text and thus you translate the words of an image to actual computer data. From image to a word document. These sorts of programs are called optical character recognizers, or OCRs and today they are apparently very accurate. Although none are foolproof and it still takes some mucking about afterward to fix the mistakes it makes after doing its magic.

I don’t yet know much about neural networks, and the math does seem to be a little intimidating to me, but I can at least read what I can from the book and think of neat ways to use neural networks to solve problems. I have that entrepreneurial gene. I like having the ideas, but I want someone else to worry about the technicalities. Still, I want to know enough about these technical issues so that I can have good ideas. Nothing is more embarrassing that coming up with an idea using knowledge of something that was completely flawed. Then again, it could lead to something brilliant, or at lease entertaining.

Thoughts on XML Web Services

2003-11-22T14:23:00.000-08:00

I’ve been reading more about C# and Web Services. I have been trying to think of some sorts of web services that I could write and then perhaps make them into products to sell or at the very least, sell the services. I would need to host these services on some other machine or get static IP addresses here with faster upload time. As it is my web server over this cable modem is very slow. I mean download to my PC screams but going the other way I think is no faster than a 56kbps modem. With the professional package I believe that its over 300kpbs, which would be adequate, perhaps, to host some kinds of services.

Some things that come to mind are services for game logic. In the book I am reading there is an example of using a web service with session state for hosting black jack games between a player and virtual dealer. I was thinking of creating a company called GameLogix or GameLogic or something along those lines where I would provide Web Services for various popular card and board games, provide the proxies stubs for C# and Java, for example, and then let people write clients (web or windows forms or whatever).

An idea I got from the MSDN site is to host a Favorites web service where people can securely maintain their list of favorite web sites and retrieve them from anywhere at any time. Also from MSDN was to create what they call ColdStorage (I think), which is basically a limited amount of file storage space. I could also provide a web page for uploading and maintaining people’s personal file storage or perhaps create a rich windows client to do this. The web service would allow people to browse, delete, rename and save files remotely.

An idea that I thought of was to create a web service that allowed you to run a finite state machine whose state actions would be themselves web services. You essentially would upload an XML document that describes the state machine (states, actions, etc.) and then feed it input. At the moment, however, I am at a loss for what sort of state machine you might wish to design using this sort of system. One thing that does come to mind would be a state machine for controlling remote devices. Turn something on, turn it off, change some property, whatever.

I suppose you with this sort of state machine you could create a system that would monitor and control remote servers. For example during the Personity days we had a web application that would allow us to monitor and control at a basic level the presence and instant messaging servers at some location. Imagine if you wrote a FSM to control the service. You could send Start and it would call another web service that started the remote Presence server. The response OK might be returned putting the FSM in the Running state. We also had a kind of paused state where we would no longer accept connections. And of course we could take a server down, putting it in the FSM in the stopped state.

Creating a Filecopy Routine to Work with std::copy()

2003-11-14T19:40:00.000-08:00

In an attempt to figure out how I might use the std::copy() method with istream and ostream iterators to copy, byte by byte, data from one file to another, I’ve come up with several solutions.

The std::copy algorithm uses the standard stream input operator, >>, and if you set up the copy statement like such:

copy(istream_iterator(in), istream_iterator(), ostream_iterator(out));

when run it seems to skip characters, namely end-of-line and perhaps even other white space.

Before I bothered delving into ways that I could manipulate the streams in such a way as to not skip such things when reading bytes into memory, I thought that I might have to write my own version of copy (something I would eventually have to do anyway because of other criteria that I’ve yet to mention), or perhaps work on a new kind of stream iterator, which didn’t really make sense.

After some contemplation and taking a gander at the source code for copy I realized, as mentioned above, that it uses the stream input operator, >>, and like any other operator this one, too, can be overloaded for different types. Thus I created a new type (a very small, shallow class) called Byte whose stream input and output operators simply called stream::get() and stream::put(), respectively, and damn if it didn’t work. Here is the snippet:

copy(istream_iterator(in), istream_iterator(),
ostream_iterator(out));

The definition for Byte is:


class Byte {
  public: Byte()
   : m_byte(0) {
  }

  operator char&() {
    return (char&)m_byte;
  }

  private:
    unsigned char m_byte;
  
 friend std::istream& operator >> (std::istream& stream, Byte& byte);
 friend std::ostream& operator << (std::ostream& stream, const Byte& byte); 
};  


The implementation of the stream input and output operators is very simple.  

std::istream& operator >> (std::istream& stream, Byte& byte) {
  stream.get(byte);
  return stream;
}

std::ostream& operator << (std::ostream& stream, const Byte& byte) {
  stream.put(byte.m_byte);
  return stream; 
}

When I tried this on a fairly large (about 49 megabytes) file, the thing turned out to be dog slow, taking minutes to complete rather than seconds. I assumed that the streams were being buffered in some way, and perhaps they are, but it was unbelievably slow (although as I discovered, building these classes and my copy routines in debug mode, with the exception of my ByteBlock type, resulted in extremely slow input and output, but when I built everything in release mode, I realized that some solutions worked the same as my ByteBlock, but read on). So, I thought more about it and an idea occurred to me. Why not create another type that has a built-in buffer (an array of characters) and whose stream input and output operators made use of the streams’s read() and write() methods, respectively? And thus ByteBlock was born, which isn’t so complicated except for the input stream operator function. Here is the code.


class ByteBlock   {   
  public: ByteBlock() : m_bytesRead(0),       
    m_fileSize(-1),       
    m_totalRead(0) {     
  }    
  private: 
    unsigned char m_block[10240];     
    int m_bytesRead;     
    long m_fileSize;     
    long m_totalRead;
    friend std::istream& operator >> (std::istream& stream, ByteBlock& byte);
    friend std::ostream& operator << (std::ostream& stream,  const ByteBlock& byte);   };    
    std::istream& operator >> (std::istream& stream, ByteBlock& block) {
      if (block.m_fileSize == -1) {
        stream.seekg(0, std::ios::end);
        block.m_fileSize = stream.tellg();
        stream.seekg(0, std::ios::beg);
      }

      std::size_t leftToRead = block.m_fileSize - block.m_totalRead;

      if (leftToRead) {
        stream.read((char*)block.m_block,
          std::min(sizeof(block.m_block), leftToRead));
        block.m_bytesRead = stream.gcount();
        block.m_totalRead += block.m_bytesRead;
      }
      else {
        stream.setstate(std::ios_base::eofbit | std::ios_base::badbit);
      }
  
      return stream;
  }

  std::ostream& operator << (std::ostream& stream, const ByteBlock& block)   {     
    stream.write((char*)block.m_block, block.m_bytesRead);     return stream;   
  }

Note that the input stream operator, the first time it is run, calculates the size of the file being copied. It then keeps a running total so that it always, in the end, reads precisely what is left in the file to read. This keeps the stream from becoming invalid and from the copy algorithm from skipping the final call to the output operator, which always resulted, in this manner, with an incomplete copy. Note that I check to see if there are any bytes left to read, if not I simply force the stream to be bad and to be at eof. Thus copy quits, the streams close and all is made right. Here, by the way, is the simple copy function: void blockCopyFile(const char* source, const char* dest) { ifstream in(source, ios::in | ios::binary); ofstream out(dest, ios::out | ios::binary); copy(istream_iterator(in),
istream_iterator(),
ostream_iterator(out));
}

Of course the more I dug into streams the more I began to realize that there must be a simpler way. A query on the comp.lang.c++ newsgroup revealed a simpler solution. Essentially just output to the output stream the input’s stream buffer like such:

void simpleCopyFile(const char* source, const char* dest)
{
ifstream in(source, ios::in | ios::binary);
ofstream out(dest, ios::out | ios::binary);

if (in && out)
{
out << in.rdbuf();
}
}

When I tried this, however, it turned out to be piss slow. I mean I couldn’t believe that this would take minutes to complete over a 40 megabyte file. However, once I built this in release mode rather than debug mode using VC++ 7.1, it flew! It only took seconds to copy the file.

The odd thing, however, is that while this takes its time in debug but flies in release mode, my solution using the ByteBlock worked very fast no matter the mode in which the project was built.

The real reason I wanted to explore copy, however, was that I wanted to use the standard library and extend it as needed to solve the problems I was facing implementing Netspoke’s Archive Viewer software. Using hand coded loops I can control when a loop needs to terminate prematurely (e.g. if I press Cancel, for example, on the progress dialogue).

A Netspoke conference archive contains several pieces. There is a standard header of a specific size (for now). After the header there is an index that contains the information, in the order that they occurred, regarding the events that were captured during a conference. After the index is a large section that contains the binary data, if any, that each event carried with it. For example, a slide show image, a JOIN or LEAVE event would contain the id and name of the person joining or leaving, etc. The very last part of the archive is the voice data that is captured during the voice portion of the conference, which of course happens in parallel with the web conference events.

The Archive Viewer actually takes its queues from the voice stream and fires the web events during the appropriate times. Essentially I have a thread that polls the media player and then checks the next web event to see if the current time index that the media player returns is equal or greater than the next event’s time index. If it is the event is fired and applied to the viewer.

The Archive Viewer can load an archive from disk or stream it over the web. When it loads from disk a progress dialog is displayed. Because loading involves decompressing elements of the archive and saving the event data and voice data into separate, randomly named files (in case we want to add events, but the Archive Viewer is read-only and shouldn’t have to worry about this sort of thing) I need a way to copy and/or append data from one file to another. And so I had an idea.

I thought that if I could use the std::copy algorithm with istream and ostream iterators to copy and append data to files, I thought I could extend the standard library by creating a copy_while algorithm that would loop and copy data while some state where true (or false). That is, while the user hasn’t pressed Cancel, and if during the save or load we’re copying a file, keep copying, otherwise quit so that the Archive save or load mechanism can recover, remove any temp data files and revert to the state it was in prior to the load or copy.

Writing a Computer GO Game

2003-11-05T15:20:00.000-08:00

This is the tale of a mediocre GO player who is attempting to write a computer game called GO, one of the hardest games to write and, indeed, it has stumped the best minds who have tried to create a game worthy of even a mere amateur ranked player.

So, I’ve taken on the extremely ambitious and perhaps somewhat foolhardy journey into the realm of writing GO. It all began with a simple idea, really. I was bored and wanted something to do, and having only my books and some PC-based GO games with which to study and play, I began to think not about playing the game so much as about creating my own computer GO game. The idea kept eating away at my brain, burrowing, in fact, into the depths of my subconscious, and I began to even dream about a computer GO game. And unfortunately when I get my mind wrapped around something like this, I can’t stop obsessing over it, and so one day, recently, I decided to take action.

I decided that I didn’t necessarily want to jump right in and take on the creation of an entire GO-playing computer program, but rather I thought that I should, over time, write the tools in C++ necessary to begin the creation of a GO-playing program. Basically, I began writing a foundation, a framework, if you will, for designing a GO game. And I plan, over time, to learn more about the AI necessary in creating a computer GO player, what I call the GO-engine. Actually, I’ve come up with a slightly snazzier name than simply “GO-engine.” I thought the “Revelation Engine” had a nice ring to it, what with its connotations of divine truth and biblical rapture.

In fact, the Merriam Webster Collegiate Dictionary, 10th edition, defines revelation as “an act of revealing or communicating divine truth,” or “an enlightening or astonishing disclosure.” Perhaps the name, being biblical and apocalyptic, isn’t necessarily appropriate, but I like it. Then again, perhaps the “Wrath of God” connotations it seems to evoke will inspire me to delve deeply into creating from nothing this monstrous beast, a Dan-level-strong game, and thus aid me in procuring that million or so reward that has thus far eluded many an attempt at writing such a thing.

Now you might think that like any disciplined researcher I would have spent many days, nay weeks! pouring through the literature and theory of games, especially the game of GO. Perhaps you might also have thought that I would have downloaded whatever source code that I could find (gnugo anyone?), studying it for hours in order to understand the nature of a GO computer game. But no, not me. I admit that I did download the source to gnugo and I do, every once in a while, even browse through it. And I also admit having, from time to time, read some bits and pieces of GO computer game theory, but for the most part, and like the lazy fool that I am, I decided instead to go about doing my own work, my own thinking, making my own mistakes.

While I plan to read about neural networks and other potentially useful ideas for creating my Revelation engine, I’ve decided that I should not pollute my mind with the thoughts of others. At least not now. I’d like, rather, to crash and burn on my own than to take the easy way out. And besides, it gives me the intellectual stimulation I need away from work, the stimulation that I don’t get anywhere else, the stimulation that only comes through self-discovery and meditation.

The Game…

Thus far I don’t have a game, but rather I have the notion of a GO board, playing pieces (go stones), points in space on the GO board, the notion of chains (‘Friend’ stones that are linked on the GO board), and a rudimentary display abstraction for displaying the GO board (currently it shows a simple text-based board similar to that of gnugo’s text board; and no, I did not look at the source code, I merely copied the output).

So far you can place a stone on the board, and some rudimentary rules will check to make sure that you didn’t place it on a point out of bounds (e.g. x(20), y(32) on a 19x19 Board) or on a point already occupied by a stone.

The board keeps track of a map of stones keyed by normalization of the points. By normalization I mean (X*100+Y). Thus, a point on the board at x(1), y(2) hashes to a value of 102. The second piece of data of the map pair is a smart pointer to a stone. I try to not waste memory by keeping smart pointers to each piece used, thus a stone on the board is the same as the same stone managed in a chain or in the captured pile of a player--a single instance of a stone is the same stone throughout its lifetime during the game.

Chains are merely another way of looking at the stones, and are useful in determining the strength or weakness of a group of connected stones on the board, or so I imagine. That is to say, while the board keeps track of all stones on the playing field, chains keep track of those ‘like’ or ‘friend’ stones (i.e. stones of the same color) on the field that are connected. These are sometimes called strings, or perhaps they’re always called strings. I like the notion of chains. Chains to me are symbols of strength. Maybe I can take the metaphor further and speak of walls and barricades. And I haven’t even begun to think about eyes. Whilst my toolkit can managed and recognize chains, and soon be able to count the liberties of a chain, it has no notion of eyes… Eyes will be an interesting challenge. And truthfully I have no idea if I’m even going about this in the right manner, but I suppose that any manner in which one chooses to go is right for him, as long as it gets the job done to his satisfaction, or until he becomes completely bored of the entire thing and decides to go do something else.

A little background… I began one night last week just putzing around. I created a simple console application called gotools, and then began creating each of the C++ classes in the same file. My next step, I think, is to reorganize the source code, putting each class into its own header file and source file, thereby making things a little easier to read. Not that Microsoft’s Visual Studio doesn’t do a good job what with it’s class browser, but I don’t plan to keep it specifically a Visual C++ application. I am designing it purely in standard C++ so that it can be built on any platform that has a standard C++ compiler. Of course specific platform code will reside in subclasses of the IDisplay interface allowing it to be compiled conditionally, or perhaps through project and make file configurations. I don’t know yet. Right now my main concern is building the framework so that I can begin to design the Revelation engine. A text-based interface, for the moment, will suffice.

Here in fact, in Figure 1, is a printout of what my go tools look like. Well, the text-based display, anyway (click this link: text screen).

I had in fact created a version previous to this one, but after I’d noticed that the text board that comes with gnugo was better presented, I decided to borrow it’s design. Note that the ‘I’ is missing from the coordinates across the X axis. I don’t know why this is except that in a number of books and in a number of GUI-based interfaces for IGS (Internet GO server), the ‘I’ is left out on purpose. I’ll have more on this later. My first thought is that it’s left out so that it doesn’t clash with the number ‘1’. I9 seems a little odd, but I wouldn’t think that it would be too difficult to interpret by eye. Still, there is a reason and I shall uncover it.

The thing to note here, too, is that the letter ‘x’ stands for black pieces while ‘o’ stands for white pieces. Using ‘b’ and ‘w’ seemed awkward. The x and o are symmetrical enough that they appear to be round stones, assuming you can stretch your imagination just a bit.

11:49 PM

Rudimentary chain management works. I can merge chains if a stone connects two or more chains together. For example assume I have the following scenario (forgive the crudeness of these sketches):

A B C D E
5 . . . . .
4 . x . . .
3 . x . x .
2 . . . . .
1 . . . . .

Initially, after these black pieces have been placed, the board’s chain manager recognizes two chains of black stones, [B4, B3] and [D3] (I’ll use the simple set notation here to denote a chain of stones.) If I were to then place a black stone at C3, the chain manager would merge the second chain [D3] with the first chain [B4, B3] and then add C3 to the merged chain, thus creating one chain from two.

A B C D E
5 . . . . .
4 . x . . .
3 . x x x .
2 . . . . .
1 . . . . .

I now have a single chain [B4, B3, C3, D3].

The next task will be to calculate a chain’s liberties. A liberty is a free adjacent point of a stone. Thus

A B C D E
5 . . . . .
4 . . . . .
3 . . x . .
2 . . . . .
1 . . . . .

[C3] has four liberties, (C4), (D3), (C2) and (B3) (note here I used parenthesis around points on the board that are empty. This is, of course, my own notation and, apart from the standard coordinate system of numbers on the Y-axis and letters on the X-axis, adheres to nothing else that I know of.

For future reference, I will have to remember to make my toolkit compatible with SGF, which I believe stands for “Standard Game Format.” It is a standard file format for storing moves made in two-player games such as GO, Backgammon, Chess (I think), etc. I looked at a sample of an SGF file and it seems quite cryptic. But I think I’ve found some BNF grammars for the SGF language and thus I can probably write a parser and generator to read and write SGF files, respectively. I might probably create, for the moment, my own persistent storage mechanism based on XML for storing GO moves. And I might, at first, keep it simply for GO and not worry about keeping it abstract enough for any two-player game, although that, in itself, shouldn’t be too difficult a task.

TODO:

1. Create static handicap Points for the different board sizes and then allow a handicap to be specified when generating the board.
2. Allow the create of a stone’s coordinates (point) to be specified as “<#>”. For example, “C5”, “T19”, “D7”, etc. Add this to the StoneFactory.
3. Design the liberty counting function for chains.
4. Pray for divine inspiration.