中國象棋的走法是有限的嗎？如果有限，有沒有先走或者後走的人必贏的可能？
先說結論。
中國象棋的走法是有限的嗎？是有限的。關於重複走棋，百度了一下中國象棋比賽規則，其中有：雙方走棋出現循環反覆已達三次，符合棋例中不變作和的有關規定，可由任何一方提議作和，經審查局面屬實，即使另一方不同意，裁判員也有權判為和棋。如雙方都沒有提和，而循環反覆局面還在延續，裁判員有權不徵得雙方同意就決定判和。
所以重複三次之後就判和局了，不能無限走下去。
感謝板藍根在評論中補充又查了一下，應該是這一條保證了中國象棋是有限步數的： 4.2.4、符合自然限著的回合規定，即在連續60個回合中（也可根據比賽等級酌減），雙方都沒有吃過一個棋子。
所以至少過60回合就少一個棋子，所以比賽是有限的。
如果有限，有沒有先走或者後走的人必贏的可能？
中國象棋，要不就是一個先走的人必贏的遊戲，要不就是一個後走的人必贏的遊戲，要不就是一個先走的人必不輸的遊戲。不單是中國象棋，絕大部分棋類都是上述情況。只是我們不知道它究竟是哪一種，也不知道必贏/必不輸的走法是什麼。-----------------下面引出理論-----------------Zermelo"s theorem (game theory) 這是維基
策梅洛定理_百度百科 這是百科
任意棋類，如果符合以下條件：
- 在有限的步數內會結束
- 這是一個完全信息博弈
- 結局可能是玩家甲獲勝、玩家乙獲勝、平局中的三種或兩種
那麼它必然是以下情況中的一種：
- 先手必勝
- 先手必平
- 後手必勝
在有限步數內會結束，這很好懂，剛也說了中國象棋符合。
完全信息博弈，大概是說輪到博弈中的一方行動時，他掌握這之前的所有信息，清楚之前發生了什麼。我猜測這條就把飛行棋這種涉及運氣的棋類排除在外了。結局可能是玩家甲獲勝、玩家乙獲勝、平局中的三種或兩種。像中國象棋就是三種都有可能，一些其他棋類沒有平局的就只有兩種。所以中國象棋是有必贏/必不輸策略的。五子棋也有，圍棋也有，國際象棋也有，井字過三關也有。由於井字過三關步數很少，窮舉完我們知道這是先手必不輸，其他棋類就無法窮舉了。ps：題外話，玩了這麼多年井字過三關，一直都是第一步就下中間的格子，直到後來我看到這篇文章：井字棋的最優策略竟是先佔角！-----------------------------------------------------------------
這樣看上去神一樣的理論居然用了很簡單的方法證明-----------------------------------------------------------------建議把這集公開課看了，你就懂怎麼回事了。耶魯大學公開課：博弈論對於那些蹲在茅坑拿客戶端刷知乎看不了視頻的，我心情好所以嘗試著寫一下，希望你們能看懂。
推導過程：
使用數學歸納法假設這種棋在第n步結束。
n=1時，甲先手，甲下了一步之後遊戲結束。
這裡假設甲這一步有5個選擇（其實多少個選擇都一樣，先用5個來舉例）情況一：分支一---勝分支二---平分支三---勝分支四---負分之五---平那甲會選擇走一或四，此時甲勝，屬於先手必勝。情況二：分支一---平
分支二---負分支三---平分支四---負分之五---負那甲選擇走一或三，此時平局，屬於先手必平。情況三：分支一---負分支二---負分支三---負分支四---負
分支五---負那甲一到五都可以走，此時乙勝，屬於後手必勝。其他情況類似。所以，n=1時，結局必為先手必勝、先手必平、後手必勝中的一種，成立。
假設時，結論成立。
當時，相當於甲走一步之後，甲乙走了剩下的p步。而p步的結果必為先手必勝、先手必平、後手必勝中的一種。
分支四---後手必勝
分支五---先手必平所以，當結論是：
1. 走法是有限的。
2. 理論上存在策略，先走的一方可以獲勝、或者逼和、或者必負。但是計算機算不出這個策略，因為太複雜了。
如果看官有興趣，可以看如下細節：
Zermelo"s theorem (game theory)
這個定理保證了，在完全信息下，有限狀態的博弈一定存在最優策略。Solved game
這裡講了一些常見的遊戲是否被解決，如果部分解決，解決的程度是怎麼樣的。Solving chess
這個主要是國際象棋的進展，畢竟在西方這是最流行的棋類。在Solved game中的引用部分，有一篇paper，是Searching For Solutions。這裡詳細介紹了棋牌類遊戲的理論分析，和各個棋牌遊戲的案例分析，其中包括狀態複雜度和遊戲樹複雜度（見下圖）。目前的主要結果是：1. 最難解的遊戲是圍棋（Go），沒有之一。2. 中國人關心的中國象棋、國際象棋、圍棋都沒有解決。3. 國際象棋的最好的進展是7個子的殘局。Endgame tablebase。感謝 @李旭昇。4. 目前已解決的最難的問題是國際跳棋（checker），其狀態複雜度為10^21，於2007年解決，結論是雙方和棋。
Strategy-stealing argument
Zugzwang
耶魯大學公開課：博弈論24集全免費高速下載-360雲盤分享_______________________________________________________________________2013.12.28 補充九井棋（Tic-Tac-Ku）的狀態複雜度和遊戲樹複雜度是多少？12.26日更新：中國象棋的走法是有限的，但是原因不是@Selbyyy的答案中提到的「循環三次」的原因。因為這裡的循環三次，如果按照規則的理解，應該是走了三個「循環節」（而且如果雙方都不提和並且在之後的走法中出現變著也是可以不和的），而不是「出現三次相同局面」。局面是有限的，但是單純繞開無限的「循環節」是可以的。一個簡單的構造性方法，把除了兵/卒以外的子按0～9編號（剩一個不管了），拿一個無理數來（pi吧），然後按小數位往後數，數字是幾就走幾號棋子，下一步收回。對手鏡像走法。因為無理數不存在無限循環節，所以這種走法也不存在無限循環節。但是現實下棋是比賽，不是為了驗證這個方法，所以現實中不會出現這種滑稽的場面！再一個但是，實際上中國象棋還有一個「六十回合規則」， 簡單來說就是連續60個回合如果沒有子被吃則判和。這會導致局面上的子力每60步必然會至少減1。 棋子個數有限所以最多肯定在有限步里結束。這才是中國象棋走法有限的真正原因。這裡是我找到的中國象棋關於 和棋 的規則：(一)屬於理論上公認的雙方均無取勝可能的局勢;
(二)提議作和,應使雙方機會均等。先得出者如被對方拒絕(口頭不同意,或走出輪走的一著棋,均為拒絕),非經對方提和一次(也被拒絕),不得再度提出,但下列(三)(四)兩款屬於提和的特殊規定,不受此限。若雙方提和次數對等,即可由任何一方再次提和。提和的一方,在對方作出明確表示之前,不能撤回自己的
提議。只要是一方提和,另一方已宣告同意,雙方都不許反悔。此外,只能在提和後,方可按動對方的計時鐘。(三)雙方走棋出現循環反覆已達三次,符合"棋例"中"不變作和"的有關規定,可由任何一方提議作和,經審查局面屬實,即使另一方不同意,裁判員也有權判為和棋。如雙方都沒有提和,而循環反覆局面還在延續,裁判員有權不徵得雙方同意就決定判和;但如所走著法已同上述循環反覆局面無關時,則不能按照本款處理。(四)符合"六十回合規則"(也稱為自然限著)的規定時。另外 井字先佔角 是用來騙不會或者不太懂的人的，而不是占角必勝。如果雙方都懂井子棋的不敗走法你占角佔中心都是一樣的。******************************12.16之前的答案***************************************************中國象棋的走法是無限（此處更新為有限，原因在12.26更新答案中說明了）的。舉個例子， 開局，雙方各有2個車的情況下，雙方都選擇其中一個走一步，然後下一步退回。因此當雙方進行2n個回合後，當前局面依然是開局局面，但是步法是2^n種。這個n顯然可以到無窮大。也就是說至少存在一種情況使得一局棋永遠下不玩且每一步永遠有多於1種選擇的走法。所以是無限的。一個更新：有人提到說規則不允許出現連續三次相同局面。但是其實考慮雙方配合，可以輕易繞開這個規則。比賽時候因為雙方並不是為了「配合求和」， 而是 對抗 ，所以你不會在比賽的時候看到這樣滑稽的局面發生。但是顯然一般人下棋也幾乎不會使用到上述方法（殘局逼和也有可能）。與其討論走法，其實更有意義的應該是具體棋局狀況。考慮到局面狀況，則是有限的。因為棋子數有限，棋盤的格子數有限，因此可能達到的狀態數肯定有限。但是這個數量十分巨大。對於先手或後手必勝的情況， 不一定存在。因為還有一種局面叫 和棋。但是 先手或後手 必不敗 的情況（即接受平局和勝利）， 那肯定存在。一個不太嚴謹的存在性證明如下： （涉及一點圖論， 語言可以進一步補充使得嚴謹）一個重要的前提是下中國象棋是嚴格輪流走（即不會出現黑白棋可能存在一方無處可走時另一方連續下子）。假設是A和B下棋，A先走，兩人均理性。把所有局面（當前棋盤狀況 + 是否輪到A走）當作點，若當前局面能通過一步轉化到另一個局面則連上一條有向邊。由於局面情況數有限，因此整張圖有限（但十分非常及其巨大）。由於最早的討論情況，所以可能存在幾步能循環局面。有些局面是當前選手必輸局面（例如被將死），有一些是必勝（例如將死了別人），有一些是和棋。對於輪到A走的局面，那麼必然會希望用一步子找一個新的局面， 使得新的局面（輪到B走）怎麼走都不可能贏。如果找到，那麼A一定不會輸了（還可能和）。如果找不到，那麼A已經不可能勝利了，所以這個是B必不敗局面。類似是輪到B走的局面。當然還有陷入循環的情況，那麼也可以認為是和棋。（如果A找不到必勝策略顯然會試圖求和）所以每一個可能的局面都必然會分配到一個 A必不敗 或者 B必不敗。 所以存在先手或後手必不敗局面。但是實際上，由於局面可能性過大。人類沒有那麼輕易能遍歷所有的情況的，所以究竟是先手還是後手必不敗應該還沒有定論。所以還是可以下棋（國際象棋類似）的。@Selbyyy的結論是正確的：
那麼它必然是以下情況中的一種：
- 先手必勝
- 先手必平
- 後手必勝
其中「後手必勝」等價於「先手必負」
所以，結論可以這樣寫：中國象棋，先手要麼必勝、要麼必平、要麼必負但具體是哪一種，無法得出結論。下面用決策樹證明這個結論（其實就是證明策梅洛定理）（回家繼續寫）走法應該是有限的，不過沒有仔細計算過，太複雜了。因為十六個子，第一步可以走任何一個子，意思是紅方走第一步就有三十二種走法。而黑方第一步也可以走十六個子其中的一步。況且一局棋有的時候走雙方都有很多選擇，每一種選擇後面又跟著無數種選擇。所以恐怕沒有定式說先走後走的人必勝必輸之類的，只有看下棋人的水平而已。
走法是有限的，其它知友已然講清楚了，並且確實存在必勝策略。
那麼為什麼找不出來呢？
粗略估計雙方每手大約各有50種策略（平均，至少數量級沒錯）。假定30手就決勝負，那就差不多是10的45次方的策略集，在這麼龐大的策略集里求均衡，即便藉助計算機，一般肯定也是搞不定的了。。。個人不懂象棋只懂博弈，不妥之處還請斧正。第一個問題：
象棋的走法是有限的，因為棋盤上的格子和棋子數量都是確定的，那麼棋子擺在棋盤上形成的狀態數也是有限的。那麼棋子走啊走，總歸會回到一個已知狀態或者結束。第二個問題：
有這個可能，但是目前應該還無法計算出來。棋盤上的狀態數目實在太多了，理論上達到(45*2*16*2)!的數量級，這個數字的十進位表示法有8711位（實際應該沒有這麼多狀態，因為有些棋子有些地方不能去）。從任何一種狀態出發，搜索到結束狀態的路徑是有可能的，這個搜索過程的複雜度應該和推銷員問題是相似的，計算量和節點呈指數關係，節點數量本身就是天文數字了，搜索路徑的計算量可想而知，是目前的計算機絕對無法承受的。====================================正好看到《奇思秒想-15位計算機天才及其重大發現》的第9章，講NP完全問題發現者的，摘一段：有些問題在原則上可以通過演算法解決，但實際中卻不行，因為等到太陽系毀滅也不會算完。
這類問題有個名字，叫NP完全問題。
問題有一些簡單，因此按我自己理解來回答：
中國象棋先走略佔優，即紅方領先一步。在雙方是大師級的水平，大約先走有55%的勝率。 象棋中術語先手，一是指紅方先走，但更主要是在棋勢的先手是指主動權的意思，即我走一步，對手往往被動應招。 因此在象棋各種布局中，紅方會盡量讓先手的優勢保持下去，直到勝利，而後走的黑方盡量把主動權爭奪過來，如果成功，稱為「反先」，當然在普通人一局棋中，常見是雙方互走軟招，造成交替反先出現。 所以在全國個人賽中，先手勝同後手勝、先手和後手和，得分都是不一樣的。那在理論上雙方是大師級水平，這種紅先走的優勢是否能確保勝利呢？ 答案是否定的，有人測算先走的優勢值一個士，如果後手不想贏的情況下，在不出任何錯情況進行大量兌子，棋局往往容易成和棋。 這也造成象棋正規比賽中大量出現和棋出現。
這也是我對象棋現狀不滿的原因之一1走法有限: 因為棋子和棋盤格數有限，所以其組合(狀態)有限
2因為狀態有限，所以所有走法構成一棵確定的有限高的樹。先走的一方能看到所有可能情況，理論上能做出最優選擇，即能贏則不平，能平則不輸
與殘局的聯繫：殘局給定了條件，是所有走法對應的樹中的一棵子樹；但樹的大小相對來說是人腦能夠處理的(得除去明顯沒有意義的走法)，即使這樣也足夠複雜。
除了大之外，這棵「樹」還足夠複雜。比如殘局，路邊經常有玩殘局賭錢的，而且隨便玩家挑先手還是後手。每走一步相當於進入樹的下一層，也就是說，每一棵子樹都是 勝負平 三者的複雜交織體，只要考慮不全面，就有可能會是不同的結果。設想一棵樹有100棵子樹，你能看到98棵子樹都是自己獲勝，但遺漏了兩個對方的妙招(輸棋的兩棵子樹)，結果就完全變了。
ps：我不清楚怎麼定義樹的複雜，也沒見過相關的數學定義，憑感覺描述了下「樹的複雜性」。先說結論：要看你在哪兒玩。如果是在聯眾世界，就不一定是有限的。
這是本人今天上午在聯眾玩出的對局截圖和棋譜。
NP問題，計算理論的入門級課程，事實上出最簡單的題目你都做不出來。比如背包問題：給200個包，每個包重量不一樣，價格不一樣，給出一個大容器限載1000KG，需要給出方案放入容器的包價格最大，前提是不超載。窮舉法是失敗的，演算法強度是自然數200次方 ，而象棋的所有變化強度遠超以上題目，用窮舉法計算，幾百億年都算不出。
先手不負是有的，必勝是沒有的。
是有限的。而且即使無限，也可能存在必勝方法。
步數是有限的毋庸置疑，只要給出規定的活動空間、活動方式、活動載體的數量，沒有無線復活這種可能，步數自然是有限的。先手為和，這倒不一定。
有，現在計算機基於0和1兩種狀態，計算能力加強只能通過開關無限小化，怎麼理解呢比如一個14納米CPU，就是CPU里有無數個0和1狀態的開關，而14納米意思就是每個開關只有14納米。所以基於這種原理，現代計算機在解高次冪和破解RSA加密都是很吃力的。我記得美國禁止出口包含RSA加密超過1024位機器出口。想了美國政府應該是可以解決RSA1024位以下加密破解的難題了，好像本拉登就是郵件被破解然後定位的。但是呢，如果有了量子計算機，這些都不是問題了，因為他有無數的狀態，所以呢，管你多少次冪多少位的分分鐘給你解出來。如果說深藍一秒鐘算200000步。那麼量子計算機就算是用窮舉法分分鐘就能把圍棋所有的走法算完！打個形象的比如，當代計算機相當於普通的土豪，給一個支票，10的x次冪 x 小於1024隨便寫。 而量子計算機呢。給你張支票，x的n次冪隨便寫！！！！！！但是呢悲劇的是，估計我們有生之年都看不到能應用的量子計算機了。
若不考慮「連續三步循環或者六十步不吃子」的判罰，並且對弈雙方沒有以下贏對方為目的的最優策略，當純從下棋走棋的可能性來說，是無限的。當然這個無限僅僅對研究計算極限有點意義。加上上述兩個限制條件，肯定有限了，不過目前貌似計算機還不能窮盡
至今沒有， 也許是人的大腦和計算機水平還達不到一種計算水平
我想知道的是，那個下國際象棋的超級計算機（李開復那個）自己跟自己下棋會是什麼情況。全是和局？還是有先走優勢？ @李開復
這麼搞確實能搞出必贏的走法，但是世界上所有計算機一起算幾年估計也算不出來，人下的這麼點次數根本不夠看
先手總能找到一種走法，不會輸
我來試著回答吧。難得在知乎看到我可以攪和下的問題。
本人身份，純粹文盲，棋的話只是略懂。第一個問題。從理論上說，走法必然是有限的。因為棋盤上走完一步以後，分支下法其實也就那麼多種，隨著棋局進程的慢慢進行，可以選擇下一步的可能選項的數量，既可能增多也可能減少，但這樣的分支，永遠是有限的。走法有限，這是毫無懸念的結論。
當然在分支裡面，會出現循環局面，前面有人說過了，按照棋規，是可以直接判決棋局結束的，結果是紅勝，和棋，黑勝都有可能。而且還涉及「自然限著」問題，即60回合未吃子，棋局自然結束。這裡就不多說了。
第二個問題。是否存在必勝和必和的策略？
如果單純從現實的角度上說，天知道。首先，客觀事實就是從來沒有先走一方必勝或者後走一定能和的策略一說，不然我們就不會看到三種棋局結果了。有所謂的「棋高一著，縛手縛腳」一說，也就是說對方水平哪怕比你高出一點，這盤棋要下起來，水平弱的一方下得總會有夠痛苦（雙方正常發揮的前提下）。象棋存在所謂的「和棋定式」。「和棋定式」一般用於先走的一方水平比後走的一方弱，想簡單謀求一盤和棋，或者是先走的一方在積分編排制的比賽中，處於比賽策略，通過先走一步的優勢把盤面往「和棋定式」的路子上引。一般而言，後走的一方會比較樂意接受，畢竟後走方吃點虧是事實，能拿後手簡單謀求一盤和棋，往往可以滿意。於是雙方默契地往一個固定的盤面走。並且在這樣的盤面下，後走的一方想求勝，不按「和棋定式」走的話，有可能被對方佔據盤面優勢，有時候也只好跟著走，接受和棋。
但「和棋定式」存在並不說明先走一方在現實中等於找到了「必和策略」。後走的一方如果要求勝，總不會讓你安心過渡到你想要的和棋盤面，他會選擇其他各種變化保持盤面的複雜性，如果雙方水平差距偏大，水平低的那方大多要掛，根本沒有必和策略一說。哪怕雙方水平相近，結果都很難說。
以上一堆羅嗦，是為了說明在當今的中國象棋界，並不存在先走的一方必勝或者必和的策略，歸根結底還是要看水平和狀態。那對於吃虧的後手方，就不用說了。
從理論上說，先走一方必佔便宜。常識判斷也必然如此，但不知道另外一個角度論述是否正確：
對於象棋，對局雙方的目的，是要將棋局導入最終的最不平衡的結果—吃掉對方的將（帥），以獲得勝利。先走的一方在絕對平衡的局面下，獲得了首先打破平衡的權利。因此，先行一方佔據優勢。」但打破平衡當然不意味著這優勢足夠保證棋局的必勝。如果先走的一方走什麼，後走一方都跟著走，那麼先走方的優勢，當然一直保留著。走到同時抓吃對方的將（帥）的時候，先走的一方直接就吃掉對方的將，棋局就結束了。所以後走的一方不可能一直跟著走，後走的一方早晚要選擇和先走一方不同的棋步，以削弱先走一方多出來那一步棋的優勢。在這種爭鬥過程中，如果雙方走得正確，一般情況下的結論會是「紅方稍先，雙方基本均勢」，也就是說紅方好一點點，但完全達不到必勝。
突然想到了矛和盾。利矛與堅盾。如果矛不夠鋒利，進攻方繼續打磨，如果盾不夠堅固，防守方改換材質，雙方在鬥爭中不斷發展，但總沒有證明矛必勝盾或者盾必勝矛的一天。
不知道我以上一堆廢話，說清楚現實情況沒有。
理論上的事情，我覺得不好說。我傾向於沒有必贏的可能，但存在必和的可能。因為棋局走向必贏，是要把棋局引向【絕對的不平衡】，把不平衡的盤面最大化。但先走一步的優勢，我覺得做不到這一點。如果先走方先走兩步的話，也許可以？因為我記得在關於職業棋手的比賽中出現過一句類似的話，大意是「一步進炮打馬等於白讓銀川兩先，這棋還怎麼下？」也就是說在全國冠軍級別的頂尖高手的較量當中，如果一方有兩先（即先走兩步棋）的優勢，這棋就沒法下了（這裡的兩先，指的還是先走兩步棋，但不能有子過河的那種兩先，而不是隨便你走啥的兩先）。
而忘記了哪個棋手說的，」聯賽想贏一盤棋就像過年一樣「。聯賽，指的全國象棋甲級聯賽，是中國象棋界最高水平的比賽，參賽棋手代表了中國象棋的最頂尖水平。看下裡面的數據統計，一大票一大票的和棋。這數據是有含金量的，我認為已經很充分檢驗了先走一步的效率不足以保證棋局的絕對勝利，但從先走方勝率高於後走方來看，先走一步，肯定對取勝有利。
我覺得我的回答很沒邏輯，希望可以勉強算是個回答。先手能必和，當年趙鑫鑫第一次奪冠時就是因為背和譜下默契棋，被查作弊，還受了懲罰。
推薦閱讀：
※中國象棋雙方的棋子為什麼寫法不一樣？
※中國象棋「一車換雙」是否合算？其中兌換雙炮、雙馬、馬炮哪個更合算？
※下象棋時，怎樣克服隨手棋？
※如何短時間內提高自己的中國象棋水平？