# [2048]遊戲製作與演算法外掛

使用程式語言:PYTHON
使用套件:PYGAME / TIME / SYS / RANDOM / DATETIME / COPY / THREADPOOLEXECUTOR
作者:允安B

*附完整程式碼
### 2048外掛撰寫動機

小遊戲都非常吸引我，尤其是需要動腦的，其中2048就是一個可以讓我花費大把時間遊玩的遊戲，因為操作簡單，過程重複但不會無聊，遊戲有難度，完成目標後也很有成就感，所以2048可以說是我從小玩到大的好遊戲。

某天在社交媒體上看到有人在玩2048而且玩得很好，我就想說這種數學運算類的遊戲是不是可以程式去玩，畢竟它可以在極短時間內算出很多東西，會必人類強很多，於是我開始上網找資料，看看有沒有人也做過類似的專案。

一查才發現，還真有不少人都做過，更是有人把它呈現在網頁上，讓大家都可以直觀的感受到程式運算速度與演算法的力量，於是我下定決心要做一樣的事情，雖然有人做過了，也有人非常成功，但不管怎麼說，我就是想要親手破解這個陪伴我多年的遊戲，於是，我開始了2048外掛演算法製作。

### 遊戲介面製作簡介
我找了別人寫的遊戲程式碼作為主軸，並加以改進，我優化了介面、調了顏色、下載了字體，我想要把它做得跟真的一樣，而我花費了將近一週的時間做出了跟網頁版的介面別無二致的遊戲視窗。

### 內部重要程式碼
#### 內部重要程式碼介紹-colors
設置顏色，我為每一個方塊調顏色，都是模仿網頁版，值得一題的是從4096開始，後面都是隨機顏色，這並不是我抓不到它的顏色，而是我想在遊戲中加入一點新鮮感。

# 設置顏色
black = '#776e65'
white = (255, 255, 255)
bg = (187, 173, 160)

colors = {
    0: {"bg": (205, 193, 180)},
    2: {"bg": (238, 228, 218), "text": black},
    4: {"bg": (237, 224, 200), "text": black},
    8: {"bg": (242, 177, 121), "text": white},
    16: {"bg": (245, 149, 99), "text": white},
    32: {"bg": (246, 124, 95), "text": white},
    64: {"bg": (246, 94, 59), "text": white},
    128: {"bg": (237, 207, 114), "text": white},
    256: {"bg": (237, 204, 97), "text": white},
    512: {"bg": (237, 200, 80), "text": white},
    1024: {"bg": (237, 197, 63), "text": white},
    2048: {"bg": (237, 194, 46), "text": white},
    4096: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white},
    8192: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white},
    16384: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white}}

#### 內部重要程式碼介紹-draw
主要的遊戲運作圖像，包含畫每一個出大正方形與小正方形、設定數字尺寸並填入數字、繪製分數與最佳分數欄位、new game按鈕等等。

這邊的程式碼都是我自己寫的，另一端還有一個繪製靜態物件的部分，那邊就包含了遊戲標題2048，還有數學笑話:世界上有兩種人，一種懂10進位，另一種懂10進位。(10在二進位中代表2)

def draw_static_elements(cell_size = 85, margin = 14):
    screen.fill('#faf8ef')
    title_font = pygame.font.SysFont("Segoe UI", 75, bold=True)
    screen.blit(title_font.render("2048", True, black), (50, 42))

    title_font = pygame.font.Font('ThePeakFont.ttf', 19)
    screen.blit(title_font.render("世界上有2種人:", True, black), (50, 135))
    screen.blit(title_font.render("一種懂10進位，另一種懂10進位", True, black), (50, 160))
    # Button
    button_font = pygame.font.SysFont("Segoe UI", 17, bold=True)
    button_text = button_font.render("New Game", True, white)
    button_text_rect = button_text.get_rect(center = button_rect.center)  # 將文字置中於按鈕
    pygame.draw.rect(screen, '#8C7765', button_rect, border_radius=2)
    screen.blit(button_text, button_text_rect)

    border_width = (500 - (margin * 5 + cell_size * 4)) / 2
    border_height = 650 - border_width - (margin * 5 + cell_size * 4)
    pygame.draw.rect(screen, bg, (border_width, border_height, (margin * 5 + cell_size * 4), (margin * 5 + cell_size * 4)), border_radius=3)

