-2

I'm creating a small game, where the computer generate pseudo random number in give range, and the user have to guess it. I also made the option to play computer vs computer. I mean the computer generate random number and the computer should guess it.

The easiest way I found was to create for loop and increase a variable by 1 until it guesses it. But I decided to try to create my own algorithm about this.
Basically the variable that holds the guess number is equal to range / 2, and then the program enters into the while loop where if the random number > the number which is generated by logic(the one which is = to range /2) then 2 it to two and add 1 to it. If the number is < the program * by 2 and add one to it until it guess the number.

Here is code in C++:

void aiVsAI(int range){ // range argument is used to be given to the randome generator func
    int random_number = generate_random_number(range); // assigning the random number to variable
    int guess = range / 2; // the computer guess number
    int tries = 0; // how many tries the computer needed to guess the number
    while(guess != random_number){ // while the guess isn't equel to the random number
        if(guess > random_number){ // if the guess is > than the random number
            guess = guess / 2 + 1; // dev it to 2 and add one to it
        }
        else if(guess < random_number){ // if the number is < than the number then
            guess = guess * 2 + 1; // * it with 2 and add one
        }
        tries++; // increase the number of tires
    }
    std::cout << tries;
}

the generate_random_number is function that will generate pseudo-random number.

My question is which algorithm is faster this one or just using for loop and increasing variable with one until it guess the number?


Here is the full code if anyone need it for something:

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>


//function that will generate random number
int generate_random_number(int range){  // the range argument is used to represent the maximum value of the number
    if(range < 10){ // the range couln't be < 10 but can be ==
        std::cout << "range can't be less than 10";
        exit(1);
    }
    std::srand(time(NULL)); // making sure that the random number will be different every time
    return rand() % range; // returning the random generated number in the specific range
}

//Game computer vs computer
void aiVsAI(int range){ // range argument is used to be given to the randome generator func
    int random_number = generate_random_number(range); // assigning the random number to variable
    int guess = range / 2; // the computer guess number
    int tries = 0; // how many tries the computer needed to guess the number
    while(guess != random_number){ // while the guess isn't equel to the random number
        if(guess > random_number){ // if the guess is > than the random number
            guess = guess / 2 + 1; // dev it to 2 and add one to it
        }
        else if(guess < random_number){ // if the number is < than the number then
            guess = guess * 2 + 1; // * it with 2 and add one
        }
        tries++; // increase the number of tires
    }
    std::cout << tries;
}


// Game human vs human
void humanVsAI(int range){ // range argument is given to the generate random function
    int random_number = generate_random_number(range); // assigning the random number to variable
    int input = 0; // this var represents the user input
    int tries = 0; // the number of tries user had make to guess the number
    while(input != random_number){
        std::cout << "Enter number: "; // alerting the user to enter a number
        std::cin >> input; // getting the number
        if(input < random_number) // checking if the input > than the random num
            std::cout << "You didn't guess it,you are too low..., try again!\n"; // alerting the user
        else{ // else it will be > than the number
            std::cout << "You didn't guess it,you are too high..., try again!\n"; // alerting the user
        }
        tries++; // increasing tries by one for each try//
    }
    std::cout << "\n\nYou guess it! You need " << tries << " to do this.\n\n";
}


