How do you create a computer memory?

[Phlegmak]

Let's say you're trying to program an AI to play checkers. You want to be able to store memories of how the last game went, and you want the AI to think, "Hey, I remember seeing that strategy. This is what I can do that will most effectively beat it."

How in the world do you encode a memory? And don't say genetic algorithms, because that's definitely not the way.

 

[Asher]

In sequential AI (eg, move history), a simple doubly linked list should suffice.

In games, simplistic AI and data structures reign king...eg, pairings via hashmap or some other O(1) access structure (X event occured, Y reaction should occur).

What you're looking for is pattern recognition algorithms, more than data structures. Each algorithm will have its own optimal data structure.

The most common solution in games is a stochastic analysis (that relies on probability theory). In this case you'd use a simple combinatorial tree. Each move the opponent makes would traverse down a tree (and this tree can be updated with each successive game).

You can then pair a branch with a successful mitigation strategy if you wanted.

Sorry if this is incoherent, I'm just thinking "out loud".

 

[ParadigmShifter]

In draughts (checkers) you can only occupy 32 squares on the board so you can just store a 64 bit word (32 bits for white and black) with the occupied/unoccupied flag for each square on the board (until you promote a piece to a king, then you need more data). You can use that to encode the board state. Chess programs often do this, sometimes with one "bit board" per piece (sometimes even extra bit boards such as squares that a piece can move to, etc.). Then you can just do logical operations to find out stuff like "what pieces are threatened by pawns", etc.

 

[Phlegmak]

In draughts (checkers) you can only occupy 32 squares on the board so you can just store a 64 bit word (32 bits for white and black) with the occupied/unoccupied flag for each square on the board (until you promote a piece to a king, then you need more data). You can use that to encode the board state. Chess programs often do this, sometimes with one "bit board" per piece (sometimes even extra bit boards such as squares that a piece can move to, etc.). Then you can just do logical operations to find out stuff like "what pieces are threatened by pawns", etc.

My problem is not with a simple game like Checkers or even Chess, it's with a game like Civ and the complexity of that particular game board.

 

[felagund]

I'm not sure, but I think you would have to create an array/linked-list containing data of the game state for every move in the game. This is not the most efficient way to do it, but it might be the only way. Or either during or after the game, you could have the AI analyse the game-state data to store meta-data about possible strategies to use when encountering different game states. And save that meta-data in a file for future use.