'''Tic tac toe in python, Minimax with alpha-beta pruning.'''棚祥敬
import sys
import random
import getopt
# Board: array of 9 int, positionally numbered like this:
# 0 1 2
# 3 4 5
# 6 7 8
# Well-known board positions
WINNING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7),
(2, 5, 8), (0, 4, 8), (2, 4, 6))
PRINTING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8))
# The order in which slots get checked for absence of a player's token:
SLOTS = (0, 1, 2, 3, 4, 5, 6, 7, 8)
# Internal-use values. Chosen so that the "链慎winner" of a finished
# game has an appropriate value, as X minimizes and O maximizes
# the board's value (function board_valuation() defines "value")
# Internally, the computer always plays Os, even though the markers[]
# array can change based on -r command line flag.
X_token = -1
Open_token = 0
O_token = 1
# Strings for output: player's markers, phrase for end-of-game
MARKERS = ['_', 'O', 'X']
END_PHRASE = ('draw', 'win', 'loss')
HUMAN = 1
COMPUTER = 0
def board_valuation(board, player, next_player, alpha, beta):
'''Dynamic and static evaluation of board position.'''
# Static evaluation - value for next_player
wnnr = winner(board)
if wnnr != Open_token:
# Not a draw or a move left: someone won
return wnnr
elif not legal_move_left(board):
# Draw - no moves left
return 0 # Cat
# If flow-of-control gets here, no winner yet, not a draw.
# Check all legal moves for "player"
for move in SLOTS:
if board[move] == Open_token:
board[move] = player
val = board_valuation(board, next_player, player, alpha, beta)
board[move] = Open_token
if player == O_token: # Maximizing player
if val >alpha:
alpha = val
if alpha >= beta:
return beta
else: # X_token player, minimizing
if val <beta:
beta = val
if beta <= alpha:
return alpha
if player == O_token:
retval = alpha
else:
retval = beta
return retval
def print_board(board):
'''Print the board in human-readable format.
Called with current board (array of 9 ints).
'''
for row in PRINTING_TRIADS:
for hole in row:
print MARKERS[board[hole]],
def legal_move_left(board):
''' Returns True if a legal move remains, False if not. '''
for slot in SLOTS:
if board[slot] == Open_token:
return True
return False
def winner(board):
''' Returns -1 if X wins, 1 if O wins, 0 for a cat game,
0 for an unfinished game.
Returns the first "win" it finds, so check after each move.
Note that clever choices of X_token, O_token, Open_token
make this work better.
'''
for triad in WINNING_TRIADS:
triad_sum = board[triad[0]] + board[triad[1]] + board[triad[2]]
if triad_sum == 3 or triad_sum == -3:
return board[triad[0]] # Take advantage of "_token" values
return 0
def determine_move(board):
''' Determine Os next move. Check that a legal move remains before calling.
Randomly picks a single move from any group of moves with the same value.
'''
best_val = -2 # 1 less than min of O_token, X_token
my_moves = []
for move in SLOTS:
if board[move] == Open_token:
board[move] = O_token
val = board_valuation(board, X_token, O_token, -2, 2)
board[move] = Open_token
print "My move", move, "causes a", END_PHRASE[val]
if val >best_val:
best_val = val
my_moves = [move]
if val == best_val:
my_moves.append(move)
return random.choice(my_moves)
def recv_human_move(board):
''' Encapsulate human's input reception and validation.
Call with current board configuration. Returns
an int of value 0..8, the Human's move.
'''
looping = True
while looping:
try:
inp = input("Your move: ")
yrmv = int(inp)
if 0 <= yrmv <= 8:
if board[yrmv] == Open_token:
looping = False
else:
print "Spot already filled."
else:
print "Bad move, no donut."
except EOFError:
sys.exit(0)
except NameError:
print "Not 0-9, try again."
except SyntaxError:
print "Not 0-9, try again."
if looping:
print_board(board)
return yrmv
def usage(progname):
'''Call with name of program, to explain its usage.'''
print progname + ": Tic Tac Toe in python"
print "Usage:", progname, "[-h] [-c] [-r] [-x] [-X]"
print "Flags:"
print "-x, -X: print this usage message, then exit."
print "-h: human goes first (default)"
print "-c: computer goes first"
print "-r: computer is X, human is O"
print "The computer O and the human plays X by default."
def main():
'''Call without arguments from __main__ context.'''
try:
opts, args = getopt.getopt(sys.argv[1:], "chrxX",
["human", "computer", "help"])
except getopt.GetoptError:
# print help information and exit:
usage(sys.argv[0])
sys.exit(2)
next_move = HUMAN # Human goes first by default
for opt, arg in opts:
if opt == "-h":
next_move = HUMAN
if opt == "-c":
next_move = COMPUTER
if opt == "-r":
MARKERS[-1] = 'O'
MARKERS[1] = 'X'
if opt in ("-x", "-X", "--help"):
usage(sys.argv[0])
sys.exit(1)
# Initial state of board: all open spots.
board = [Open_token, Open_token, Open_token, Open_token, Open_token,
Open_token, Open_token, Open_token, Open_token]
# State machine to decide who goes next, and when the game ends.
# This allows letting computer or human go first.
while legal_move_left(board) and winner(board) == Open_token:
print_board(board)
if next_move == HUMAN and legal_move_left(board):
humanmv = recv_human_move(board)
board[humanmv] = X_token
next_move = COMPUTER
if next_move == COMPUTER and legal_move_left(board):
mymv = determine_move(board)
print "I choose", mymv
board[mymv] = O_token
next_move = HUMAN
print_board(board)
# Final board state/winner and congratulatory output.
try:
# "You won" should never appear on output: the program
# should always at least draw.
print ["Cat got the game", "I won", "You won"][winner(board)]
except IndexError:
print "Really bad error, winner is", winner(board)
sys.exit(0)
#-------
if __name__ == '__main__':
try:
main()
except KeyboardInterrupt:
sys.exit(1)
#include<stdio.h>#include<ctype.h>
#include<conio.h>
int n=9, z=0, qp[10]={0}
int chkwin(int t[], int w)
{if (t[1]==w &&t[1]==t[2] &&t[2]==t[3]) return(w)
if (t[4]==w &&t[4]==t[5] &&t[5]==t[6]) return(w)
if (t[7]==w &&t[7]==t[8] &&t[8]==t[9]) return(w)
if (t[1]==w &&t[1]==t[4] &&t[4]==t[7]) return(w)
if (t[2]==w &&t[2]==t[5] &&t[5]==t[8]) return(w)
if (t[3]==w &&t[3]==t[6] &&t[6]==t[9]) return(w)
if (t[1]==w &&t[1]==t[5] &&t[5]==t[9]) return(w)
if (t[3]==w &&t[3]==t[5] &&t[5]==t[7]) return(w)
return(0)
}
long search(int n, int k, int t[])
{int i, h, f, g
long j
if (n==0) return(chkwin(t,k))
for (f=0, j=0,i=1i<10i++)
if (t[i]==0)
{t[i]=kh=chkwin(t,k)
if (h==k) f++
else j+=search(n-1,k*-1,t)
t[i]=0
}
if (f>z) for (j=k, g=ng>0j*=g--)
return(j)
}
/*2.若走当前位置电脑能赢，则走这一步，否则转（3） */
/* 3.若当前位置被人走电脑会输，则走这一迅旁步，否则转（4）*/
/*4.试走当前位置并调用 search（）函数，求走当前位置电脑的有利程度 */
/*5.找对电脑有利程度最大的位置走 */
void cgo()
{int i, ti=0
long j=-8000000, t=0
for (ti=1ti>-2ti-=2) /*ti=1，先看自己能否赢；ti=-1,看对受能否赢*/
for (i=1i<10i++)
if (qp[i]==0)
{qp[i]=ti
if (chkwin(qp, ti)!=0) {n--qp[i]=1return}
qp[i]=0
}
for (i=1i<10i++)
if (qp[i]==0)
{qp[i]=1t=search(n-1,-1,qp)
if (t>埋宴j) {j=tti=i}
qp[i]=0
}
n--qp[ti]=1
}
/* 函数mgo(),人输入走棋位置 */
void mgo()
{int c=0
printf ("\nPlease enter the Num to go: ")
for (c=getche()printf("\n"), c=getche() )
if (isdigit(c) &&c!='0' &&qp[c-48]==0)
{n--qp[c-48]=-1return
}}
/* 屏幕输亩液橡出函数display,在屏幕上输出当前的棋盘*/
void display(int x)
{int i
char t[10]={0}
for (i=1i<10i++)
{if (qp[i]>0) t[i]=88
if (qp[i]<0) t[i]=79
}
printf ("\n%c|%c|%c\n-----\n%c|%c", t[1], t[2], t[3], t[4], t[5])
printf ("|%c\n-----\n%c|%c|%c\n", t[6], t[7], t[8], t[9])
if (x==0) printf("\ndraw!\n")
if (x==1) printf("\ncomputer win!\n")
if (x==2) printf("\ncontinue \n")
}
main()
{char c
printf ("\nGo first? [Y/N]:")/*选择谁先走*/
for (c=getche()c!='Y'&&c!='y'&&c!='N'&&c!='n'c=getche())
if (c=='N'||c=='n') {cgo()z=1display(2)}
while (1)
{mgo()if (!n) {display(0)break} /*人走，若不是最后一步，继续；否则跳出*/
cgo()if (chkwin(qp,1)) {display(1)break} /*电脑走，若没赢，继续；否则跳出*/
if (n)display(2) /*还没走到最后一步，继续；否则跳出*/
else {display(0)break}
}
getchar()
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）