Discuz! Board

 找回密碼
 立即註冊
搜索
熱搜: 活動 交友 discuz
查看: 302|回復: 0
打印 上一主題 下一主題

博弈论

[複製鏈接]

1253

主題

1253

帖子

3773

積分

管理員

Rank: 9Rank: 9Rank: 9

積分
3773
跳轉到指定樓層
樓主
發表於 2023-10-25 17:20:48 | 只看該作者 回帖獎勵 |正序瀏覽 |閱讀模式
今天是算法和数据布局專题第25篇文章,咱們继续消脂茶,博弈论專题。

在上一篇文章傍邊咱們领會了最简略的巴什博奕,今天咱們来看看另外暖手神器,一個經典的博弈模子——威佐夫博弈。博弈论和呆板进修有些雷同,数學家們针對場景举行建模,設計出了几個經典模子。然後咱們在面對详细問题的時辰,對問题举行深刻阐發,寻觅最符合的模子利用来解决它。

咱們来看一道經典的洗鞋神器,例题,有两堆石子,有两個尽頭聪慧的人在玩一個遊戲。每次每小我可以從此中一堆石子傍邊取走肆意数目的石子,或是從两堆傍邊同時取走不异数目的石子。没法取石子的人落败,请問,在告诉两堆石子数目的环境下,這两小我傍邊哪一方會获胜?

咱們简略阐發一下,會發明一些場合排場是先手必败的。好比说(0, 0),再好比(1, 2)。咱們简略阐發一下(1, 2),先手有4種计谋,起首他可以取走第一堆,那末背工可以取完第二堆,明显背工获胜。他也能够在第二堆傍邊取1個,這時候剩下(1, 1),背工會同時取完,一样是背工获胜。第三種是他取走第二堆,背工可以取完第一堆,背工获胜。第四健康美容,種是他在第一堆和第二堆傍邊同時取走一個,這時候第二堆剩下一個,背工胜。

那末,這些必败的状况之間有甚麼纪律呢?咱們怎样找到這個纪律,而且找到解呢?

咱們可以罗列几個必败的状况:(0, 0), (1, 2), (3, 5), (4, 7)...

咱們察看一下這些状况,可以找到两条纪律。咱們假如從小到大排的第k個必败状况是(x, y),而且x < y。咱們可以發明y = x + k。也就是说必败状况两個数的差值是递增的,這也阐明了每個必败状况的差值都各不不异。

實在這是很轻易證實的,咱們用反證法,假如(a, a+k), (b, b+k)都是必败状况,而且a < b。那末先手在面對(b, b+k)的時辰,只必要在两堆傍邊同時取走b-a個石子,那末给背工的場合排場就是(a, a+k)。對付背工来讲,這是一個必败的場合排場,這就和(b, b+k)先手必败抵牾,以是不存在两個必败場合排場的差值相称

咱們也能够作圖阐發,咱們把两堆石子的数目當作是坐標轴上的一個點。以是遊戲就酿成了:棋盘上有一個點,每次每小我可以将它向下、向左或向左下挪動若干個格子,不克不及挪動的人输。终止节點明显是原點,一步就可以挪動到原點的點明显是必胜點,假如咱們给這些所有必胜點都染色的话,剩下的的没傍邊横纵坐標和最小的點就是下一個必败點。由於它非论若何挪動,城市给敌手留下一個必胜點。

咱們按照上面的逻辑把必败點都染色,可以获得下面這张圖:

從這张圖可以看出,必败點之間不克不及經由過程一次挪動获得,换句话说可以一次挪動到必败點的點都是必胜點,從圖上可以看出,除必败點的以外的點都是必胜點,而且每個天然数都必定只會被包括在一個必败状况傍邊。

到這里,咱們間隔解法已很靠近了,如今剩下的問题是,咱們若何按照x和y的取值快速果断它們是不是组成一個必败場合排場呢?也就是说咱們能不克不及找出一個通項公式,對付第k個必败場合排場,它的坐標是(x_k, y_k)呢?

为了寫出通項公式,咱們必要引入Betty定理

P\cap Q = \varnothing

反證,咱們假如存在k \in P而且k \in Q,即存在正整数n, m知足 k < an,  bm < k+1。

也就是:\frac{n}{k} > \frac{1}{a} > \frac{n}{k+1}, \frac{m}{k} > \frac{1}{b} > \frac{m}{k+1}两個式子相加可以获得:\frac{m+n}{k} > 1 > \frac{m+n}{k}

即k < n+m < k+ 1,這與n,m,k都是正整数抵牾

P \cup Q = N^+

反證,假如存在k \notin P且k \notin Q,即存在正整数n,m知足an < k < a(n+1)-1, bm < k < b(m+1)-1

即:\frac{n}{k} < \frac{1}{a} < \frac{n+1}{k+1}, \frac{m}{k} < \frac{1}{b} < \frac{m+1}{k+1}

相加,可以获得:\frac{m+n}{k} < 1 < \frac{n+m+2}{k+1}

即:n + m < k 洗澡神器,< n + m + 1,這與n,m,k均为正整数抵牾

咱們花了這麼鼎力气来證實Betty定理就是为了用的,由於咱們發明必败状况的通項和Betty定理序列很像。咱們無妨假如存在如许的a, b同時知足Betty定理與必败状况的性子:

[an] + n = [bn], \frac{1}{a} + \frac{1}{b} = 1 \\[an] + n = [an + n] = [(a+1)n] = [bn] \\

代入可以获得:

\frac{1}{a} + \frac{1}{a+1} = 1 \\

解這個方程,可以获得a = \frac{1 + \sqrt{5}}{2}\approx 1.618,認识数學的同窗信赖一下就看出来了,這個数是黄金朋分的比例,這是偶合嗎,仍是藏着更深的事理呢?

最少,求出了a以後,咱們便可以很是简略地果断必败状况了:

  1. import math
  2. def lose_or_win(a, b):
  3. if a > b:
  4. a, b = b, a
  5. k = b - a
  6. # 按照差值k求出第k個必败状况,果断是不是相称
  7. return not (int(k * (math.sqrt(5)+1) / 2)) == a
複製代碼

和以前先容的巴什博奕比拟,威佐夫博弈的推导进程要繁杂很多,可是固然推导进程仍然繁杂,可是依然挡不住最後實現的代码很是简略。

此外,在推导的进程傍邊,咱們用到了Betty定理,這個定理的推导和證實固然不難,可是若是不是数學專業的同窗,可能大要率都没有接触過。這實在表現了博弈论自己和数學的瓜葛是很是慎密的。一個看起来很是简略的問题,引伸出了一系列目炫纷乱的推导和證實,怎样样,大師看得還過瘾嗎?

今天的中藥減肥茶,文章到這里就竣事了,若是喜好本文,可以的话,请點個存眷,给我一點鼓動勉励,也便利获得更多文章。
回復

使用道具 舉報

您需要登錄後才可以回帖 登錄 | 立即註冊

本版積分規則

Archiver|手機版|小黑屋|台灣娛樂城合作加盟廠商論壇  

旅行社代辦簽證, 市場調查, 電子遊戲, 鞋工廠, 台灣美食台北美容燈飾照明桃園借錢沙發工廠床墊工廠眼科儀器中醫診所家具品牌創意設計手作烘焙高雄當舖清潔社近視雷射檢查中心日本包車

GMT+8, 2024-11-24 08:18 , Processed in 0.025117 second(s), 5 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回復 返回頂部 返回列表