The computer tries to determine all the traits of a Game Moves, which is determined by the level of. At level 1, He tried out a stone's throw, one for himself and one for the opponent. At level 2 he try 4 Stone's throw from, at level 3, 6 and from level 3 always one more.
For each position, the results from it, he leads by an assessment and then selects the train, resulting in the end the best rating. He leads for the opponents moves through the same method. In this way he always calculates the (determined by this method) best train the enemy, to determine their own best train.
How the computer evaluated a position?
He is one for every stone of his color, How many ways there are still, 4 to get into a series. On an otherwise empty field with a stone bottom left is a review of 3, because it 3 The possibilities, This stone from 4 to get into a series: to the top, upwards to the right and to the right.
This census is carried out for the computer and the Gegnger. A review of the position is calculated from these two counts, where can other weighted the counting result of the opponent as its own. The weighting is determined by the Angriffslust of the computer. In extreme Angriffslust, the count of Gegngers only lexicographically a role, meaning. If two trains are the same number after the counting of the own stones, the train is preferred, who has a worse counting results to an enemy.
The Angriffslust (= Strategy) the computer is chosen at random for a game. She can 5 Take values between the “almost only own opportunities to expand”-Strategy to “minimize the chances of the opponent in the first place”. This selects the computer in a level a strategy, with which he once lost, not again (If possible).
The case of the profit is measured with a number, which is greater than all reviews, that obtained for the above schema. Losing is rated as a negative number.
The alpha-beta-abort algorithm is used to improve speed. The idea is the following: Select the opponent is always the train, which is the worst for the computer. Therefore do not need to be calculated all own trains, If the opponent by one other previous train (meaning. in another branch) has the ability, better to face than by grade analyzed. All other trains in the current tree need not be analysed, because there is a possibility for the enemy, the computer less to make than in another branch.
The other branch is therefore preferred by the computer, without having to try and evaluate all trains in the current tree.
This algorithm is purely logical, meaning. He is not restricts the result set, but reduces the number of necessary operations to achieve that exactly the same result as with the full search. Many thanks to Marc Becker, the me has stated this algorithm.
Opportunities for improvement
Speed
To improve the speed, expects the computer while the opponent still thinking. To be 7 Generates fields, While each field contains a possible move of the opponent. Then the calculation will be at the same time for all 7 Started playing fields. Has the opponent made his move, so, the calculations are stopped, which were launched for an other his opponent's move and waited until the calculation for the train, which the opponent has made actually, is completed. Unfortunately this has not much, because the advance calculation must share the performance of the processor, they come only with ca. a seventh of the speed of a single calculation ahead. At train speeds of people between 5 and 15 A time saving seconds per move arises from 5/7 up to 15/7 that is, from 0,7 up to 2 Seconds. In ca. 60 Second level calculation 5 is no more than a drop in the bucket 🙁 Unfortunately I made the observation of human train speed only, After I the “count on opponents time” had already programmed 🙁
Perhaps it might be worth, the routines, be used during the calculation, to optimize speed. I tried with moderate success and no special effort. Both are in the source code (which “slower” and that “faster”) Still contain routines, the tags have the new “fast”. For those who desire, here what to improve, like to!
Another way, to make the game in higher levels more bearable,
would be, build an opening library. If the opening library is processed, is it however not faster than before.
Could it also be, the computer “Intelligent” to make, meaning. Forecasts cancel, before the default calculation depth is reached, If somehow “foreseeable” is, that this be conversion branch in question is. However, is in this way the computer “creative potential” taken, He can do no more trains, look bad at first glance (= predictably come out of the question), but after some trains beneficial prove. All chess programs have to be with such “Heuristics” These methods work, because the number of possibilities after only a few trains so great is there, that not all trains can be evaluated in an acceptable time. To develop of good heuristics much game experience is necessary. Perhaps someone feels, Since approached to go? – I will be (at least in the near future) do not worry, because this play so to speak for me should be the test, how well a computer without heuristics, meaning. without built-in gaming experience, can play. The result is: It goes pretty well, but against a person, is the computer (without heuristics) slow and beatable.
Skill level
The first version of this program evaluated only the quality of the own position, regardless of the position of the opponent. The current version used with the evaluation of the position of the opponent according to Angriffslust (= Strategy) varying weights. Thus the skill level of the computer could be significantly enhanced.
Is not implemented: Hire. is the weight, This should be measured to the opposing position assessment, Depending on the stage and the skill level of the opponent.
Another way, the skill level to improve, could it be, not only the best opponents of the train to take into account, but involving the distribution of the evaluations of the opponent. A mechanism could also, It uses a different algorithm for the opposing train for the machine train.
Another way is to, certain constellations (p.E.. “Fall”, can not be recognized within the depth of anticipation) with certain reviews to provide. Probably this is the method most promising, because such systematic weaknesses can be reduced. Allderdings be so always only a few “Fall” taught the computer. Also, this requires such as in heuristics gaming experience, which is why I do not plan any time soon, to implement such.
An easier way, the skill level to improve, could it be, not only the number of possible Viererreihen to include, but also take into account, How many stones the Viererreihe already exists. So far, the machine evaluates two possible Viererreihen, they already made a, There are two or three stones, the same. Probably the game of the computer is aggresiver, but hire. also less strategically, so short-term targeted, because of the prefabricated by 3 Stones in a row is important –
hire. more important than the construction of new facilities. – I can hardly appreciate,
whether or not the game this is better, It is probably also because of the weight compared to more opportunities. I plan this improvement opportunity, in principle any time soon.
Source code
There is the Java source code as ZIP file here.
It can freely distributed, used and to be changed, as long as my name with
is passed. I personally use the modified class massage box
by Jack Harich, to messages (p.E.. Player with the color of X has won”)
spend.
The main file is “kreise.Java”, It implements the graphical user interface. The file “tspielfeld.Java” provides basic functionality of Viergewinntspielfeldes, during the file “SchlauesSpielfeld.java” Position evaluation functions including the method “has player won?” extended, the method for the determination of best turn adds and
implements the interface for threads, to simultaneous projections to
enable.
I have here a short tutorial written, how you include this small Viergewinnt game on his own page.
Ideas? Suggestions? Praise songs?
Simply leave a comment.