Wednesday, February 9, 2011

Intelligent Code

Greetings

Every problem in Computer Science can be solved by accounting for every possible permutation that the program might encounter. Naturally this is not an efficient practice, especially when  the number of possibilities can grow exponentially, reaching billions in no time. To effectively solve such problems, we need to implement  a kind of logic, based on our own thinking while problem solving. This inherent 'common sense' of humans can help create powerful algorithms to solve computer problems, without the aid of brute force. An example of such a problem is a computer game (Source .cpp, and .exe), where a computer tries to guess a users' choice within a given range. If the users' choice is >= the computers' guess, the user inputs 0. If the user's choice is < than the computer;s guess, the user inputs 1. Naturally, the computer can iterate through all numbers in the range from lowest to highest and check whether the computers' guess matches the users' choice and arrive upon the answer when the user inputs one(the users' choice will be the current computers' guess - 1). However what if the range extended from 1 to 2^10? Does it make sense to loop through all those numbers, check for user input and output the answer? This method is not time or user friendly. However, if we implement an algorithm that imitates the way we think when solving such a problem, we can arrive upon an extremely efficient solution for this problem. Consider the range 0 to 16. The user's choice is 11. Now lets add 1 to 0 and 1 to 16, to make the range 1-17. This is done because we will than have 2 nice halves of the range: 1-8 and 9-17. This idea of dividing the range into half will be central to out algorithm. You will get why I do this later. Now the computer has 1\16 or 6.25 % chance of guessing the right user's choice. If it iterated through all the values of the range and checked it against the user input, the probability of the program guessing the right choice will be increased to 6.67% -> 7.14 %...etc.(Not really, but for the time being, let us consider the case to be true). What should the program do to arrive upon the answer faster and in fewer tries? It should try to increase the probability of getting the right answer in each successful turn by a greater rate. For example in the range 1-17, the computer programs' first guess has to be (1+17)/2 = 9 or the average of the range extremes. Why? Because if the user inputs 1, the users' guess is less than 9, so it is in the range 1-8. Alternatively, if the user inputs 0, the users' guess will be greater than or equal to 9, and thus in the range 9-16. What have we achieved here? We have increased them probability of the computer guessing the right answer in the next turn to a whooping (1/8)% = 12.5%, which is the double the probability of guessing the right answer of the programs' first turn. Compare this with the 6.67% probability while iterating through all values!Now since the user's choice is 11, he will input 0, and now the computer program will carry out the same operation, although this time on a different range, that is 9-16. After this turn, the probability of guessing the answer right will increase to 25%, then to 50% and finally to 100% When it reaches 1000%, the program will have the answer! his method only works on ranges whose higher extreme can be expressed as:
Log2(Higher Extreme) = some Natural Number.
Therefore 16 works(log2(16) = 4), so does 8. 32 and 4096. The number of guesses the program will make is log2(higher Extreme). In the case of the higher Extreme being 16, the program will make 4 guesses, in the case of 32, it will make 5 guesses and so on.
I have provided the links to the source code and .exe file of this 'game'. Feel free to edit it, distribute it and use it, although with proper credit!

Link to .cpp source file.
Link to .exe playable game file.


This is not the end

Aravind Rao