programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Tic Tac Toe

Ranch Hand
Posts: 209
I just learnt how to use binary operators from here.
I then took a look at the TicTacToe game that comes in with JDK. Nearly everywhere they used left-shift operators or right-shift operators. I really can't understand it. Can anyone please explain the logic of the game in a synopsis or pseudocode. Please I can't get it through my thich brains.

marc weber
Sheriff
Posts: 11343
Consider the 3x3 square board as binary "switches" that can be turned on or off...

000
000
000

There are a total of 8 winning patterns -- since there are 3 rows, 3 columns, and 2 diagonals. For example, one way of winning is the bottom row...

000
000
111

If you string all of these switches together, you have a binary quantity, 000000111. One way to represent this quantity is using the bitwise "or" operator. In binary, 000000111 = 000000001 | 000000010 | 000000100. A convenient way to express this is to use left-shift operators, (1<<0) | (1<<1) | (1<<2).

In the same manner, the middle row could be expressed as (1<<3) | (1<<4) | (1<<5). And the first column would be expressed as (1<<2) | (1<<5) | (1<<8).

Each of these 8 winning patterns is initialized to "true" in the boolean array called "won." This array has an element representing each possible pattern. The number of theoretical possibilities is 2^9 (two choices for each of the nine squares). 2^9 is equivalent to 1<<9 (binary), which is 512. So the boolean array of size 512 is created with "new boolean[1<<9]."
[ May 12, 2005: Message edited by: marc weber ]