Python/backtracking/minimax.py at master · PreciousJac0b/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.

nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
from __future__ importannotations

importmath


defminimax(
depth: int, node_index: int, is_max: bool, scores: list[int], height: float
) ->int:
"""
 >>> import math
 >>> scores = [90, 23, 6, 33, 21, 65, 123, 34423]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 65
 >>> minimax(-1, 0, True, scores, height)
 Traceback (most recent call last):
 ...
 ValueError: Depth cannot be less than 0
 >>> minimax(0, 0, True, [], 2)
 Traceback (most recent call last):
 ...
 ValueError: Scores cannot be empty
 >>> scores = [3, 5, 2, 9, 12, 5, 23, 23]
 >>> height = math.log(len(scores), 2)
 >>> minimax(0, 0, True, scores, height)
 12
 """

ifdepth<0:
raiseValueError("Depth cannot be less than 0")

iflen(scores) ==0:
raiseValueError("Scores cannot be empty")

ifdepth==height:
returnscores[node_index]

ifis_max:
returnmax(
minimax(depth+1, node_index*2, False, scores, height),
minimax(depth+1, node_index*2+1, False, scores, height),
 )

returnmin(
minimax(depth+1, node_index*2, True, scores, height),
minimax(depth+1, node_index*2+1, True, scores, height),
 )


defmain() ->None:
scores= [90, 23, 6, 33, 21, 65, 123, 34423]
height=math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()