before the main body (of a book)
I did a course on Artificial Intelligence a while back, and I wrote about an artificial retard. It's probably a stupid son of a bitch who can play backgammon with you. Here is the code and the effect
main body (of a book)
1. Summary
Machine gaming is an important branch in the field of artificial intelligence, and its research object is mostly based on complex chess intellectual games. Almost all the chess games that have been solved should be attributed to the development of machine gaming in the past half century. The advantage of computer problem solving lies in the fact that it is not easy to analyze the problem and enumerate all the reasonable situations with the help of modern computers; however, the complexity of the game problem decides that it can not rely too much on the machine's computational ability. The state space complexity or game tree complexity of many chess games to be solved or already solved is too large, so we need to add constraints and use reasonable algorithms for optimization.
The backgammon problem is a classic problem in artificial intelligence. In today's world, AlphaGo has taken the lead in Go, but the field of backgammon is seldom asked. In this paper, based on the knowledge learned in the classroom, combined with literature, blogs, based on two development languages to realize an intelligent battle AI backgammon game platform.
The work done in this paper is as follows:
(1) Backgammon interface realization;
(2) Intelligent determination of board movement;
(3) Improved board scanning;
(4) Improved systematic rating scale assessment;
(5) Realized to find out the best way to drop a child based on point rating scale valuation.
2. Description of the problem, expression of knowledge
2.1 Description of the problem
The biggest problem of the backgammon AI problem is how to realize the intelligent game, i.e., when a person makes a move, how does the algorithm interpret the current board and analyze and interpret it to get the best move for the computer side. Secondly, there is another problem is how to judge the victory, which can be a sub-problem of the previous board situation determination, or can be regarded as a separate problem, but this problem is relatively simple in general, so it will not be described in detail.
2.2 Expression of knowledge
The overall knowledge construction of futsal consists of the following parts:
(1) Representation of board positions
(2) Determination of Game Victory
(3) Knowledge base of chess patterns
(4) Intelligent Gaming Process
For problem (1), an array representation is used. Each intersection point in the board has three states, let 0 denote empty (no piece is placed), -1 denotes a black disc, and 1 denotes a white disc. The basic idea of array representation is to express the physical position by the index value of the array corresponding to the intersection point, and to express the state (empty, black, and white discs) by the value of the element corresponding to the intersection point. Let V = {0 , 1 , -1}, the state Si ∈ V of the ith intersection point of the board, any game can be represented as an n × n binary.
For problem (2), when using the array representation, to know whether any two elements Si and Sj are covariant, it is necessary to judge by the numerical law between i and j. In this respect, the array representation is a primitive and inefficient representation, but its performance loss is acceptable for the rating scale algorithm. In this respect, the array representation is a primitive and inefficient representation, but the performance loss is acceptable for the scoring table algorithm. To determine whether one side has won, it is sufficient to judge the entire board to see whether the longest extensions of the current drop point in the vertical, horizontal, forward-sloping, and backward-sloping directions extend out to four positions to see if they can be connected into a straight line of the same color. The specific operation can be regarded as follows: start from the drop point, extend in two directions, if you encounter the same color, then the counter will be added one, if you encounter a non-same color (blank or different color), then stop the extension in that direction, a counter to note down the number of consecutive same-color pieces at both ends of the direction. When all four directions have been explored, if one of the four counters reaches 5, then it can be determined that there are five consecutive pieces, and the game is over.
Problem (3) The chess-type knowledge base consists mainly of various established forms of chess boards, as follows:
² lit. live four days : There are two points of five (i.e., there are two points that can form a five), and the white dot in the diagram is the point of five. When the live four appears, the whole situation is no longer able to stop the five, and the player who has the live four will surely be able to win;
² take the bull by the horns : There is a five-point sequence, as shown in the following three diagrams, all of which are of the Punch Four type. The white point in the diagrams is the five-point line. Compared to the live four, the punch four is much less threatening, because at this point, the punch four cannot form a five by following the defense at the only five-point.
² Live III:It is possible to form the three of live four, as shown below, representing the two most basic types of live three. The white point in the diagram is the live-four point. The live three pattern is one of the most common in the attack, because after a live three, if the opponent does not take care of it, he will be able to turn the live three into a live four with the next move, and a live four is impossible to defend. Therefore, one needs to be very careful when facing a live three. In the absence of a better attack, it must be defended against to prevent it from forming the dreaded Live-4 pattern.
² Sleep three: It is only possible to form the three of punch four, as shown in the following diagrams, which represent each of the six most basic sleep three shapes. The white dots in the diagrams represent the four-point moves. Sleeping threes are much less dangerous than live threes, because even if you don't defend a sleeping three, it can only form a rush four on the next move, whereas a simple rush four can be easily defended against.
² second part of a living (e.g. party) The following diagrams show the three basic types of live twos. The white dots in the diagram are live three points.
² sleep two The four diagrams show the basic two-playing patterns. The four diagrams show the most basic sleep-two patterns, and the careful and thoughtful student will find sleep-two patterns different from the following four basic sleep-two patterns according to Diagram 2-13 in the introduction to sleep-three. The white dots in the diagram are the sleep three dots.
For the above patterns, we mainly consider the defense and composition of the main attacking patterns: live 4, punch 4, live 3, sleep 3. The overall pattern follows the following principles: priority is given to the number, and equal numbers are considered whether to live or sleep. The overall design of the score sheet algorithm favors defense.
For problem (4), the evaluation of the current chess type is analyzed and the algorithm strictly follows the following procedure:
When the human side drops a piece, the algorithm kicks in and scans the whole game to get the set of human pieces and the set of computer pieces. After the global scan, the current situation is sorted and calculated. Each blank point position in each set is scored, based on the number of consecutive pieces of the same color in the four directions around the point. According to these final scores obtained, a maximum value is derived. After obtaining the two maxima for the human side and the computer side, a comparison is made; if the human side is in a better situation (higher score), the algorithm sets the next move to the point where the human side has the highest score, trying to minimize the score of the human side's next move; if the computer side's score is higher, then it is sufficient to directly move to the point that makes the highest score.
3. Development tools
For this course design, a total of two versions were designed, a Java version for a 19X19 chessboard, equipped with simple message prompts, based on AWT to implement the GUI, development tools IntelliJ IDEA 2018.1
Another version is designed using Python with the same core algorithm, but limited by the image source files, for a 15X15 board, with a GUI implementation based on pygame, developed with: JetBrains PyCharm 2018.2.4 x64
4、 Code realization
from time import sleep
import pygame
from import *
from random import randint
level = 15
grade = 10
MAX = 1008611
def Scan(chesspad, color):
shape = [[[0 for high in range(5)] for col in range(15)] for row in range(15)]
# Scan each point and then make a value assessment in each direction of the blank point!
for i in range(15):
for j in range(15):
# If this is empty, then you can start scanning the perimeter #
if chesspad[i][j] == 0:
m = i
n = j
# If the top matches the current incoming color parameter, then add points to 0 bits!
while n - 1 >= 0 and chesspad[m][n - 1] == color:
n -= 1
shape[i][j][0] += grade
if n-1>=0 and chesspad[m][n - 1] == 0:
shape[i][j][0] += 1
if n-1 >= 0 and chesspad[m][n - 1] == -color:
shape[i][j][0] -= 2
m = i
n = j
# If the underside matches the current incoming color parameter, then add points to 0 bits!
while (n + 1 < level and chesspad[m][n + 1] == color):
n += 1
shape[i][j][0] += grade
if n + 1 < level and chesspad[m][n + 1] == 0:
shape[i][j][0] += 1
if n + 1 < level and chesspad[m][n + 1] == -color:
shape[i][j][0] -= 2
m = i
n = j
# If the left side matches the current incoming color parameter, then add points to 1 place!
while (m - 1 >= 0 and chesspad[m - 1][n] == color):
m -= 1
shape[i][j][1] += grade
if m - 1 >= 0 and chesspad[m - 1][n] == 0:
shape[i][j][1] += 1
if m - 1 >= 0 and chesspad[m - 1][n] == -color:
shape[i][j][1] -= 2
m = i
n = j
# If the right side matches the current passed-in color parameter, then add points to 1 place!
while (m + 1 < level and chesspad[m + 1][n] == color):
m += 1
shape[i][j][1] += grade
if m + 1 < level and chesspad[m + 1][n] == 0:
shape[i][j][1] += 1
if m + 1 < level and chesspad[m + 1][n] == -color:
shape[i][j][1] -= 2
m = i
n = j
# If the lower left matches the current incoming color parameter, then add points to 2 digits!
while (m - 1 >= 0 and n + 1 < level and chesspad[m - 1][n + 1] == color):
m -= 1
n += 1
shape[i][j][2] += grade
if m - 1 >= 0 and n + 1 < level and chesspad[m - 1][n + 1] == 0:
shape[i][j][2] += 1
if m - 1 >= 0 and n + 1 < level and chesspad[m - 1][n + 1] == -color:
shape[i][j][2] -= 2
m = i
n = j
# If the top right matches the current incoming color parameter, then add points to 2 digits!
while (m + 1 < level and n - 1 >= 0 and chesspad[m + 1][n - 1] == color):
m += 1
n -= 1
shape[i][j][2] += grade
if m + 1 < level and n - 1 >= 0 and chesspad[m + 1][n - 1] == 0:
shape[i][j][2] += 1
if m + 1 < level and n - 1 >= 0 and chesspad[m + 1][n - 1] == -color:
shape[i][j][2] -= 2
m = i
n = j
# If the top left matches the current incoming color parameter, then add points to 3!
while (m - 1 >= 0 and n - 1 >= 0 and chesspad[m - 1][n - 1] == color):
m -= 1
n -= 1
shape[i][j][3] += grade
if m - 1 >= 0 and n - 1 >= 0 and chesspad[m - 1][n - 1] == 0:
shape[i][j][3] += 1
if m - 1 >= 0 and n - 1 >= 0 and chesspad[m - 1][n - 1] == -color:
shape[i][j][3] -= 2
m = i
n = j
# If the bottom right matches the current incoming color parameter, then add points to 3!
while m + 1 < level and n + 1 < level and chesspad[m + 1][n + 1] == color:
m += 1
n += 1
shape[i][j][3] += grade
if m + 1 < level and n + 1 < level and chesspad[m + 1][n + 1] == 0:
shape[i][j][3] += 1
if m + 1 < level and n + 1 < level and chesspad[m + 1][n + 1] == -color:
shape[i][j][3] -= 2
return shape
def Sort(shape):
for i in shape:
for j in i:
for x in range(5):
for w in range(3, x - 1, -1):
if j[w - 1] < j[w]:
temp = j[w]
j[w - 1] = j[w]
j[w] = temp
print("This Time Sort Done !")
return shape
def Evaluate(shape):
for i in range(level):
for j in range(level):
if shape[i][j][0] == 4:
return i, j, MAX
shape[i][j][4] = shape[i][j][0]*1000 + shape[i][j][1]*100 + shape[i][j][2]*10 + shape[i][j][3]
max_x = 0
max_y = 0
max = 0
for i in range(15):
for j in range(15):
if max < shape[i][j][4]:
max = shape[i][j][4]
max_x = i
max_y = j
print("the max is "+ str(max) + " at ( "+ str(max_x)+" , "+str(max_y)+" )")
return max_x, max_y, max
class chess(object):
def __init__(self):
= [[0 for high in range(15)] for col in range(15)]
def fall(self, x, y, color):
if (x < 0 or x > level - 1 or y < 0 or y > level - 1):
return
[x][y] = color
if Judge(x, y, color, , 4):
if color < 0:
print("The Winner is White!!")
else:
print("The Winner is Black!!")
def isEmpty(self, m, n):
if [m][n] != 0:
return False
else:
return True
def Judge(x, y, color, CHESSLOCATION, length):
count1, count2, count3, count4 = 0, 0, 0, 0
# Horizontal judgment
i = x - 1
while (i >= 0):
if color == CHESSLOCATION[i][y]:
count1 += 1
i -= 1
else:
break
i = x + 1
while i < level:
if CHESSLOCATION[i][y] == color:
count1 += 1
i += 1
else:
break
# Vertical judgment
j = y - 1
while (j >= 0):
if CHESSLOCATION[x][j] == color:
count2 += 1
j -= 1
else:
break
j = y + 1
while j < level:
if CHESSLOCATION[x][j] == color:
count2 += 1
j += 1
else:
break
# Positive diagonal judgment
i, j = x - 1, y - 1
while (i >= 0 and j >= 0):
if CHESSLOCATION[i][j] == color:
count3 += 1
i -= 1
j -= 1
else:
break
i, j = x + 1, y + 1
while (i < level and j < level):
if CHESSLOCATION[i][j] == color:
count3 += 1
i += 1
j += 1
else:
break
# Anti-diagonal judgment
i, j = x + 1, y - 1
while (i < level and j >= 0):
if CHESSLOCATION[i][j] == color:
count4 += 1
i += 1
j -= 1
else:
break
i, j = x - 1, y + 1
while (i > 0 and j < level):
if CHESSLOCATION[i][j] == color:
count4 += 1
i -= 1
j += 1
else:
break
if count1 >= length or count2 >= length or count3 >= length or count4 >= length:
return True
else:
return False
def Autoplay(ch, m, n):
a1 = [1,-1,1,-1,1,-1,0,0]
b1 = [1,-1,-1,1,0,0,1,-1]
rand = randint(0,7)
while m+a1[rand]>=0 and m+a1[rand]<level and n+b1[rand]>=0 and n+b1[rand]<level and ch[m+a1[rand]][n+b1[rand]]!=0 :
rand = randint(0,7)
return m + a1[rand], n+b1[rand]
def BetaGo(ch, m, n, color, times):
if times < 2:
return Autoplay(ch, m, n)
else:
shape_P = Scan(ch, -color)
shape_C = Scan(ch,color)
shape_P = Sort(shape_P)
shape_C = Sort(shape_C)
max_x_P, max_y_P, max_P = Evaluate(shape_P)
max_x_C, max_y_C, max_C = Evaluate(shape_C)
if max_P>max_C and max_C<MAX:
return max_x_P,max_y_P
else:
return max_x_C,max_y_C
def satrtGUI(ch):
()
bg = ''
white_image = ''
black_image = ''
screen = .set_mode((750, 750), 0, 32)
background = (bg).convert()
white = (white_image).convert_alpha()
black = (black_image).convert_alpha()
white = (white, (int(white.get_width() * 1.5), int(white.get_height() * 1.5)))
black = (black, (int(black.get_width() * 1.5), int(black.get_height() * 1.5)))
(background, (0, 0))
font = ("bold.", 40)
.set_blocked([1, 4, KEYUP, JOYAXISMOTION, JOYBALLMOTION, JOYBUTTONDOWN, JOYBUTTONUP, JOYHATMOTION])
.set_allowed([MOUSEBUTTONDOWN, MOUSEBUTTONUP, 12, KEYDOWN])
dot_list = [(25 + i * 50 - white.get_width() / 2, 25 + j * 50 - white.get_height() / 2) for i in range(level) for
j in range(level)]
color = -1
times = 0
flag = False
while not flag:
for event in ():
if == QUIT:
exit()
elif == MOUSEBUTTONDOWN:
x, y = .get_pos()
if 25 <= x <= 725 and 25 <= y <= 725 and ((x - 25) % 50 <= level or (x - 25) % 50 >= 0) and (
(y - 25) % 50 <= level or (y - 25) % 50 >= 0):
color = -1 * color
m = int(round((x - 25) / 50))
n = int(round((y - 25) / 50))
if not (m, n):
print("Black OverWrite~~")
continue
(m, n, color)
(black, dot_list[level * m + n])
if Judge(m, n, color, , 4):
(('GAME OVER,Black is win!', True, (110, 210, 30)), (80, 650))
break
color = -1 * color
sleep(0.1)
x, y = BetaGo(, m, n, color, times)
times += 1
print("Predict:" + str(x) + " and " + str(y))
(x, y, color)
(white, dot_list[level * x + y])
if Judge(x, y, color, , 4):
(('GAME OVER,White is win!', True, (217, 20, 30)), (80, 650))
break
()
if flag:
sleep(5)
now = chess()
satrtGUI(now)
5. Summary and outlook
5.1 Summary
Because of the recent time constraints, I chose a simpler five pieces chess problem for the course design of the course "Artificial Intelligence". In this course design, my coding ability, debugging ability, algorithm interpretation and implementation ability, function optimization ability and other aspects have made great progress. There were also a few problems that arose during this design process, and a brief description of these problems is given below:
(1) Insufficient judgment of the board situation, since simply judging the current board situation is basically equivalent to a backgammon player with a cursory knowledge of the rules and little talent. If the opponent is very careful and skillful in various layout strategies, then basically the algorithm will be drilled out of habit, and thus easily targeted, and the targeting scheme will be tried and true;
(2) The scoring algorithm for the boundary when judging the form of the game is the same as the scoring algorithm for the center region, which is not able to effectively identify the boundary in advance, and reduces the weight of the boundary blank points;
(3) The graphical user interface needs to be improved, and PK mode can be added, as well as the functions of color selection and board size selection;
5.2 Outlook
The game tree algorithm can be tried later to try to compare with the current algorithm. The scoring table algorithm sacrifices higher accuracy in order to quickly arrive at the optimal drop point, while the game tree allows for a more holistic pursuit of the human side by making global predictions in advance of the drop.
In addition, the knowledge learned in the classroom, such as BFS, DFS, A* algorithm, decision tree algorithm, etc., can be applied to the intelligent decision-making of backgammon.
The class "Artificial Intelligence" has given me a better understanding and experience of various aspects of graphs, knowledge representation, intelligent decision-making, etc. The class design is full of interesting content, which has benefited me a lot, and I hope that in the future I can delve deeper into this aspect and apply what I have learned in the classroom in practice.
This is the whole content of this article.