基于決策樹模型的通關游戲決策問題的研究

陳雨晴 阮淑雯 劉聯

（重慶師范大學數學科學學院金融數學 重慶市 400047）

1 概述

在穿越沙漠的小游戲中，玩家憑借一張地圖（見圖1），利用初始資金購買一定數量的水和食物，從起點出發，途中會遇到不同的天氣。玩家可在礦山、村莊補充資金或資源，目標是在規定時間內到達終點，并保留盡可能多的資金。現根據游戲設定，假設只有一名玩家，玩家僅知道當天的天氣狀況，而天氣狀況有三種（“晴朗”、“高溫”、“沙暴”），在不知道該游戲區域內天氣分布狀況前提下，給出合理天氣分布。本文基于最少損失和最大收益原則，借助機器學習算法中的決策樹算法分析驗證并建立模型求解。

2 模型的建立與求解

2.1 假設與分析

游戲中玩家僅知道當天的天氣狀況，據此決定當天的行動方案。首先，由于玩家不能提前知道天氣狀況，所以屬于不確定型決策方法。在起點購買物質時，玩家要考慮在到達終點時剩余的水和食物最少、資金最多的目的。其次，游戲的時間限制為10天，去礦山挖金的基礎收益是200元，并且已知玩家在游戲中10天內不會出現沙暴天氣，因此，在10天之內為了使玩家到終點資源最多，是否去礦山對玩家來說值得思考。經過分析考慮，我們可以選擇兩種策略。

第一種策略：采取不考慮賺錢，但盡量使花費的錢最少的策略

要使花費的費用最少，就需要選擇消耗時間最少的路徑：1→5→6→13。通過分析可得，有四天時間花費在路途上，我們設有p的概率為晴天，1-p的概率為高溫。因為在路途中消耗量為基礎消耗量的兩倍，所以一共需要水72-48p 箱，食物72-40p 箱。我們算得成本函數為：

剩余資金函數為：

第二種策略：采取去礦山賺錢

這種策略使得花在路途上的時間最短，留在礦山挖礦的時間最長，從而使得在終點留下的資金最多的策略。選擇路線:1→4→3→9→11→13可使留在礦山挖礦時間最長，收益最大。在路上的六天共耗費水 108-72p 箱，食物 108-60p箱。挖礦四天消耗的水108-72p箱，食物108-60p箱.總共消耗的水的箱數為216-144p箱，食物216-120p箱。算得成本函數：

剩余資金函數：Q2(x)=10000-L2(x)=1920p+6760,

我們可以先假設10天內全部都是高溫天，消耗的水和食物的箱數最大，此時消耗水的箱數為216 箱，消耗食物的箱數為216箱，負重1080kg小于1200kg，所以最大負重符合要求。因此：

圖1：游戲地圖

圖2：在礦山時面對不同天氣的決策樹

圖3：在礦山時挖礦決策

圖4：凈收益函數圖

解得P>1.6875，由概率的性質可得：P<1，所以無論天氣狀況如何，有多少天是高溫天，有多少天是晴朗天氣，去礦山都是最優方案，選擇路線：1→5→6→13。我們發現在路線：1→5→6→13中，無論在什么天氣下，不停留繼續行走就是其最佳策略，因為可以盡可能增加在礦山采礦的時間，從而增加在礦山的收益，若假設某天天氣是高溫天氣，資源損耗量最大，若是在路途中采取停留策略，則在該天的水的損耗量為9箱，食物的損耗量為9箱，該天共花費費用135元，若采取行走策略，則消耗水18箱，消耗食物18箱，共花費費用270元，但是可以增加一天在礦山挖礦獲得的收益200元，相當于共花費費用70元，所以無論天氣如何，玩家只要不在某地停留(除礦山外)就是其最佳策略。

2.2 模型建立

本文主要考慮在礦山時面對不同天氣采取的不同策略，我們將這個過程用決策樹的方法來進行表示。決策樹，是在已知各種情況發生概率的基礎上，通過構成決策樹來求取凈現值的期望值大于等于零的概率，判斷其可行性的決策分析方法。

本文將玩家在礦山的四天里面所面臨的抉擇過程用決策樹表達出來。其中，晴天選擇挖礦一定是其最佳策略，因為資源的損耗量最小,同時可賺取收益200元；若是高溫天氣，我們可能會選擇挖礦賺取收益，同時也可能會選擇不賺錢，但使花費最少的方式來盡可能地保留資金。如圖2所示。

行走過程中所耗費資源的花費由天氣決定，我們主要考慮在挖礦過程中的資源的耗費所產生的費用，以及選擇挖礦情境下收益，我們通過使這部分凈收益最大來達到一種最優狀態。如圖3所示。

2.2 模型求解

在礦山一共呆了四天，設晴天為a天，則高溫為4-a天，其中以p的概率選擇挖礦，以1-p的概率選擇休息，一共消耗水72p-18ap+36箱，食物36+3a+72p-18ap箱。

費用函數:

收入函數：

凈收益函數:

凈收益函數小于0，則為虧損；凈收益函數大于0，則為有盈余。在圖4中，我們可以看到（表1）。

表1：決策情況表

3 評價與改進

本文在條件假設、選擇都特別多的情況下，盡可能多假設多分析，最終結果存在一定偏差。另外在天氣狀況不確定條件下，基于大量參考文獻，設置天氣狀況分布，顯然有誤差，運用決策樹過程中，由于基本數據不全，效果也不會特別好。因此若能知道該地區長時間一個天氣狀況，基于馬爾科夫鏈模型，可以減少誤差，決策出來的策略會更加優化。