; =============================================================================== ; tic/tac/toe in x86 assembler by lostcauz ; =============================================================================== ; DaWei said: ; "There have been a few posts regarding Tic-Tac-Toe (Naughts and Crosses). ; Write such a game. Five facets will be judged totally independently: ; ; 1) presentation/user interface ; 2) ability of the computer to win (AI, if you will) ; 3) robustness of the code ; 4) style and clarity ; 5) creativity of approach ; ; Judging will be by poll of the community as a whole. ; ; If you're up for it, deadline is November 1, 2005." ; =============================================================================== ; =============================================================================== ; lostcauz -- notes ; =============================================================================== ; I wrote this stuff down as I thought about the game. ; My thought process can be freaky so continue at your own risk. ; ; Comment the code heavily so everyone can follow the rabbit... ; ; 32 bits- I'll use 18 bits for occupied square positions, 1 game_over_bit, 1 turn_bit ; A=Player ; B=Computer ; topleft ; AB -player A or B's bit will be set when occupied A=2 B=1 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; topcenter ; AB -player A or B's bit will be set when occupied A=8 B=4 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; topright ; AB -player A or B's bit will be set when occupied A=32 B=16 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; centerleft ; AB -player A or B's bit will be set when occupied A=128 B=64 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; center ; AB -player A or B's bit will be set when occupied A=512 B=256 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; centerright ; AB -player A or B's bit will be set when occupied A=2048 B=1024 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; dnleft ; AB -player A or B's bit will be set when occupied A=8192 B=4096 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; dncenter ; AB -player A or B's bit will be set when occupied A=32768 B=16384 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; dnright ; AB -player A or B's bit will be set when occupied A=131072 B=65536 ; ^^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; game_over_bit == 262144 == 40000h ; ^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; turn_bit == 524288 == 80000h (computer==0, player==1) ; ^ ; 0000 0000 0000 0000 0000 0000 0000 0000 ; ; ================================================================================== ; TABLES: ; xxx --- --- x-- -x- --x x-- --x ; --- xxx --- x-- -x- --x -x- -x- ; --- --- xxx x-- -x- --x --x x-- ; ============================================== ; computer 1+4+16=21 00015h ; computer 64+256+1024=1344 00540h ; computer 4096+16384+65536=86016 15000h ; computer 1+64+4096=4161 01041h ; computer 4+256+16384=16644 04104h ; computer 16+1024+65536=66576 10410h ; computer 1+256+65536=65793 10101h ; computer 16+256+4096=4368 01110h ; =============================================== ; player 2+8+32=42 0002Ah ; player 128+512+2048=2688 00A80h ; player 131072+32768+8192=172032 2A000h ; player 2+128+8192=8322 02082h ; player 8+512+32768=33288 08208h ; player 32+2048+131072=133152 20820h ; player 2+512+131072=131586 20202h ; player 32+512+8192=8736 02220h ; ================================================================================================= ; If any of these combinations are true we can win if the open square is unoccupied. ; WINNING BITS 0 AND 1, 0 AND 2, 1 AND 2, 3 AND 4, 3 AND 5, 4 AND 5, 6 AND 7, 6 AND 8, 7 AND 8, ; 0 AND 3, 0 AND 6, 3 AND 6, 1 AND 4, 1 AND 7, 4 AND 7, 2 AND 5, 2 AND 8, 5 AND 8, ; 0 AND 4, 0 AND 8, 4 AND 8, 2 AND 4, 2 AND 6, 4 AND 6 ; ================================================================================================= ; xxx --- --- x-- -x- --x x-- --x ; --- xxx --- x-- -x- --x -x- -x- ; --- --- xxx x-- -x- --x --x x-- ; ================================================================================================= ; move logic: ; is square empty? ; if so can i win here? 'and' with potential_wins for that square ; if not can player win here? 'and' with potential_loss for that square ; if not try next square ; if all squares have been iterated and haven't provoked a move then use a decent sequence, ; strong but beatable, so it's still fun. ; ; Play for the win in square 0 if 0 is available and any of the following combinations are owned by comp: ; 1 and 2, 3 and 6, 4 and 8 ; Play for the win in square 1 if 1 is available and any of the following combinations are owned by comp: ; 0 and 2, 4 and 7 ; Play for the win in square 2 if 2 is available and any of the following combinations are owned by comp: ; 0 and 1, 5 and 8, 4 and 6 ; Play for the win in square 3 if 3 is available and any of the following combinations are owned by comp: ; 4 and 5, 0 and 6 ; Play for the win in square 4 if 4 is available and any of the following combinations are owned by comp: ; 3 and 5, 1 and 7, 0 and 8, 2 and 6 ; Play for the win in square 5 if 5 is available and any of the following combinations are owned by comp: ; 3 and 4, 2 and 8 ; Play for the win in square 6 if 6 is available and any of the following combinations are owned by comp: ; 7 and 8, 0 and 3, 2 and 4 ; Play for the win in square 7 if 7 is available and any of the following combinations are owned by comp: ; 6 and 8, 1 and 4 ; Play for the win in square 8 if 8 is available and any of the following combinations are owned by comp: ; 6 and 7, 2 and 5, 0 and 4 ; ; Play for the block the same as above except combinations are owned by player ; ============================================================================================================ .686 .model flat, stdcall option casemap :none include \masm32\include\windows.inc include \masm32\macros\macros.asm include \masm32\include\masm32.inc include \masm32\include\kernel32.inc include \masm32\include\user32.inc includelib \masm32\lib\user32.lib includelib \masm32\lib\masm32.lib includelib \masm32\lib\kernel32.lib .data ; strings -n- things cmp_win db 'The computer has won.',0Dh,0Ah,0 plr_win db 'The player has won.',0Dh,0Ah,0 itsa_tie db 'You have battled to a tie.',0Dh,0Ah,0 s_about db 0Dh,0Ah,' |== TIC/TAC/TOE in assembler by lostcauz ==|',0 s_format db ' ',0 board_view db '---------',0 two_newlines db 0Dh,0Ah,0Dh,0Ah,0 one_newline db 0Dh,0Ah,0 buffer db 'EEE',0 ; counter num_moves db 0 num_wins db 0h,0h,0h ; dword variables board_state dd 00000000h game_over_bit dd 00040000h turn_bit dd 00080000h ; =============================================== TABLES =================================================== ; win tables represent board states that cause victory cmp_win_table dd 00000015h,00000540h,00001041h,00001110h,00004104h,00010101h,00010410h,00015000h plr_win_table dd 0000002Ah,00000A80h,00002082h,00002220h,00008208h,00020202h,00020820h,0002A000h ; value tables represent squares being occupied comptr_values dd 00000001h,00000004h,00000010h,00000040h,00000100h,00000400h,00001000h,00004000h,00010000h player_values dd 00000002h,00000008h,00000020h,00000080h,00000200h,00000800h,00002000h,00008000h,00020000h ; Artificial Intelligence table (I chose a playable level of difficulty) ai_comp_moves dd 00000014h,00001040h,00010100h,00000028h,00002080h,00020200h dd 00000011h,00004100h,00000022h,00008200h dd 00000005h,00010400h,00001100h,0000000Ah,00020800h,00002200h dd 00000500h,00001001h,00000A00h,00002002h dd 00000440h,00004004h,00010001h,00001010h,00000880h,00008008h,00020002h,00002020h dd 00000140h,00010010h,00000280h,00020020h dd 00014000h,00000041h,00000110h,00028000h,00000082h,00000220h dd 00011000h,00000104h,00022000h,00000208h dd 00005000h,00000410h,00000101h,0000A000h,00000820h,00000202h ; =========================================================================================================== .code start: print addr s_about xor eax,eax ; start new game mov board_state,eax ; clear board_state mov num_moves,al ; clear num_moves game_loop: call get_move ; get next move call show_board ; show board... mov eax,board_state ; load current board state and eax,game_over_bit ; and to see if game is over cmp eax,game_over_bit ; if bit is set, game over jne game_loop ; continue mov eax,sval(input("Press <enter> to continue, any letter first to quit. ")) or eax,eax ; quit? jnz byby ; yep... time ta jet. mov ecx,board_state and ecx,turn_bit cmp ecx,turn_bit jne start xor ecx,ecx ; clear current state of board mov num_moves,cl xor ecx,turn_bit ; toggle turn switch mov board_state,ecx ; save state jmp game_loop ; play it again. byby: exit ; i'm outta here.... ; ============================= get_move ==================================== get_move: mov ecx,board_state ; load current state of board add num_moves,1 ; increment move counter xor ecx,turn_bit ; toggle turn switch mov board_state,ecx ; save state and ecx,turn_bit ; gotta take turns cmp ecx,turn_bit ; ... je cmp_turn ; computer turn jmp plr_turn ; player turn mov_ret: cmp num_moves,9 ; 9 total moves in this game jb @f ; continue playing mov eax,game_over_bit ; 9 moves reached mov ecx,board_state ; load current state and ecx,eax ; see if game_over_bit is set yet cmp ecx,eax ; ... je c_up ; get out, the win came on move 9 add board_state,eax ; set the game_over_bit @@: cmp num_moves,5 ; 5 moves before we need to test for win jb c_up ; just leave call test_win ; better see if there's a winner c_up: ret ; return to caller ; ========================= players turn ================================ plr_turn: print addr two_newlines ; couple newlines @@: xor eax,eax ; zero the register, prolly not necessary mov eax,sval(input("Enter your move 1-9 : ")) or eax,eax ; did the dummy enter '0' anyhow? jz @b ; yep... mov ecx,board_state ; load current state sub eax,1 ; adjust per array cmp eax,8 ; did the waferhead enter > 9? ja @b ; yep... mov ebx,ecx ; need to make sure nobody owns this square and ebx,[player_values+eax*4] ; and board state with table position value cmp ebx,[player_values+eax*4] ; determine if it is set je @b ; player owns the square mov ebx,ecx ; load board state and ebx,[comptr_values+eax*4] ; and with table position value cmp ebx,[comptr_values+eax*4] ; determine if it is set je @b ; computer owns the square add ecx,[player_values+eax*4] ; update state with new move mov board_state,ecx ; save new board state jmp mov_ret ; ======================== computers turn =============================== cmp_turn: print addr two_newlines ; couple newlines mov ebx,-4 ; prepare for loop try_cmp: add ebx,4 ; increment computer value table position mov eax,board_state ; load board state... yawn... and eax,[comptr_values+ebx] ; and state with comptr_values table pointer cmp eax,[comptr_values+ebx] ; test if bit was set je try_cmp ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+ebx] ; and with player value table cmp eax,[player_values+ebx] ; bit set? je try_cmp ; player owns this square ; ========================== AI begins ========================= cmp ebx,0 jne @f mov edx,-4 ; used as index mov ecx,5 ; loop counter jmp cmp_ai @@: cmp ebx,4 jne @f mov edx,010h mov ecx,4 jmp cmp_ai @@: cmp ebx,8 jne @f mov edx,024h mov ecx,6 jmp cmp_ai @@: cmp ebx,12 jne @f mov edx,03Ch mov ecx,4 jmp cmp_ai @@: cmp ebx,16 jne @f mov edx,04Ch mov ecx,8 jmp cmp_ai @@: cmp ebx,20 jne @f mov edx,06Ch mov ecx,4 jmp cmp_ai @@: cmp ebx,24 jne @f mov edx,07Ch mov ecx,6 jmp cmp_ai @@: cmp ebx,28 jne @f mov edx,094h mov ecx,4 jmp cmp_ai ; (final square), try an advantageous sequence here after testing wins/blocks @@: cmp ebx,32 jne @f mov eax,board_state and eax,[ai_comp_moves+0A8h] ; check winning combinations cmp eax,[ai_comp_moves+0A8h] je ai_move mov eax,board_state and eax,[ai_comp_moves+0ACh] cmp eax,[ai_comp_moves+0ACh] je ai_move mov eax,board_state and eax,[ai_comp_moves+0B0h] cmp eax,[ai_comp_moves+0B0h] je ai_move ; blocking code mov eax,board_state ; load board state and eax,[ai_comp_moves+0B4h] cmp eax,[ai_comp_moves+0B4h] ; determine if player is in a '1 move to win' situation je ai_move ; We must block or player can win mov eax,board_state ; ... and eax,[ai_comp_moves+0B8h] cmp eax,[ai_comp_moves+0B8h] je ai_move ; it's set, play the block. mov eax,board_state ; ... and eax,[ai_comp_moves+0BCh] cmp eax,[ai_comp_moves+0BCh] ; hopefully it's not set... je ai_move ; it's set, play the block. jmp m_seq cmp_ai: mov eax,board_state add edx,4 and eax,[ai_comp_moves+edx] ; check winning combinations cmp eax,[ai_comp_moves+edx] je ai_move dec ecx jnz cmp_ai jmp try_cmp m_seq: ; now just make a move in a decent sequence - 4,0,5,6,1,8,3,2,7 mov eax,board_state ; load board state.. and eax,[comptr_values+010h] ; center square cmp eax,[comptr_values+010h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+010h] ; and with player value table cmp eax,[player_values+010h] ; bit set? je @f ; player owns this square mov ebx,010h jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values] ; upper-left square cmp eax,[comptr_values] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values] ; and with player value table cmp eax,[player_values] ; bit set? je @f ; player owns this square xor ebx,ebx jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+014h] ; middle-right square cmp eax,[comptr_values+014h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+014h] ; and with player value table cmp eax,[player_values+014h] ; bit set? je @f ; player owns this square mov ebx,014h jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+018h] ; lower-left square cmp eax,[comptr_values+018h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+018h] ; and with player value table cmp eax,[player_values+018h] ; bit set? je @f ; player owns this square mov ebx,018h jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+04h] ; upper-center square cmp eax,[comptr_values+04h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+04h] ; and with player value table cmp eax,[player_values+04h] ; bit set? je @f ; player owns this square mov ebx,04h jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+020h] ; lower-right square cmp eax,[comptr_values+020h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+020h] cmp eax,[player_values+020h] ; bit set? je @f ; player owns this square mov ebx,020h jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+0Ch] ; middle-left square cmp eax,[comptr_values+0Ch] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+0Ch] cmp eax,[player_values+0Ch] ; bit set? je @f ; player owns this square mov ebx,0Ch jmp ai_move @@: mov eax,board_state ; load board state.. and eax,[comptr_values+08h] ; upper-right square cmp eax,[comptr_values+08h] ; test if bit was set je @f ; computer already owns this square mov eax,board_state ; reload board state and eax,[player_values+08h] cmp eax,[player_values+08h] ; bit set? je @f ; player owns this square mov ebx,08h jmp ai_move @@: mov ebx,01Ch ; lower-left square ai_move: mov eax,board_state add eax,[comptr_values+ebx] ; set the bit mov board_state,eax ; save new board state ;print str$([comptr_values+ebx]) ; debugging... jmp mov_ret ; cruise... ; =============================== test_win ===================================== test_win: push ebx ; preserve registers mov ecx,board_state ; load current state of board xor edx,edx ; counter for table traversal traverse: mov ebx,ecx ; load for manipulation mov eax,ecx ; load for manipulation and ebx,[cmp_win_table+edx] ; and cmp_win_table for computer win and eax,[plr_win_table+edx] ; and plr_win_table for player win cmp ebx,[cmp_win_table+edx] ; test result with cmp_win_table je computa ; equal, computer wins cmp eax,[plr_win_table+edx] ; test result with plr_win_table je playa ; equal, player wins add edx,4 ; increment counter cmp edx,32 jb traverse ; continue and ecx,game_over_bit ; determine if all moves are exhausted cmp ecx,game_over_bit ; ... jne clean ; nope, next move print addr itsa_tie ; must be a tie.. print addr two_newlines ; couple newlines add byte ptr[num_wins+2],1 score: print chr$(" Computer: ") ; print scores xor eax,eax mov al,byte ptr[num_wins] print str$(eax) print chr$(" Player: ") xor eax,eax mov al,byte ptr[num_wins+1] print str$(eax) print chr$(" Ties: ") xor eax,eax mov al,byte ptr[num_wins+2] print str$(eax) clean: print addr one_newline pop ebx ; clean up ret ; return computa: print addr cmp_win ; computer wins print addr two_newlines ; couple newlines mov eax,game_over_bit ; game over add board_state,eax ; update board state add byte ptr[num_wins],1 jmp score ; clean up playa: print addr plr_win ; player wins print addr two_newlines ; couple newlines mov eax,game_over_bit ; game over add board_state,eax ; update board state add byte ptr[num_wins+1],1 jmp score ; =============================== show_board ================================== show_board: push ebx ; preserve registers push esi ; continue housekeeping push edi ; ... mov ecx,board_state ; load current state lea esi,comptr_values ; address computer values lea edi,player_values ; address player values xor ebx,ebx ; counter for table traversal sub esi,4 ; prepare fer computer_value table cipherin' sub edi,4 ; prepare fer player_value table cipherin' l1: mov eax,ecx ; load board state for testing add esi,4 ; update pointer to computer values table mov edx,ecx ; load board state for testing against player add edi,4 ; update pointer to player values table and eax,[esi] ; computer == 'O' and edx,[edi] ; player == 'X' cmp eax,[esi] ; computer owns the square je c_square ; ... cmp edx,[edi] ; player owns the square je p_square ; ... mov byte ptr[board_view+ebx],'-' ; unoccupied square pr_ret: add ebx,1 ; increment base index for board_view cmp ebx,9 ; last one? jnz l1 ; continue print addr one_newline ; newline lea edi,buffer ; buffer helps break down board_view for print lea esi,board_view ; load effective address board_view mov ax,[esi] ; load first word stosw ; store word mov al,[esi+2] ; load next byte stosb ; store byte print addr s_format ; formatting print addr buffer ; print 1 word and 1 byte print addr one_newline ; newline lea edi,buffer ; reload buffer mov ax,[esi+3] ; load word stosw ; store word mov al,[esi+5] ; load byte stosb ; store byte print addr s_format ; formatting print addr buffer ; print the 3 characters in buffer print addr one_newline ; newline lea edi,buffer ; reload mov ax,[esi+6] ; load word stosw ; store it mov al,[esi+8] ; load byte stosb ; store byte print addr s_format ; formatting print addr buffer ; print 3 characters print addr one_newline ; newline pop edi ; sweep... pop esi ; mop... pop ebx ; and wax... ret ; return to caller p_square: mov byte ptr[board_view+ebx],'X' ; set players square jmp pr_ret ; return c_square: mov byte ptr[board_view+ebx],'O' ; set computers square jmp pr_ret ; return end start
This was written and tested on Win XP sp2. If you prefer, you may download ttt3.exe ~5k. If you would like to assemble the code yourself and you have the MASM32 package installed, simply open it in QEDITOR and choose 'Project - Console Assemble & Link' from the Menu.