A bit of randomness

A colleague of mine asked a question that seemed trivial, but then it revealed interesting layers of complexity: how would you build an algorithm for a random number in any integer interval assuming that you already have a function that returns a random binary bit? The distribution of the bit is perfectly random and so it should be that of your function.



My first attempt was to divide the interval in two, then choose the first or second half based on the random bit function. This worked perfectly for intervals of even length, but there were issues with odd sized intervals. Let's take the most basic version there is: we want a random number between 7 and 9. The interval has a size of 3, which is not divisible by 2.



One solution is to split it in half anyway, ignoring one number, then use the random bit function one more time to determine in which half the remaining number should be added. For example the random bit yields 1, so we add the odd number to the second half: 7,8,9 -> 7 and 8,9 . Now the random bit is 0, thus choosing the first half, which is 7. This sounds good enough, let's see how this works:



Possible random bit results:

• 0 (7,8|9)
  • 0 (7|8)
    • 0 (=7)
    • 1 (=8)
  • 1 (=9)
• 1 (7|8,9)
  • 0 (=7)
  • 1 (8|9)
    • 0 (=8)
    • 1 (=9)

The interesting part is coming when deciding (pun not intended) what type of probability we would consider. From the tree above, if we take the terminal leafs and count them, there are exactly 6. Each of the numbers in the interval appear exactly twice. There is a perfectly balanced probability that a number will appear in the leaf nodes. But if we decide that each random bit run divides the total probability by two, then we have a 50% chance for 0 or 1 and thus the probability that 7 would be chosen is 1/4 + 1/8 (3/8), the same for 9, but then 8 would have a 2/8 probability to be chosen, so not so perfect.



What is the correct way to compute it? As I see it, the terminal graph leaf way is the external method, the algorithm can end in just 6 possible states and an external observer would not care about the inner workings of the algorithm; the second is an internal view of the use of the "coin toss" function inside the algorithm. The methods could be reconciled by continuing the algorithm even when the function has terminated, until all the possible paths have the same length, something akin to splitting 7 in two 7 nodes, for example, so that the probability would be computed between all the 2 to the power of the maximum tree height options. If the random bit yielded 0, then 0, we still toss the coin to get 000 and 001; now there are 8 terminal nodes and they are divided in 3,2,3 nodes per numbers in the interval. But if we force this method, then we will never get a result. No power of two can be equally divided by 3.



Then I came with another algorithm. What if we could divide even an odd number in two, by multiplying it with two? So instead of solving for 7,8,9 what if we could solve it for 7,7,8,8,9,9 ? Now things become interesting because even for a small finite interval length like 3, the algorithm does not have a deterministic running length. Let's run it again:



Possible random bit results:

• 0 (7,7,8)
  • 0 (7,7,7)
  • 1 (7,8,8)
    • 0 (7,7,8)... and so on
    • 1 (8,8,8)
• 1 (8,9,9)
  • 0 (8,8,9)
    • 0 (8,8,8)
    • 1 (8,9,9)... and so on
  • 1 (9,9,9)

As you can see, the tree looks similar, but the algorithm never truly completes. There are always exactly two possibilities in each step that the algorithm will continue. Now, the algorithm does end most of the time, with a probability to end increasing exponentially with each step, but its maximum theoretical length is infinity. We are getting into Cantoresque sets of infinite numbers and we want to calculate what is the probability that a random infinite number would be part of one set or another. Ugh!



And even so, for the small example above, it does seem that the probability for each number is 25%, while there is another 25% chance to continue the algorithm, but if you look at the previous stage you have a 25% chance for 7 or 9, but no chance for 8 at all. If we arbitrarily stop in the middle of the algorithm, not only does it invalidate the result, but also makes no sense to compute any probability.



You can look at it another way: this new algorithm is splitting probability in three equal integer parts, then it throws the rest into the future. It is a funny way of using time and space equivalence, as we are trading interval space for time. (See the third and last algorithm in the post)



My conclusion is that the internal method of computing the probability of the result was flawed. As a black box operator of the algorithm I don't really care how it spews its output, only that it does so with an as perfect probability as possible (pun, again, not intended). That means that if I use the algorithm two times there is no way it can output equals amounts of three values. The probability can't be computed like that. If we use it a million times we would expect a rough 333333 times of each value, but still one would be off one side or another. So the two algorithms are just as good.



