Loops, Algorithms, and Headaches

Loops

When I got into coding, loops were one of the more difficult tasks for me to get the hang of – especially iterating through conditions. Part of my struggle is that I made my loops too complicated…I tried addressing symptoms, not the overall desired behavior.

When I jumped into the Noughts and Crosses game, my algorithm was seven or eight steps long…I tried to account for each potential play as a ladder. Needless to say, I lost a lot of games. So, I simplified. I cut some steps. And lost again.

In college, a friend of mine was programming his own tic tac toe game as part of his CS master’s program. He explained the tree his program would use to make the best possible move. In it’s final state, it would always win or draw…never lose. To make it more interesting, he added a line to create a mistake at a random interval. It at least gave the human player a chance to win.

I came across an article explaining the Minimax algorithm. In short, it looks at a game state and finds the path which leads to a win or a draw. At the same time, it assumes that the other player wants to make us lose. It sounds confusing, and it certainly is, but the article linked did a great job explaining the principles. Ultimately, computers can be good at Tic Tac Toe because it can quickly build a move tree and execute the path to the best result.

Algorithms

I went back to Naughts and Crosses and took another stab. What was my desired goal? It wasn’t to win…I couldn’t win for two reasons: the game’s AI was probably using the minimax algorithm, and 2) I play second. It’s a significant disadvantage because I only get four board spaces while the opponent gets five. If I can’t win, I can try to force draw. I was able to make a simple program:

1. Always make sure I don’t lose. Block the opponent’s three-in-a-row first.
2. If they aren’t going to win, can I? Go for three in a row.
3. If I don’t need to block, and I can’t win, just pick a free space.

Changing my approach was immensely helpful, because I didn’t have to worry about “what if?” moments. It finally clicked in my head – establish a general choice and iterate down the list to match your case. The algorithm I picked wasn’t perfect – I still lose about 30% of the time, but it’s much better than my earlier attempts.

Headaches

I like to tell myself that I enjoy thought problems. They get in my head and I have a hard time focusing on things. I’ve also learned (as explained above) that I need to keep it simple.

The Suitcases took me a while. Rather than writing it out, here’s a diagram of my solution:

I found the Pancake puzzle to be easier, probably because my daughter plays with stacking cups and blocks. I was able to get them ordered from largest to smallest in five flips.

The hard part of this task wasn’t finding a solution…it was to find a solution in the most efficient way possible. It’s easy to come up with an answer or a method, but that doesn’t mean it’s the best way to accomplish the task. To be totally honest, I wish the prompts hadn’t given as much information as they did. Once I knew what path to head down, I felt like I was stuck in one mindset. With students, we always face the danger of leading with too much information and boxing in their methods. Problem solving needs to have an ebb and flow of success and failure. The challenge is supporting students through the process of failure rather than labeling their work as a failure. There’s a major mindset difference, and it links back to Computational Thinking as the process of problem solving.