#### 內部重要程式碼介紹-move
這邊主要也是用別人的邏輯，它會先把整個board都翻轉，翻轉到對的方向之後執行"向左滑"也就是遊戲中的向左合併，合併後再將整個board翻轉回來，這樣就不需要寫很多運算式就可以實現四種方向的合併，只需要判斷要向哪裡翻轉，以及運算向左合併的結果即可。

因為在AI移動時也會用到move，所以導致分數在模擬移動時也會增加，於是我增加了score_來設定此次移動是否加分，讓 AI 在模擬移動時輸入0
這樣就不會亂加分了。

def move(board, directions, score_=0):
    def merge(board):
        global score
        new_board = [row[:] for row in board]
        for i in range(4):
            list_data = new_board[i]
            zero_to_end(list_data)
            for j in range(3):
                if list_data[j] == 0:
                    break
                if list_data[j] == list_data[j + 1]:
                    list_data[j] *= 2
                    del list_data[j + 1]
                    list_data.append(0)
                    score += list_data[j] * (score_)
        return new_board

    def reverse(board):
        new_board = [row[::-1] for row in board]
        return new_board

    def transposition(board):
        new_board = [list(row) for row in zip(*board)]
        return new_board

    for direction in directions:
        if direction == 'a':
            board = merge(board)
        elif direction == 'd':
            board = reverse(merge(reverse(board)))
        elif direction == 'w':
            board = transposition(merge(transposition(board)))
        elif direction == 's':
            board = transposition(reverse(merge(reverse(transposition(board)))))
    return board

#### 內部重要程式碼介紹-main
主程式碼，包含判斷使用者是否按下右上角的關閉視窗按鈕、是否按下new game按鈕等，如果想改變玩家類型，只需要在player中輸入man 或是 ai 就可以改變玩家類型了。

man 模式：當有按鍵按下並為wasd中的一種，會判斷現在可否進行移動，若可以則移動，若無法移動則不做任何事情，移動過後判斷是否出局，若沒有出局則可增加方塊。

AI 模式：用到等等會介紹的AI演算法進行移動，一樣偵測是否出局，然後增加方塊。

def main():
    global board, score, best_score,  start_time
    init()
    player = 'ai'
    while 1:
        draw()
        old_board = copy.deepcopy(board)
        for event in pygame.event.get():  # 持續獲取未處理資料
            if event.type == pygame.QUIT:  # 使用者按下右上X
                pygame.quit()
                return
            if event.type == pygame.MOUSEBUTTONDOWN:
                if button_rect.collidepoint(event.pos):
                    print('--New Game!!--')
                    init()
            
            if event.type == pygame.KEYDOWN and player == 'man':
                MOVE = ''
                if event.key == pygame.K_n:
                    gameover()
                MOVE = {pygame.K_a: 'a', pygame.K_d: 'd', pygame.K_w: 'w', pygame.K_s: 's'}.get(event.key, MOVE)
                if MOVE:
                    print('move')
                    board = move(board, MOVE, 1)
                    if old_board != board:
                        print(datetime.now().time(), MOVE.upper(), board)
                        random_site()

                        for i in ['d','a','s','d']:
                            if move(copy.deepcopy(board), i, 0) != board:
                                break
                        else:
                            time.sleep(1)
                            gameover()
  
        if player == 'ai':
            if not ai_move():
                gameover()

            random_site()
        # time.sleep(0.1)

### 核心AI運作原理
內部最重要的函式 ai_move() 他的原理是把現在的 board 丟掉多線除理器裡面模擬上下左右的行動之後的分數，然後用位置分數權重乘上該位置的方塊數字，最後全部加總出來得到該行動的最終分數，並以最高分數的行動作為真實行動，由此來讓board的方塊配置達到最佳排序。
以下是目前的分數權重：
[ [128, 64, 5, 1],
[256, 32, 5, 1],
[516, 63, 5, 1],
[1024, 1, 5, 1] ]
"算到幾步之後"也相當重要，如果是make_ACTlist(3)會輸出
['www', 'wwa', 'wws', 'wwd', 'waw', 'waa', 'was', 'wad', 'wsw', 'wsa', 'wss', 'wsd', 'wdw', 'wda', 'wds', 'wdd', 'aww', 'awa', 'aws', 'awd', 'aaw', 'aaa', 'aas', 'aad', 'asw', 'asa', 'ass', 'asd', 'adw', 'ada', 'ads', 'add', 'sww', 'swa', 'sws', 'swd', 'saw', 'saa', 'sas', 'sad', 'ssw', 'ssa', 'sss', 'ssd', 'sdw', 'sda', 'sds', 'sdd', 'dww', 'dwa', 'dws', 'dwd', 'daw', 'daa', 'das', 'dad', 'dsw', 'dsa', 'dss', 'dsd', 'ddw', 'dda', 'dds', 'ddd']