Also, some people might ask: how can you possible use the second algorithm for large intervals. You are not going to work with arrays of millions of items for million size intervals, are you? In fact, you only need five values for the algorithm: the limits of the interval (a and b), the amount of lower edge values (p), the amount for the higher edge (r), then the amount for any number in between (q). Example: 7778888888899999 a=7, b=9, p=3, q=8, r=5 . You split this in two and (for the coin toss of 0) you get 7778888 a=7, b=8, p=3, q=1 (don't care at this point), r=4. The next step of the algorithm you multiply by two p,q and r and you go on until a=b.



You can consider a simpler version though: there are three values in the interval so we need at least a number equal or bigger than three that is also a power of two. That means four, two coin tosses. If the coin toss is 00, the result is 7; if the coin toss is 01, the result is 8; for 10, the result is 9. What happens when you get 11? Well, you run the algorithm again.

Read More

Sending an array to a stored procedure in Sql Server 2008

I needed to pass an array of IDs to a stored procedure on SQL Server 2008. This version of the server supports user defined table types and a way to access it from .Net, of course. A comprehensive resource for sending arrays to any version of SQL Server can be found here.



Long story short, for 2008 you first define a user table type that has a single int column (we are talking about an array of integers here, obviously), then a stored procedure that takes a parameter of that type. A way to send the array from .Net code is detailed here. As you can see, you create an array of something called SqlMetaData, holding the information of each column as defined in the user defined type, then you use an SqlParameter of SqlDbType Structured and with the TypeName the name of the user defined table in SQL Server. The parameter will have a list of SqlDataRecord instances that have the integer values in their first columns. Yes, there is an even longer story and I consider this short :-P



All nice and easy, but there is a caveat, something that is not immediately obvious from the code. The column metadata is set as a property value for any of the records that are added to the sql parameter value list. What if the list is empty? In this case it appears that there is a bug somewhere. The stored procedure fails, I guess because it does not receive the structure of the user defined table declared in the metadata and cannot map it to the user defined type.



A solution for this is to add a dummy SqlDataRecord with no values and then, in the stored procedure, check for NULL. A very ugly solution. The solution on Erland Sommarskog's blog did not say anything about this specifically, but I did find this: There are a few peculiarities, though. This does not work:

EXEC get_product_names NULL

but results in this error message:

Operand type clash: void type is incompatible with integer_list_tbltype

It is quite logical when you think of it: NULL is a scalar value, and not a table value. But what do you think about this:

EXEC get_product_names

You may expect this to result in an error about missing parameters, but instead this runs and produces an empty result set!. Therefore the solution I used was to check in code if the .Net list of integers was empty and, in that case, do not send a parameter to the stored procedure. And it worked.

Read More

Removing User Access Control from Windows 7, even if enforced by domain policy

UAC is the most annoying feature of Windows 7, one that just has to be specifically designed to annoy the user with useless "Do you want to" alerts. Not even regular alerts, but screen dimming modal panic dialogs. I want it off. There are several options to do that, but the automated way to get rid of UAC is to change a value in the registry. Here is the reg file for it:

Windows Registry Editor Version 5.00



[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System]

"EnableLUA"=dword:00000000

Warning! If you don't know what a registry entry is, then you'd better not do anything stupid! Now, if I could dim the screen while you read that, I would be Microsoft material.



But I digress. In order to execute the reg file above you need to save it into a file with the .reg extension (let's say nouac.reg) and then load it with regedt32 /s nouac.reg. The /s switch removes any confirmation messages and silently loads the file into the registry effectively disabling UAC.



However, my laptop is in a domain with some ridiculous policies enforcing the UAC setting so that when I next restart the computer I get the annoying popups again. Now if I could only run nouac.reg at logoff, I would be all set. And we can do that, also. Just run gpedit.msc, go to User Configuration -> Windows Settings -> Scripts (logon/logoff) and double click logoff. Create a batch file that contains the line to load the registry file and then add it as a logoff script. All set.



Update: Hold the celebration. After I restarted my computer, the hated UAC was back. Either the script was not executed, or it doesn't work like that because the policy is enforced after logoff scripts or before logon. Drat it!

Read More

Computer vs. Human in chess

Ok, I am cheating now. I was feeling bad for not playing chess lately (or playing badly when I had other stuff to do, generating even more guilt) and having nothing to blog about except maybe books and also thinking about all the other directions of the blog that I failed to cover: programming, music, tech news.

So I bring you Brute force or intelligence? The slow rise of computer chess, which is an article about chess, it is from Ars Technica (tech news) and it involves some notions of programming. All I need for this to be complete is music!

Seriously now, I went to a friend's last night and played a bit of chess. We were both a little tired and drunk, so we played chess "for fun" (which translates to incredibly bad), but it really felt fun as opposed to playing a computer at a very low level. Why is that? I believe it is all about prioritization.

When a human plays, he is trying to use the principles of chess, but he doesn't have the time or mental resources to take each one and analyse each piece or position. Humans do use subconscious mechanisms to quickly scan a table, but that only comes with a lot of chess training. So basically, what a beginner human player is left with is finding a strategy that would quickly and (preferably) forcibly win the game. That means that we use something akin with the "Type B" algorithm from the article above. But it's not quite it, because it is a bit of everything, something that is traditionally hard to implement in a computer program (and that has more to do with the psychology of programming engineers than with a specific level of difficulty). Basically we look at the pieces, prioritised by their power and reach as well as their position relative to an area of attack or defence. That is why we don't see the queen or bishop in the corner of the table, because, looking in ever wider circles around the area we are focused on, we suddenly stop and start doing something else. Compare that with a computer which can take the measly 32 pieces on the board and computer in a few fractions of a second all their possible moves and the resulting board position.

Then, when we see a possible good move, we take it forward as many steps as we can. Does a chess beginner do a comprehensive tree of all possible moves in that scenario? Of course not. Not only we do not see all (or most) of the moves, but when we see a possibility for the opponent to play a counter move, we quickly analyse the likelihood that the other guy would see it and sometimes we even gamble that they won't do it, just because we wish they didn't. This is also psychological: the gambler way of thinking has been documented for a while, they are motivated by loss which gives them more of an adrenaline rush than winning or that makes winning ever sweeter; also the guy we play with is probably our friend and we partly root for the guy as well. Program that into a computer! I've had games where I took huge risks on the hope that my friend would a) not see the move, which would make me look good when playing a cool game and b) that he would see the move, making his game look cool, thus making the entire session interesting.

Back to programming, I think that the easiest way of implementing this kind of bad human play in a computer game is to take a normal computer algorithm for playing chess, like mini-max, then program a sort of Alzheimer routine, that would remove bits of its reasoning based on a probability computed from the following factors: proximity of pieces to a region of interest (which would also have to be defined, but let's just assume it would be the average of positions of the pieces involved in the current line of thought), the artistic value of a line of thought (which would be defined either by massive sacrifices for important gains, or by how severely we limit the opponent options - in other words: power), the probability that the opponent would see a move (computed based on current history of play) and also by the artistic value of the entire game, as described in the last paragraph.

In other words, what I am proposing here is that we have a perfect algorithm for playing chess, one that is limited by computing power alone. What we don't have is a good algorithm for bad play, for fun play. Most computer programs I've seen, including ChessMaster, which boasts with its ability to simulate human players of varying abilities, have incredibly stupid ways of limiting performance. For example: a knight wants to attack f7, the black soft spot; it has plans to move a bishop there as well. I move a pawn to prevent the bishop from attacking that spot and the computer takes with the knight, sacrificing a minor piece for a pawn and my king's ability to castle. Or a rook attacks a knight. It then takes the knight, even if defended. In other words, random, pointless moves. Every human move is purposeful, even if the purpose if flawed by bad judgement. Random moves won't do, they have to be moves that follow a plan, no matter how bad that plan is. We need a perfect algorithm for throttling the playing chess level. We need to look at human bad games, make their own chess database, extract rules for bad play and implement this into computers.

Read More

Dancing Naked in the Mind Field by Kary Mullis

Kary Mullis is a chemist who, in 1983, invented Polimerase Chain Reaction, something that would revolutionize DNA analysis in terms of increased speed. He won the 1993 Nobel prize for that. He also is a controversial scientist who claims possible alien encounters and telepathy, denies global warming as an effect of human intervention, is skeptic about HIV causing AIDS and generally believes that most scientists are inventing reasons to get funded rather than doing anything scientific. He also admits smoking pot, taking LSD and generally experimenting with any mind altering chemical that he can make. He likes women and some of them like him. That is what this book is all about, a sort of "I am Kary Mullis, hear me roar!".

I started reading the book because I was falsely led to believe that he describes how training his mind with LSD lead him to the idea of PCR. The book is not about that at all, and if the article above is true about Mullis had an advantage over his colleagues: he had trained his brain to think differently by using hallucinogenic drugs, there is no mention of that in this book.

It is simply an autobiography, but written with gusto and sincerity. Some of the things he says are both logical and hard to accept (because so many others are of opposite views), some of them are simply personal beliefs. As many a talented person, he is intelligent, he had early opportunity to practice his passion (chemistry), a close friend to share it with and support from a local chemistry business owner who kind of adopted him for the summers and gave him the tools he needed to grow. The way he writes his book reminds me of the style of another scientist friend of mine: devoid of bullshit and intolerant of stupidity.

Bottom line, it is a nice book, simply written, short, I've read it in a few hours. It is a window in the life of an interesting person, and as such, I liked it. I can't say I've learned much from it, though, and that is somewhat of a disappointment coming from a book written by a man of science.

Read More

The Art of Learning: A Journey in the Pursuit of Excellence, by Josh Waitzkin

The Art of Learning is a wonderful book, both concise and useful, with tremendous sources for inspiration at every level. It also has more meaning to me, as it started with an investigation in the life of Josh Waitzkin, prompted by my renewed attention to chess.
To start from the beginning, I've first heard of Josh Waitzkin when I've started going through the "academy" section of ChessMaster XI. The first chapter in this section was Josh Waitzkin's academy, which taught with examples of both life and game. I was intrigued, so I looked the guy up. This way I found references to Searching for Bobby Fischer, a Hollywood movie about the early life of chess prodigy Josh Waitzkin, based on a book by his father. I watched the film, with both positive and negative feelings, but at the most I was even more intrigued. I then found out about the two books that Josh wrote: Attacking Chess and The Art of Learning and started reading the latter, since I had to read it on my old Palm in the subway and I am not yet at the level in which I can mentally visualize chess notation.
The Art of Learning is everything I wanted in a book about learning: the personal introspective view, the theory of learning and its mechanics, clear examples and methods of achieving the same results. Frankly told, I doubt many people can learn at the same speed as Josh Waitzkin can - clearly the guy is a genius - but there are insights in this book that blew me away.
The book is structured in three parts:

• The Foundation - describing the early experience of learning, the downfalls, the insights, the situations in which Josh found himself as a child discovering the game of chess and then becoming National chess champion.
• My Second Art - the part where he finds less peace in chess and decides to abandon it in favor of the martial art of Tai Chi Chuan, which centers him and presents new opportunities for learning. Here similar principles are found to the ones related to chess.
• Bringing it All Together - where Waitzkin describes methods for identifying your own method of learning and reaching the state of mind most conducive to high performance

It all ends with a climactic Taiwan International martial arts championships that Josh wins, overcoming adversity and malevolent judges, a story that rivals any of Van Damme's movies, but also shows where the inspiration for those came from.

There are some ideas that I could understand immediately, seem obvious, but I've never thought of before:
One of them is that the unconscious mind acts like a high speed parallel processor, while the conscious mind is a serial decisional engine. An expert in a field does not think faster than a beginner; he only placed many of the underlying principles in the subconscious, running them at high speed, and leaving the conscious mind decide, like a manager, from the granular information that is precomputed and available. That makes sense at the smallest biological level. Think of the frog eye that sends a yes/no signal through the optical nerve when a fly enters the field of view - the frog does not have to decide if what it sees is a fly or not. But it also explains quite clearly the effect of training, something that I, to my shame, had not understood until now. Training is not simply learning, it is also moving the information downwards, "internalizing" it, as Waitzkin calls it. GrandMasters do not think about the possibilities on the chess board from the bottom up, they already see structure and work directly with the aggregated, higher level information. Martial arts experts don't count the steps in a complicated move, they just make them. Normal people do not put a foot in front of the other, they walk, they don't string words up, they speak.
Another idea is that the process of learning, done in small increments, allows the direct internalization of concepts before we use them in combinations. First move a few pieces until you know how they work, don't start with complicated chess games. Reduce the scope of your training and the internalization will come a lot faster. Then, in a complex game, you just use the things you have learned previously. When training to fight, train each small move before you start combining them.
This is an important idea in The Art of Learning: the difference between what Waitzkin calls entity-learning and process-learning. Entity learners will try to find the quick way out, find the small trick that get the problem done; they will care only about the end result, collapsing under the fear of losing. The process learner would enjoy the challenge, see each problem as something that can be solved if attacked metodically and chipped away at bit by bit. They will value the process of learning over the end result. An entity learner will try to learn as much as possible, in the end reaching mediocre levels of understanding in all fields, while a process learner will take each process as far as possible before engaging another. Process learners would say "I didn't learn enough" when losing, while entity learners would say "I wasn't good enough".
I am sorry to say that I apparently fall towards the entity-learner category. It is obvious that must change and I hope it can. What I gathered from this concept is that entity learners identify themselves with the solution of a problem. Losing makes them losers, winning makes them winners. Process learners identify themselves with the process of learning, making them bad or good learners. A very good point Josh makes is that the type of learning is usually caused by the way parents reacted to the early success of their children and also that it can be changed, it is not set in stone like just another cemmented childhood psychological baggage.
An interesting thing about the book is that it also provides some mechanisms to improve, to reach that "zone" of serenity and presence in the moment. Borrowing from Taoist concepts, Josh Waitzkin advocates leaving in the moment, being present, aware, and he provides methods to train to reach that present state at will. I find that very interesting.

In the end I would call this one of the most useful books I've read and I certainly intend to improve on myself using some of the guiding principles in it. Josh is an extremely competitive and intelligent person and, given the opportunity of having good and talented parents, made the best of it. I am not saying that all can reach the same level of success and internal balance, but it is surely refreshing to see one of these great people lowering themselves to the level of the normal guy and giving him a few pointers. That is exactly what The Art of Learning is.

Read More

Changing jobs

I guess it is finally official: I am now a corporate employee. While the previous company I worked with was nice in terms of the people there and the technology used, I got bored. I blame myself for getting depressed when assigned disconnected UI tasks and when singled out socially. It shouldn't have mattered. Surely I could have worked on overcoming adversity and improving my development methods, no matter how boring the task at hand.

However, bored I did get and when a big corporate company approached me with a job offer, I was intrigued. This is a long story, though, because I passed their phone screening, their 6 hour long technical interview and got the approval of the top brass yet in another interview, all some time at the end of March. This coincided with my birthday so I thought it was like a present to myself: an opportunity to learn new things, work in an environment I was scared of, but which was different and exciting, not the mention better payroll, although that didn't matter that much.

So, why am I writing this blog entry now, at the end of July? Because I only got hired two days ago. Budgetary strategy, corporate decisional speed and pure bad luck (I hope) pushed the employment date for four stressful and uncertain months. And I am not even fully employed, I am a contractor with an intermediary for the time being.

I can't tell you yet how things truly are in the new company. People are certainly more professional and yet relaxed, not at all like the stick-in-the-ass image I had (well, most of them). Frankly, these people are more geek and less social monkey than some of the juniors at my last job, which is great. On the other hand, until I start actual work (which will take another two weeks of gruelling meetings and annoying bureaucracy) I will not know how (and if) this company gets anything done.

Certainly, a quad-core laptop with 8Gb of RAM and SSD harddrive will decrease developing time (I used to watch movies and read books while compiling projects at the old job). They also seem very communicative (to the point of never stopping from talking about a project), which is something I am less used to and I welcome gladly. They encourage and help with personal development and good development techniques, like TDD and a commitment to Scrum. And if you don't know something, people are not sneering, but offering to help. So far, I can't complain (and you know me, I am so good at it).

I will be working on an ASP.Net CRM project, something evolving from an older VB ASP.Net 1.0 thing to a C# ASP.Net MVC monster. Hopefully, this will reignite my passion for development, rather than reassert my disgust with web work. So you will see Javascript and ASP.Net posts again soon and not so much WPF. Too bad, I really liked that particular technology.

So, wish me luck!

Read More