Beginner Pong AI contest proposal

Miscellaneous Topics
#1

I had recently begun learning C++, and I wrote a Pong clone again, and as I got to the computer controlled paddle, I realized that, if you really try, you can pretty much make it unbeatable. So then I thought, wouldn’t it be cool to have a Pong ‘AI’ competition? Somebody writes a standard engine (i’d be happy to), and then everybody who wants to compete writes a class extending a standard Paddle class with their AI code.

Obviously there would be a maximum speed that the paddle is allowed to move every frame and so on, but if you write the basic engine well enough, checking it won’t even be necessary. So what do you think? Especially for beginners. I’ve never heard of this kind of competition before, maybe we can try it with a different kind of game even?

#2

I think that’s pretty much a solved problem, isn’t it? With a fixed paddle speed and a predictable ball speed, it’s just down to simple mathematics:

If the ball is heading your way: if you can reach it in time, go to point of intersection, else go to centre of field.
If the ball is heading away from you: go to centre of field, or alternatively predict where the ball might be heading next and offset accordingly.

Pong is only interesting for imperfect human opponents - computers just don’t make mistakes and never need to gamble on a particular outcome.

Now, writing an AI that plays Connect 4, for instance - that would be a worthy challenge! ;D

#3

Why not just try your skill at JRobots ?

#4

Now, writing an AI that plays Connect 4, for instance - that
would be a worthy challenge!

Actually it’s not. That problem is “solved”.

Nevertheless I was really proud of my imperfect AI back in 1998 :wink:

It was able to prevent you from getting your chance, weighted doing a connected 4 line higher than everything else and it could look one step ahead. And all that without 2d arrays, because I hadn’t known how to use em… and I used pixel lookups instead haha ;D

(TurboC’s integrated help system could only show me some method names etc, but not that basic stuff. I also didn’t noticed that I could use a 1D array for 2D stuff.)

#5

why don’t all just play pinball for the first time in your life?? ;D ;D ;D

#6

[quote]Actually it’s not. That problem is “solved”.
[/quote]
Really? I had no idea. While the rules are extremely simple and the problem domain very restricted, I thought there would have been enough scope for some off-the-wall tactics.

Alright…

How about chess? Anyone solved that yet? ;D

#7

4x4 has 30 squares, with one of two states. That means you can fit every possible end-of game state into a single int. That really isn’t much. Especially seeing as every end-of-game state fully stores all states leading up to it (although it loses the ordering, which requires a tiny bit of extra storage). The route to any end state is largely deterministic (i.e. very few alternatives to analyse)

By comparison, chess has a huge number of possible end-states and a mind-boggling number of ways of getting to each, with very very little determinism along the way (i.e. masses of information to analyse at every single step).

Hence, whilst Chess is unpredictable on modern computers, Connect-4 can be fully predicted in-memory by a VB program.

Of course, there is room for manoeuvre in making a c-4 that tries to “win” as opposed to “not lose”.

#8

Not true. each square has 3 states, unoccupied, filled with player 1 's piece, or filled with player 2’s piece.

Unless your int is stored on a trinary computer, 30 bits aren’t enough :). Hey, on a trinary computer should we say the int has 32 tits instead of 32 bits? :o

#9

I typed a longer post originaly, then cut it down to that because it looked boring.

At the end of the game, you can fill in all unfilled spaces with any piece and not ADD any additional possible end states. In practice, the number of actual end states is going to be considerably less because a single blank removes all the bits above it from consideration at all.

So, as an upper bound, 2^30 is OK, no?

#10

I assumed you meant that each of the 30 bits within the int would be 0 or 1 depending on which player’s piece was in that position, but of course that can’t work as a model for representing the game state. That was my point.

If you pretended the blanks were all filled in with something after the game had been won, then you would destroy the game state (there may be more winning runs of 4 at that point).

I would use 2 ints, one to indicate occupied or not, the other to indicate the color that occupies it.

The upper bound on the number of possible game states I will leave as an exercise for the terminally bored.

#11

Isn’t it actually a 6x7 board? And you forgot to analyze the search space and appropriate search algorithms. ::slight_smile: