% -------------------------------------------------------------- % tic_game_space.erl % -------------------------------------------------------------- % % Erlang module to explore the tic-tac-toe game space. % You can use this to explore the entire tic-tac-toe game % space. % % This lets you reduce the game space by treating all % reflected and rotated boards as equal. % Another way to reduce the size of the game space is to % describe boards using wildcards. If you were designing % a simple tic-tac-toe playing machine (maybe in hardware) % you should consider this approach instead of the rotation % and reflection method of reducing the game space. -module( tic_game_space ). % Usage examples: % tic_game_space:report3( ). % tic_game_space:report3( summary). % tic_game_space:report3( ply_overview). % tic_game_space:report3( 5). -export([ report0/0, report1/0, report2/0, report3/0, report4/0, report5/0, report6/0, report7/0, report8/0, report9/0, report0/1, report1/1, report2/1, report3/1, report4/1, report5/1, report6/1, report7/1, report8/1, report9/1 ]). -compile( nowarn_unused_function ). -author( "Neal Binnendyk" ). -copyright( "Copyright (c) 2009 Neal Binnendyk, Ixacta Inc" ). % -------------------------------------------------------------- % no_rotation_relection_collapse % % This reduces the game space by treating all reflected and % rotated boards as equal. You can easily get rid of this % simplifying feature however, by re-defining % get_canonical_board(..). % % Define no_rotation_relection_collapse if you do not want to % treat all board rotations/reflects as equal. % % From the shell you can say: % 1> c( 'c:/erlang/tic_game_space', % {d, no_rotation_relection_collapse}). % % Or you can define the macro here: % -define( no_rotation_relection_collapse, 1 ). % -------------------------------------------------------------- % Exported reporting functions % -------------------------------------------------------------- % % Here are a few reporting functions for describing parts of % the tic-tac-toe game space. You can use these as a starting % place for writing your own reports. % % These are meant to provide an overview of the tic-tac-toe % game-space, and also let you examine boards in the space. % % These functions take zero or one argument. When called with % no arguments these functions report on general facts about % a game space. An arguement (interpreted as a ply_index) % changes it so the report is about the boards in a ply. % % report6( ) - reports on game-space 6 % report6( 5) - report on the boards at ply 5, game-space 6 % % Improvements? % Generate code (in C? Javascript?) to match boards and play % the game of tic-tac-toe. % % Generate HTML tables for its reports. % Generate XML. % % Put everything under one function. It asks for user input, % you specify what kind of game space you want and what % report you want and how you want to present the report. % % A graphics user interface. % A web interface. % Start by letting the user choose options. % The first option is "Do you want to treat all board % reflections and rotations as equal?" % % Starting with the full game space, let the user filter % out moves. For example you might want to filter out all % dumb moves in ply 5. % The user can keep filtering out moves to carve out any % game space. % % Let the user craft patterns (wildcards) to simplify the % logic behind move choices. % % If we're exploring another game (not tic-tac-toe) with % a large game space, we could let the user evaluate % specific moves and plys to see where they lead. % The code does not have to generate an entire game space. % We only do that because this game space is small. % % Bigger boards? More dimensions? % Other turn-based games? % Other turn-based simulations. Like a sim or a life game. % -------------------------------------------------------------- % Report on the full tic-tac-toe game space. % % The full game space encompasses every possible tic-tac-toe % game, even ones with very perverse sequences of moves. The % moves just have to be legal, with player 1 and player 2 % taking turns. Games do not continue after a player wins with % 3 in-a-row. % % Usage: % report0( ) same as report0( summary) % report0( summary) report summary of game space % report0( ply_overview) describe each of the plys % report0( Ply_index) describe the boards in one ply % Ply_index is integer 0-9 % % Game space: % Player 1: all moves % Player 2: all moves report0( ) -> report0( summary ). report0( Instruction ) -> write_line( "Full tic-tac-toe game space:"), write_line( " Player 1: all moves"), write_line( " Player 2: all moves"), Full_game_space = full_game_space( ), report_game_space( Instruction, Full_game_space). % -------------------------------------------------------------- % Report on the game space where neither player makes mistakes. % % This is a subset of the full game space. % This is the intersection of the "smart 1st player" and % "smart 2nd player" game spaces described below. % % This shows the part of the tic-tac-toe game space that you'd % normally see, assuming you and the other player know how to % avoid losing. All game paths lead to tie games. % % This does not show all possible tie games. It is possible to % make a mistake and let the other player get into a winning % situation, and then for the other player to also make a % mistake so you can get back to a tie. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 1: all smart moves % Player 2: all smart moves report1( ) -> report1( summary ). report1( Instruction ) -> write_line( "Smart tic-tac-toe game space:"), write_line( " Player 1: all smart moves"), write_line( " Player 2: all smart moves"), Full_game_space = full_game_space( ), Smart_game_space = smart_game_space( Full_game_space), report_game_space( Instruction, Smart_game_space). % -------------------------------------------------------------- % Report on game space where the 1st player never makes a % mistake. % % This is a subset of the full game space, and a superset of % of the "smart game space" where neither player makes any % mistakes. % % Player 1 never loses in this game space. % % In this game space player 1 is restricted to only non-dumb % moves, but player 2 is not restricted. All possible moves % for player 2 are represented. If you were building a machine % to play against a human, and the machine always got the % first move, then you could use this game space to describe % all moves you might want to allow your machine to make. % (Unless you wanted your machine to lose occasionally). % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 1: all smart moves % Player 2: all moves report2( ) -> report2( summary ). report2( Instruction ) -> write_line( "Smart 1st player game space:"), write_line( " Player 1: all smart moves"), write_line( " Player 2: all moves"), report_game_space( Instruction, smart_game_space_1st_player( all_first_moves, all_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on game space where the 2nd player never makes a % mistake. % % Player 2 (who does not move first) never loses in this game % space. % % All possible moves by player 1 are captured. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 1: all moves % Player 2: all smart moves report3( ) -> report3( summary ). report3( Instruction ) -> write_line( "Smart 2nd player game space:"), write_line( " Player 1: all moves"), write_line( " Player 2: all smart moves"), report_game_space( Instruction, smart_game_space_2nd_player( all_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 1st player % never makes a mistake. % % In this game space, the 1st player starts with an X in the % corner. All other moves by the player 1 are also chosen % ahead of time. % % The algorithm that chooses moves ahead of time is simple. % If there are several moves available, the first one grabbed % is the move that's chosen. There is no further analysis. % % All possible moves (responses) by player 2 are captured. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 2: all moves % Player 1: single smart move % 1st move: Corner % Algorithm for chosing other moves: Simple report4( ) -> report4( summary ). report4( Instruction ) -> write_line( "Smart 1st player, moves picked ahead of time:"), write_line( " Player 2: all moves"), write_line( " Player 1:"), write_line( " First move : corner"), write_line( " Move choice: simple"), report_game_space( Instruction, smart_game_space_1st_player( corner_first_move, simple_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 1st player % never makes a mistake. % % In this game space, the 1st player starts with an X in the % corner. All other moves by the player 1 are also chosen % ahead of time. % % The algorithm that chooses moves ahead of time is % complicated and tries to minimize the number of boards % in the game space. % % All possible moves (responses) by player 2 are captured. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 2: all moves % Player 1: single smart move % 1st move: Corner % Algorithm for chosing other moves: Minimize Boards report5( ) -> report5( summary ). report5( Instruction ) -> write_line( "Smart 1st player, moves picked ahead of time:"), write_line( " Player 2: all moves"), write_line( " Player 1:"), write_line( " First move : corner"), write_line( " Move choice: minimize boards"), report_game_space( Instruction, smart_game_space_1st_player( corner_first_move, carefully_reduced_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 1st player % never makes a mistake. % % In this game space, the 1st player starts with an X in the % side. All other moves by the player 1 are also chosen % ahead of time. % % The algorithm that chooses moves ahead of time is % complicated and tries to minimize the number of boards % in the game space. % % All possible moves (responses) by player 2 are captured. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 2: all moves % Player 1: single smart move % 1st move: Side % Algorithm for chosing other moves: Minimize Boards report6( ) -> report6( summary ). report6( Instruction ) -> write_line( "Smart 1st player, moves picked ahead of time:"), write_line( " Player 2: all moves"), write_line( " Player 1:"), write_line( " First move : side"), write_line( " Move choice: minimize boards"), report_game_space( Instruction, smart_game_space_1st_player( side_first_move, carefully_reduced_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 1st player % never makes a mistake. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 2: all moves % Player 1: single smart move % 1st move: Middle % Algorithm for chosing other moves: Minimize Boards report7( ) -> report7( summary ). report7( Instruction ) -> write_line( "Smart 1st player, moves picked ahead of time:"), write_line( " Player 2: all moves"), write_line( " Player 1:"), write_line( " First move : middle"), write_line( " Move choice: minimize boards"), report_game_space( Instruction, smart_game_space_1st_player( middle_first_move, carefully_reduced_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 2nd player % never makes a mistake. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 1: all moves % Player 2: single smart move % Algorithm for chosing other moves: Simple % % When trimming the moves for player 1 we specify a starting % move (corner, side, or middle). But that's not relevant in % this case since the 2nd player has to have a response to % all of the first moves. report8( ) -> report8( summary ). report8( Instruction ) -> write_line( "Smart 2nd player, moves picked ahead of time:"), write_line( " Player 1: all moves"), write_line( " Player 2: single move for every situation"), write_line( " Move choice: smart, simple"), report_game_space( Instruction, smart_game_space_2nd_player( simple_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Report on a subset of the game space where the 2nd player % never makes a mistake. % % Instruction values: % summary % ply_overview % Ply_index 0-9 % % Game space: % Player 1: all moves % Player 2: single smart move % Algorithm for chosing other moves: Minimize Boards report9( ) -> report9( summary ). report9( Instruction ) -> write_line( "Smart 2nd player, moves picked ahead of time:"), write_line( " Player 1: all moves"), write_line( " Player 2: single move for every situation"), write_line( " Move choice: smart, minimize boards"), report_game_space( Instruction, smart_game_space_2nd_player( carefully_reduced_single_moves, full_game_space( ))). % -------------------------------------------------------------- % Game space reporting details % -------------------------------------------------------------- % % There are several things we can count: % Games (paths thru the game space) % Boards % Moves (transitions between boards) % -------------------------------------------------------------- % report_game_space( Game_space ) report_game_space( Instruction, Game_space ) -> if is_integer( Instruction), 0 =< Instruction, 9 >= Instruction -> Ply_index = Instruction, Ply = lists:nth( Ply_index + 1, Game_space), report_ply_boards( Ply); Instruction =:= ply_overview -> report_game_space_ply_overview( Game_space); Instruction =:= summary -> report_game_space_summary( Game_space) end. % -------------------------------------------------------------- % report_game_space_summary( Game_space ) report_game_space_summary( Game_space ) -> write_line( ), % Report total number of game paths in game space. write_line( " Total number of game paths: ~w", get_ply_leaf_count( hd( Game_space))), % Report total number of boards in game space. % Break down the board count as % Number of tie boards % Number of boards where player1 wins % Number where player2 wins % Number of boards player 1 must respond to % Number player 2 must respond to write_line( ), write_line( " Total number of boards: ~w", get_game_space_board_count( Game_space)), write_line( " Player 1 winning boards : ~w", get_game_space_board_count_won_by_1st_player( Game_space)), write_line( " Player 2 winning boards : ~w", get_game_space_board_count_won_by_2nd_player( Game_space)), write_line( " Player 1 must respond to: ~w", get_game_space_board_count_requires_1st_player_response( Game_space)), write_line( " Player 2 must respond to: ~w", get_game_space_board_count_requires_2nd_player_response( Game_space)), write_line( " Tie boards : ~w", get_game_space_tie_board_count( Game_space)), % Break down the total number of boards again, this time as % Initial board (always 1) % Number of boards produced by player 1 % Number of boards produced by player 2 write_line( ), write_line( " Total number of boards can also be broken down as:"), write_line( " Initial board count : 1"), write_line( " Boards produced by player 1: ~w", get_game_space_board_count_produced_by_player_1( Game_space)), write_line( " Boards produced by player 2: ~w", get_game_space_board_count_produced_by_player_2( Game_space)), write_line( ). % -------------------------------------------------------------- % report_game_space_ply_overview( Game_space ) % % Report details for all the plys except ply-0. % Ply-0 is not very interesting since it only contains the % initial blank board. The only interesting statistic, number % of game paths in this game space, we've already reported % in the summary. report_game_space_ply_overview( Game_space ) -> write_line( ), lists:foreach( fun report_ply/1, tl( Game_space)). % -------------------------------------------------------------- % get_game_space_board_count( Game_space ) % % All of the boards in the entire game space, including the % initial blank board in ply-0. get_game_space_board_count( Game_space ) -> lists:sum( lists:map( fun get_ply_board_count/1, Game_space)). % -------------------------------------------------------------- % get_game_space_continuing_board_count( Game_space ) % get_game_space_win_board_count( Game_space ) % get_game_space_tie_board_count( Game_space ) % % All the boards in the game space can be divided into these % catagories: % % Continuing boards (require a response from player 1 or 2) % Won boards (won by either player 1 or 2) % Tied boards (last ply only) get_game_space_continuing_board_count( Game_space ) -> lists:sum( lists:map( fun( Ply ) -> get_ply_state_count( continuing, Ply) end, Game_space)). get_game_space_win_board_count( Game_space ) -> lists:sum( lists:map( fun( Ply ) -> get_ply_state_count( win, Ply) end, Game_space)). get_game_space_tie_board_count( Game_space ) -> get_ply_state_count( tie, lists:last( Game_space)). % -------------------------------------------------------------- % get_game_space_board_count_requires_1st_player_response( G_s ) % get_game_space_board_count_won_by_1st_player( Game_space ) % get_game_space_board_count_requires_2nd_player_response( G_s ) % get_game_space_board_count_won_by_2nd_player( Game_space ) % % You can also divide all the boards in the game space into % these catagories. This is a finer division than the one % above. % % Requires 1st player response % Requires 2nd player response % Won by 1st player % Won by 2nd player % Tied boards (last ply only) get_game_space_board_count_requires_1st_player_response( [Ply0, _, Ply2, _, Ply4, _, Ply6, _, Ply8, _] ) -> get_ply_state_count( continuing, Ply0) + get_ply_state_count( continuing, Ply2) + get_ply_state_count( continuing, Ply4) + get_ply_state_count( continuing, Ply6) + get_ply_state_count( continuing, Ply8). get_game_space_board_count_won_by_1st_player( [_, _, _, _, _, Ply5, _, Ply7, _, Ply9] ) -> get_ply_state_count( win, Ply5) + get_ply_state_count( win, Ply7) + get_ply_state_count( win, Ply9). get_game_space_board_count_requires_2nd_player_response( [_, Ply1, _, Ply3, _, Ply5, _, Ply7, _, _] ) -> get_ply_state_count( continuing, Ply1) + get_ply_state_count( continuing, Ply3) + get_ply_state_count( continuing, Ply5) + get_ply_state_count( continuing, Ply7). get_game_space_board_count_won_by_2nd_player( [_, _, _, _, _, _, Ply6, _, Ply8, _] ) -> get_ply_state_count( win, Ply6) + get_ply_state_count( win, Ply8). % -------------------------------------------------------------- % get_game_space_board_count_produced_by_player_1( Game_space ) % get_game_space_board_count_produced_by_player_2( Game_space ) % % You can also divide the boards in the game space into these % catagories: % % Initial blank board (exactly one, in ply-0) % Boards produced by 1st player % Boards produced by 2nd player % % Boards produced by player 1 can be catagorized further: % % Player 2 must respond (state continuing) % Player 1 is the winner % Tie game % % Boards produced by player 2 can also be catagorized further. % Player 2 never produces tie boards. % % Player 1 must respond (state continuing) % Player 2 is the winner % % Player 1 must also respond to the initial blank board. get_game_space_board_count_produced_by_player_1( [_, Ply1, _, Ply3, _, Ply5, _, Ply7, _, Ply9] ) -> get_ply_board_count( Ply1) + get_ply_board_count( Ply3) + get_ply_board_count( Ply5) + get_ply_board_count( Ply7) + get_ply_board_count( Ply9). get_game_space_board_count_produced_by_player_2( [_, _, Ply2, _, Ply4, _, Ply6, _, Ply8, _] ) -> get_ply_board_count( Ply2) + get_ply_board_count( Ply4) + get_ply_board_count( Ply6) + get_ply_board_count( Ply8). % -------------------------------------------------------------- % Game spaces % -------------------------------------------------------------- % % The game space is a directed graph of game boards. % Boards that are identical after rotation and reflection are % considered the same. % % At each ply of the game there are a set of possible game % boards that can be achieved. These are divided into two % groups: winning boards (3 in a row), and other boards % which are continuing games, except after ply 9 when the % board is full and the game ends in a tie. % -------------------------------------------------------------- % full_game_space( ) % % Returns a game space that describes every possible % tic-tac-toe game, even ones with very perverse sequences % of moves. The moves just have to be legal, with player 1 % and player 2 taking turns. Games do not continue after a % player wins with 3 in-a-row. full_game_space( ) -> Ply0 = init_ply( ), Ply1 = next_ply( Ply0), Ply2 = next_ply( Ply1), Ply3 = next_ply( Ply2), Ply4 = next_ply( Ply3), Ply5 = next_ply( Ply4), Ply6 = next_ply( Ply5), Ply7 = next_ply( Ply6), Ply8 = next_ply( Ply7), Ply9 = next_ply( Ply8), calc_game_space_predictions_and_leaf_counts( Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9). % -------------------------------------------------------------- % smart_game_space( Full_game_space ) % % Returns a game space with all the mistake moves removed. % Without any mistakes all game paths lead to ties. % This game space doesn't represent all possible tie games % though since you can also get a tie if both players make % mistakes. smart_game_space( [ _, Ply1_predictions, Ply2_predictions, Ply3_predictions, Ply4_predictions, Ply5_predictions, Ply6_predictions, Ply7_predictions, Ply8_predictions, Ply9_predictions ] ) -> % Ply0 contains the empty board and the 3 first moves from there. % We don't trim these moves because we know all of them are % predicted to lead to ties, and so all of them are "smart". % We could trim them though, since we do have Ply0_predictions % and Ply1_predictions. Ply0 = init_ply( ), % Ply1 is generated from all the moves in Ply0. % Ply1 is all the boards with the first mark, and also all % the moves from there by the 2nd player. Ply1 = next_ply_smart_moves_only( all_moves, Ply0, Ply1_predictions, Ply2_predictions), Ply2 = next_ply_smart_moves_only( all_moves, Ply1, Ply2_predictions, Ply3_predictions), Ply3 = next_ply_smart_moves_only( all_moves, Ply2, Ply3_predictions, Ply4_predictions), Ply4 = next_ply_smart_moves_only( all_moves, Ply3, Ply4_predictions, Ply5_predictions), Ply5 = next_ply_smart_moves_only( all_moves, Ply4, Ply5_predictions, Ply6_predictions), Ply6 = next_ply_smart_moves_only( all_moves, Ply5, Ply6_predictions, Ply7_predictions), Ply7 = next_ply_smart_moves_only( all_moves, Ply6, Ply7_predictions, Ply8_predictions), Ply8 = next_ply_smart_moves_only( all_moves, Ply7, Ply8_predictions, Ply9_predictions), Ply9 = next_ply( Ply8), calc_game_space_predictions_and_leaf_counts( Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9). % -------------------------------------------------------------- % smart_game_space_1st_player( % Start_instruction, Trim_instruction, Full_game_space ) % % This generates game spaces that assumes we have control % over the 1st player, which allows us to discard all moves % by the 1st player that are not "smart". % % A not-smart move leads a winning board into a tying or % losing situation. It can also lead a tying board into a % losing situation. % % Start_instruction let's us choose how to trim the first-move % in the game space. It can have these values: % all_first_moves % corner_first_move % side_first_move % middle_first_move % % Trim_instruction can be one of these values. Each generates % a different game space: % all_moves % simple_single_moves % carefully_reduced_single_moves % % We need Full_game_space for the predictions stored for every % board in every ply. The predictions must be calculated % ahead of time. smart_game_space_1st_player( Start_instruction, Trim_instruction, [ _, _ , Ply2_predictions, Ply3_predictions, Ply4_predictions, Ply5_predictions, Ply6_predictions, Ply7_predictions, Ply8_predictions, Ply9_predictions ] ) -> % Ply0 contains the empty board. It also contains the % next_boards for the empty board, which are the boards after % the first move. % There are 3 possible first moves, and all are predicted to % lead to ties (assuming smart moves by both players). % With Start_instruction the caller can choose whether to % keep all three moves in the game space, or to just keep one. Ply0 = case Start_instruction of all_first_moves -> init_ply( ); corner_first_move -> init_ply_corner_move( ); side_first_move -> init_ply_side_move( ); middle_first_move -> init_ply_middle_move( ) end, % Ply1 contains all the moves by the 2nd player. % We don't trim any moves since we have no control over % the 2nd player. Ply1 = next_ply( Ply0), Ply2 = next_ply_smart_moves_only( Trim_instruction, Ply1, Ply2_predictions, Ply3_predictions), Ply3 = next_ply( Ply2), Ply4 = next_ply_smart_moves_only( Trim_instruction, Ply3, Ply4_predictions, Ply5_predictions), Ply5 = next_ply( Ply4), Ply6 = next_ply_smart_moves_only( Trim_instruction, Ply5, Ply6_predictions, Ply7_predictions), Ply7 = next_ply( Ply6), Ply8 = next_ply_smart_moves_only( Trim_instruction, Ply7, Ply8_predictions, Ply9_predictions), Ply9 = next_ply( Ply8), calc_game_space_predictions_and_leaf_counts( Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9). % -------------------------------------------------------------- % smart_game_space_2nd_player( % Trim_instruction, Full_game_space ) % % This generates game spaces that assumes we have control % over the 2nd player, which allows us to discard all moves % by the 2nd player that are not "smart". % % A not-smart move leads a winning board into a tying or % losing situation. It can also lead a tying board into a % losing situation. % % Trim_instruction can be one of these values. Each generates % a different game space: % all_moves % simple_single_moves % carefully_reduced_single_moves % % We need Full_game_space for the predictions stored for every % board in every ply. The predictions must be calculated % ahead of time. smart_game_space_2nd_player( Trim_instruction, [ _, Ply1_predictions, Ply2_predictions, Ply3_predictions, Ply4_predictions, Ply5_predictions, Ply6_predictions, Ply7_predictions, Ply8_predictions, _ ] ) -> % The initial ply is the blank board and the 3 possible % first moves (stored as next_boards in the ply dictionary). Ply0 = init_ply( ), % Ply1 is generated from all the moves (next_boards) in Ply0. % Ply1 is all the boards with the first mark, and also all % the moves from there by the 2nd player. % This trims all the moves by the 2nd player that are not % not "smart". Ply1 = next_ply_smart_moves_only( Trim_instruction, Ply0, Ply1_predictions, Ply2_predictions), % Ply2 contains all the boards with 2 marks and all the moves % by the 1st player. We don't trim any 1st-player move in this % function. Ply2 = next_ply( Ply1), Ply3 = next_ply_smart_moves_only( Trim_instruction, Ply2, Ply3_predictions, Ply4_predictions), Ply4 = next_ply( Ply3), Ply5 = next_ply_smart_moves_only( Trim_instruction, Ply4, Ply5_predictions, Ply6_predictions), Ply6 = next_ply( Ply5), Ply7 = next_ply_smart_moves_only( Trim_instruction, Ply6, Ply7_predictions, Ply8_predictions), Ply8 = next_ply( Ply7), % We don't trim Ply9 because there are no moves leading % to Ply10. To trim this we'd need Ply10_predictions, and % there is no Ply10 in tic-tac-toe. Although we could % create an empty ply (no boards) and use that for Ply10. Ply9 = next_ply( Ply8), calc_game_space_predictions_and_leaf_counts( Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9). % -------------------------------------------------------------- % Ply trimming % -------------------------------------------------------------- % -------------------------------------------------------------- % next_ply_smart_moves_only( % Instruction, % Previous_ply, % This_ply_superset_with_predictions, % Next_ply_superset_with_predictions) % % Calculates the next ply. % Trims some of the next moves (next_boards) from the next % ply we're creating. % % There are 4 ways to calculate the next ply. The simplest way % is just to call next_ply( Previous_ply), which returns the % next ply will all possible next_boards (next moves) after % that ply. You can use this to generate the entire un-trimmed % game space. % % The three other ways to calculate the next ply involve % trimming. From this function you can choose between them % with the first arg Instruction, which can take these values: % % all_moves % The next_boards (next moves) are trimmed so that a % possibly winning board will not stray to a tying or % losing path, and a winning/tying path will not % be downgraded to a losing board. % % simple_single_moves % After the next_boards are trimmed to only the smart % moves, they are further trimmed so that each continuing % board has only a single move. A very simple algorithm % chooses that single move from the possible set of % smart moves. % % carefully_reduced_single_moves % As above, but the next moves are trimmed so as to % the number of boards in the next ply (after the one % returned) as much as possible. % % Improvement? (code design only) % This calculates a "smart" next ply, and then reduces it to % single next-moves afterwards. These two could be separated % more cleanly, so we'd have one function that only % calculates the "smart" game-space for one player, and then % separate functions that trimmed this game space (again for % one player). This is what we do below, except we % generate the intermediate "smart" game-space on the fly % as needed, ply by ply. % This might improve code design, but should yield identical % results. next_ply_smart_moves_only( Instruction, Previous_ply, This_ply_superset_with_predictions, Next_ply_superset_with_predictions) -> This_ply_smart_moves_only = next_ply_smart_moves_only( Previous_ply, This_ply_superset_with_predictions, Next_ply_superset_with_predictions), case Instruction of all_moves -> This_ply_smart_moves_only; simple_single_moves -> trim_ply_next_boards_to_singles( This_ply_smart_moves_only); carefully_reduced_single_moves -> trim_ply_next_boards_to_singles_careful( This_ply_smart_moves_only) end. % -------------------------------------------------------------- % next_ply_smart_moves_only( % Previous_ply, % This_ply_superset_with_predictions, % Next_ply_superset_with_predictions) % % The superset plys have to contain all the boards we'll see % in next_ply( Previous_ply), and all the boards have to have % accurate (calculated) win/tie/loss predictions. % % Prev_ply must not have any moves that force us into a % losing situation. next_ply_smart_moves_only( Prev_ply, This_ply_predictions, Next_ply_predictions ) -> % Keep moves that don't let the other player win. % We don't have any moves that leads to the other player % losing or we would just keep those. Next_board_filter_for_ties = fun( Next_board ) -> Next_prediction = get_board_props_prediction( get_ply_board_props( Next_board, Next_ply_predictions)), case Next_prediction of win -> false; tie -> true end end, % Only keeps the moves that lead to the next other player % losing. The next ply prediction is for the other player. Next_board_filter_for_wins = fun( Next_board ) -> % Next_prediction is for the next ply, so 'win' means % the next-next player, also the previous player, is % expected to win. Next_prediction = get_board_props_prediction( get_ply_board_props( Next_board, Next_ply_predictions)), case Next_prediction of win -> false; tie -> false; loss -> true end end, % Predictions are foward looking, so 'win' means the % next player is expected to win and the previous player % is expected to lose. This_ply_map_filter_next_boards = fun( This_board, This_board_props ) -> This_prediction = get_board_props_prediction( get_ply_board_props( This_board, This_ply_predictions)), filter_board_props_next_boards( case This_prediction of win -> Next_board_filter_for_wins; tie -> Next_board_filter_for_ties end, This_board_props) end, % Generate the next ply with all possible following moves. This_ply_unfiltered = next_ply( Prev_ply), % Remove any following moves that are not "smart". map_ply( This_ply_map_filter_next_boards, This_ply_unfiltered). % -------------------------------------------------------------- % trim_ply_next_boards_to_singles( Ply ) % % Takes all the continuing boards in a ply and discards all % next_boards except for the first one. % This is the simplest way to reduce a game space. trim_ply_next_boards_to_singles( Ply ) -> map_ply( fun( _, Board_props ) -> filter_board_props_to_single_next_board( Board_props) end, Ply). % -------------------------------------------------------------- % trim_ply_next_boards_to_singles_careful( Ply_original ) % % Implements a "smart" (ie complicated) algorithm to reduce % the next_boards in a game space. % % Contrast this to trim_ply_next_boards_to_singles( Ply). trim_ply_next_boards_to_singles_careful( Ply_original ) -> % Make a ply that only has empty and singlular % next-board sets. Ply_singles = filter_ply( fun( _, Board_props ) -> Count = count_next_boards( get_board_props_next_boards( Board_props)), Count =< 1 end, Ply_original), % If all the boards are now in the singles, we are done. Count_original = get_ply_board_count( Ply_original), Count_singles = get_ply_board_count( Ply_singles), if Count_original =:= Count_singles -> Ply_singles; Count_original > Count_singles -> % Remove all the singles from the original. % We are left with boards that have multiple next-boards. Ply_multis = subtract_ply( Ply_original, Ply_singles), % Find all the boards in Ply_multis that share any target % boards with the Ply_singles over to the singles ply. Ply_to_move = find_ply_multi_boards_with_single_targets( Ply_multis, Ply_singles ), % Repeatedly remove boards with common targets from % Ply_multis and add them to Ply_singles. keep_trimming_until_no_more_multis( subtract_ply( Ply_multis, Ply_to_move), merge_ply_no_overlap( Ply_singles, Ply_to_move)) end. % -------------------------------------------------------------- % find_ply_multi_boards_with_single_targets( % Ply_multis, Ply_singles ) % % Part of a "smart" (ie complicated) algorithm to reduce the % next_boards in a game space. % % Finds all the boards in Ply_multis that share any target % boards with Ply_singles. Stores them in a ply with % board_props with only a single target. find_ply_multi_boards_with_single_targets ( Ply_multis, Ply_singles ) -> % We need a set of all the next boards in Ply_singles. % This is the easiest way to get it. Ply_next_singles = next_ply( Ply_singles), % Folded over a set of boards. % Finds the first board in Ply_next_singles. Find_matching_next_board_fn = fun ( Board_look, not_found ) -> case is_board_in_ply( Board_look, Ply_next_singles) of true -> Board_look; false -> not_found end; ( _, Board_found ) -> Board_found end, % Collect a dictionary (a ply) of boards and props. % Each board collected comes from Ply_multis, but has % a board_props with a single target board. Collect_ply_fn = fun( Board, Board_props, Ply_collect ) -> Next_boards = get_board_props_next_boards( Board_props), Next_board = fold_next_boards( Find_matching_next_board_fn, not_found, Next_boards), case Next_board of not_found -> Ply_collect; _ -> Board_props_singlet = set_board_props_next_boards( get_singlet_next_boards( Next_board), Board_props), ply_add_board( Board, Board_props_singlet, Ply_collect) end end, % Walk thru Ply_multi collecting any boards that have at least % one next_board that is also a next_board in Ply_singles. fold_ply( Collect_ply_fn, empty_ply( get_ply_index( Ply_multis)), Ply_multis). % -------------------------------------------------------------- % find_ply_multi_boards_with_common_target( % Ply_multis, Next_board ) % % Part of a "smart" (ie complicated) algorithm to reduce the % next_boards in a game space. % % Builds a ply of all the boards in Ply_multis that target % Next_board. The new ply will have Board_props with % next_boards sets targeting the single board Next_board. find_ply_multi_boards_with_common_target ( Ply_multis, Next_board ) -> % Collect a dictionary (a ply) of boards and props. % Each board collected comes from Ply_multis, but has % a board_props with a single target board. Collect_ply_fn = fun( Board, Board_props, Ply_collect ) -> Next_boards = get_board_props_next_boards( Board_props), case is_in_next_boards( Next_board, Next_boards) of false -> Ply_collect; true -> Board_props_singlet = set_board_props_next_boards( get_singlet_next_boards( Next_board), Board_props), ply_add_board( Board, Board_props_singlet, Ply_collect) end end, % Walk thru Ply_multis collecting any boards that can lead % to Next_board. fold_ply( Collect_ply_fn, empty_ply( get_ply_index( Ply_multis)), Ply_multis). % -------------------------------------------------------------- % keep_trimming_until_no_more_multis( Ply_multis, Ply_singles ) % % Part of a "smart" (ie complicated) algorithm to reduce the % next_boards in a game space. % % Tail-recusing loop that removes a small number of boards % (at least one) from Ply_multis and adds it to Ply_singles % in each iteration. The boards in Ply_multi all have more % than one target in their next_boards, but they are added % to Ply_singles with a single target. % % This stops (and returns Ply_singles) when there are no % more boards in Ply_multis. keep_trimming_until_no_more_multis( Ply_multis, Ply_singles ) -> % If there are no more boards in Ply_multis, we are done. case get_ply_board_count( Ply_multis) of 0 -> Ply_singles; _ -> % The following function is key. It reduces the number of % boards in the next ply to a minimum. { Next_board_to_peel, Src_count } = find_board_with_highest_src_count( next_ply( Ply_multis)), % If all the next_boards in Ply_multis are unique, we can % finish by just trimming the next_boards in a very simple % way, by discarding all next_boards after the head. if Src_count =:= 1 -> merge_ply_no_overlap( Ply_singles, trim_ply_next_boards_to_singles( Ply_multis)); Src_count > 1 -> % Find all the boards in Ply_multis that target % Next_board_to_peel. We use a ply (instead of a % dictionary or a set) to keep track of these boards. Ply_to_move = find_ply_multi_boards_with_common_target( Ply_multis, Next_board_to_peel), % Recurse. keep_trimming_until_no_more_multis( subtract_ply( Ply_multis, Ply_to_move), merge_ply_no_overlap( Ply_singles, Ply_to_move)) end end. % -------------------------------------------------------------- % find_board_with_highest_src_count( Ply ) % % Part of a "smart" (ie complicated) algorithm to reduce the % next_boards in a game space. % % Returns a pair: % { Board_from_ply, Src_count_for_board } % % Do not call this with an empty ply. It will return % 'unknown' if you do. % % This is a critical function for the algorithm that reduces % the number of boards in a game space by deciding on all the % next moves for one of the players ahead of time. % % Given a ply, this finds the board with the highest % src_count, which is a count of the number of boards % from the previous (generating) ply have moves leading % to this board. % This is used to build a (previous) ply with next moves % that lead to a few boards as possible. % So this acts to reduce the number of boards in the entire % game space. % % When there are several boards with the same src_count to % choose from, this just returns the first it sees. % But there are other criteria we could us. % We could try to avoid middle moves (since they close off % the board), or better might be to choose the board with % the highest forward leaf_count. The leaf_count tells us % how many game-paths lie ahead for that board. The more % paths there are, the more interesting the game is for the % user. % % The problem with leaf_paths is they can only be calculated % after the entire forward game-space is known. They are not % calculated in the Ply we get in this function. % % And we cannot really calculate the entire game-space (to % get the leaf_count) without calling this function to trim % the game space. So we're in a catch-22. % % There are ways around this if we want to calculate huge % numbers of intermediate game spaces. Although probably a % better way is just use the leaf_counts from a superset % game-space calculated ahead of time. find_board_with_highest_src_count( Ply ) -> fold_ply( fun ( Board, Board_props, unknown ) -> { Board, get_board_props_src_count( Board_props) }; ( Board, Board_props, Pair_board_count ) -> Count = get_board_props_src_count( Board_props), if Count > element( 2, Pair_board_count) -> { Board, Count }; true -> Pair_board_count end end, unknown, Ply). % -------------------------------------------------------------- % Next ply calculations % -------------------------------------------------------------- % -------------------------------------------------------------- % calc_game_space_predictions_and_leaf_counts( % Ply0, Ply1, Ply2, Ply3, Ply4, % Ply5, Ply6, Ply7, Ply8, Ply9 ) % % Calculates all the forward-looking properties (leaf_count % and prediction) for all boards in a game space. % This is the last thing you do when making a game space. calc_game_space_predictions_and_leaf_counts( Ply0_, Ply1_, Ply2_, Ply3_, Ply4_, Ply5_, Ply6_, Ply7_, Ply8_, Ply9_ ) -> Ply9 = Ply9_, Ply8 = calc_ply_predictions_and_leaf_counts( Ply9, Ply8_), Ply7 = calc_ply_predictions_and_leaf_counts( Ply8, Ply7_), Ply6 = calc_ply_predictions_and_leaf_counts( Ply7, Ply6_), Ply5 = calc_ply_predictions_and_leaf_counts( Ply6, Ply5_), Ply4 = calc_ply_predictions_and_leaf_counts( Ply5, Ply4_), Ply3 = calc_ply_predictions_and_leaf_counts( Ply4, Ply3_), Ply2 = calc_ply_predictions_and_leaf_counts( Ply3, Ply2_), Ply1 = calc_ply_predictions_and_leaf_counts( Ply2, Ply1_), Ply0 = calc_ply_predictions_and_leaf_counts( Ply1, Ply0_), [ Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9 ]. % -------------------------------------------------------------- % empty_ply( Ply_index ) % % Returns an empty (and illegitimate) ply. We use this as a % starting place when building a new ply. A ply in a game % space must contain at least one board, so this ply cannot % be part of a game space. empty_ply( Ply_index ) -> { Ply_index, dict:new( ) }. % -------------------------------------------------------------- % init_ply( ) % % Returns the initial ply (ply 0) in the game space. % The dictionary for ply 0 contains a single empty board. % The board_props for that empty board contains 3 next_boards, % each with a single mark (corner, side, and middle). % % Use this with next_ply(..) to calculate a series of 10 ply % that describes the entire tic-tac-toe game space. init_ply( ) -> Ply_index = 0, Init_board = init_board( ), Prev_mark = flip_mark( get_starting_mark( )), Init_props = init_board_props( Init_board, Prev_mark, 0), init_ply( Ply_index, dict:store( Init_board, Init_props, dict:new( ))). % -------------------------------------------------------------- % init_ply_corner_move( ) % init_ply_side_move( ) % init_ply_middle_move( ) % % Returns initial plys (ply 0) where the initial empty board % in the dictionary has a single next_boards move instead of % the full set of 3 possible next moves. init_ply_corner_move( ) -> init_ply_with_board_props( get_board_props_first_move_corner( )). init_ply_side_move( ) -> init_ply_with_board_props( get_board_props_first_move_side( )). init_ply_middle_move( ) -> init_ply_with_board_props( get_board_props_first_move_middle( )). init_ply_with_board_props( Board_props ) -> Ply_index = 0, Init_board = init_board( ), init_ply( Ply_index, dict:store( Init_board, Board_props, dict:new( ))). % -------------------------------------------------------------- % next_ply( Prev_ply ) % % Given a ply, calculates the next ply in the game space. % All the next_boards in Prev_ply will appear in the next ply. % % The board_props in the returned "next" ply will have all % possible next_boards filled in, along with state and % src_count. % % The board_props leaf_count and prediction have to be % calculated later. next_ply( Prev_ply ) -> init_ply( get_ply_index( Prev_ply) + 1, init_dict_from_prev_ply( Prev_ply)). init_dict_from_prev_ply( Prev_ply ) -> % This_mark is the mark (X or O) that was used to get from % Prev_ply to the ply we are constructing. Prev_mark = get_ply_next_mark( Prev_ply), % For every board in the newly constructed ply, create a % board_props entry. dict:map( fun( Board, Src_count ) -> init_board_props( Board, Prev_mark, Src_count) end, init_dict_from_prev_dict( get_ply_dict( Prev_ply))). % For every dictionary entry in the previous ply, get % the board_props, which contains a set of next_boards. init_dict_from_prev_dict( Prev_dict ) -> dict:fold( fun( _, Board_props, Dict_outer ) -> collect_dict_from_next_boards( Board_props, Dict_outer) end, dict:new( ), Prev_dict). % Collect all the next_boards into the dictionary. % Keep track of the source count. collect_dict_from_next_boards( Board_props, Dict_init ) -> fold_next_boards( fun( Board, Dict_collect ) -> dict:update_counter( Board, 1, Dict_collect) end, Dict_init, get_board_props_next_boards( Board_props)). % -------------------------------------------------------------- % calc_ply_predictions_and_leaf_counts( Next_ply, This_ply ) % % Call this after you have built the plys that describe a % game space. This will calculate the forward-looking values % (leaf_count and prediction) stored with every board in % This_ply. % % This will do nothing for the last ply. % Next_ply must be calculated first. calc_ply_predictions_and_leaf_counts( Next_ply, This_ply ) -> map_ply( fun( _, Board_props ) -> fill_in_board_props_forward_props( Next_ply, Board_props) end, This_ply). % -------------------------------------------------------------- % Ply interface % -------------------------------------------------------------- % % A ply contains: % % ply_index - integer, 0-9. % How many marks are on the boards in this ply. % % dict % A dictionary of boards in this ply. Each board is % associated with a board_props tuple. % -------------------------------------------------------------- % Getters for Ply get_ply_index( Ply ) -> element( 1, Ply). get_ply_dict( Ply ) -> element( 2, Ply). get_ply_prev_mark( Ply ) -> prev_ply_mark( get_ply_index( Ply)). get_ply_next_mark( Ply ) -> next_ply_mark( get_ply_index( Ply)). % -------------------------------------------------------------- % init_ply( Ply_index, Dict ) % set_ply_dict( Dict, Ply ) % % A ply is a 2-tuple (pair). It's an index (zero-based) and % a dictionary associating all the boards at that ply with % a board_props. % The ply_index tells you how many marks are on the boards in % the ply dictionary. Ply0 always has only one board, with no % marks on it. Ply9 contains only boards with 9 marks (and % thus no empty spaces). init_ply( Ply_index, Dict ) -> { Ply_index, Dict }. set_ply_dict( Dict, Ply ) -> init_ply( get_ply_index( Ply), Dict). % -------------------------------------------------------------- % is_board_in_ply( Board, Ply ) % get_ply_board_props( Board, Ply ) % % Board_props is the object (tuple) associated with the Board % in the ply dictionary. is_board_in_ply( Board, Ply ) -> dict:is_key( Board, get_ply_dict( Ply)). get_ply_board_props( Board, Ply ) -> dict:fetch( Board, get_ply_dict( Ply)). % -------------------------------------------------------------- % ply_add_board( Board, Board_props, Ply ) % % Adds a new Board and Board_props to the Ply dictionary. % Replaces Board_props if Board is already in the dictionary. ply_add_board( Board, Board_props, Ply ) -> set_ply_dict( dict:store( Board, Board_props, get_ply_dict( Ply)), Ply). % -------------------------------------------------------------- % ply_remove_board( Board, Ply ) % % Removes Board from Ply. % It's OK if Board is not in Ply. ply_remove_board( Board, Ply ) -> set_ply_dict( dict:erase( Board, get_ply_dict( Ply)), Ply). % -------------------------------------------------------------- % fold_ply( Fold_fn, Init_value, Ply ) % % Fold_fn( Board, Board_props, Collect_init ) -> Collect_next fold_ply( Fold_fn, Init_value, Ply ) -> dict:fold( Fold_fn, Init_value, get_ply_dict( Ply)). % -------------------------------------------------------------- % map_ply( Map_fn, Ply ) % % Calculate a new board_props for every board in Ply. % Map_fn( Board, Board_props ) -> Board_props map_ply( Map_fn, Ply ) -> set_ply_dict( dict:map( Map_fn, get_ply_dict( Ply)), Ply). % -------------------------------------------------------------- % filter_ply( Filter_fn, Ply ) % % Filter out some Boards from Ply. % Filter_fn( Board, Board_props ) -> true/false filter_ply( Filter_fn, Ply ) -> set_ply_dict( dict:filter( Filter_fn, get_ply_dict( Ply)), Ply). % -------------------------------------------------------------- % merge_ply( Merge_fn, Ply1, Ply2 ) % % Combines all the Boards and Board_props from two plys. % If any board is in both ply, the Merge_fn(..) function will % be called to resolve what should be stored as Board_props. % % Merge_fn( Board, Board_props1, Board_props2 ) -> % Board_props_to_store % % Both plys should have the same ply_index, or this operation % doesn't make sense. merge_ply( Merge_fn, Ply1, Ply2 ) -> set_ply_dict( dict:merge( Merge_fn, get_ply_dict( Ply1), get_ply_dict( Ply2)), Ply1). % -------------------------------------------------------------- % merge_ply_no_overlap( Ply1, Ply2 ) % % Combines all the Boards and Board_props from two plys into % one ply. Error if the two plys have any overlap. merge_ply_no_overlap( Ply1, Ply2 ) -> merge_ply( fun( false, false, false ) -> ok end, Ply1, Ply2). % -------------------------------------------------------------- % subtract_ply( Ply_start, Ply_remove ) % % Removes all boards in Ply_remove from Ply_start. % It's OK if Ply_remove holds boards not in Ply_start. % Although this does not check, the ply_index values for both % plys should be the same or there will be no matching boards. subtract_ply( Ply_start, Ply_remove ) -> filter_ply( fun( Board, _ ) -> not is_board_in_ply( Board, Ply_remove) end, Ply_start). % -------------------------------------------------------------- % count_ply( Count_predicate, Ply ) % % Count_predicate( Board, Board_props ) -> true/false count_ply( Count_predicate, Ply ) -> fold_ply( fun( Board, Board_props, Count ) -> case Count_predicate( Board, Board_props) of true -> Count + 1; false -> Count end end, 0, Ply). % -------------------------------------------------------------- % sum_ply( Sum_fn, Ply ) % % Sum_fn( Board, Board_props ) -> integer sum_ply( Sum_fn, Ply ) -> fold_ply( fun( Board, Board_props, Sum ) -> Sum + Sum_fn( Board, Board_props) end, 0, Ply). % -------------------------------------------------------------- % get_ply_board_count( Ply ) % % How many (canonical) boards are in this ply. % Includes all boards, continuing and finished. get_ply_board_count( Ply ) -> dict:size( get_ply_dict( Ply)). % -------------------------------------------------------------- % get_ply_state_count( State, Ply ) % % Counts how many boards in a Ply have a specified State. % So get_ply_state_count( tie, Ply) tells you how many boards % in this ply were tied in the last move. Of course this is % always zero except in the last ply, since ties can only % occur in the last ply in tic-tac-toe. get_ply_state_count( State, Ply ) -> count_ply( fun( _, Board_props ) -> get_board_props_state( Board_props) =:= State end, Ply). % -------------------------------------------------------------- % get_ply_prediction_count( Prediction, Ply ) % % Counts how many boards in the Ply have a prediction that % matches Prediction. So get_ply_prediction_count( tie, Ply) % tells you how many boards in the ply are predicted to end % in a tie. % % Another useful number might be the number of forward paths % (leaf_counts) in the game_space are predicted to end in a % win/tie/loss. get_ply_prediction_count( Prediction, Ply ) -> count_ply( fun( _, Board_props ) -> get_board_props_prediction( Board_props) =:= Prediction end, Ply). % -------------------------------------------------------------- % get_ply_leaf_count( Ply ) % % Sums the leaf_counts for all the boards in the Ply. % A leaf_count for a board is the number of forward paths from % this board to all finished games in the game space. get_ply_leaf_count( Ply ) -> sum_ply( fun( _, Board_props ) -> get_board_props_leaf_count( Board_props) end, Ply). % -------------------------------------------------------------- % get_ply_src_count( Ply ) % % Sums the src_counts for all the boards in the ply. get_ply_src_count( Ply ) -> sum_ply( fun( _, Board_props ) -> get_board_props_src_count( Board_props) end, Ply). % -------------------------------------------------------------- % report_ply( Ply ) % % Reports a basic summary of what's in a Ply. Does not % display all the boards in the ply. report_ply( Ply ) -> case get_ply_index( Ply) of 0 -> report_ply_0( Ply); 9 -> report_ply_9( Ply); _ -> report_ply_detail( Ply) end. report_ply_detail( Ply ) -> Ply_index = get_ply_index( Ply), Player = case Ply_index band 1 of 0 -> 2; 1 -> 1 end, Player_other = case Ply_index band 1 of 0 -> 1; 1 -> 2 end, Board_count = get_ply_board_count( Ply), Cont_count = get_ply_state_count( continuing, Ply), Win_states = get_ply_state_count( win, Ply), Tie_predict = get_ply_prediction_count( tie, Ply), Win_predict = get_ply_prediction_count( loss, Ply), Win_after = Win_predict - Win_states, Loss_predict = get_ply_prediction_count( win, Ply), write_line( " Player ~w moves, leading to ply ~w", Player, Ply_index), write_string( " ~w boards ", Board_count), if Board_count =:= Cont_count -> if Tie_predict =:= Cont_count -> write_line( "(all continue to ties)"); true -> write_line( "(all continue)") end; true -> if Tie_predict =:= Cont_count -> write_line( "(~w continuing to ties)", Cont_count); true -> write_line( "(~w continuing)", Cont_count) end end, if Win_states =/= 0 -> write_line( " ~w boards won by player ~w", Win_states, Player); true -> ok end, if Tie_predict =/= 0 -> if Tie_predict =/= Cont_count -> write_line( " ~w boards lead to ties", Tie_predict); true -> ok end; true -> ok end, if Win_after =/= 0 -> write_line( " ~w boards lead to a win by player ~w", Win_after, Player); true -> ok end, if Loss_predict =/= 0 -> write_line( " ~w boards lead to a win by player ~w", Loss_predict, Player_other); true -> ok end. % X moves next report_ply_0( Ply ) -> write_line( " Starting blank board"), write_line( " Total number of game paths: ~w", get_ply_leaf_count( Ply)). % X just moved report_ply_9( Ply ) -> Tie_count = get_ply_state_count( tie, Ply), Win_count = get_ply_state_count( win, Ply), write_line( " Player 1 moves (last move)"), if 0 =/= Tie_count -> write_line( " ~w tie boards", Tie_count); true -> ok end, if 0 =/= Win_count -> write_line( " ~w boards won by player 1", Win_count); true -> ok end. % -------------------------------------------------------------- % report_ply_boards( Ply ) % % Reports on all the boards in a ply. report_ply_boards( Ply ) -> write_line( ), write_line( " Boards in ply ~w", get_ply_index( Ply)), { Win_boards, Tie_boards, Continuing_boards } = lists:foldl( fun( Pair, Tuple ) -> { _, Board_props } = Pair, Index = case get_board_props_state( Board_props) of win -> 1; tie -> 2; continuing -> 3 end, setelement( Index, Tuple, [Pair | element( Index, Tuple)]) end, erlang:make_tuple( 3, []), dict:to_list( get_ply_dict( Ply))), lists:foreach( fun( {Board, Board_props} ) -> report_board( Board, Board_props), write_line( ) end, lists:sort( Win_boards)), lists:foreach( fun( {Board, Board_props} ) -> report_board( Board, Board_props), write_line( ) end, lists:sort( Tie_boards)), lists:foreach( fun( {Board, Board_props} ) -> report_board( Board, Board_props), write_line( ) end, lists:sort( Continuing_boards)). % -------------------------------------------------------------- % Next_boards % -------------------------------------------------------------- % % Next_boards are part of board_props. % Each next_board represents a "next move". % -------------------------------------------------------------- % calc_next_boards( Mark, Src_board ) % % Returns a Next_boards set. This is a set of canonical boards % derived from Src_board with one more mark on it. So if % Src_board is full this will return an empty set. calc_next_boards( Mark, Src_board ) -> lists:foldl( fun( Position, Set_of_trg_boards ) -> case is_board_marked_at( Position, Src_board ) of false -> add_to_next_boards( mark_board_at( Position, Mark, Src_board), Set_of_trg_boards); true -> Set_of_trg_boards end end, get_empty_next_boards( ), lists:seq( 1, 9)). % -------------------------------------------------------------- % add_to_next_boards( Board, Next_boards ) add_to_next_boards( Board, Next_boards ) -> ordsets:add_element( get_canonical_board( Board), Next_boards). % -------------------------------------------------------------- % is_in_next_boards( Board, Next_boards ) is_in_next_boards( Board, Next_boards ) -> ordsets:is_element( Board, Next_boards). % -------------------------------------------------------------- % get_empty_next_boards( ) get_empty_next_boards( ) -> ordsets:new( ). % -------------------------------------------------------------- % get_singlet_next_boards( Board ) get_singlet_next_boards( Board ) -> add_to_next_boards( Board, get_empty_next_boards( )). % -------------------------------------------------------------- % count_next_boards( Next_boards ) count_next_boards( Next_boards ) -> ordsets:size( Next_boards). % -------------------------------------------------------------- % has_next_board( Next_boards ) % % We could also call this something like: % is_set_of_next_boards_not_empty( Next_boards ) has_next_board( Next_boards ) -> count_next_boards( Next_boards) =/= 0. % -------------------------------------------------------------- % get_next_boards_first_board( Next_boards ) get_next_boards_first_board( Next_boards ) -> % Assumes 'first' is never considered a board. % We could generalize this for any fold by using make_ref( ). fold_next_boards( fun ( Board, first ) -> Board; ( _ , Board ) -> Board end, first, Next_boards). % -------------------------------------------------------------- % fold_next_boards( Fold_fn, Accumulate, Next_boards ) % % Iterates over the set of Next_boards. Order of iteration % is not specified because the order of the set of boards % in Next_boards is not specified. % % The fold function should look like this: % Fold_fn( Board, Accumulate_0 ) -> Accumulate_1 fold_next_boards( Fold_fn, Accumulate, Next_boards ) -> ordsets:fold( Fold_fn, Accumulate, Next_boards). % -------------------------------------------------------------- % filter_next_boards( Filter_pred, Next_boards ) % % Filter_pred looks like this: % Filter_pred( Board ) -> true or false filter_next_boards( Filter_pred, Next_boards ) -> ordsets:filter( Filter_pred, Next_boards). % -------------------------------------------------------------- % Board_props interface % -------------------------------------------------------------- % % A board_props is a tuple describing the next moves a board % may take. These tuples are paired with a board in the ply % dictionary. Each board_props tuple includes: % % next_boards % A set (ordsets) of boards that we'll get after the next % move. This might include all possible moves, or the % set might be restricted to only wise moves, or to only % the moves we want to consider. % % Instead of storing next_boards we could store next % moves. From the next move we'd like to know: % The resulting board % Resulting state % Predicted result(s) % How many game paths make this move % % src_count % Number of predecessors. % Number of source boards in the previous ply that lead % to this board after one move. % % leaf_count % Number of paths from here to a leaf. % The number of game paths from here to a finished game. % This is always 1 if state is win or tie. % For continuing boards this is calculated after all the % plys in the game-space are set up. % Possible values: % 1 - for boards with states win or tie % unknown - for continuing boards (before calculation) % >= 1 - for continuing boards % % state % An atom that tells us about the dictionary-entry board. % One of these values: % win - the board has 3-in-a-row % tie - the board is full with no 3-in-a-row % continuing % Win means the last move won. This is different from % the prediction prop which talks about the next move. % % If state is win or tie, the next_boards set must be % empty. Otherwise next_boards must not be empty. % State tie can only occur in the last ply. % State win can not occur in the last ply, and really % only in plys 5, 6, 7, and 8. % % prediction % An atom that tells us how this game will end up, % assuming it is played without mistakes. % One of these values: % win % loss % tie % unknown % This is a prediction for the next-move player. So in % ply0, the predictions will be for the first player. % Even plys hold predictions for the first player, and % odd plys for the 2nd player. % -------------------------------------------------------------- % Getters for Board_props % % The properties of board_props are: % next_boards % src_count % leaf_count % state % prediction get_board_props_next_boards( Board_props ) -> element( 1, Board_props). get_board_props_src_count( Board_props ) -> element( 2, Board_props). get_board_props_leaf_count( Board_props ) -> element( 3, Board_props). get_board_props_state( Board_props ) -> element( 4, Board_props). get_board_props_prediction( Board_props ) -> element( 5, Board_props). % -------------------------------------------------------------- % init_board_props( Board, Prev_mark, Src_count ) % % Calculates the board_props to store with a board when % building a ply. Does not include forward-looking properties % leaf_count and prediction. These have to be calculated % later, starting with the last ply and working backwards. init_board_props( Board, Prev_mark, Src_count ) -> case is_board_won_by( Prev_mark, Board) of true -> % This is a winning board. init_board_props_win( Src_count); false -> % This is a tie board if this the last ply. % Otherwise this is a continuing board. Next_mark = flip_mark( Prev_mark), Next_boards = calc_next_boards( Next_mark, Board), case has_next_board( Next_boards) of false -> init_board_props_tie( Src_count); true -> init_board_props_continuing( Src_count, Next_boards) end end. init_board_props_win( Src_count) -> % If this board is won (state is win), then it is a loss for % the player who moves next. That is why the prediction is % loss instead of win. Win marks this board as finished, % loss means it is a loss for the NEXT player, not the last. { get_empty_next_boards( ), Src_count, 1, win, loss }. init_board_props_tie( Src_count ) -> { get_empty_next_boards( ), Src_count, 1, tie, tie }. init_board_props_continuing( Src_count, Next_boards ) -> { Next_boards, Src_count, unknown, continuing, unknown }. % -------------------------------------------------------------- % get_board_props_first_move_corner( ) % get_board_props_first_move_side( ) % get_board_props_first_move_middle( ) % % Returns boards with the three possible first moves. % X.. .X. ... % ... ... .X. % ... ... ... get_board_props_first_move_corner( ) -> get_board_props_first_move_( get_board_first_move_corner( )). get_board_props_first_move_side( ) -> get_board_props_first_move_( get_board_first_move_side( )). get_board_props_first_move_middle( ) -> get_board_props_first_move_( get_board_first_move_middle( )). get_board_props_first_move_( Board ) -> { get_singlet_next_boards( get_canonical_board( Board)), 1, unknown, continuing, unknown }. % -------------------------------------------------------------- % set_board_props_next_boards( Next_boards, Board_props ) % % Changes the set of next_boards in a Board_props. % For non-continuing (win/tie) boards the board_props should % always have an empty set of next_boards. For continuing % boards the set should always be non-empty. set_board_props_next_boards( Next_boards, Board_props ) -> { Next_boards, get_board_props_src_count( Board_props), get_board_props_leaf_count( Board_props), get_board_props_state( Board_props), get_board_props_prediction( Board_props) }. % -------------------------------------------------------------- % fill_in_board_props_forward_props( Next_ply, Board_props ) % % Calculates the leaf_count and prediction properties for % board_props. Assumes all the next_boards are in Next_ply % and have leaf_counts and predictions already calculated. fill_in_board_props_forward_props( Next_ply, Board_props ) -> case get_board_props_state( Board_props) of continuing -> % It would be a little more efficient to calculate both % the leaf_count and prediction in the same in the same % function since both functions look up all the % next_boards in Next_ply. { get_board_props_next_boards( Board_props), get_board_props_src_count( Board_props), calc_board_leaf_count( Next_ply, Board_props), get_board_props_state( Board_props), calc_board_prediction( Next_ply, Board_props) }; _ -> % Non-continuing (win and tie) boards already have % leaf_count and prediction values. For these, the set of % next_boards is always empty, leaf_count is always 1, and % prediction is either loss (for state win) or tie. Board_props end. % -------------------------------------------------------------- % calc_board_prediction( Next_ply, Src_board_props ) % % Calculates the win/tie/loss prediction for Src_board_props. % Assumes all the next_boards are in Next_ply, and that they % all have calculated predictions. % % Remember a win at this ply is the same as forcing a loss at % the next ply. And a loss at this ply means the other player % can force a win for himself at the next ply. calc_board_prediction( Next_ply, Src_board_props ) -> fold_next_boards( fun ( _ , win ) -> win; ( Next_board, tie ) -> Next_props = get_ply_board_props( Next_board, Next_ply), case get_board_props_prediction( Next_props) of loss -> win; _ -> tie end; ( Next_board, _ ) -> Next_props = get_ply_board_props( Next_board, Next_ply), case get_board_props_prediction( Next_props) of loss -> win; tie -> tie; win -> loss end end, unknown, get_board_props_next_boards( Src_board_props)). % -------------------------------------------------------------- % calc_board_leaf_count( Next_ply, Src_board_props ) % % Assumes all the next_boards are in Next_ply, and the % leaf_counts in the board_props in Next_ply are already % calculated. % % Only works for continuing boards. % Returns 0 for win/tie boards (instead of 1, the correct % answer). You never have to calculate leaf_count for win/tie % next_boards. calc_board_leaf_count( Next_ply, Src_board_props ) -> fold_next_boards( fun( Next_board, Sum ) -> Sum + get_board_props_leaf_count( get_ply_board_props( Next_board, Next_ply)) end, 0, get_board_props_next_boards( Src_board_props)). % -------------------------------------------------------------- % filter_board_props_next_boards( Filter_pred, Board_props ) % % This removes next_boards that do not pass Filter_pred. % Filter_pred only gets to see the boards in next_boards, not % the source board. % Filter_pred only gets to the the next boards one at a time, % so it cannot compare all the next boards and just choose the % ones it likes. % % It is not legal to filter out all the boards in next_boards. % Continuing boards should have at least one next_board. % % Filter_pred( Board ) -> true/false % where Board is from a set of next_boards. filter_board_props_next_boards( Filter_pred, Board_props ) -> case get_board_props_state( Board_props) of % Only continuing props have non-empty next_boards. % This clears leaf_count and prediction. continuing -> { filter_next_boards( Filter_pred, get_board_props_next_boards( Board_props)), get_board_props_src_count( Board_props), unknown, continuing, unknown }; _ -> Board_props end. % -------------------------------------------------------------- % filter_board_props_to_single_next_board( Board_props ) % % If Board_props has more than one board in next_boards, this % discards all but the first one. % This also clears leaf_count and prediction board_props, but % only for continuing board_props. filter_board_props_to_single_next_board( Board_props ) -> case get_board_props_state( Board_props) of % Only continuing Board_props have non-empty next_boards, % and they always have at least one next_board. % This chops off all next_boards after the first one. % This also clears leaf_count and prediction, which are the % forward-looking properties that depend on next_boards. % Leaf_count and prediction are cleared even if next_boards % starts with only a single board (and is thus not changed % here). continuing -> { get_singlet_next_boards( get_next_boards_first_board( get_board_props_next_boards( Board_props))), get_board_props_src_count( Board_props), unknown, continuing, unknown }; _ -> % Board_props for non-continuing (win/tie) boards have no % next_boards, so there's no point in trimming them. Board_props end. % -------------------------------------------------------------- % Mark interface % -------------------------------------------------------------- % % A Mark is the mark you put on a board. It is one of: % empty - zempty % x_mark - amark % o_mark - bmark % % We use amark, bmark, and zempty because that gives us the % ordering we want. When we choose the canonical board, we % choose the reflected/rotated board that compares least. -define( X_MARK, amark). -define( O_MARK, bmark). -define( EMPTY, zempty). % -------------------------------------------------------------- % get_starting_mark( ) % % We start with an X. get_starting_mark( ) -> ?X_MARK. % -------------------------------------------------------------- % flip_mark( Mark ) flip_mark( ?X_MARK ) -> ?O_MARK; flip_mark( ?O_MARK ) -> ?X_MARK. % -------------------------------------------------------------- % prev_ply_mark( Ply_index ) % % Tells you the mark used to get from the previous ply to % this one. Ply_index must be 1..9. If Ply_index is 1, returns % the mark used on the empty board (ply 0) to get to the % current board (ply 1). % % Returns: % Ply_index is odd -> x_mark % Ply_index is odd -> o_mark % % Since the first move is from ply 0 to ply 1, when a board % has only one mark, that mark is X (x_mark). X always starts. prev_ply_mark( Ply_index ) when (1 =< Ply_index), (Ply_index =< 9) -> case Ply_index band 1 of 0 -> ?O_MARK; 1 -> ?X_MARK end. % -------------------------------------------------------------- % next_ply_mark( Ply_index ) % % Tells you the next mark to put on the boards in this ply. % Ply_index must be 0..8. The board is full at ply 9, so there % is no next mark. next_ply_mark( Ply_index ) -> prev_ply_mark( Ply_index + 1). % -------------------------------------------------------------- % get_mark_string( Mark ) % % Returns a one-character string. get_mark_string( ?X_MARK ) -> "X"; get_mark_string( ?O_MARK ) -> "O"; get_mark_string( ?EMPTY ) -> " ". % -------------------------------------------------------------- % Board interface % -------------------------------------------------------------- % % A Board is a 9-tuple, representing a 3x3 tic-tac-toe board. % (9 elements is 3 rows times 3 columns.) % -------------------------------------------------------------- % init_board( ) init_board( ) -> { ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY, ?EMPTY }. % -------------------------------------------------------------- % get_board_first_move_corner( ) % get_board_first_move_side( ) % get_board_first_move_middle( ) get_board_first_move_corner( ) -> { get_starting_mark( ), ?EMPTY, ?EMPTY, ?EMPTY , ?EMPTY, ?EMPTY, ?EMPTY , ?EMPTY, ?EMPTY }. get_board_first_move_side( ) -> { ?EMPTY, get_starting_mark( ), ?EMPTY, ?EMPTY, ?EMPTY , ?EMPTY, ?EMPTY, ?EMPTY , ?EMPTY }. get_board_first_move_middle( ) -> { ?EMPTY, ?EMPTY , ?EMPTY, ?EMPTY, get_starting_mark( ), ?EMPTY, ?EMPTY, ?EMPTY , ?EMPTY }. % -------------------------------------------------------------- % is_board_marked_at( Position, Board ) is_board_marked_at( Position, Board ) -> element( Position, Board) =/= ?EMPTY. % -------------------------------------------------------------- % mark_board_at( Position, Mark, Board ) % % Returns a new board with Mark at Position. mark_board_at( 1, M, { _,_2,_3,_4,_5,_6,_7,_8,_9} ) -> { M,_2,_3,_4,_5,_6,_7,_8,_9}; mark_board_at( 2, M, {_1, _,_3,_4,_5,_6,_7,_8,_9} ) -> {_1, M,_3,_4,_5,_6,_7,_8,_9}; mark_board_at( 3, M, {_1,_2, _,_4,_5,_6,_7,_8,_9} ) -> {_1,_2, M,_4,_5,_6,_7,_8,_9}; mark_board_at( 4, M, {_1,_2,_3, _,_5,_6,_7,_8,_9} ) -> {_1,_2,_3, M,_5,_6,_7,_8,_9}; mark_board_at( 5, M, {_1,_2,_3,_4, _,_6,_7,_8,_9} ) -> {_1,_2,_3,_4, M,_6,_7,_8,_9}; mark_board_at( 6, M, {_1,_2,_3,_4,_5, _,_7,_8,_9} ) -> {_1,_2,_3,_4,_5, M,_7,_8,_9}; mark_board_at( 7, M, {_1,_2,_3,_4,_5,_6, _,_8,_9} ) -> {_1,_2,_3,_4,_5,_6, M,_8,_9}; mark_board_at( 8, M, {_1,_2,_3,_4,_5,_6,_7, _,_9} ) -> {_1,_2,_3,_4,_5,_6,_7, M,_9}; mark_board_at( 9, M, {_1,_2,_3,_4,_5,_6,_7,_8, _} ) -> {_1,_2,_3,_4,_5,_6,_7,_8, M}. % -------------------------------------------------------------- % get_canonical_board( Board ) % % Chooses one board from all the 8 rotations/reflections. % % This function greatly reduces the number of boards in each % ply and the total size of the game space by treating all % board rotations and reflections as equal. To remove this % reduction and make the game-space include all rotated and % reflected boards, just re-define this function like this: % % get_canonical_board( Board ) -> Board. % % This will make the game-space much bigger (and noticeably % slower). % % This is the only function that calls: % rotate_board(..) % reflect_board(..) -ifdef( no_rotation_relection_collapse ). get_canonical_board( Board ) -> Board. -else. get_canonical_board( Board ) -> Rot1 = rotate_board( Board), Rot2 = rotate_board( Rot1), Rot3 = rotate_board( Rot2), Ref0 = reflect_board( Board), Ref1 = rotate_board( Ref0), Ref2 = rotate_board( Ref1), Ref3 = rotate_board( Ref2), lists:min( [Board, Rot1, Rot2, Rot3, Ref0, Ref1, Ref2, Ref3]). -endif. % -------------------------------------------------------------- % rotate_board( Board ) - rotates Board quarter turn clockwise % reflect_board( Board ) - reflects Board around horizontal axis % % Transforms a tic-tac-toe board by rotating it 90 degrees % clockwise, and by reflecting it around the horizontal axis. % Reflecting it is like picking the paper up and putting it % face down. % % From these 2 primitive transforms we can construct the 8 % simple rotation/reflection transforms. rotate_board( {_1,_2,_3, _4,_5,_6, _7,_8,_9} ) -> {_7,_4,_1, _8,_5,_2, _9,_6,_3}. reflect_board( {_1,_2,_3, _4,_5,_6, _7,_8,_9} ) -> {_7,_8,_9, _4,_5,_6, _1,_2,_3}. % -------------------------------------------------------------- % is_board_won_by( Mark, Board ) % % Predicate to test if Board is a winning board for Mark. % Returns 'true' or 'false'. % Check all winning combinations. % Check for 3-in-a-row: is_board_won_by( X, {X,X,X,_,_,_,_,_,_} ) -> true; is_board_won_by( X, {_,_,_,X,X,X,_,_,_} ) -> true; is_board_won_by( X, {_,_,_,_,_,_,X,X,X} ) -> true; % Check for 3-in-a-column: is_board_won_by( X, {X,_,_,X,_,_,X,_,_} ) -> true; is_board_won_by( X, {_,X,_,_,X,_,_,X,_} ) -> true; is_board_won_by( X, {_,_,X,_,_,X,_,_,X} ) -> true; % Check diagonals: is_board_won_by( X, {X,_,_,_,X,_,_,_,X} ) -> true; is_board_won_by( X, {_,_,X,_,X,_,X,_,_} ) -> true; % No winner (yet): is_board_won_by( _, {_,_,_,_,_,_,_,_,_} ) -> false. % -------------------------------------------------------------- % report_board( Board, Board_props ) % % We could pass in the current and next ply are report % predictions for all the next moves: % % XXX % .O. X wins % O.. % % XX. XXO XX. % .O. -> .O. O wins OO. X will win (in 1 or 3 moves) % O.X O.X O.X % % We could even report on all predictions from here. % For each next_board: % X will win: 10 paths % 3 moves: 9 paths % 2 moves: 1 path % 1 move: 0 paths % Tie: 13 paths % Lose: 3 paths % 3 moves: 9 paths % % Maybe we should have a report_move(..) function that % reports on a source board and move. Usually we want to % know about all the next moves. report_board( {_1,_2,_3,_4,_5,_6,_7,_8,_9}, Board_props ) -> State = get_board_props_state( Board_props), Next_boards = get_board_props_next_boards( Board_props), Write_mark = fun( M ) -> write_string( if M =:= ?EMPTY -> "."; true -> get_mark_string( M) end) end, Write_strip = fun( A, B, C ) -> Write_mark( A), Write_mark( B), Write_mark( C) end, write_space( 4), Write_strip( _1, _2, _3), case State of continuing -> write_string( " "), filter_next_boards( fun( {__1,__2,__3,_,_,_,_,_,_} ) -> Write_strip( __1, __2, __3), write_space( 2), false end, Next_boards); _ -> ok end, write_line( ), write_space( 4), Write_strip( _4, _5, _6), case State of win -> write_string( " winner"); tie -> write_string( " tie"); continuing -> write_string( " -> "), filter_next_boards( fun( {_,_,_,__4,__5,__6,_,_,_} ) -> Write_strip( __4, __5, __6), write_space( 2), false end, Next_boards) end, write_line( ), write_space( 4), Write_strip( _7, _8, _9), case State of continuing -> write_string( " "), filter_next_boards( fun( {_,_,_,_,_,_,__7,__8,__9} ) -> Write_strip( __7, __8, __9), write_space( 2), false end, Next_boards); _ -> ok end, write_line( ). % -------------------------------------------------------------- % Simple String Output % -------------------------------------------------------------- % -------------------------------------------------------------- % write_line( ) % write_line( Str, Arg) % write_line( Str, A1, A2) % write_line( Str, A1, A2, A3) % write_line( Str, A1, A2, A3, A4) % write_string( Str) % write_string( Str, Arg) % write_string( Str, A1, A2) % write_string( Str, A1, A2, A3) % write_string( Str, A1, A2, A3, A4) % write_space( ) % write_space( N) write_line( ) -> io:nl( ). write_line( Str ) -> write_string( Str), write_line( ). write_line( Str, Arg ) -> write_string( Str, Arg), write_line( ). write_line( Str, A1, A2 ) -> write_string( Str, A1, A2), write_line( ). write_line( Str, A1, A2, A3 ) -> write_string( Str, A1, A2, A3), write_line( ). write_line( Str, A1, A2, A3, A4 ) -> write_string( Str, A1, A2, A3, A4), write_line( ). write_string( Str ) -> io:fwrite( Str). write_string( Str, Arg ) -> io:fwrite( Str, [Arg]). write_string( Str, A1, A2 ) -> io:fwrite( Str, [A1, A2]). write_string( Str, A1, A2, A3 ) -> io:fwrite( Str, [A1, A2, A3]). write_string( Str, A1, A2, A3, A4 ) -> io:fwrite( Str, [A1, A2, A3, A4]). write_space( ) -> write_string( " "). write_space( 0 ) -> ok; write_space( N ) when N > 0 -> write_space( ), write_space( N - 1).