views:

1258

answers:

7

I was reading that question and I remember of the Wikipedia list of algorithms. I know that Wikipedia have a list of Open Source games too, but what I want is a links for simple game algorithms, even if written in pseudocode.

As "simple" games, I mean games like Sudoku, Bejeweled, Solitaire, Minesweeper, Labyrinth, Snakes, Gorilla, Chess, Tetris, etc.

Bonus for C# source code :)

A: 

Event thought the games you mention above IS simple, I don't think the algorithm for that games aren't. (Truly no offence :))

Jace Jung
+1  A: 

You can't get much simpler than Conway's Game of Life. There are only four rules:

  1. Any live cell with fewer than two live neighbours dies, as if by needs caused by underpopulation.
  2. Any live cell with more than three live neighbours dies, as if by overcrowding.
  3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
  4. Any dead cell with exactly three live neighbours becomes a live cell.

It can be easily implemented in any language, requires zero players, and produces some interesting patterns.

William Brendel
Really Interesting! Thanks!
Click Ok
A: 

Here is the algorithm for most games:

Once the game is initialized...

  1. Accept user input
  2. Update game state based on user input
  3. Provide visual feedback (update the screen)
  4. Check for score changes and update as necessary
  5. Check for "game over" and jump to step 1 if game not over yet
  6. Um... That's about it.

Hope this helps.

BoltBait
+6  A: 

Most game-playing algorithms are simply search algorithms. In fact, you could say that AI is search.

For Sudoku, dancing links is a good algorithm. Alternatively, it's solved very concisely in Prolog.

For chess, start with Minimax, then try Minimax with alpha-beta pruning.

Minesweeper is NP-complete. There aren't any known reliable and fast algorithms.

Dan Dyer
Generalized minesweeper may be NP-complete, but so is Sudoku [Yato and Seta, 2002] and chess is much more complex (EXPTIME-complete). In practice, the NP-completeness of Sudoku doesn't mean there aren't reliable and fast algorithms for the problems people actually want to solve.
Gareth Rees
"In fact, you could say that AI is search" I don't know what is supposed to mean. I think the statement is wrong.
Niyaz
@Gareth: Good points. Unlike Sudoku and Chess, I haven't tried to write a program to play Minesweeper.
Dan Dyer
+1 for "All of AI _is_ search". I'm pretty sure I heard that quote in my AI class...was it Herbert Simon?
awshepard
+2  A: 

As the others have pretty much hinted at, the idea of an 'algorithm' for a game doesn't really fit, except for something trivial and not particularly game-like such as Life. An algorithm is a way to process a set of data in a known manner to produce a specific output of that data, typically within some sort of time/complexity bound. Games don't fit that simple criteria - they're more like simulations where they repeatedly alter the state of objects based on input until game-specific conditions are reached. As such they almost all follow the input->update->display loop with bespoke game logic in the update stage. Individual parts of the game will undoubtedly be implemented in terms of simple and well-known algorithms but the game program itself is really just the simulation loop and the logic within it.

Kylotan
+1  A: 

What about algorithms, not for playing the games, but for relatively complex tasks within them. For instance, in Bejeweled you have an 8x8 grid filled with jewels in one of 7 colors. At any time, there are about 8 jewels of each color. After a user moves a jewel to create a match, at least three jewels (all the same color) will disappear from the screen, and three new ones will fall onto the screen. How do you make sure that there is always at least one match available on the screen? How do you ensure that the matches are likely to appear around the screen, and not just at the top?

Matt