用來算出三步以內的所有狀況，選擇最佳的結果作為真實行動

### 算出算到幾步是最佳
所有外掛都完成了，接下來就是更加精進，現在會影響到運算的就是要"算到幾步之後"
用來算出三步內會有的情況，所以我寫了一個專門給電腦模擬遊戲的程式，去除很多不必要的文字、美編，讓畫面精簡，把算力放在運算數字上。

最上面的三個數字分別代表現在局數/現在分數/最高分數，可以設定要跑幾局，跑完了會自動進行下一局，由此來收集數據，最後用圖表的方式呈現出來，讓使用者一目了然這幾局的最終分數以及達成大方塊的用時

### 3步之內又快又準
匯入之後開始測試，經過許多次測試之後發現只算3步是最剛好的，平均都可以到達2048，四步可以穩定到達4096，要再上去就要畫更多時間運算。
當然如果想要算更遠的一樣可以，但是就是會花很多時間。
這邊玩了50場是記錄我到達某方塊的時候的時間，綠色則是結束時的分數

### 心得與反思

期初和老師討論就獲得支持，之後就開始一步步地完成這次專案，當中遇到許多困難而都被一一克服的困難，後面也試過很多種演算法，也和數學老師、資訊老師討論過，也詢問了家人、朋友大家的意見，最後預計結合枝剪完成權重分配與情況模擬，也算是正式開始了這次外掛撰寫。其實這次算是蠻快速的完成第一版、第二版，也在期中就完成了完整的遊戲模式、顏色調配、排版等等，大多時間都花在演算法選擇與撰寫，最後雖然沒有成功寫出枝剪的程式，但也完成了最佳運算量的測試。

[Youtube演示影片連結](https://www.youtube.com/watch?v=JERc6RuoZKs)
[canva簡報連結](https://www.canva.com/design/DAGXq53qwus/uDxzeY8I-YOgai53gQXcmg/view?utm_content=DAGXq53qwus&utm_campaign=designshare&utm_medium=link2&utm_source=uniquelinks&utlId=h997401de72)

### 完整程式碼

import random
import pygame
import sys
import time
from datetime import datetime
import copy
from concurrent.futures import ThreadPoolExecutor

# 初始化pygame
pygame.init()

# 設置顯示窗口
screen = pygame.display.set_mode((500, 650))
pygame.display.set_caption("2048")

# 設置顏色
black = '#776e65'
white = (255, 255, 255)
bg = (187, 173, 160)

colors = {
    0: {"bg": (205, 193, 180)},
    2: {"bg": (238, 228, 218), "text": black},
    4: {"bg": (237, 224, 200), "text": black},
    8: {"bg": (242, 177, 121), "text": white},
    16: {"bg": (245, 149, 99), "text": white},
    32: {"bg": (246, 124, 95), "text": white},
    64: {"bg": (246, 94, 59), "text": white},
    128: {"bg": (237, 207, 114), "text": white},
    256: {"bg": (237, 204, 97), "text": white},
    512: {"bg": (237, 200, 80), "text": white},
    1024: {"bg": (237, 197, 63), "text": white},
    2048: {"bg": (237, 194, 46), "text": white},
    4096: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white},
    8192: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white},
    16384: {"bg": (random.randint(1, 255), random.randint(1, 255), random.randint(1, 255)), "text": white}}

score = 0
best_score = 0
random_tuple = (2, 4)  # 初始添加的值、移動時添加的值
button_rect = pygame.Rect(347, 142, 101, 40)  # new game位置
# View
def init():
    global score, best_score, board, start_time
    
    if score > best_score:
        best_score = score
    score = 0
    board = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    start_time = time.time()  # 記錄開始時間
    draw_static_elements()
    for i in range(2):
        random_site()

# Controller
def zero_to_end(list_data):
    for i in range(3, -1, -1):
        if not list_data[i]:
            del list_data[i]
            list_data.append(0)

def draw_static_elements(cell_size = 85, margin = 14):
    screen.fill('#faf8ef')
    title_font = pygame.font.SysFont("Segoe UI", 75, bold=True)
    screen.blit(title_font.render("2048", True, black), (50, 42))

    title_font = pygame.font.Font('ThePeakFont.ttf', 19)
    screen.blit(title_font.render("世界上有2種人:", True, black), (50, 135))
    screen.blit(title_font.render("一種懂10進位，另一種懂10進位", True, black), (50, 160))
    # Button
    button_font = pygame.font.SysFont("Segoe UI", 17, bold=True)
    button_text = button_font.render("New Game", True, white)
    button_text_rect = button_text.get_rect(center = button_rect.center)  # 將文字置中於按鈕
    pygame.draw.rect(screen, '#8C7765', button_rect, border_radius=2)
    screen.blit(button_text, button_text_rect)

    border_width = (500 - (margin * 5 + cell_size * 4)) / 2
    border_height = 650 - border_width - (margin * 5 + cell_size * 4)
    pygame.draw.rect(screen, bg, (border_width, border_height, (margin * 5 + cell_size * 4), (margin * 5 + cell_size * 4)), border_radius=3)

def rating(A, B):
    return sum(A[i][j] * B[i][j] for i in range(4) for j in range(4))

def move(board, directions, score_=0):
    def merge(board):
        global score
        new_board = [row[:] for row in board]
        for i in range(4):
            list_data = new_board[i]
            zero_to_end(list_data)
            for j in range(3):
                if list_data[j] == 0:
                    break
                if list_data[j] == list_data[j + 1]:
                    list_data[j] *= 2
                    del list_data[j + 1]
                    list_data.append(0)
                    score += list_data[j] * (score_)
        return new_board

    def reverse(board):
        new_board = [row[::-1] for row in board]
        return new_board

    def transposition(board):
        new_board = [list(row) for row in zip(*board)]
        return new_board

    for direction in directions:
        if direction == 'a':
            board = merge(board)
        elif direction == 'd':
            board = reverse(merge(reverse(board)))
        elif direction == 'w':
            board = transposition(merge(transposition(board)))
        elif direction == 's':
            board = transposition(reverse(merge(reverse(transposition(board)))))
    return board

def make_ACTlist(n, ACTs=['w', 'a', 's', 'd'], RET=['w', 'a', 's', 'd']):
    def generate_list(ACTs, REACT):
        delmod = len(REACT)
        for j in range(len(REACT)):
            for i in range(len(ACTs)):
                REACT.append(REACT[j] + ACTs[i])
        return REACT[delmod:]

    if n > 1:
        x = generate_list(ACTs, RET)
        return make_ACTlist(n - 1, ACTs, RET=x)
    else:
        return RET

def random_site(evil_=0):  # 增加方塊
    random_list_len = len(random_tuple)
    while True:
        x = random.randint(0, 3)
        y = random.randint(0, 3)
        if board[x][y] == 0:
            board[x][y] = random_tuple[random.randint(0, random_list_len - 1)]
            break

def can_move():
    temp_source = copy.deepcopy(board) 
    for direction in ['a', 'd', 'w', 's']:
        new_board = move(temp_source, direction)
        if temp_source != new_board:
            return True
    print('out')
    return False

