% March 20th 2008 % Written by PRBaldwin %% % Part 1. Create Possible Board Configurations % Part 2. Create a Matrix showing the connectivity of the game % Part 3. Create Connection Arry JStartEnd % Part 4. Play the Game % Part 1. % Given NimStart % set up an array Nim % which is a cell labelled by two entries % The first entry gives 1+ number of elements that % have been removed from NimStart % The second entry labels an ordered vector of numbers % that are characterized by the first entry. % % Nim is a series of cells % Nim{j} is a list of the board configurations where (j-1) % elements have been removed % % Nim{j}{k} is the kth board positon of the above % % NimColumn has all the board positions arranged as a single % cell: NimColumn{2} is the second board config % % ssNim= total number of elements in NimStart % % NumStates is the total number of elements in Nim % including the empty vector % sNimVec(j) is the number of states in each Nim{j} % sNimSumVec(j) is partial sums of sNimVec clear Nim NimStart =[3 4 5]; Nim{1}{1}= NimStart; ssNim= sum(NimStart); for jRemove=1:ssNim % This indexes cells; how many have been removed sNim=length(Nim{jRemove}); % number for jj=1:sNim % Take a Nim from the previous layer NimNow= Nim{jRemove}{jj}; sNimNow = length(NimNow); for js=1:sNimNow % Remove an element from the js index NimNextjs= NimNow; NimNextjs(js) = NimNextjs(js)-1; if NimNextjs(js)==0 NimNextjs(js)=[]; end NimNextjs = sort(NimNextjs); [jRemove, jj,js] ; NimNextjs; sNimNextjs= length(NimNextjs); % Check whether to put this string array into Nim Found=0; if ((jj==1) & (js==1)) % if you try the very firsttime Nim{jRemove+1}{1} = NimNextjs; Found=1; else Found=0; CurrentNimS= Nim{jRemove+1}; sCurrentNimS= length(CurrentNimS); for jT=1:sCurrentNimS Nim2Check = CurrentNimS{jT}; sNim2Check= length(Nim2Check); if (sNimNextjs==sNim2Check) if all(NimNextjs == Nim2Check) Found=1; end end % sCurrentNimS== sNim2Check end % jT =1:sCurrentNimS if Found==0 Nim{jRemove+1}{sCurrentNimS+1}= NimNextjs; end end % if js ~=1 end end end clear sNimSumVec sNimVec Count=1; % include NimStart sNimVec(1)=1; sNimSumVec(1)=1; NimColumn{1}= NimStart; for jRemove=1:ssNim % This indexes cells; how many have been removed sNim=length(Nim{jRemove+1}); % number at each level Count=Count+sNim; sNimVec(jRemove+1)=sNim; sNimSumVec(jRemove+1)=Count; for js=1:sNim NimColumn{Count-sNim+js}= Nim{jRemove+1}{js}; end end NumStates=Count % Cleanup clear jj jRemove js jT Found Count sCurrentNimS CurrentNimS NimNow Nim2Check NimNextjs sNim sNim2Check sNimNextjs sNimNow %% %Part 2. % Given an array Nim (See above in Part 1) of NimColumn % ssNim= total number of elements in NimStart % % NumStates is the total number of elements in Nim including the empty vector % % Create a matrix of % Interactions which states which states are connected to % which % Which is connected to which % Label States Interactions=zeros(NumStates); for jRemove=1:ssNim % This indexes cells; how many have been removed sNim=length(Nim{jRemove}); % number at each level for jj=1:sNim NimNow= Nim{jRemove}{jj}; NimNowNumber = sNimSumVec(jRemove)-sNim+jj; sNimNow = length(NimNow); for js=1:sNimNow % Pick the js index of NimNow for jsp=1:NimNow(js) % from which to remove elements NimNextjs= NimNow; NimNextjs(js) = NimNextjs(js)-jsp; if NimNextjs(js)==0 NimNextjs(js)=[]; end NimNextjs = sort(NimNextjs); sNimNextjs= length(NimNextjs); Found=0; jRemoveB=jRemove+jsp-1; CurrentNimS= Nim{jRemoveB+1}; sCurrentNimS= length(CurrentNimS); jT=0; while ( (jT0 Nim2CheckNumbers = sNimSumVec(jRemoveB+1)-sCurrentNimS+jT; else Nim2CheckNumbers= NumStates; end if (sNimNextjs==sNim2Check) if all(NimNextjs == Nim2Check) Found=1; [Nim2Check]; [Nim2CheckNumbers, sNim2Check,jT]; MatchIndex=Nim2CheckNumbers; Interactions(NimNowNumber,MatchIndex)=1; end end % sCurrentNimS== sNim2Check end % jT =1:sCurrentNimS end % jsp end % js end % end clear jj jRemove jRemoveB js jsp jT Found MatchIndex Nim2CheckNumbers CurrentNimS sCurrentNimS NimNow sNimNow Nim2Check NimNextjs sNimNextjs NimVec clear sNim2Check sNim NimNowNumber % Put connections into a matrix %% % Part 3 Create Connection Array JStartEnd and JEndStart from % Interactions matrix [JStart,JEnd]= find(Interactions==1); [JStartIX,IX] = sort(JStart); JEndIX= JEnd(IX); JStartEnd= ([JStartIX,JEndIX]); [JEndIY,IY] = sort(JEnd); JStartIY= JStart(IY); JEndStart = ([JStartIY,JEndIY]); clear JStart JStartIX JStartIY JEnd JEndIX JEndIY IX IY save NimNow.mat %% Aside % The Connection table is stored in JStartEnd % for NimStart =[1 2 3]; % These connections should exist but have approx equal probs of being chosen % [1,2; 1,3; 1,4; 1,5;1,7;1,9; % % 6,9; 6,11; % 10,12; % % 1,6 and 10 and 13 are losing positions % % These connections should strengthen % 2,6; 4,6; % 3,10; 7,10; % 5,13; 8,13; 9,13; 11,13; 12,13;] %% Part 4 % Play The Game NumRounds2Play=40000; sJStartEnd= length(JStartEnd); Qas=2*( rand(sJStartEnd,1)-.5); % Between -1 and 1 % Has as many entries as there are possible % moves Qas=[Qas,ones(sJStartEnd,1)]; % Keep track of the number of updates for NumRound=1:NumRounds2Play clear MoveVec if round(NumRound/100)*100==NumRound, NumRound, end CountMoves=1; MoveVec(1)=1; % This is the index for the initial board position CurrentBoardPosition=1; NimColumn{CurrentBoardPosition}; GameOver=0; while (~GameOver) % keep playing while the game is not over CountMoves=CountMoves+1; [NewBoardPosition,GameOver] =PlayNim(CurrentBoardPosition,JStartEnd,Qas); MoveVec(CountMoves)=NewBoardPosition; NimColumn{NewBoardPosition}; CurrentBoardPosition= NewBoardPosition; end NewQas=UpdateQ(JStartEnd,Qas,MoveVec); Qas=NewQas; end clear MoveVec CurrentBoardPosition %% Part 5 % Summarize vv= [JStartEnd,Qas]; % This summarizes the entire play jvv= find(vv(:,3)>.3) vvGoodMoves= vv(jvv,1:2) for jj=1:(NumStates-1) jww= find(jj==vvGoodMoves(:,1)); if length(jww)==0 display(strcat('Board ',num2str(jj), ' is a losing Position' )) ; NimColumn{jj} end end clear jj jww jvv open vv