Fun With Python: Connect 4!!! This is an attempt at making a console connect4 game in Python - as a hobby. If you're interested, I need help writing the AI. Edit: Here is an update on the code. I have a general layout of what I want the AI to behave like, but I'm still in the planning phase.

Author: Martin SAVESKI
Date: May 2009
License: MIT

This is a program I have developed during my undergraduate studies as a project for an introductory course in Artificial Intelligence. I particularly like this program as it is the first thing I have developed that seems to show intelligence, i.e., can kind of make its own decision, beyond what it was explicitly programmed by a human.

Connect four is a strategy board game where the player who aligns four disks wins. Program has two main components: (1) the search algorithm, and (2) the evaluation function. The evaluation function quantifies how desired or undesired a state of the board is for the agent. The search algorithm helps the agent decided on the next move by efficiently exploring what might be the consequences of each move. This program implements the Minmax algorithm with two extensions: Alpha Beta pruning — which substantially cuts the search space; and iterative deepening — which combines the advantages of depth-first and breadth-first search.

Belajar bahasa arab mudah. Advertisements or commercial links Disruptive posting: Drake take care zip sharebeast Home.

Evaluation function

The Evaluation function is supposed to evaluate how good a given state is for the agent, i.e., how close it is to winning the game. Since, this is the agent’s view of the “real world”, I considered the design of the evaluation function as most important. Having complex evaluation function with many features results with more clever behavior of the agent, but it increases the number of calculations and time needed to evaluate each board state. As the time for each move is limited, searching with complex evaluation function cannot be performed in great depth. The trade-off between complex evaluation function and search at larger depth is obvious. After experimenting with several different models I found an approach that suited me the best in evaluation of a state. I decided to consider all possible combinations of four fields (horizontal, vertical and diagonal) and if none of the players or both of the players has selected fields in the same 4-field combination, the combination will be instantly discarded. Otherwise, it will be added to a state-score depending on the number of fields taken. Depending on the number, and if it’s agent or player fields, a certain weight will be applied. Initially, I started out with weights that were the square of the number of occupied fields in each block of four (i.e., 3-in-a-row would give a score of 9, 2 would be 4, 1=1) and if state resulted in 4 in a row it would get a big bonus/punishment of 10000/-10000. However, it quickly became evident that I would at least need to raise the punishment if the opponent had 4 in a row. In order to compare between the suitability of the weights I set up a game to allow two agents with different weights to play against each other. After trying with different weights 15-20 times, I decided that it was fairly optimized. I could imagine automating this process, perhaps using Simulated Annealing.

Search Algorithm

My initial implementation used solely the Minimax search algorithm and could search in depth of six for around one minute. Obviously this was not fast enough, my first improvement was implementing Alpha Beta Pruning to minimize the search space. In order to improve the pruning I changed the order in which moves are considered, stating in the middle and alternating one row left and right. This resulted in tremendous speed up of the search. However, searching only to fixed depth it was hard to control the time for search to be in the given time limit. As a solution, I implemented Iterative Deepening Search, which called the Alpha Beta Pruning search with increased the depth in each iteration and returned the value of the last iteration.

Optimizations

Obviously, to make the agent look more intelligent it had to be well optimized. Since the evaluation function is called extremely often during the search, it is the best place to start. As there are 2187 (3^7) possible combinations of lines of seven fields (729 of six fields, and 243 lines of five fields), I precomputed the evaluation values of every possible horizontal, vertical, diagonal line on the board. The evaluated values I stored in hash tables with the combinations as keys. So that the evaluation function only looks up the value for each line and adds it to the state value. The next optimization was inspired by the Iterative Deepening Search. During the search in every iteration, we know exactly what was the best move in the previous iteration, so if we consider the best row from the previous iteration first, it is very possible that it will have a high alpha/beta value and more of the search tree will be pruned. This results in decreased search space and allows search to be performed at grater depth.

I'm wondering what's the best way to check for a winner on a connect four field.I'm interested in what you guys think and whether there is some 'well-known' algorithm for this sort of problems?Solution:I implemented Ardavan's hash-table solution in Python.I let the algorithm run over every field once. The best checking time with my implementation was 0.047 ms, the worst 0.154 ms and the average 0.114 ms on my Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz. This is fast enough for my needs, and the algorithm seems neat to me.

Each cell can only attribute to a maximum number of 12 winning combinations. (4 horizontal, 4 vertical and 4 diagonal). Each combination would have 4 cells including the one under consideration. And these numbers are going to be much lower for the cells closer to the sides.

So it would make sense to pre-compile these combinations and store a hash of hash of related cells which can make a single play a winner. This way after each cell is player you simply pull out the related combinations/cells to check if it's a winner. If I calculated that right, there are a total amount of 69 winning combinations.

For each row there are 4 possible combinations, there are 6 rows = 24. For each column there are 3 possible combinations, there are 7 columns = 21. For each diagonal and anti-diagonal you have 12 combinations = 24. Resulting in a total of 69. Unsure whether storing all those in a hash table is more performant than checking them by hand? I guess hash tables are faster, but I think I have to try it out.–Aug 12 '11 at 11:22. This is related to this question:The twist is the 7x6 board with 4 in a row winning rather than a NxN board with N in a row winning.

But it is trivial to adapt the solution to NxN tic tac toe to connect 4.EDIT: Actually, it's not quite trivial to adapt the other solution to this one. But you can get there with a little bit of extra work.Store a count for each player for every row, column, diagonal and anti-diagonal that could ever have 4 pieces in a row. When that count hits 4 or more for either player, check to see if that row/column/diagonal/anti-diagonal has the four pieces in a row. If it does, that player wins!