def draw(cell_size=85, margin=12):
    global button_rect
    global board
    border_width = (500 - (margin * 5 + cell_size * 4)) / 2
    border_height = 650 - border_width - (margin * 5 + cell_size * 4)
    
    for i in range(4):
        for j in range(4):
            value = board[i][j]
            color = colors.get(value, {"bg": bg, "text": black})
            # 計算格子的座標
            x = j * (cell_size + margin) + border_width + margin
            y = i * (cell_size + margin) + border_height + margin
            # 繪製格子
            pygame.draw.rect(screen, color["bg"], (x, y, cell_size, cell_size), border_radius=2)
            if value != 0:
                text_color = color["text"]
                # 根據數字大小調整字體大小
                S = len(str(value))
                text_size = (S < 3) * (45) + (S == 3) * (38) + (S == 4) * (28) + (S == 5) * (30)

                dynamic_font = pygame.font.SysFont("Segoe UI", text_size, bold=True)
                # 渲染文字
                text = dynamic_font.render(str(value), True, text_color)
                text_rect = text.get_rect(center=(x + cell_size // 2, y + cell_size // 2))
                screen.blit(text, text_rect)

    # 繪製 best score 和 score，以及其他文字
    now_score_rect = pygame.draw.rect(screen, bg, (255, 70, 97, 50), border_radius=2)
    best_score_rect = pygame.draw.rect(screen, bg, (355, 70, 97, 50), border_radius=2)

    score_font = pygame.font.SysFont("Segoe UI", 24, bold=True)
    score_text = score_font.render(f"{score}", True, white)
    score_text_rect = score_text.get_rect(center=(now_score_rect.centerx, now_score_rect.centery + 6))
    screen.blit(score_text, score_text_rect)

    best_score_text = score_font.render(f"{best_score}", True, white)
    best_score_text_rect = best_score_text.get_rect(center=(best_score_rect.centerx, best_score_rect.centery + 6))
    screen.blit(best_score_text, best_score_text_rect)

    title_font = pygame.font.SysFont("Segoe UI", 16, bold=True)
    score_text = title_font.render("SCORE", True, (238, 228, 218))
    score_text_rect = score_text.get_rect(center=(now_score_rect.centerx, now_score_rect.centery - 15))
    screen.blit(score_text, score_text_rect)

    best_score_text = title_font.render("BEST", True, (238, 228, 218))
    best_score_text_rect = best_score_text.get_rect(center=(best_score_rect.centerx, best_score_rect.centery - 15))
    screen.blit(best_score_text, best_score_text_rect)

    pygame.display.flip()


def ai_move():
    global board, ACT

    x = [
        [128, 64, 5, 1],
        [256, 32, 5, 1],
        [516, 63, 5, 1],
        [1024, 1, 5, 1]
    ]

    actions = []
    with ThreadPoolExecutor() as executor:
        futures = [executor.submit(lambda d: rating(move(copy.deepcopy(board), d), x) if move(copy.deepcopy(board), d) != board else 0, D) for D in ACT]
        for future in futures:
            actions.append(future.result())

    if not any(actions):
        return False

    best_direction = ACT[actions.index(max(actions))]
    board = move(board, best_direction, 1)
    return True

def gameover():
    time.sleep(0.314159265358979323846264)
    # 創建一個帶有透明度的表面
    rect_surface = pygame.Surface((500, 650), pygame.SRCALPHA)
    rect_surface.fill((*(205, 193, 180), 210))
    screen.blit(rect_surface, (0, 0))


    texe = pygame.font.SysFont('Impact',80).render("Game Over", True, '#776e65')
    screen.blit(texe, texe.get_rect(center=(250,250)))

    texe = pygame.font.Font('ThePeakFont.ttf', 40).render("-成功為失敗之子-", True, '#776e65')
    screen.blit(texe, texe.get_rect(center=(250,330)))

    texe = pygame.font.Font('ThePeakFont.ttf', 20).render("[點擊任意位置重新開始]", True, '#776e65')
    screen.blit(texe, texe.get_rect(center=(250,380)))

    print(f"/\n/\n--GAME OVER--\n{score}\n{board[0]}\n{board[1]}\n{board[2]}\n{board[3]}")
    pygame.display.flip()

    waiting = True
    while waiting:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()
            elif event.type == pygame.MOUSEBUTTONDOWN:
                waiting = False
    init()

def main():
    global board, score, best_score,  start_time
    init()
    player = 'ai'
    while 1:
        draw()
        old_board = copy.deepcopy(board)
        for event in pygame.event.get():  # 持續獲取未處理資料
            if event.type == pygame.QUIT:  # 使用者按下右上X
                pygame.quit()
                return
            if event.type == pygame.MOUSEBUTTONDOWN:
                if button_rect.collidepoint(event.pos):
                    print('--New Game!!--')
                    init()
            
            if event.type == pygame.KEYDOWN and player == 'man':
                MOVE = ''
                if event.key == pygame.K_n:
                    gameover()
                MOVE = {pygame.K_a: 'a', pygame.K_d: 'd', pygame.K_w: 'w', pygame.K_s: 's'}.get(event.key, MOVE)
                if MOVE:
                    print('move')
                    board = move(board, MOVE, 1)
                    if old_board != board:
                        print(datetime.now().time(), MOVE.upper(), board)
                        random_site()

                        for i in ['d','a','s','d']:
                            if move(copy.deepcopy(board), i, 0) != board:
                                break
                        else:
                            time.sleep(1)
                            gameover()
  
        if player == 'ai':
            if not ai_move():
                gameover()

            random_site()
        # time.sleep(0.1)

if __name__ == "__main__":
    ACT = make_ACTlist(3)
    main()