A dumb brute force would be very slow even for simple games.
Take pong, the ball would have an x and y coordinate (let's assume an unsigned 8-bit value) and two paddle heights (also assumed to be unsigned 8-bit values). This would give you 255*255 possible states for the ball, 255 states for each paddle and would give you a total search space of 255^4 or an unsigned 32-bit number which if you were to hold every possible state that may occur in pong would be computable on modern hardware. This is before factoring in score values which would increase that value by ~81.
As you can see this approach will not scale well and a smarter approach would be needed. For long it's simple - just have the computer play the game, taking physics into account, brute-forcing all possible memory states is cool but even a mere 8 bytes already contains a gigantic search space of 2^64 which is the largest hardware-accelerated integer value that modern hardware performs - save more exotic architectures and vector extensions with a bit of software-based processing added.
A different approach may be to only consider the player-accessible inputs rather than memory states, but this falls down in games that can go on forever either because no inputs are pressed or some circular path, this will raise the question "How do you decide when to quit a search?" One answer is a function that evaluates player-trackable game properties such as a score and should the change of score be too low for too long, end this search and begin the next. This would still leave a gigantic search space and may cut out interesting bugs that may occur but require considerable time and little 'progress' to set up. Despite this reduction of search space by brute forcing inputs over time rather than all states still isn't really possible - you aren't going to be brute forcing super Mario bros anytime soon, you would be lucky to complete it.
So taking the above into consideration, how do you actually perform such a search? Currently, the best answer that I have is reinforcement learning which is still slow but at least it will complete within a few hours to weeks rather than several thousand lifetimes and works by randomly performing actions and over time learning a connection between actions and 'rewards'. The main algorithms used are NEAT (Think natural selection) and Q/deep-Q learning (Kind of like what you were after with the memory state of the entire game, but doesn't consider all possible states)