//game Human vs Human
void humanVsHuman(int range){
    int number_to_guess; // the number which must be guessed
    int user_guess; // user input
    int guess;
    std::cout << "Enter number int range 1- "<< range<<": \n"; // alerting the user to enter number
    std::cin >> number_to_guess; // entering number
    for(int i = 0; i < 100;i++){ //Clearing the screen
        std::cout << "\n";
    }
    while(user_guess != number_to_guess){
        guess++;
        std::cout << "Please enter numer:\n"; // alerting the user
        std::cin >> user_guess; // Getting the user input
        if(user_guess < number_to_guess)
            std::cout << "You didn't guess it,you are too low..., try again!\n";
        else if(user_guess > number_to_guess)
            std::cout << "You didn't guess it,you are too high..., try again!\n";
    }
    std::cout << "You guess the number\n";
}
int main(){
    std::string game_type;
    char play_game;
    int range = 0;
    while(1){
        std::cout << "Please enter range(type 100 to leave it as default)\n";
        std::cin >> range;
        std::cout <<"What you want to play AI vs human, human vs human or AI vs AI ?\n";
        std::cin.ignore(); // for get line
        std::getline(std::cin, game_type); // getting the user input
        std::cin.clear(); // clearing
        if(game_type == "AI vs AI" || game_type == "ai vs ai"){ // if the user chose AI vs AI
            std::cout<<"You choosed AI vs AI\n";
            aiVsAI(range); // calling the AI function
        }
        else if(game_type == "human vs ai"
                || game_type  == "ai vs human"
                || game_type == "human vs AI"
                || game_type == "Human vs AI"
                || game_type == "Human vs ai"
                ){ // if the user chossed AI vs human
            std::cout << "You choosed human vs AI\n";
            humanVsAI(range); // calling the human vs human function
        }
        else if(game_type == "human vs human"
                ||game_type == "Human vs Human"
                ||game_type == "Human vs human"
                ||game_type == "human vs Human"){ // if the user choosed human vs human
            std::cout <<"You choose human vs human\n";
            humanVsHuman(range); // calling the human vs human function
        }
        else{ // In case of any error
            std::cerr << "An error occured!";
        }
        std::cout << "Do you want to play another game?\n"; // do you want another game????
        std::cin >> play_game;
        if(play_game == 'y' || play_game == 'Y')
           std::cout <<" starting another game\n";
        else
            break;  // enough playing for now.
    }
    return 0;

}

closed as off-topic by GlenH7, DougM, Wayne Molina, JBRWilkinson, Ampt Jul 29 '14 at 20:18

  • This question does not appear to be about software engineering within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • You can't beat divide et impera if you know the range :) – Silviu Burcea Jul 24 '14 at 11:58
  • 1
    Put it to codereview, it is certainly off-topic here. But as a hint: just use binary search since you've got access to whether your guess is over or under the number. Also, do you really need to bounce around and multiply/divide your guess by 2 every time? You will check stupid numbers out of range half the time. – Ordous Jul 24 '14 at 12:00
  • I didn't understand you divide et impera? – user3868594 Jul 24 '14 at 12:01
  • 1
    Have a look at big-O notation. – ctrl-alt-delor Jul 28 '14 at 13:55
  • 2
    This question appears to be off-topic because it is about testing the speed of an algorithm, and the programmer should be able to do that themselves. – DougM Jul 28 '14 at 14:11
1

As long as the guess is consistently high, your algorithm performs well by roughly halving the guess.
Once you have made a low guess, the algorithm severely deteriorates in performance. By doubling after a low guess, you are guaranteed that the next guess will be too high. Now, the +1 factors come into play (especially the one after halving), which let you walk towards the right number at half the speed of a normal loop.

For performance measurements, I would expect the slow walk up to be the dominant factor, making your algorithm slower on average than the simple loop. Given your measurements, either my expectations are wrong, or the distribution of your pseudo-random values happens to be slightly in favor of your algorithm.


If you want a challenge, you could try to implement a binary search. With a range of 100, that algorithm is able to find any number within 10 steps (given that it knows the range).

  • 1
    Binary search can find a number in range 0—127 in 7 steps. – ctrl-alt-delor Jul 28 '14 at 13:51
1

The more sophisticated algorithm is definitely more efficient: it requires logarithmic time vs. linear time to find the value. Here is a description of binary search; that's basically what you have reinvented.

  • 1
    Yeah. No. That is not binary search. – Ordous Jul 24 '14 at 12:01
  • 1
    Ordered search space, picking a middle element from that input space and comparing it against the value, partitioning the search space in two and recursing into the now-reduced search space. Yes, this is very much binary search. The fact that the search space is not an array is irrelevant. – MSalters Jul 24 '14 at 13:35
  • 1
    @MSalters: If you look carefully at the algorithm, you will find that it only partitions the search space during an initial, downward search. It looks vaguely like a binary search, but it isn't. – Bart van Ingen Schenau Jul 25 '14 at 9:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.