Connect 4: Rules based approach.
This project has been developed for the subject: "Artificial Intelligence".
Professor: Dr. Witold Paluszynski.
Politechnika of Wroclawska
Gabriel Barrionuevo Rosales
Yari Lorenzo Martínez
Wroclaw, 07/02/2012
Index
3. Identification of the production parts system in the game
4. Design of the knowledge base
1. Short description about Connect 4
Connect 4 is a game for 2 players wich each turn one player inserte his chip upper in a column’ gameboard, which is composed of 6 rows and 7 columns.
The chips fall down, occupating the next available slot in the column.
The goal is to connect 4 pieces of your own color in line vertically, horizontally or diagonally before the opponent to do so.
If neither player gets the wind , and the gameboard has been completely filled, then the game ends in a draw.
The turn will be choosen firstly at random. After, will stat the player who lost the previous game or alternatively.
The game board is usually similar to this shown in the picture. However, variations may occur sometimes in size.
2. Problem Analysis.
After we have read some articles about games based in rules (ref: http://www.personal.psu.edu/prm5031/AI_Paper.pdf), we have decided to use this tecnique to solve our own problem.
We chose this game because we had some ideas from the last year 2011. We were analysing this game in our course in University of Almería so now we have taken the task for implementing the system and giving some conclusion. Ref: Proposed Project University of Almeria.
3. Identification of the production parts system of the game
The production system consists on the following parts:
- Set of rules : The rules will be followed by a machine player to select the movement. Theser are based on the current state of the game. If for the current state, the condition of the rule, then it will execute its corresponding action.
- Knowledge Base : It reflects the current state of the game. In addition, make use of two feature vectors, wich indicate some values on the game state.
- Control Strategy : It will decide the movement wich the player wil do in each turn.In principle, the control strategy will be to read the rules and apply the first wich satisfy your condition.
- Rules Applier : The rules are read from an XML file, and the machine player will be who interprets and applies.
4. Design of the knowledge base.
The knowledge base is the current situation game, when you start taking a decision. In this case, the current situation will be awarded to the player passing the board, so he can do about it all the checks what are arppropiate.
In order to draw any more detailed information, we must first consider what are the possibilities in the moment of decision. These possibilities are clear: you can insert the chip in any of the 7 columns. However, occasionally it is possible that a column is full, wich would not be a possibility.
Another key in the decision process is to ask what we want. Crearly, we have 7 (or less) possibilities where to place the chip, but we have not decided how we will built to choose one of these options. We will use the most logical thing: when we play Connect 4, we are looking to unite 4 chips in line. So we will do is calculate how many chips you would get chained placing the chip in each option, ie at each position available.
The problem of considering only that logic is that you are not allowing for any behavior or opposing player options. That is, if this player wer playing only expensive machine to finish his own plays, it’s ease for another player to complete its line of 4 before it, and win. Therefore, what we will do the same process of counting the number of chips back, but in this case we do to the opponent.
To make this calculations, we will place ourselves in one of the possible positions, and go over the gameboard horizontally (to both sides), vertically (going down), and diagonally (both sides and up and down). We will go over them while the color of the chips we find is matching the player we are analysing; while we go over, we will add each chip to the total so we can return the exact number of chips that are linked in that direction.
5. Production rules design
Once we have described the base of knowledge, we proceed to define the structure for the rules the machine player shall follow. These rules will work on the vector of properties described before.
As it is always done, these rules will consist of two parts: condition and action. This way, if the condition of the rule we are evaluating is verified, then the action will be realized. If not, then nothing will be done, and we will continue evaluating the other rules.
In our case, the condition will be compound of two variables: "chips" and "own". The first it's related to the number of chips that should be on a row to perform the action; the second it's representing if those chips are owned by the self player (this is, the player who is being processed), or not (so they are owned by the opposite player).
Actions will be simply to "Throw" or "Random". With "Throw" we mean that the chip will be left in the position of the gameboard where the condition have been verified. If it is more than one, the chip will be thrown randomly into one of them. With "Random" we mean that the machine will leave the chip in any position (considering only the available positions, this is, not full).
One example could be the next:
Moreover, all the rules are grouped by the label <behaviour>. This way we can read and write them easily using the XStream library. With this library we simply need to link each element (alias) with his corresponding class: Behaviour.class, Rule.class and Condition.class. The rest of the names are the properties inside those classes: chips, own and action.
6. The rules applier
The rules described before show a pretty direct relation between the properties vectors. The rules applier will be in charge of interpreting them and realize the convenient actions in each moment.
We have seen that each rules contains the number of chips and who's the owner. Well, the applier will search into the properties vectors if there is any entry where the number of chips matches the specified. If "own" is true, it will search into the own machine vector, so it will complete his turn. If "own" is false, it will search into the opposite player vector in order to check if it's worth to block his play.
If the applier finds some entries that match, then it will save it into one list together with the rest of them. If it is more than one in that list, and the action is to "Throw", then it will leave the chip in one of those positions.
7. Strategy of control design
The strategy of control will be the way we read and apply the rules. What we will do will be the next. We begin from the first rule, check his condition and in case it is verified then the action will be taken, and the process is ended. If the condition of the first rule is not verified then we start to evaluate the immediate next rule, and the same process is repeated.
Then the rules is being applied from the first, one by one, until the last, or until one of them is verifying the condition.
8. Example execution
One example Player1 vs Machine.
Player1
Machine
| 1.Initial state. |  |
| 2.First movement |  |
| 3. Second movement: The machine firstly try to block the movement of the player1, so it insert in the column 6. |  |
| 4. After few movements the state of the gameboard is this. |  |
| 5. Final state of the game. The player1 have got 4 connected chips. The machine only has been able to block one winner movement, because the player1 had got 2 winner movements. |  |
9.Conclusions
This conclusions will be made taking the example of rules which is loaded by default. It is also possible to change the set of rules by writting in the white box in the right side of the window.
We have done 30 tests with differents situations so we have implemented one scorer to show the results of each game.
Situation 1: Player versus Machine.
In order to test the intelligence of our system we have played against it and these are the results. As we can observe the computer win 22 times when beginner is playing. The result can variate if the player is expert.
Situation 2: Machine versus Machine.
As the computer players play the same way they get more or less the same amounts of winning games. The behaviour based in rules is quite good because in each game they fill about half gameboard.
10. References
| Nilsson, N., Artificial Intelligence: A New Synthesis. |
| Rules of the game: http://en.wikipedia.org/wiki/Connect_Four. |
| Elaine Rich, Kevin Knight, Artificial intelligence. |
| http://www.personal.psu.edu/prm5031/AI_Paper.pdf |
| Similar Project: Checkers -‐> http://sequoia.ict.pwr.wroc.pl/~witold/ai/Checkers/ |
Extract everything from this RAR and exectute .jar file.