Connect Four AI

Artificial Intelligence Programming

Started by Jaap85 March 18, 2012 04:42 PM

13 comments, last by willh 11 years, 10 months ago

21,604

June 17, 2012 11:37 AM

You don't need to use nearly as much memory as you are using. Actually, you basically only need one game state, on which you'll make and undo moves. It might be useful for you at this point to use a global game state, to guarantee you are not copying game states around. The negamax function (a version of minimax with the convention that positive score means the player to move is ahead; and forget about alpha-beta for now) looks something like this:

int negamax(int depth) {

  if (game_over())

	return game_score_from_the_point_of_view_of_player_to_move();

  if (depth <= 0)

	return static_evaluation_function_from_the_point_of_view_of_player_to_move();



  int move_list[7];

  int n_moves = generate_moves();

  int best_score = -INFINITY;

  for (int i=0; i<n_moves; ++i) {

	make_move(move_list);

	int score = - negamax(depth-1);

	undo_move(move_list);

	 if (score > best_score)

	  best_score = score;

  }



  return best_score;

}

Notice that this algorithm only uses O(depth) memory, instead of your current O(7^depth) memory usage.

Jaap85

267

Author

June 17, 2012 03:13 PM

Thanks a lot for the useful insight. I hadnt considered using only one gamestate with undo moves. I will definitely give it a try and see if this is a faster way to perform the search.

Update: Well, it turned out to be quite easy to implement. After editing my code, my program issued me the following response:

I visited 137257 nodes, of which 117649 are leaves, in 304 miliseconds which is 452 nodes/ms

Almost 400 times as fast

Thanks a lot, it gave me a great insight in how memory is being used.

My personal blog on game development!

Black Wolf Game Development

Jaap85

267

Author

June 23, 2012 03:15 PM

The past few days i worked a bit more on my Connect Four game (i have now implemented that AI players can play each other a certain amount of times in a row, so i can test easier). The next thing i want to dive into, is iterative deepening.

Right now, i just set my maximum searchdepth to 6, but this is just an arbitrary number (it takes about 300 milliseconds per move on my machine). When approaching the end of the game, when there are less choices, the thinking time decreases. In this case i would like the AI to try and think further ahead.

Of course it would be easy to hard code this (for example, when a certain percentage of the field is filled, increase searchdepth), but i dont think its the correct way. I dont know how to implement it in the search itself though. Since negamax is depth first, how can you determine how deep the AI has to search? If it would be breadth-first search, it would be easier (check first level, if time left, check second level).

I would be happy to hear any ideas on this problem!

Edit: i read online that the best way to implement it, is to do a search with depth 1 first, then depth 2 and so on, but this seems rather inefficient to me, because in the early stages of the game you have to search a lot more to get to the same result:

Search with iterative deepening
1. start at the top, search with depth 1
2. start at the top, search with depth 2
...
6. start at the top, search with depth 6
return

Search without iterative deepening
1. start at the top, search with depth 6
return

Or did is misinterpret something?

PS. i already implemented a simple version of AB pruning, this wasnt very hard in my opinion (unless i did it completely wrong

My personal blog on game development!

Black Wolf Game Development

alvaro

21,604

June 24, 2012 11:57 AM

It is a common misconception that iterative deepening will be slower than doing a single search of the appropriate depth.

How long an alpha-beta search takes is heavily dependent on how well the moves are sorted. Iterative deepening allows you to improve move order in two ways:

Keep the list of moves at the root sorted from most promising to least promising: You do this by simply moving a move to the top of the list when it's found to be best during the search at the root.
Store the best move found at each position in a hash table, so that you can try it first whenever you encounter this position in the future.

Those two improvements make iterative deepening actually faster than searching depth 6 directly. There are a few other things that can be done to reuse information from previous searches: You can read about them here.

willh

160

June 24, 2012 03:11 PM

Alvaro gives good advice.

Keep in mind that your code spend 99% of its time looking at useless positions. Anything you can do to get plausible positions explored early will eliminate a whole lot of work for the algorithm (thanks to alpha beta).

Iterative deepening and killer move heuristics can really speed things up substantially.

Connect Four AI

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Connect Four AI

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines