The work we are presenting extends the scenario based testing methodology to make it applicable to the testing of intelligent software systems. Due to the unpredictability of the environments in which intelligent systems are deployed, we have extended the scenario tree concept to include equivalent classes of events and system states, and the probability with which the classes of events are expected to occur. Using the notion of utility, we define the concept of importance of testing an event in an intelligent system, possibly equipped with a learning module. Finally, we quantify the degree of confidence achieved by partial testing of a system. Our approach allows the designer to determine which test cases should be executed to meet the given confidence requirements, and to examine the tradeoffs between further testing and increased confidence in the system.