The Quixotic Engineer

I’ve been following a very interesting thread on the skrud.net forums recently about the role of formal documentation in the software process. In it, Dr. Constantinos Constantinides interjected with some sound arguments in favor of formal documentation. I thought he presented a very persuasive defense of an aspect of software design that is often maligned by undergraduate students. Because the thread in question requires forum registration to read, I sought his permission to reproduce the arguments here

The topic of discussion was SOEN341, Concordia’s “Software Process” class. Many past and present Concordia students were grumbling about what they felt was excessive formality and an overemphasis on arbitrary documentation completeness in the class. Dr. Constantinides’ argument was as follows:

In Software Engineering, I am not much interested in those things which you either can build on your own or you build only for yourself. I am very interested in those things that you alone cannot build and in those things that you together with a team of engineers build for others. In doing that, you must prove to me (your boss, line-manager, stakeholder, etc.) that what you are about to build is what you are expected to build (validation), and what you have built is what you were expected to build (verification). Asking me to “just trust” your code because “you know what you are doing” (maybe because you had a high GPA in some college, or you’ve been programming in this language for many years, etc.) is not enough for me. I cannot trust my medical / financial / … data on how sexy your CV looks. I want proof of concept for a solution to my problem. Architects and civil engineers refer to this as “blueprints”; Electrical engineers refer to this as “circuit diagrams”, etc. The proof of concept can done by paper and pencil, chalk on a blackboard, drawing software, etc.

Later in the discussion he elaborated on this position:

Let us talk about development as the production of a number of artifacts, at various levels of abstraction.

In my opinion EVERY artifact produced during development is important: You have artifacts produced in a natural language (e.g. English), others produced in a modeling language (e.g. UML) and others produced in a formal system (e.g. C++). You must be fluent with all different languages because you use each one for a different purpose. Yes, we can argue that implementation is vital because code is absolutely necessary for a system to run. However, in the absence of a requirements / analysis / architecture / design model, your level of confidence on the correctness of the system is rather low (and the maintainability of your system is very low).

Someone told me: “Go to the code.” Yes, I can do that. I should be able to do that. The code describes your rationale at a very low level and it’s not very helpful for a number of reasons including a) I need to stop you from doing something wrong before you start coding and b) a formal system is rather cryptic when it’s the only means of communication. Again, let me reiterate that I am interested in VERY large scale systems, not something which is a couple of thousand lines.

To maintain a high level of confidence, you must build strong confidence during requirements analysis (validation) and maintain it throughout the development life cycle. Because as your project manager I am the one who is responsible for it (see: lose the contract, being sued, etc.), then if your use case model is not validated I will not allow you to proceed to analysis. If your analysis model is not validated I will not allow you to proceed with architecture-design and if your architecture-design is not validated I will not allow you to map it to code. If your code is not correct (if tests fail etc.) or consistent, I will not allow you to consider the verification of requirements successful (for example, assume iterative process).

There is no such a thing as “documentation and source code.” I would love to eliminate the word “documentation” from our vocabulary. Let us talk about artifacts and models. With the exception of the magnetic 1s and 0s, everything else (installation scripts, user’s manual with screen shots, test suite, source code, supporting libraries, architectural-design model, analysis model, use case model – requirements) can be regarded as “documentation.” However, the problem is that many software engineering textbooks (and many instructors in many schools) place emphasis EITHER on requirements / analysis / architecture / design XOR (that’s an exclusive OR) on implementation. I think this creates confusion (and frustration) among students. Especially in the first case (emphasis on early stages only), it is very frustrating to focus on formatting (and dissemination) of reports and other issues as if a model will be mapped to implementation by magic or as if it’s not our job to map it. Give me the design mode in pencil and paper, as long as it is correct. Show me that you can faithfully map it to implementation.

Because of the above and with all tradeoffs considered, then my view is that ALL artifacts are equal. In fact, there are artifacts produced even after deployment (e.g. execution traces) which are valuable for post-deployment tasks (maintenance and evolution).

[...]

One last comment. There is a misconception (among us) that Software Engineering is that bureaucratic activity you do AFTER you build something to provide supporting documentation and explain what you did so that you can satisfy your instructor/ line manager/ boss, etc.. This is wrong. The adoption of UML as a common vocabulary helps us produce small documents and the advancement of modern (iterative) process methods helps us do the whole thing with confidence. Software Engineering is not about avoiding programming. In fact you cannot be a good software engineer if you are not a very good programmer.

Thanks again to Dr. Constantinides for allowing me to quote him here.

I think I had best wrap up this series before I completely alienate my non-programmer readers. Firstly, I have an algorithm by fellow blogger and mathematician Tim Sell of Planet Nectarius.

[A.I Competition - Tim's Algorithm]

What I did was get 3 values for all the empty spaces to the left, right and in front of the player. To be “in front” the empty spaces must be connected to the forward move square and it must be forward of the player. So each connected space is bounded by a rectangle to one side of the current cycle position. I then regard each rectangles emptiness value as half if the nemesis cycle is within that rectangle. Then I arbitrarily decide to move to the square which has the second highest empty space value associated with it. [...] Basically the idea is to cut of the nemesis cycle from the empty space without retreating into it.

He later added:

I made a slight mistake, best explained by example: If I am getting the space that is south, the GetSpace function gets each empty square that’s below it and to the left and right recursively. What I meant it to do was to do that, but also go up again if it is still below the player’s cycle, this would let it account for spaces that go down and then up again to one side.

To reiterate, what Tim’s algorithm does is compare the amount of space connected to the three spaces adjacent to the cycle. However, it only counts the spaces contained in a rectangle defined by the cycle and the scanning direction. To illustrate:

The forward scanners will only scan within the forward box, the left ones within the left box, and so on. It’s an interesting approach, but I fear that it may suffer from the same weakness as algorithm 3: doing a bad job of filling empty space slowly. Without real code to test, of course, this is mere speculation.

Lastly, I have a few wild and crazy algorithm ideas I came up with while trying to approach the problem sideways. I don’t think any of them would work particularly well, but they make good thought exercises.

• The Calculus Approach: I thought of this algorithm while working on a Numerical Methods assignment. We could send out a 90 scanners, 30 in each direction. These scanners would have semi-random behavior; they would never run into a wall if they could avoid it but would make all other turning decisions randomly. These scanners would leave walls behind themselves on cloned maps as they moved, and return their path length upon death. Once they have all died, we could take the average of their path lengths and choose to turn in the direction with the highest average. We could increase the number of scanners for a better estimation at the cost of processing time.
• The Cardinal Directions Approach: We could send out four scanners from the cycle: one that can only turn North and West, another North and East, another South and West, etc. We could then calculate the free space value for each cardinal direction using the average of the two ordinal directions: (NW+NE)/2 = N. We decide in which direction to turn based on this information.
• Average of BFS and DFS: I mentioned in my last post that a Breadth First Search and a Depth First Search estimated free space in a slightly different way. Perhaps the best solution would be to perform both and take the average, hoping that the strengths of one would cancel out the weaknesses of the other. It would involve twice as much calculation, but I think it might actually work reasonably well.

In conclusion, I would like to quickly thank Sven and William (my CS games teammates), Alexei, Andrew and Tim (for taking the time to discuss their algorithms with me), and Renaud and Thomas (for the lengthy algorithm discussions.) I learned a lot by writing this series, and am now exceptionally prepared for next year’s A.I. competition.

Since I returned from the CS games a few weeks ago, I’ve been vigorously discussing the Tron A.I. problem with anyone who would listen. Much of this took place on the skrud.net forums, where I had a chance to debate with Alexei and Andrew of the other Concordia team. Their team tied for third place on the second day, and they had some really interesting ideas. I’ll be posting snippets of our discussion here, including the pseudocode for their algorithm.

In part 2 of this series, I wrote about how the recursive Algorithm 4 was memory intensive because it needed to clone the entire map at every step. Alexei, however, thought of a very clever way to get around this problem by implementing backtracking.

[A.I Competition - Backtracking Algorithm]

Using this algorithm, you would need to clone the map exactly once (assuming the original map cannot be modified.) In Alexei’s words:

Nothing is being cloned, because you are always operating on the same state. As it recurses in, it marks the node, and then unmarks it as it recurses out.

So if you’re in a 10-level deep recursion, you have 10 nodes marks as visited (ie the “path” you’re currently looking at). Suppose that you’re in that state, and there’s 3 directions for you to take (a, b, or c).

You call yourself on [a], which gets marked as visited. Then [a], calls all of its adjacent nodes, one by one. Each one marks itself as visited, and before it returns, it marks it as unvisited. So after your call on [a], your array of booleans (which you didn’t clone ever!), is in the same state as it was before the call. But you now have the longest path starting at [a]. Then you do the same for b and c, and return (to your parent caller), the longest of those three, and unmark your node as visited. Your parent caller does the same thing for all the other nodes adjacent to it, and returns to its parent, and so forth. It works.

However, even with this modification an exhaustive longest path search can be no more efficient than O(2ⁿ), making it unsuitable for anything but small maps. We must therefore find a way to estimate the longest path in quadratic (or linear, ideally) time. The other Concordia team accomplished this as follows:

[A.I Competition - Alexei/Andrew/Jason's Algorithm]

Alexei explains once more:

On startup, we calculated the density of the map (how dense walls are vs. empty space.) Then we implemented two general purpose algorithms:

1. BFS: Breadth First Search to the enemy. Finds the shortest path to the enemy, and returns the first direction.

2. LongestPath (modified BFS): Finds which of the three directions would produce the largest open space. Essentially, 3 BFS searches are done, each one from scratch from each of the possible directions. However, instead of terminating when something is found, you instead count how many locations were traversed in total (the algorithm terminates when all reachable locations are traversed). Algorithm returns the direction that gives the highest such value.

In addition, the LongestPath was modified to not return a direction that would put us in a location to which the enemy could also move next turn, as otherwise this can cause a tie.

The idea is: At first, you want to advance the closest possible to the enemy, to “conquer” the most ground. After this, you want to take the direction that would produce the longest path.

Since we didn’t have time to code something that would detect when advancing BFS to the enemy would put us in a dead end path in the future (i.e. locking us and the enemy into a trap), the density check was necessary. On maps with lots of walls, like the chessboard – this situation could happen, so our AI just goes for LongestPath all the time there.

I’m really not sure how to go about analyzing their enemy chasing intelligence, other than to say that it sounds like a very good idea. When the wall density is low, following the longest path is less critical and it makes sense to try and restrict the amount of free space that the enemy has. This feature may very well have been their team’s winning edge. What is also remarkable about their algorithm, however, is how they went about searching for free space.

To reiterate, their team used a Breadth First Search, which is O(n), to estimate the longest path. Why is this an estimate? Because it fails to return the longest path (and therefore the theoretical best move) in every situation. Consider the following:

In this case, is it advantageous to turn right and survive for 7 turns. However, a modified BFS would choose to turn left, since there are a total of 8 free spaces as opposed to 7 on the right. The cycle would die sub-optimally in 4 turns. The same weakness is true for a modified depth-first search:

In this situation, the longest possible move is to turn left for 8 moves before dying. However, the modified DFS would return 6 for the right path and 5 for the left one, resulting in a disadvantageous right turn. Therefore, we can find specific situations where both BFS and DFS fail as estimators for the longest path.

Despite the shortcomings, I believe that estimating the longest path in this way is truly the most effective solution in a real time system. Since performing the exhaustive longest path search within the time constraints is impossible on a medium or large sized map, we must settle for using reasonable estimators. The modified BFS and DFS both do a very good job of measuring free space, each in a slightly different way.

In my last post I wrote about the simple yet functional algorithms we wrote on the first day of the A.I. Competition. Today I will discuss the two more complex algorithms we developed on the second day and why they were both beautiful failures.

[A.I Competition - 3rd Iteration]

This is where the pseudocode starts to become a little obscure. Essentially, this is a case of algorithm 2 where the scanners can turn exactly once. In other words, at every point along the straight line search we send a second set of scanners out perpendicularly left and right until they reach a wall. We find the maximum value of the sum of a straight and perpendicular scanner and turn in that direction.

In theory this algorithm is more powerful than the one from our second iteration. It looks further ahead, avoiding the situation that prematurely killed our cycle in the first competition. However, in execution, it actually dies a bit faster than the previous A.I. on some maps. The reason for this is that algorithm 3 will often turn faster when filling up an empty space. For instance, in the diagram below, algorithm 2 survives four turns longer in an empty rectangular space.

While the light cycle deathmatch was ostensibly a head to head fight, matches usually degenerated into a race to fill a separate space more slowly than the opponent. Needing to slowly fill empty space was actually much more common than the situation that exposed the flaw in algorithm 2. Algorithm 3 was therefore a bit of a flop.

[A.I Competition - 4th Iteration]

Where algorithm 3′s scanners could turn exactly once, these scanners search the map exhaustively and turn as many times as possible. This is achieved recursively, with each cell calling the check method on the left, right and forward cells. The result is a longest path value for each direction, and the cycle chooses to turn towards the maximum of the three.

However, the moment you allow the scanner to turn more than once you must allow for the possibility of visiting the same cell more than once. Algorithm 4 gets around this by cloning the map at every step. The scanners can leave walls behind themselves on these replicated maps without affecting the real one. Note that the map must be cloned at every recursion and that is is the modified clone that is passed as a parameter to the next step.

Unless some bug in the pseudocode has evaded me, there is no logical error in this algorithm. It will find the longest movement possible on any kind of map, which is exactly what we were looking for. However, there are two big problems with it in execution.

1. If placed in the centre of an empty map with n cells, this algorithm would have a worst case time complexity of O(2ⁿ)* (see Big O Notation.) The resulting calculation would take much longer than one second to process.
2. The entire map is cloned at every recursion, potentially using a tremendous amount of memory. We could slightly improve on this by instead keeping a list of visited nodes, but this list would also need to be cloned. There is a very clever way to get around this problem, but I’ll save it for my next post.

*Finding the time complexity of a recursive algorithm without having real code to test is tricky. I’m basing my analysis on the fact that the longest path problem is NP-complete. Feel free to disagree in your comments, and enjoy the following nerdy song (thanks Skrud.)

Longest Path – Daniel Barrett [download]

Were time and memory not factors, algorithm 4 would be sufficient to find the longest path at every step. In a real time system, however, it’s unfortunately completely useless. Since algorithms 3 and 4 were failures, we were forced to resubmit algorithm 2 for the final competition.

I’ve been discussing this problem with programmers smarter than myself (including the other Concordia team who came in 3rd on the second day) ever since I got back from the CS Games and have learned a great deal in the process. In my next post I’ll be discussing a few of their solutions.

I had a chance to participate in a number of events at the CS games, but the most interesting by far was the A.I. competition. All I had been told about the event beforehand was that in past years they had programmed the A.I. for Pac-man ghosts (enough for me to know that I HAD sign up.) Fortunately this year’s challenge also did not disappoint, as we were asked to program the A.I. of the Light Cycles from Tron.

The match was played on a roughly 30×30 grid where each cell was either empty, a wall or a cycle. Each player was given one second every turn to decide whether to move forward, left or right, with each movement leaving a wall in place behind. The cycle that could survive longest without running into a wall or another cycle was deemed the winner.

The competition took place over two sessions, the first worth 25% and the second 75%. The A.I.s from all thirty schools went head to head in a round robin tournament at the end of each day. With this in mind, my teammates and I decided to apply what we were learning in Software Processes and grow the program iteratively. This was a wise decision; we had a simple yet effective working model ready for the first competition while many groups were still debugging their more complex algorithms. In the end, we tied for 6th on the first day and 10th on the second.

After the competition, however, I found myself still thinking about this problem. It’s a twist on pathfinding, as there’s no set destination, and could nearly be described as a longest path problem. The ideal solution has to be flexible enough to accommodate both narrow corridors and open spaces. Our algorithms didn’t even take into account the position of the enemy, mostly because we weren’t sure what to do with that data.

I’ve written from memory the pseudocode for our four iterations, as well as a little something about their performance, strengths and weaknesses. I present this in the hopes that you too will get this problem stuck in your brain, and will soon return to comment with your wild and crazy ideas about the best Tron A.I.

Note: I’ve tried to keep my pseudocode notation consistent and as close to plain English as possible. They looked ugly when embedded, so click through to read each txt.

[A.I Competition - 1st Iteration]

We began with a very simple algorithm that could look exactly one square ahead. It would therefore never run into a wall unless it was the only possible move. It’s simple and it works reasonably well, but with no foresight it quickly gets caught in traps that it should have avoided. There’s really not much else to say about it, it was a stepping stone to greater things.

[A.I Competition - 2nd Iteration]

Our next plan was to look in a straight line in every direction, and turn in the direction with the most empty space. Another simple yet solid algorithm, but with more foresight than the first. This was what we ended up submitting for the first day’s competition, so we have a glut of experimental data on it. Namely, we discovered one common situation that it handles very poorly.

We lost two of our first round matches getting caught in this scenario. Any human can see that the correct choice in the above situation is to turn left, but algorithm 2 only evaluates one block left and one block forward. Since we hard coded it to move forward in the event of a tie, it traps itself and dies in two turns. Clearly a robust A.I. would need to evaluate length around corners, a concept that we applied to our next iteration.

Since I got a little carried away with the diagram, I’ll finish writing about our two final iterations this weekend. Stay tuned.