Yesterday my four year old son came into the room while I was drinking a cup of coffee and watching the news on televison and said "Dad I want to play with you". I put down my cup and turned the news down and said "sure let's find those paper soldiers from christmas". They were a quick find, a number of space soldiers I got from : http://www.gwindel.eu/Autre/Figs/Figurines.html.
I decided it was time to introduce him to wargaming. He's watched me do it and play RPGs his whole life (he actually played an RPG before he could talk much) so it wasn't alien to him.
I decided to start really simple; we each had six soldiers on opposite sides if the living room and a little base built of legos, the goal was to takeover the other sides base, each turn you could move one of your soldiers or shoot at an enemy soldier. Movement and shooting were resolved with rolling a normal six sided die. We used the floorboards on the dining room floor as spaces. You could shoot an enemy soldier if you rolled higher then the number of boards 2 soldiers were apart.
I won game one, but my son loved it. He made up a more complicated rule for the second game: If you rolled high enough to land on a board with points left on the die roll you could beat up a soldier on the other side. He won game two (actually easier than game one despite having one more rule).
Game three I introduced cover using legos to make barriers that 2 soldiers could hide behind scattered about the battlefield and reinforcement squares that allowed for extra soldiers. We got rid of the melee rule from game 2 but had a close combat roll that beat a foe on a die roll of 2 or higher if on the same board. The little guy made a dash for all the reinforcements and got all but one of them so his force ended up being 50% larger. It was a bitter battle down to the last two soldier in each force fighting it out in my son's base. He won that one as well.
He and I had a ton of fun and we are going to add robots into a future battle.